Ordered-Index Complete Listing¶

Version: v2 · 2026-10-31 · History
Prime #: 1604
Domain group: Formal Sciences
Origin domain: Mathematics
Related primes: Indexed family, Surjectivity, Order, Function (Mapping)

Core Idea¶

An ordered-index complete listing assigns each position in a specified ordinal $\alpha$ an element of a separately declared target set $S$, and reaches every element of $S$. Formally it is a total function $e:\alpha\to S$ with $e[\alpha]=S$. The well-order belongs to the positions; the target need not come with its own order. A value may appear at several positions unless a particular convention requires uniqueness. The ordinal length can be finite, $\omega$, or another ordinal.^[1]^[2]

The target must be stated independently of the coverage check. If one simply defines $S$ to be the image after selecting $e$, equality with the image is automatic and does not demonstrate coverage of a prior target. For each member of a covered target, its nonempty set of positions has a least position, because an ordinal is well-ordered. This first-occurrence observation does not require that the whole map be injective.

How would you explain it like I'm…

Nobody Left Out Line

Your teacher hands you a card with all the class animals on it. You line up numbered spots and put an animal picture in every spot, so the line has no empty spots. You're done when every animal on the card shows up somewhere in the line. It's okay if the bunny shows up twice, as long as nobody on the card is left out.

Numbered Check-Off List

Start with a list of things you must cover, like every state you want to visit. Then make numbered positions 1, 2, 3, and so on, and write one state in every position. The listing is complete when every state from your original list appears in at least one position. A state can appear more than once, and the states don't need any order of their own; the order comes from the numbered positions. Importantly, you check against the list you started with, not a list you made up afterward from whatever you happened to write down.

Ordered Covering List

An Ordered-Index Complete Listing fills every position in an ordered sequence of positions with a member of a target set that was named in advance, and every member of that target set appears somewhere. The positions carry the order; the target set itself need not be ordered at all. Repeats are allowed unless some rule says otherwise, which is what separates a listing like this from a one-to-one numbering. The sequence of positions can be finite, or it can go on forever like 0, 1, 2, ..., or even continue past that in set theory. The target must be fixed independently first: if you just define the target as "whatever ended up in the list," coverage is automatic and proves nothing. Because the positions always have a first one in any nonempty collection, every covered item has a first position where it appears, even if it appears again later.

An Ordered-Index Complete Listing is a total function e from an ordinal alpha (the index positions) to a separately specified target set S that is surjective, meaning its image e[alpha] equals S. Totality means every position receives a value; surjectivity means every element of S is reached at least once. The well-ordering lives on the domain: alpha is an ordinal, while S need carry no order of its own. Injectivity is not required, so values may repeat unless a convention demands uniqueness, which distinguishes this from an enumeration-as-bijection. The length alpha may be finite, omega (giving an ordinary infinite sequence), or a larger ordinal, as in transfinite enumerations. Crucially, S must be specified before and independently of the check; defining S as the image of an already chosen e makes e[alpha] = S a tautology rather than a demonstration of coverage. Finally, for each s in S the preimage e^{-1}(s) is a nonempty subset of an ordinal and therefore has a least element, so each covered element has a well-defined first occurrence even though e may be many-to-one.

Structural Signature¶

Recurring features:

Target: a set $S$ fixed independently of the listing whose members must be covered.
Positions: an ordinal $\alpha$ with its well-order, including the empty ordinal and limit ordinals.
Assignment: a total map $e$ assigns a member of $S$ to each position.
Coverage: every member of $S$ occurs at some position; equivalently $e[\alpha]=S$.
Position identity: distinct positions remain distinguishable even when their values coincide.
Optional restrictions: a particular problem may demand distinct values, effective generation, or preservation of a target order; those are extra conditions.

What It Is Not¶

A bare onto map from an unordered domain has coverage but no specified positional sequence. An ordered family missing a member of a declared target is not complete for that target. An ordinal limit position is an abstract position, not a step reached in finite time after completing infinitely many steps. The relation alone does not provide an algorithm or a termination guarantee.

Broad Use¶

A finite coding table and an ordinal-indexed representation of exponent vectors both retain a position-to-item map and cover a declared set. The reason for the order differs: one construction supports a code, the other aligns algebraic terms with a chosen well-order.^[3]^[1]

Clarity¶

Three questions are separate: which positions exist, what each position denotes, and whether every independently specified target is reached. A repeated value changes uniqueness, not coverage. An order on positions does not automatically say that the assigned target values preserve some other order.

Manages Complexity¶

An ordered index gives a place to refer to each occurrence, while the coverage condition prevents a required target from being omitted. Checking only that every position has a value verifies totality, not completeness: one must also check every target has a preimage.

Abstract Reasoning¶

The empty function $0\to\varnothing$ is complete; no total map from a nonempty ordinal to the empty set exists. A nonempty finite target can be listed by finitely many positions or by $\omega$ if repetition is allowed. A surjection $\mathbb N\to S$ implies that nonempty $S$ is at most countable; the empty set is countable but has no map from nonempty $\mathbb N$ onto it. A nonempty countable set may also be indexed by an ordinal longer than $\omega$ under a suitable map, so ordinal length alone does not imply target uncountability.

Knowledge Transfer¶

Carry the declared target, ordered positions, total map and coverage test together. In a coding table, positions may identify signal levels; in formal algebra, ordinal positions organize exponent vectors. Neither setting makes the other's additional rules automatic.

Examples¶

Formal/abstract¶

Aschenbrenner fixes an admissible well-order on $\mathbb N^N$ for a positive number $N$ of indeterminates, lets $\lambda$ be its order type, and writes the increasing enumeration as $\nu_\alpha$ for $\alpha<\lambda$. It indexes the exponent vectors used in a formal power series. The paper also describes admissible orders of type $\omega$; its general notation does not assert that every such $\lambda$ is greater than $\omega$.^[1]

Mapped back: The independently specified target is $\mathbb N^N$; positions are ordinals below $\lambda$, and the order-preserving enumeration reaches each exponent vector. Its uniqueness and preservation of the chosen target order are specific to this construction.

Applied/industry¶

Gray's reflected binary coding construction lists the two-bit words in the order $00,01,11,10$ for the four values zero through three. In this construction each word is unique and successive words differ in one digit; the patent develops the code for pulse communication.^[3]

Mapped back: The target is the four two-bit strings; the four ordered positions map to them completely. The one-digit adjacency rule is useful in this code but is not part of every complete listing.

Structural Tensions¶

No universal competing-cost tension follows from the definition. For a particular task, asking for no repetitions or a special adjacency order adds a constraint and may restrict available constructions. That conditional design issue should not be mistaken for a tradeoff that every listing must exhibit.

Structural–Framed Character¶

The relation is structural once a target, ordinal and map have been fixed: coverage and positional order do not require approval of the listed objects. Choosing a target or constructing a code is a human practice, while the relation itself remains recognizable in the formal algebra and communication examples. The terminology comes from mathematical listing; applying the test in a new setting requires identifying actual positions and an independent coverage obligation, not merely calling a collection a list. These examples show the relation in mathematical representations, without establishing its use in every domain.

Substrate Independence¶

The tentative composite score is 3 / 5: the inspected cases show the same positional coverage relation in formal power-series organization and communication coding, while both are mathematical representations. This supports limited transfer rather than unrestricted breadth.

Composite substrate independence — 3 / 5
Domain breadth — 2 / 5
Structural abstraction — 5 / 5
Transfer evidence — 2 / 5

Relationships to Other Abstractions¶

Current abstraction Ordered-Index Complete Listing Prime

Parents (1) — outgoing typed relations

Ordered-Index Complete Listing is a kind of Surjectivity Prime

Every ordered-index complete listing is a surjective map, with an ordinal position domain as its defining specialization.

Hierarchy path (1) — routes to 1 parentless root

Ordered-Index Complete Listing → is a kind of Surjectivity → is a kind of Function (Mapping)

Neighborhood in Abstraction Space¶

Ordered-Index Complete Listing has no computed distinctiveness yet.

Family — Locality & Local-to-Global Structure (9 primes)

Nearest neighbors

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

Not to Be Confused With¶

Indexed Family: a total assignment to arbitrary indices retains position identity but need not have an ordinal order or cover a separately stated target.
Surjectivity: supplies the no-gap map but does not require ordered positions.
Order: supplies comparative structure, not a total map onto a target.
Enumeration Algorithm: a specialized effective finite-solution procedure with additional soundness, uniqueness, exhaustion and complexity obligations.
Counting or an enumerated programming type: uses of the word with different outputs and rules, not this relation by default.

Solution Archetypes¶

No catalogued solution archetypes reference this prime yet.

Notes¶

Practices vary. An onto map from $\mathbb N$ is one convention for a nonempty countable target; Edalat treats the infinite case and illustrates positive rational numbers by a diagonal listing.^[2] Not every set is asserted to admit an ordinal-indexed listing without suitable well-orderability or choice assumptions. This account covers the ordered-listing sense; counting and programming enumeration use the term differently.

References¶

[1] Matthias Aschenbrenner, Reduction mod p of Standard Bases, Communications in Algebra 33 (2005), 1635–1661; author-hosted paper §1, PDF p. 6. registry ↩a ↩b ↩c

[2] Abbas Edalat, Countable and uncountable sets, Imperial College lecture notes, PDF pp. 4–5; instructional treatment. registry ↩a ↩b

[3] Frank Gray, “Pulse Code Communication,” U.S. Patent 2,632,058, filed 1947, issued 1953, description column 6. registry ↩a ↩b