Let $A$ be a countable set. Prove that $A^{\mathbb N}$ is countable.

Question

Let $A$ be a countable set. Prove that $A^{\mathbb N}$ is countable.

Just had trouble proving this. I thought about using a bijection but i wasn't really getting anywhere with that.

Answer 1

As many already pointed out, this is simply wrong: consider the set $A :=\{0,1\}$. Then by Cantor's theorem, $2^\mathbb{N}$ is uncountable.

(Cantor's Theorem). For every set $A$, we have that $$|2^A| > |A|.$$

Proof. Since there is an obvious injection $i : A \to 2^A$ given by $$x \mapsto \{x\}$$ it is enough to show that there exists no surjection from $A$ to $2^A$. So let $g: A \to 2^A$ be an arbitrary function and consider $$\Gamma := \{x \in A : x \notin g(x)\} \subseteq A.$$ Thus $\Gamma \in 2^A$. Towards a contradiction, assume that there exists a $y \in A$ such that $g(y) = \Gamma$. Now, if $y \in \Gamma$, then $$y \notin g(y) = \Gamma$$ and if $y \notin \Gamma$, then $y \in \Gamma$ by definition of $\Gamma$, which is absurd. Thus $\Gamma \notin \mathrm{im}(g)$ for any function $g$. $\quad\>\>\>\>\Box$