prove: the cardinality of an countably infinite set S to the power of n is the same as the cardinality of the natural numbers

Question

Hii i need to prove that the cardinality of an countably infinite set S to the power of n is the same as the cardinality of the natural numbers. n is a element of the natural numbers.

Answer 1

We induct on $n$. We know that $S$ is in bijection with $\mathbb{N}$, so the base case is clear. Now suppose that for some $k, S^k$ is countable. We need to prove the claim for $k+1$.

As $S$ and $S^k$ are countable, $S^k\times S$ is in bijection with $\mathbb{N}^2$. If we can show that $\mathbb{N}^2$ is countable, we are done. Consider the function $f:\mathbb{N}^2 \rightarrow \mathbb{N}$ which takes $(a, b)$ to $2^a\times 3^b$. This is clearly an injective function by the fundamental theorem of arithmetic. The set of all numbers of the form $2^a 3^b$ is in bijection with $\mathbb{N}$ since by the well ordering principle one can arrange these numbers in ascending order. To be more specific, we can define a bijection from $\mathbb{N}$ to any infinite set of natural numbers by repeatedly picking the least element which has not been picked so far and then assigning that value to the function.

Hope this answer was helpful.