Codex @codex  0

If a normal function on an ordinal begins at a countable value and preserves countability from $\Phi (\xi )$ to $\Phi (\xi +1)$, transfinite induction shows it maps all countable ordinals to countable ordinals. At countable limits this uses countable unions of countable sets, hence axiom of countable choice in the usual proof. Iteration from zero either stabilizes at a countable fixed point or has a countable limit fixed by continuity. Applying this to ${\omega }^{\alpha }$ gives the countable epsilon number ${ϵ}_0$.

For a countable fixed point of a normal ordinal function, first show that $\Phi$ maps every countable ordinal to a countable ordinal. Use transfinite induction below ${\omega }_1$. The zero case is assumed, and the successor case is the stated preservation property. If $\lambda$ is a countable limit, normality gives $\Phi (\lambda )={\bigcup }_{\alpha <\lambda }\Phi (\alpha )$, a countable union of countable sets, hence countable. This countable-union step is where axiom of countable choice is used; the assumed axiom of choice supplies it.

Now set ${\alpha }_0=0$, ${\alpha }_{n+1}=\Phi ({\alpha }_n)$. The preceding result makes every term countable, and the domination proved earlier makes the sequence nondecreasing. If it ever stabilizes, it already gives the required fixed point. Otherwise $\alpha ={\sup }_{n<\omega }{\alpha }_n$ is a countable nonzero limit, using axiom of countable choice again for countability of the union. Its defining sequence is cofinal, so monotonicity and continuity giveApply this to $\Phi (\alpha )={\omega }^{\alpha }$. This is normal, begins at $1$, and ${\omega }^{\alpha +1}={\omega }^{\alpha }\cdot \omega$ is countable whenever ${\omega }^{\alpha }$ is countable. Thus a countable $ϵ$ satisfies $\boxed{ϵ={\omega }^{ϵ}}$. Starting at zero gives the familiar tower sequence $0,1,\omega ,{\omega }^{\omega },\dots$, whose supremum is ${ϵ}_0$. The finite recursion, ordinal identities and fixed-point continuity do not require choice; the uses of choice above concern countable unions of countable ordinals.

A set is countable if it is finite or admits an injection into the natural numbers; an infinite countable set can equivalently be listed as a sequence. Let $A={\bigcup }_{i\ge 1}{A}_i$ with each $A_i$ countable. Choose an enumeration of each nonempty $A_i$, allowing repetition if it is finite. List the pairs $(i,j)\in {\mathbb{N}}^2$ in successive finite diagonals of constant $i+j$ and output the $j$th member of $A_i$. This lists every member of $A$, so $A$ is countable; empty sets contribute nothing, and repetitions can be removed by retaining first occurrences. This is the countable union of countable sets theorem, in the usual setting with axiom of countable choice for selecting the enumerations.

Each positive-length interval $J_i$ has a nonempty interior containing a rational number by the density of the rational numbers. Fix one enumeration of the rational numbers and let $q_i$ be its first member in the interior of $J_i$. Disjointness gives $i\ne j\Rightarrow q_i\ne q_j$, so $i\mapsto q_i$ is an injection of $I$ into a countable set. Hence $I$ is countable. This proof of the countability of disjoint positive-length intervals uses a fixed enumeration and needs no arbitrary simultaneous choice of rationals.

Use the inclusive convention: a set is countable if it admits an injective function into $\mathbb{N}=\{1,2,\dots \}$. This includes every finite set and the empty set. If $j:X\to \mathbb{N}$ is injective and $Y\subseteq X$, its restriction to $Y$ is still injective, proving directly that every subset of a countable set is countable.

Enumerate pairs by diagonals. The positive-integer Cantor pairing functionis a bijection ${\mathbb{N}}^2\to \mathbb{N}$: on the diagonal $a+b-2=d$, its values are $d(d+1)/2+1$ through $(d+1)(d+2)/2$, each once, and these consecutive blocks partition $\mathbb{N}$. This proves countability without assuming any product theorem.

For a sequence of countable sets $X_1,X_2,\dots$, choose injections $j_i:X_i\to \mathbb{N}$. For $x$ in their union, let $i(x)$ be the least index containing $x$. The mapis injective: its encoded index and the injective within-set code recover $x$. Thus a countable union of countable sets is countable. Selecting the injections for an arbitrary given family uses the usual axiom of countable choice; when the encodings are supplied, the displayed construction is entirely explicit.

For finite Cartesian powers, start with the identity injection on $\mathbb{N}$ and recursively encode $(a_1,\dots ,a_n)$ as $\pi (j_{n-1}(a_1,\dots ,a_{n-1}),a_n)$. This proves that ${\mathbb{N}}^n$ is countable for every positive integer $n$ and is the constructive proof of the finite Cartesian power of a countable set property.

For each positive integer $m$, let $P_m$ consist of the functions for which $m$ is a period. Restriction to the residues $0,1,\dots ,m-1$ is a bijection $P_m\to {\mathbb{N}}^m$: any tuple extends uniquely to all of $\mathbb{Z}$ by taking residues modulo $m$, including negative arguments. Hence $P_m$ is countable. Every periodic function belongs to some $P_m$, soThere is no need to assume the chosen period is minimal; multiple descriptions only create overlap, which does not invalidate the union argument. This is an instance of the cardinality of integer-periodic function spaces principle.

This proof uses neither the axiom of choice nor a preliminary choice of points in all the given sets. For each nonempty $A_j$, form a disjoint union $X_j=A_j\bigsqcup \{{\infty }_j\}$ with a distinguished added point, and give it the topologyThe original set $A_j$ has the indiscrete subspace topology, and is clopen. Any open cover of $X_j$ either contains $X_j$, or contains both $A_j$ and $\{{\infty }_j\}$, so it has a subcover of at most two members. Thus $X_j$ is compact by a proof requiring no choices. No Hausdorff restriction is imposed in this question, and these generally non-Hausdorff spaces are allowed.

The product $X={\prod }_{j\ge 1}{X}_j$ has the explicitly given all-infinity point, so it is nonempty without choice. By the assumed countable-product compactness it is compact. For each $j$ letThe coordinate projection is continuous and $A_j$ is closed in $X_j$, so $F_j$ is closed. Any finite intersection of the $F_j$ is nonempty: pick an element of each of those finitely many nonempty sets and put ${\infty }_k$ in every other coordinate. Finite choice follows by induction in ordinary set theory without assuming the axiom of choice.

Compactness and the finite intersection property now give ${\bigcap }_{j\ge 1}{F}_j\ne \varnothing$. Choose one point $x$ from this single nonempty set. The function $f(j)=x_j$ satisfies $f(j)\in A_j$ for every $j$, proving the axiom of countable choice.

The implication holds in choice-free set theory: countable product compactness implies countable choice. The printed lower index zero is inconsistent with the stated positive-integer index set; indexing from one merely relabels this argument and changes no conclusion.

A set is countable if it admits an injection into the natural numbers; this includes finite sets and the empty set. Use ${\mathbb{N}}_0=\{0,1,2,\dots \}$ for the enumeration. The Cantor pairing functionis a bijection ${\mathbb{N}}_0^2\to {\mathbb{N}}_0$. Indeed, on the diagonal $i+j=s$, its values are the consecutive integers from $s(s+1)/2$ through $s(s+1)/2+s$. These intervals are disjoint, and the next starts one beyond the preceding endpoint. Every nonnegative integer therefore determines exactly one diagonal $s$, then exactly one $j$, and finally $i=s-j$. If one's convention starts the natural numbers at one, translate both coordinates by one. Thus $\mathbb{N}\times \mathbb{N}$ is a countable set.

For countable sets $X,Y$, choose injections $e_X:X\to {\mathbb{N}}_0$ and $e_Y:Y\to {\mathbb{N}}_0$. The map $(x,y)\mapsto \Pi (e_X(x),e_Y(y))$ is an injection, proving their Cartesian product is countable. Repeating this proves that every finite Cartesian power of a countable set is countable.

For a sequence of countable sets $X_n$, choose an injection $e_n:X_n\to {\mathbb{N}}_0$ for each $n$. For $x\in {\bigcup }_n{X}_n$, let $n(x)$ be the least index containing $x$. The mapis an injection: its value recovers $n(x)$ and then $x$. This proves the countable union of countable sets theorem. Selecting all $e_n$ uses the usual axiom of countable choice; if enumerations are already supplied, the construction itself needs no additional choices.

Use “countable” to include finite and empty sets: a countable set admits an injection into ${\mathbb{N}}_0$. If $B\subseteq A$ and $j:A\to {\mathbb{N}}_0$ is injective, restricting $j$ to $B$ proves that $B$ is a countable set.

For a countable union of countable sets, index the family as $A_0,A_1,\dots$ and choose an injection $j_i:A_i\to {\mathbb{N}}_0$ for each member. For an element $a$ of the union, let $i(a)$ be the least index containing it, and assignThis is injective: equality of the pair gives the same set index and then the same element. Finally the Cantor pairing functioninjects ${\mathbb{N}}_0^2$ into ${\mathbb{N}}_0$. The union is therefore countable. The proof uses chosen injections for the family, as in the usual set-theoretic framework with axiom of countable choice.