# 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

• 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
• 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
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.
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}}$.
{"ft_lang_label":"__label__en","ft_lang_prob":0.8970459,"math_prob":0.99972194,"size":635,"snap":"2019-26-2019-30","text_gpt3_token_len":187,"char_repetition_ratio":0.19651347,"word_repetition_ratio":0.0,"special_character_ratio":0.27086616,"punctuation_ratio":0.10852713,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9999807,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2019-07-21T13:33:14Z\",\"WARC-Record-ID\":\"<urn:uuid:676e5463-366c-4ba9-bcc7-85e21e23f17a>\",\"Content-Length\":\"140454\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:d586145c-45bd-41f3-bf4d-f904cb3be524>\",\"WARC-Concurrent-To\":\"<urn:uuid:8474afa1-5ec5-4cd6-b05f-455aa55159c0>\",\"WARC-IP-Address\":\"151.101.65.69\",\"WARC-Target-URI\":\"https://math.stackexchange.com/questions/314682/is-the-sets-of-all-maps-from-mathbbn-to-mathbbn-countable?noredirect=1\",\"WARC-Payload-Digest\":\"sha1:5YHPYAROYCBJPAZUITMD3EAOLV5U3YDC\",\"WARC-Block-Digest\":\"sha1:KDQME57K54HDAZYMVQ7HPP32JQBMK4TC\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2019/CC-MAIN-2019-30/CC-MAIN-2019-30_segments_1563195527000.10_warc_CC-MAIN-20190721123414-20190721145414-00291.warc.gz\"}"}