Theorem·T53
An omega-indexed union of countable sets is countable
Stack countably many countable sets and the whole stack is still countable, by choosing one injection per layer and pairing with the layer number.
For a function
with
, such that
for every
:
In words
For a family of sets indexed by the naturals with every set in the family countable: their union is countable - choose one witnessing injection per index, tag each element by the least index witnessing its membership, and pair the tag with that injection's value.
Never needed: F10 · F13 · A03 · A04 · A05 · A07 (computed from the citation graph, not asserted).
Proof
- 1For each , the set of injections is nonempty (as is countable); by Choice applied to the family of these nonempty sets (indexed by ), there is a function with an injection , for every .
- 2Write . For , the set is nonempty (as ); by the well-ordering of omega, has a least element, .
- 3
- 4By the pairing function being injective, the composite is an injection. Hence , i.e. is countable.
∎
Remarks
The one use of Choice in reaching Gödel's completeness theorem: picking a SINGLE injection witness for each of the countably many
simultaneously is exactly what Choice licenses, with no way to avoid it in general (each
being countable only asserts that *some* injection exists, not a canonically chosen one). Feeds directly into countability of finite sequences:
, an exactly
-indexed union.