Sign up ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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??

share|cite|improve this question

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

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

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

2 Answers 2

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}} $.

share|cite|improve this answer

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.

share|cite|improve this answer

Not the answer you're looking for? Browse other questions tagged or ask your own question.