Skip to content

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

A complete ordered listing assigns a value to every position of a declared ordinal and reaches every member of a separately specified target set. Values can repeat; the positions remain distinct.[1][2]

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.

Broad Use

A coding table can cover a finite set of bit strings, and an ordinal-indexed sequence can cover the exponent vectors of a formal power series.[3][1]

Clarity

State the target before checking coverage. A position having a value is not enough: every target must also appear. The order belongs to positions and need not be an order of the values.

Manages Complexity

Positions let a reader identify occurrences, while the no-gap requirement checks whether any target was missed. Repetitions are allowed unless a particular task prohibits them.

Abstract Reasoning

The empty list covers the empty set; no nonempty index can map into it. A nonempty finite set can be listed with finitely many positions or repeatedly from the natural numbers. An infinite ordinal index is an abstract order, not a promise of a completed finite-time computation.

Knowledge Transfer

Identify the target, position order, map and coverage obligation in both settings. A useful extra condition in one setting, such as adjacent codes differing by one bit, need not transfer to the other.

Example

Gray assigns the values 0 through 3 the two-bit words $00,01,11,10$: all four words appear once.[3] In formal algebra, Aschenbrenner indexes all exponent vectors by the ordinal positions of a chosen well-order.[1] Both cover a specified target in position order; their additional ordering rules differ.

Relationships to Other Abstractions

Local relationship map for Ordered-Index Complete ListingParents appear above the current abstraction, mutual partners to the right, and children below. Node labels state whether each abstraction is prime or domain-specific; colors identify relation types.Ordered-IndexComplete ListingPRIMEPrime abstraction: Surjectivity — is a kind ofSurjectivityPRIME

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

Not to Be Confused With

An indexed family need not cover a separately declared target, and a surjection need not have ordered positions. An effective enumeration algorithm has extra computational requirements. Counting a set is a different use of the word “enumeration.”

Notes

A map from the natural numbers onto a nonempty target witnesses at-most-countability; the empty set is countable but has no such map. Ordinal length does not itself determine the target's cardinality, and no universal well-orderability claim is made.[2]

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