Proof of Enumeration of an Infinite Countable Set

Each result cited is universally quantified over the data in its own statement, and is applied here to the data named. Throughout, $S(k)$ denotes the successor of $k$, and $[k]$ the initial segment determined by $k$. Claims 1 to 7 concern clause 1, so $A\subseteq\mathbb{N}$ is throughout them a set that is not finite; claim 8 proves clause 2.

Claim 1 (Every natural number is exceeded in $A$). For every $m\in\mathbb{N}$ the set $A_{m}=\{u\in A:m<u\}$ is nonempty.

Suppose $A_{m}$ is empty for some $m\in\mathbb{N}$, and let $u\in A$. Then $m<u$ fails, so by the trichotomy of claim 3 of Properties of the Order on the Natural Numbers either $u=m$ or $u<m$; in the first case $u\le m$ by the reflexivity of claim 1 of that lemma, and in the second case $u\le m$ by the second part of claim 1. Hence $A\subseteq[m]$ by Initial Segment of the Natural Numbers. The set $[m]$ has $m$ elements by claim 1 of Basic Properties of Finite Sets, hence is finite by Finite Set, and so $A$ is finite by claim 3 of Basic Properties of Finite Sets — contrary to the hypothesis on $A$.

Claim 2 (The successor map of $A$). The set $A$ is nonempty, and there is a map $\nu:A\to A$ such that for every $m\in A$ one has $m<\nu(m)$, and $\nu(m)\le u$ for every $u\in A$ with $m<u$.

The empty set is finite by Finite Set, so $A$ is nonempty. Let $m\in A$. The set $A_{m}$ of claim 1 is a nonempty subset of $\mathbb{N}$, so it has a least element by The Natural Numbers Are Well Ordered; put $\nu(m)=\min A_{m}$. Then $\nu(m)\in A_{m}$, so $\nu(m)\in A$ and $m<\nu(m)$; and $\nu(m)\le u$ for every $u\in A_{m}$, that is, for every $u\in A$ with $m<u$.

Claim 3 (The enumerating sequence). There is a sequence $(t_{k})_{k\in\mathbb{N}}$ with $t_{k}\in A$ for every $k\in\mathbb{N}$, with $t_{1}=\min A$, and with $t_{S(k)}=\nu(t_{k})$ for every $k\in\mathbb{N}$.

By claim 2 the set $A$ is nonempty, so $\min A$ exists by The Natural Numbers Are Well Ordered. Let $\ast$ be the map $A\times A\to A$ with $x\ast y=\nu(x)$, a binary operation on $A$ in the sense of Existence and Uniqueness of Iterates of a Binary Operation, and for $p\in\mathbb{N}$ let $a^{p}:[p]\to A$ be the map with $a^{p}_{k}=\min A$ for every $k\in[p]$. By Existence and Uniqueness of Iterates of a Binary Operation, applied to the set $A$, the operation $\ast$, the number $p$ and the map $a^{p}$, there is exactly one map $\sigma_{p}:[p]\to A$ with

These maps are compatible: let $p,q\in\mathbb{N}$ with $p\le q$, and let $\tau$ be the restriction of $\sigma_{q}$ to $[p]$, which is a map $[p]\to A$ because $[p]\subseteq[q]$ by claim 4 of Basic Properties of Initial Segments of the Natural Numbers. Since $1\in[p]$ by claim 1 of that lemma, $\tau(1)=\sigma_{q}(1)=\min A$. Let $k\in\mathbb{N}$ with $S(k)\in[p]$. Then $S(k)\in[q]$, and $k\in[p]$: indeed $k<S(k)$ by claim 5 of Properties of the Order on the Natural Numbers, hence $k\le S(k)$ by claim 1 of that lemma, and $S(k)\le p$, so $k\le p$ by the transitivity of $\le$ in claim 1. Therefore $\tau(S(k))=\sigma_{q}(S(k))=\nu(\sigma_{q}(k))=\nu(\tau(k))$. Thus $\tau$ satisfies the two conditions that characterise $\sigma_{p}$, so $\tau=\sigma_{p}$ by the uniqueness in Existence and Uniqueness of Iterates of a Binary Operation; that is,

Put $t_{k}=\sigma_{k}(k)$ for $k\in\mathbb{N}$, which is defined because $k\in[k]$ by claim 1 of Basic Properties of Initial Segments of the Natural Numbers, and takes values in $A$. Then $t_{1}=\sigma_{1}(1)=\min A$. Let $k\in\mathbb{N}$. By claim 5 of Properties of the Order on the Natural Numbers one has $k<S(k)$, hence $k\le S(k)$ by claim 1 of that lemma, so the compatibility just proved, used with $p=k$ and $q=S(k)$, gives $\sigma_{S(k)}(k)=\sigma_{k}(k)=t_{k}$. Since $S(k)\in[S(k)]$, it follows that

Claim 4 (Strict monotonicity). One has $t_{k}<t_{S(k)}$ for every $k\in\mathbb{N}$, and $t_{k}<t_{l}$ whenever $k,l\in\mathbb{N}$ satisfy $k<l$.

The first assertion is claim 2 applied to $t_{k}\in A$, together with $t_{S(k)}=\nu(t_{k})$ from claim 3. For the second, let $P$ be the set of those $j\in\mathbb{N}$ such that $t_{k}<t_{k+j}$ for every $k\in\mathbb{N}$; we show $P=\mathbb{N}$ using Principle of Induction for the Natural Numbers with the inductive set $P$. First, $1\in P$: for $k\in\mathbb{N}$ one has $k+1=S(k)$ by claim 1 of Arithmetic of Addition on the Natural Numbers, so $t_{k}<t_{k+1}$ by the first assertion. Next, let $j\in P$ and $k\in\mathbb{N}$. By the recursive identity $k+S(j)=S(k+j)$ of Natural Numbers we have $t_{k+S(j)}=t_{S(k+j)}$, and $t_{k+j}<t_{S(k+j)}$ by the first assertion; combining with $t_{k}<t_{k+j}$ through the transitivity of $<$ in claim 1 of Properties of the Order on the Natural Numbers gives $t_{k}<t_{k+S(j)}$. As $k$ was arbitrary, $S(j)\in P$. Hence $P=\mathbb{N}$. Finally, let $k<l$. By claim 7 of Properties of the Order on the Natural Numbers there is $j\in\mathbb{N}$ with $l=k+j$, and then $t_{k}<t_{l}$ because $j\in P$.

In particular $t_{k}<t_{k+1}$ for every $k\in\mathbb{N}$, so $(t_{k})_{k\in\mathbb{N}}$ is strictly increasing in the sense of Subsequence of a Sequence in a Set.

Claim 5 (Injectivity). If $k,l\in\mathbb{N}$ satisfy $k\ne l$, then $t_{k}\ne t_{l}$.

By the trichotomy of claim 3 of Properties of the Order on the Natural Numbers, either $k<l$ or $l<k$. By claim 4 the corresponding one of $t_{k}<t_{l}$, $t_{l}<t_{k}$ holds. Were $t_{k}=t_{l}$, this would give $t_{k}<t_{k}$, which is false by claim 2 of Properties of the Order on the Natural Numbers.

Claim 6 (Surjectivity). For every $s\in A$ there is $k\in\mathbb{N}$ with $t_{k}=s$.

Let $s\in A$. The sequence $(t_{k})_{k\in\mathbb{N}}$ is strictly increasing by claim 4, so by Strictly Increasing Sequences of Natural Numbers Dominate Their Index, used with $N=s$, there is $k\in\mathbb{N}$ with $s\le t_{k}$. Hence the set $B=\{k\in\mathbb{N}:s\le t_{k}\}$ is nonempty, and it has a least element $k_{0}=\min B$ by The Natural Numbers Are Well Ordered; in particular $s\le t_{k_{0}}$.

Suppose first $k_{0}=1$. Then $t_{k_{0}}=\min A$ by claim 3, so $t_{k_{0}}\le s$ because $s\in A$; with $s\le t_{k_{0}}$ and the antisymmetry of claim 2 of Properties of the Order on the Natural Numbers, $t_{k_{0}}=s$.

Suppose now $k_{0}\ne1$. By claim 6 of Arithmetic of Addition on the Natural Numbers there is $j\in\mathbb{N}$ with $k_{0}=S(j)$, and $j<k_{0}$ by claim 5 of Properties of the Order on the Natural Numbers. Then $j\notin B$: otherwise $k_{0}\le j$ by the minimality of $k_{0}$, while $j\le k_{0}$ by claim 1 of Properties of the Order on the Natural Numbers, so $j=k_{0}$ by the antisymmetry of claim 2, contradicting $j<k_{0}$ together with the irreflexivity in that same claim. So $s\le t_{j}$ fails, and the trichotomy of claim 3 of Properties of the Order on the Natural Numbers leaves $t_{j}<s$, the alternatives $t_{j}=s$ and $s<t_{j}$ each giving $s\le t_{j}$ by claim 1. Since $s\in A$ and $t_{j}<s$, claim 2 gives $\nu(t_{j})\le s$, and $t_{k_{0}}=t_{S(j)}=\nu(t_{j})$ by claim 3. Thus $t_{k_{0}}\le s$, and with $s\le t_{k_{0}}$ the antisymmetry of claim 2 of Properties of the Order on the Natural Numbers gives $t_{k_{0}}=s$.

Claim 7 (Clause 1). By claim 3 every term $t_{k}$ lies in $A$, so $k\mapsto t_{k}$ is a map from $\mathbb{N}$ to $A$. By claim 6 every $s\in A$ equals $t_{k}$ for some $k\in\mathbb{N}$, and by claim 5 such a $k$ is unique; this is the condition of Bijection of Sets, so the map is a bijection from $\mathbb{N}$ onto $A$. It is strictly increasing by claim 4. This proves clause 1.

Claim 8 (Clause 2). Let $X$ be countable and not finite. The empty set is finite by Finite Set, so $X$ is nonempty; hence by Countable Set there is a sequence $(x_{m})_{m\in\mathbb{N}}$ in $X$ such that every $y\in X$ equals $x_{m}$ for some $m\in\mathbb{N}$. Put

and let $q:T\to X$ be the map with $q(m)=x_{m}$.

The map $q$ is injective. Indeed, let $m,m'\in T$ with $q(m)=q(m')$ and suppose $m\ne m'$. By the trichotomy of claim 3 of Properties of the Order on the Natural Numbers either $m<m'$ or $m'<m$. In the first case $m'\in T$ gives $x_{m}\ne x_{m'}$, and in the second case $m\in T$ gives $x_{m'}\ne x_{m}$; either way $q(m)\ne q(m')$, a contradiction. Hence $m=m'$.

The map $q$ is onto $X$. Indeed, let $y\in X$ and put $C=\{m\in\mathbb{N}:x_{m}=y\}$, which is nonempty by the choice of the sequence; let $m_{0}=\min C$ by The Natural Numbers Are Well Ordered. Let $i\in\mathbb{N}$ with $i<m_{0}$. Then $i\notin C$: otherwise $m_{0}\le i$ by minimality, while $i\le m_{0}$ by claim 1 of Properties of the Order on the Natural Numbers, so $i=m_{0}$ by the antisymmetry of claim 2, contradicting $i<m_{0}$ together with the irreflexivity in that same claim. Hence $x_{i}\ne y=x_{m_{0}}$. As $i$ was arbitrary, $m_{0}\in T$, and $q(m_{0})=y$. Together with injectivity this makes $q$ a bijection from $T$ onto $X$, by Bijection of Sets.

The set $T$ is not finite. Suppose it were. It is nonempty, since $q(m_{0})=y$ above exhibits an element of $T$ for any $y\in X$ and $X$ is nonempty; so $T$ has $p$ elements for some $p\in\mathbb{N}$ by Finite Set. Claim 4 of Basic Properties of Finite Sets, applied to $T$, to $X$ and to the surjective map $q$, then makes $X$ finite, contrary to the hypothesis on $X$.

Since $T\subseteq\mathbb{N}$ is not finite, clause 1, proved in claim 7, supplies a bijection $w$ from $\mathbb{N}$ onto $T$. By claim 2 of Injectivity, Composition, and Restriction of Bijections, applied to $w$ and to $q$, the map $m\mapsto q(w(m))$ is a bijection from $\mathbb{N}$ onto $X$. This proves clause 2.