# Is the sets of all maps from $\mathbb{N}$ to $\mathbb{N}$ countable? [duplicate]

Is the sets of all maps from $\mathbb{N}$ to $\mathbb{N}$ countable?

Attempts: I think it is uncountable. Consider $P(\mathbb{N})$ where $P(A)$ denote as the power sets of A. We know that $P(\mathbb{N})$ is uncountable. Moreover, by the axiom of choice, for any non empty set, we know that there exist a function $f: P(\mathbb{N})\to \mathbb{N}$ . Note that $P(\mathbb{N})$ have uncountable many elements and since each $f$ belongs to the set of all mapping from $\mathbb{N}$ to $\mathbb{N}$ so there exist infinite uncountably elements and hence this set are uncountable. Is my attempt work??

-

## marked as duplicate by Seirios, Martin Sleziak, Asaf Karagila, Stefan Hansen, Alexander Gruber♦Feb 26 '13 at 11:35

you're right, its uncountable. Don't need axiom of choice. Just use cantors diagonalization argument. The powerset of N is uncountable but it only contains finite sets and countable sets. –  user58512 Feb 26 '13 at 7:52
Do you know about cardinal exponentiation? The cardinality of the set of all maps $\mathbb{N}\to\mathbb{N}$ is $\aleph_0^{\aleph_0}\geq2^{\aleph_0}>\aleph_0$. –  Ben West Feb 26 '13 at 7:54
The axiom of choice really has nothing to do with the uncountablitiy of this set. –  Asaf Karagila Feb 26 '13 at 7:57
Once you know Cantor's theorem, take $\text{id} : \mathbb{N} \to \mathbb{N}$ and notice that for every non-empty $A \in \mathcal{P}(\mathbb{N})$ the restriction $\text{id} \mid_{A} : \mathbb{N} \to \mathbb{N}$ is of the required form. –  J.H. Feb 26 '13 at 8:04

Simply observe that $${\sf{card}} \left( \mathbb{N}^{\mathbb{N}} \right) \geq {\sf{card}} \left( 2^{\mathbb{N}} \right).$$ You can prove $2^{\mathbb{N}}$ to be uncountable without assuming the Axiom of Choice. Just apply Cantor’s Theorem, which states that there does not exist a surjection from a set $X$ onto its power set $\mathcal{P}(X)$ (Cantor’s Theorem can be established strictly within the framework of ${\sf{ZF}}$). In particular, there cannot exist a surjection from $\mathbb{N}$ onto $\mathcal{P}(\mathbb{N})$, which can be easily shown to be equipollent to $2^{\mathbb{N}}$.

-

Inside the set of functions $\def\N{\Bbb N}\N\to\N$ is the subset of functions $\N\to\{0,1\}$ which are precisely the characteristic functions of subsets of $\N$ (as indicated in this answer), and which subsets you already know to be uncountable un number. So certinaly $\N^\N$ is uncountable.

-