-2

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.

malii
  • 1
  • Welcome to MSE. Your question is phrased as an isolated problem, without any further information or context. This does not match many users' quality standards, so it may attract downvotes, or be closed. To prevent that, please [edit] the question. This will help you recognize and resolve the issues. Concretely: please provide context, and include your work and thoughts on the problem. These changes can help in formulating more appropriate answers. – José Carlos Santos Mar 29 '24 at 09:29

1 Answers1

0

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.

Shreya Mundhada
  • 299