Proof of Products and Powers of Countable Sets

Claim 1. If $X=\emptyset$ or $Y=\emptyset$, then $X\times Y=\emptyset$, which is countable. Otherwise $X$ and $Y$ are countable and nonempty, so there are sequences $(x_{m})_{m\in\mathbb{N}}$ in $X$ and $(y_{n})_{n\in\mathbb{N}}$ in $Y$ whose sets of terms are $X$ and $Y$ respectively. Define

Every $(x,y)\in X\times Y$ satisfies $x=x_{m}$ and $y=y_{n}$ for some $m,n\in\mathbb{N}$, so $X\times Y=\{g(w):w\in\mathbb{N}\times\mathbb{N}\}$. Since $\mathbb{N}\times\mathbb{N}$ is countable by The Set of Pairs of Natural Numbers is Countable, claim 4 of Basic Properties of Countable Sets shows that $X\times Y$ is countable.

Claim 2. Let $X$ be countable and let $E$ be the set of those $k\in\mathbb{N}$ for which $X^{k}$ is countable. Recall that an element of $X^{k}$ is a map $u$ from the initial segment $[k]$ to $X$, with components $u_{i}=u(i)$ for $i\in[k]$. Claim numbers below refer to Properties of the Order on the Natural Numbers for the order and to Arithmetic of Addition on the Natural Numbers for addition.

$1\in E$. If $i\in[1]$ then $1\le i$ and $i\le1$, so $i=1$ by claim 2 of the order lemma. Hence a map $u:[1]\to X$ is determined by the single value $u_{1}$, and the map $X\to X^{1}$ sending $x$ to the unique $u\in X^{1}$ with $u_{1}=x$ has image all of $X^{1}$. By claim 4 of Basic Properties of Countable Sets, $X^{1}$ is countable.

$k\in E$ implies $k+1\in E$. By claim 1 of the addition lemma, $k+1=S(k)$, where $S$ is the successor map of the natural numbers; by claim 5 of the order lemma every $i\in[k+1]$ with $i\ne k+1$ satisfies $i\le k$, and conversely $i\le k$ implies $i\le k+1$ and $i\ne k+1$, because $k<k+1$ by claim 6 of the order lemma. In particular $[k]\subseteq[k+1]$, and the conditions $i\le k$ and $i=k+1$ are exhaustive and mutually exclusive on $[k+1]$. Define

by letting $F(u,x)$ be the map $v:[k+1]\to X$ with $v_{i}=u_{i}$ for $i\in[k]$ and $v_{k+1}=x$; by the previous sentence $v$ is well defined. Conversely, given $v\in X^{k+1}$, the map $u:[k]\to X$ with $u_{i}=v_{i}$ for $i\in[k]$ is an element of $X^{k}$ and $F(u,v_{k+1})=v$. Hence $X^{k+1}=\{F(w):w\in X^{k}\times X\}$. By the induction hypothesis and claim 1, $X^{k}\times X$ is countable, so $X^{k+1}$ is countable by claim 4 of Basic Properties of Countable Sets.

By Principle of Induction for the Natural Numbers, $E=\mathbb{N}$, which is claim 2.