Proof of Basic Properties of Countable Sets

Throughout, countability of a set $Z$ means that $Z$ is empty or that some sequence in $Z$ has $Z$ as its set of terms.

Claim 1. The family $(x_{n})_{n\in\mathbb{N}}$ with $x_{n}=n$ is a sequence in $\mathbb{N}$, and every $y\in\mathbb{N}$ equals $x_{y}$, so its set of terms is $\mathbb{N}$.

Claim 2. Let $X$ be finite. If $X=\emptyset$, it is countable. Otherwise $X$ has $n$ elements for some $n\in\mathbb{N}$, so there is a bijection $f:[n]\to X$, where $[n]$ is the initial segment determined by $n$, that is, the set of natural numbers $m$ with $1\le m\le n$. Since $1\le m$ for every natural number $m$ by claim 4 of Properties of the Order on the Natural Numbers, we have $m\in[n]$ precisely when $m\le n$. Define

$$x_{m}=f(m)\ \text{ if } m\le n,\qquad x_{m}=f(n)\ \text{ otherwise},$$

which is a sequence in $X$. Every $y\in X$ equals $f(m)$ for some $m\in[n]$ by the defining property of a bijection, and then $y=x_{m}$. So the set of terms is $X$.

Claim 3. If $Y=\emptyset$ it is countable. Otherwise fix $y_{0}\in Y$. Then $y_{0}\in X$, so $X$ is nonempty and, being countable, admits a sequence $(x_{n})_{n\in\mathbb{N}}$ in $X$ with set of terms $X$. Define $y_{n}=x_{n}$ if $x_{n}\in Y$ and $y_{n}=y_{0}$ otherwise; this is a sequence in $Y$. If $y\in Y$ then $y\in X$, so $y=x_{n}$ for some $n$; that term lies in $Y$, so $y_{n}=x_{n}=y$. Hence the set of terms is $Y$.

Claim 4. If $X=\emptyset$ then $Y=\{g(x):x\in X\}=\emptyset$, which is countable. Otherwise let $(x_{n})_{n\in\mathbb{N}}$ be a sequence in $X$ with set of terms $X$ and put $y_{n}=g(x_{n})\in Y$. Every $y\in Y$ equals $g(x)$ for some $x\in X$, and $x=x_{n}$ for some $n$, so $y=y_{n}$.

Claim 5. If $X=\emptyset$ it is countable. Otherwise fix $x_{0}\in X$. Then $h(x_{0})\in Y$, so $Y$ is nonempty and admits a sequence $(y_{n})_{n\in\mathbb{N}}$ in $Y$ with set of terms $Y$. For each $n\in\mathbb{N}$: if there is an $x\in X$ with $h(x)=y_{n}$, then that $x$ is unique by the hypothesis on $h$, and we set $u_{n}=x$; otherwise we set $u_{n}=x_{0}$. This defines a sequence $(u_{n})_{n\in\mathbb{N}}$ in $X$ without any appeal to choice, since in the first case the element $x$ is uniquely determined. If $x\in X$, then $h(x)\in Y$, so $h(x)=y_{n}$ for some $n$, and then $u_{n}=x$. Hence the set of terms is $X$.

Claim 6. The set $X\cup\{z\}$ is nonempty. If $X=\emptyset$, then $X\cup\{z\}=\{z\}$ and the constant sequence with $u_{n}=z$ has set of terms $\{z\}$. Otherwise let $(x_{n})_{n\in\mathbb{N}}$ be a sequence in $X$ with set of terms $X$, let $S$ denote the successor map of the natural numbers, and define $u_{1}=z$ and, for $n\ne1$, $u_{n}=x_{j}$ where $j$ is the unique natural number with $n=S(j)$, which exists by claim 6 of Arithmetic of Addition on the Natural Numbers. Every term lies in $X\cup\{z\}$. Conversely $z=u_{1}$, and for $x\in X$ we have $x=x_{j}$ for some $j$, hence $x=u_{S(j)}$ because $S(j)\ne1$ by claim 7 of that lemma together with $S(j)=j+1$ from its claim 1. So the set of terms is $X\cup\{z\}$.