Friedberg numbering¶
An effective natural-number numbering of a specified mathematical family that covers every member exactly once under equality of the denoted objects.
Core Idea¶
A Friedberg numbering assigns a natural-number index to every object in a declared mathematical family, with exactly one index per object. Its map \(\nu:\mathbb N\to A\) is total, covers the whole family, and is injective under equality of the denoted objects, rather than equality of program strings. It also gives uniform effective access appropriate to the family; neither a bare bijection nor a particular proof construction is the named type.[ref-5672c2c5789b][ref-8a394ecb412b]
Scope of Application¶
The family and its equality relation must be specified before the one-to-one and effectiveness claims can be tested.
- C.e. sets: Friedberg's historical theorem covers every c.e. set once, with uniformly c.e. membership.[ref-ca3fc78ca425][ref-8a394ecb412b]
- Partial computable functions: every unary function appears once extensionally, with uniform partial evaluation.[^ref-5672c2c5789b]
- Left-c.e. reals: the whole family appears once, accessed through c.e. dyadic lower cuts.[^ref-8a394ecb412b]
- Martin-Löf-random left-c.e. reals: a separate theorem covers this restricted family under the same lower-cut convention.[^ref-8a394ecb412b]
Clarity¶
Different programs may compute the same function, so nonrepeating syntax does not prove extensional injectivity. Given two indices in the same Friedberg numbering, comparing them decides whether their denoted objects are equal; the definition supplies no general method for translating arbitrary outside descriptions into those indices. The map \(\nu\) is total even when a function it names is undefined on some inputs.[^ref-5672c2c5789b] A fixed randomness-constant subfamily may lack an effective enumeration despite the broader positive theorem.[^ref-8a394ecb412b]
Manages Complexity¶
The definition keeps three obligations separate: full coverage, no repeated denotations, and uniform carrier-appropriate access. An injective list may omit objects, an effective complete numbering may repeat them, and a set-theoretic bijection may lack an effective interface. These are mathematical conditions, not a preference for unique labels over useful redundant descriptions. Thus a theorem for c.e. sets, partial functions, or reals cannot be moved to another family without proving its own presentation and existence conditions.[ref-5672c2c5789b][ref-8a394ecb412b]
Abstract Reasoning¶
First declare the family and extensional equality; then give a total natural-number map and prove it covers every member. Next specify the carrier's uniform access relation and prove distinct indices never denote one object. For partial functions, undefined outputs belong to the named objects' semantics rather than to a failure of the indexing map. These checks identify whether failure lies in coverage, effectiveness, or injectivity, instead of confusing a proof method or a theorem for another family with the definition.[ref-5672c2c5789b][ref-8a394ecb412b]
Knowledge Transfer¶
Numbering (Computability Theory) is the direct parent: it requires complete natural-number naming but permits repetition and noneffective maps. Friedberg numbering adds carrier-relative effectiveness and extensional injectivity; its map also satisfies the broader Function (Mapping) ancestor. The same test works for the cited set, function, and real families although their effective interfaces differ. A unique database or specimen ID alone lacks the required whole-family and effective-access proofs; Admissible Numbering and Gödel Numbering impose different specializations.[ref-5672c2c5789b][ref-8a394ecb412b]
Relationships to Other Abstractions¶
Current abstraction Friedberg numbering Domain-specific
Parents (1) — more general patterns this builds on
-
Friedberg numbering is a kind of Numbering (Computability Theory) Domain-specific
Friedberg numbering is an effective, extensionally injective numbering of a declared object family.
Hierarchy path (1) — routes to 1 parentless root
- Friedberg numbering → Numbering (Computability Theory) → Function (Mapping)
Neighborhood in Abstraction Space¶
Friedberg numbering sits in a sparse region of the domain-specific corpus (79th percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.
Family — Algebraic Operations & Quasigroup Structures (13 abstractions)
Nearest neighbors
- Back-and-Forth Method — 0.85
- Numbering (Computability Theory) — 0.84
- Cylindrification — 0.83
- Creative and Productive Sets — 0.83
- S-m-n Theorem — 0.82
Computed from structural-signature embeddings · 2026-10-17
References¶
[^ref-ca3fc78ca425]: Richard M. Friedberg (1958), “Three Theorems on Recursive Enumeration. I. Decomposition. II. Maximal Set. III. Enumeration Without Duplication”, Journal of Symbolic Logic 23(3), 309–316. The original publisher record and extract and indexed Theorem 3 title support the historical attribution; the full 1958 theorem body was access-gated, so no internal proof step is attributed to direct inspection. [^ref-5672c2c5789b]: Takuma Imamura, “Game Arguments in Some Existence Theorems of Friedberg Numberings”, arXiv:1508.04387v15 (2020 version), original author preprint. Physical PDF p.1 Introduction gives the historical attribution and later methods; p.2 §2 defines numberings, computable partial evaluation and the injective subtype; p.2 Theorem 1 covers all partial computable unary functions and cites Friedberg's corollary to Theorem 3; pp.2–4 §3 presents the later game proof; p.4 notes Kummer's priority-free method. These are physical PDF pages, not an assertion about later publication pagination. [^ref-8a394ecb412b]: Katie Brodhead and Bjørn Kjos-Hanssen (2014 arXiv v1), “Numberings and Randomness”, arXiv:1408.2169v1, original author preprint. Physical PDF p.1 Introduction records the c.e.-set attribution and effective interface; p.2 Definition 3 gives the dyadic rational lower-cut condition; pp.3–4 Theorems 7–8 give Friedberg numberings of all left-c.e. reals and of Martin-Löf-random left-c.e. reals; p.5 Theorem 9 gives the fixed-randomness-constant nonenumerability boundary, illustrated by p.6 Figure 1. The preprint's internal date and later publication pagination are not silently substituted for the cited arXiv version.