Friedberg numbering¶

An effective natural-number numbering of a specified mathematical family that covers every member exactly once under equality of the denoted objects.

Version: v1 · 2026-10-17 · History
Domain-specific #: 14160
Domain group: Formal Sciences
Origin domain: Mathematics
Subdomains: Computability Theory, Effective Numberings → Mathematics

Core Idea¶

A Friedberg numbering assigns natural-number indices to every object in a specified effectively presented family \(A\), with exactly one index for each object. Formally, it is a total surjection \(\nu:\mathbb N\to A\) that is injective under equality of the denoted objects, and its presentation is uniformly effective in the sense appropriate to \(A\). A distinct program string or description does not count as a distinct object merely because its code differs.^[1]^[2]

The named type is a condition on a whole numbering. It is neither a particular priority construction nor a theorem promising one for every family. Friedberg's 1958 result established enumeration without duplication for computably enumerable (c.e.) sets; later author papers explicitly attribute the partial-function corollary to that result and establish analogous numberings for specified families of left-c.e. reals.^[3]^[1]^[2]

Structural Signature¶

Specified family and extensional equality. First fix \(A\) and what makes two outputs the same mathematical object. Without this role, “no repetition” might say only that printed codes differ. Two programs can compute one partial function.^[1]
Total natural-number indexing and full coverage. The map \(\nu\) assigns an object to every natural-number index and is onto the declared \(A\). An injective sublist that omits even one member is not a Friedberg numbering of that whole family.^[1]
Uniform effectiveness relative to the carrier. The numbering exposes its objects through a computability condition appropriate to \(A\): c.e. membership for c.e. sets, computable partial evaluation for partial functions, or a c.e. dyadic lower-cut relation for left-c.e. reals. A bare set-theoretic bijection lacks this role.^[1]^[2]
Extensional injectivity. If \(e\ne e'\), then \(\nu(e)\ne\nu(e')\) as objects. Combined with coverage, this gives exactly one index per member. Remove this condition and an effective onto numbering may contain repeated denotations.^[1]^[2]

The indexing map is total even when the objects it names are partial functions: \(\nu(e)\) exists for every index, while \(\nu(e)(x)\) can be undefined for a particular input \(x\).^[1] For objects already supplied by indices in this same Friedberg numbering, injectivity makes equality decidable by comparing the indices. It does not provide an effective translation from arbitrary external descriptions to those indices.

What It Is Not¶

A unique serial number for each listed item need not be a Friedberg numbering. It may omit members of the declared family or provide no uniform effective way to access the denoted objects. Conversely, an effective onto numbering can have many indices for one object; nonrepeating syntax does not remove that extensional duplication.^[1]^[2]

An acceptable numbering imposes a different package of computable translation and universality conditions in the partial-function setting. Those conditions do not replace extensional injectivity, and Friedberg numberings are not defined by a blanket assertion about acceptable systems. A finite-injury construction, a two-board game proof, or a priority-free method may establish that a Friedberg numbering exists, but none is the definition of the type.^[1]^[2]

Scope of Application¶

The scope is a declared family of effectively presentable objects, not all countable families. Four source-attested habitats carry the same four roles while changing the effective interface:

All c.e. sets. Natural indices cover every c.e. subset of \(\mathbb N\) once as a set; the membership relation is uniformly c.e.^[3]^[2]
All partial computable unary functions. Indices cover every partial computable \(\mathbb N\to\mathbb N\) function once extensionally; the indexed evaluation map is partial computable.^[1]
All left-c.e. reals. Indices cover the entire real-valued family once, with a c.e. dyadic lower-cut relation as the effective interface.^[2]
Martin-Löf-random left-c.e. reals. A separate theorem covers this restricted family once under the same lower-cut convention; it is not a claim about all random reals.^[2]

The family boundary matters. Brodhead and Kjos-Hanssen separately show that a family restricted by a fixed randomness constant need not have an effective enumeration at all. Its negative result does not contradict the positive theorem for the full Martin-Löf-random left-c.e. family.^[2]

Clarity¶

Check which equality is meant. For c.e. sets, equality is equality of their members; for partial functions, it includes agreement about both values and undefined inputs; for left-c.e. reals, it is equality of real values. Two different codes can denote the same object, so a syntactically duplicate-free list is not enough.^[1]^[2]

Check which family is meant. “All left-c.e. reals,” “Martin-Löf-random left-c.e. reals,” and “those meeting a fixed randomness-constant bound” are distinct declarations with different existence results.^[2] Finally, check what effective means in that family. Uniform c.e. set membership is not a universal test for function or real numberings.

Manages Complexity¶

The definition lets a proof speak about an entire effectively presented family without silently counting the same denoted object twice. Its four conditions separate the coverage question from the uniqueness question: showing that every object appears does not show it appears only once, and showing a list has no repetitions does not show it is complete. The family-relative effective relation prevents a merely set-theoretic bijection from posing as a computability result.^[1]^[2]

For objects already supplied by their Friedberg indices, extensional equality reduces to comparing those indices. This does not provide a general procedure for converting arbitrary external descriptions into Friedberg indices or recovering an index from an object supplied without one. It also does not transfer an existence theorem between families. The c.e.-set, partial-function, and real-valued results need their own effective interfaces and source-backed arguments.^[1]^[2]

Abstract Reasoning¶

To test a proposed instance, declare the family \(A\) and its equality relation first. Next, state a total map \(\nu:\mathbb N\to A\) and prove that every member of \(A\) occurs. Then specify the uniform effective access relation for that carrier. Finally, prove that distinct indices never denote the same object. Only after these tests is an existence theorem for that particular family relevant.^[1]^[2]

The order also locates failures. An injective effective list missing some c.e. sets fails coverage; an onto computable partial-function numbering with two codes for the same function fails injectivity; a non-effective bijection fails presentation. For a fixed-randomness-constant real family that admits no effective enumeration, the failure is earlier still: no candidate can meet the coverage-plus-effectivity requirements.^[2]

Knowledge Transfer¶

The same test can be used for sets, functions, and reals without treating their access relations as identical. In the c.e.-set setting one uniformly enumerates membership pairs \((e,n)\) with \(n\in\nu(e)\). In the partial-function setting one computes the partial evaluation \((e,x)\mapsto\nu(e)(x)\). In the left-c.e.-real setting one enumerates dyadic rational pairs \((q,e)\) satisfying \(q<\nu(e)\).^[1]^[2]

What transfers is the conjunction of a declared family, complete natural-number coverage, carrier-relative effectiveness, and extensional one-to-one naming. What does not transfer automatically is a particular proof construction, a specific membership algorithm, or the existence result for a newly narrowed family. A physical specimen label or database identifier may be unique but lacks this full computability-theoretic relation unless those obligations are independently established.

Examples¶

C.e. sets: membership as the uniform interface¶

Take \(A\) to be all c.e. subsets of \(\mathbb N\). Friedberg's historical no-duplication result concerns this whole family; Brodhead and Kjos-Hanssen describe the c.e.-set result and its uniformly c.e. membership relation. The original 1958 article's publisher record and indexed Theorem 3 support the bounded historical attribution, while its full proof text was not inspected here.^[3]^[2]

Mapped back: \(A\) and set equality supply the family/identity role. A natural-number index for every c.e. set supplies coverage. Uniform enumeration of \(n\in\nu(e)\) supplies effectiveness. No two distinct indices denoting the same subset supplies extensional injectivity. These are a theorem realization, not an empirical deployment or a claim about every c.e. subfamily.^[2]

Partial computable functions: evaluation rather than membership¶

Let \(A=P^{(1)}\), the family of all partial computable functions \(\mathbb N\to\mathbb N\). Imamura defines effectiveness by computability of the partial evaluation map \((e,x)\mapsto\nu(e)(x)\) and states in Theorem 1 that this full family has a Friedberg numbering. He attributes the theorem to Friedberg's corollary to Theorem 3, while presenting a later game-based proof.^[1]

Mapped back: Extensional equality of partial functions supplies family/identity, including agreement on undefinedness. Every member of \(P^{(1)}\) appearing supplies coverage. The uniform partial evaluator supplies effectiveness even though individual outputs may be undefined. No two indices computing one function supplies injectivity. This is a function-valued result, not merely a relabeling of the c.e.-set membership condition.^[1]

Left-c.e. reals: an ordered-value interface¶

For \(A\) equal to all left-c.e. reals, Brodhead and Kjos-Hanssen's Definition 3 uses a c.e. relation of dyadic rational lower-cut pairs \((q,e)\) with \(q<\nu(e)\). Their Theorem 7 establishes an injective effective numbering of the entire declared family.^[2]

Mapped back: Equality of real values supplies family/identity; Theorem 7 gives coverage and injectivity; the dyadic lower cut supplies effectiveness. This third carrier shows the shared structure with a different interface. Their Theorem 8 concerns Martin-Löf-random left-c.e. reals, whereas Theorem 9's fixed-constant negative result concerns a narrower declaration.^[2]

Structural Tensions¶

No source-warranted two-sided structural tradeoff is needed to define this type. Surjectivity and injectivity are simultaneous requirements, not opposing objectives that a practitioner should balance. Proving both may be difficult; dropping either simply changes the classification. Likewise, positive theorems for some families and nonexistence for another mark a family boundary, not a cost paid for a chosen design.^[1]^[2]

The useful diagnostic is: Which declared family and effective interface does the theorem cover, and have both coverage and extensional nonduplication been proved? This question prevents a construction technique or a negative result for one restricted family from being mistaken for a general tradeoff.

Structural–Framed Character¶

On the structural–framed spectrum, Friedberg numbering is predominantly formal structural within computability theory. Surjectivity, a uniform effective interface, and extensional injectivity are mathematical predicates. The framing enters when a researcher specifies \(A\), its equality relation, and an accepted representation convention; after that declaration, a candidate either meets the conditions or does not.^[1]^[2]

Evaluative weight: one-to-one presentation is a definitional constraint here, not a claim that it is always preferable to redundant descriptions. Human practice: researchers select the family and formal interface, but social approval does not make an injective map onto. Institutional origin: Friedberg's paper supplied the historical name and result; the type is not tied to that publisher or one proof. Vocabulary travel: the name applies literally to the source-backed set, function, and real families with different effective interfaces. Import versus recognition: it is recognized in a new setting by proving all four roles, while applying it to a merely nonrepeating list imports the label without the structure.^[3]^[1]^[2]

Its character: a precise formal subtype of effective numbering whose carrier can change within computability theory while its complete, effective, extensionally one-to-one relation remains intact.

Structural Core vs. Domain Accent¶

The portable skeleton is declared object family and extensional equality → total natural-number coverage → uniform carrier-relative effective access → extensional injectivity. Friedberg's finite-injury construction, Imamura's game proof, Kummer's method, and dyadic notation illustrate or establish particular instances; no one method is a role required of every Friedberg numbering.^[1]^[2]

The domain-bound residual is substantive: the indices are natural numbers, the access relation has computability-theoretic force, and equality is equality of the represented mathematical objects. Numbering (Computability Theory) has the broader surjective naming relation and explicitly admits redundant indices; Friedberg adds a necessary one-to-one condition. The set, function, and real cases stay within computability theory, so their diversity alone does not establish a new substrate-independent Prime. A stronger claim would need independent literal cases outside this domain—for example, a specimen registry and a document registry—where complete coverage, uniform effective access, and extensional identity all survive without collapsing into ordinary unique IDs or an existing representation concept. If either setting supplies only a serial number or an analogy, the Prime claim fails.

This entry is a kind of Numbering (Computability Theory).

The broader Numbering (Computability Theory) concept permits surjective natural-number coding without requiring one-to-one denotation. Friedberg numbering specializes that relation by adding extensional injectivity and a carrier-appropriate effective interface. Symbolic Representation supplies a more general sign-to-object perspective, but its breadth does not by itself establish that every property of a computability-theoretic numbering is a property of all symbolic representations.

Admissible Numbering concerns a distinct translation and universality package for partial computable functions, while Gödel Numbering centers on coding formal syntax. Neither is a synonym for the four-role Friedberg type.

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 (79^th 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

Computed from structural-signature embeddings · 2026-10-17

Not to Be Confused With¶

A redundant effective numbering: onto and effective may hold while two indices denote the same object.^[1]
A non-effective bijection: unique complete labels lack the carrier's required uniform presentation.
A syntactically nonrepeating program list: different programs can compute one partial function.^[1]
An acceptable numbering or Gödel code: translation/universality conditions or syntactic coding do not substitute for extensional injectivity.
A proof construction: finite injury, a game, or a priority-free method may witness existence but is not the named type.^[1]^[2]
A universal existence theorem: the fixed-randomness-constant left-c.e.-real family in Theorem 9 lacks an effective enumeration, despite separate positive theorems for other declared families.^[2]

References¶

[1] 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. registry ↩a ↩b ↩c ↩d ↩e ↩f ↩g ↩h ↩i ↩j ↩k ↩l ↩m ↩n ↩o ↩p ↩q ↩r ↩s ↩t ↩u ↩v ↩w ↩x

[2] 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. registry ↩a ↩b ↩c ↩d ↩e ↩f ↩g ↩h ↩i ↩j ↩k ↩l ↩m ↩n ↩o ↩p ↩q ↩r ↩s ↩t ↩u ↩v ↩w ↩x ↩y ↩z ↩27

[3] 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. registry ↩a ↩b ↩c ↩d