# Prove that set $\{f \in \mathbb{N^N} \: | \:f \:$is strictly increasing $\}$ has the same cardinality as $\mathbb R$ [duplicate]

Prove, that set $\{f \in \mathbb{N^N} \: | \:f \:$is strictly increasing $\}$ has the same cardinality as $\mathbb R$.

My attempts:

The beginning of this task was quite easy, but then I got stuck on constructing an injection between a set of function (let's call it $X$) and $\mathbb R$. I started with proving that $|\mathbb R| \geq |X|$:

• $|\mathbb R| \geq |X|$ because if $\forall _f , f\in \mathbb{N^N}$, and $|\mathbb{N^N}|=|\mathbb R$|, then $X \subset\mathbb R$.

Then I tried to prove that $|\mathbb R| \leq |X|$, but I don't know how to do it. I tried to define a function $g(x)=x^3$, but the result is a number, not a function. Or maybe it is a correct solution?

If not, can you explain to me how can I construct an injective function from $\{f \in \mathbb{N^N} \: | \:f \:$is strictly increasing $\}$ to $\mathbb R$? Is it even possible?

## marked as duplicate by Clement C., Henning Makholm elementary-set-theory StackExchange.ready(function() { if (StackExchange.options.isMobile) return; $('.dupe-hammer-message-hover:not(.hover-bound)').each(function() { var$hover = $(this).addClass('hover-bound'),$msg = $hover.siblings('.dupe-hammer-message');$hover.hover( function() { $hover.showInfoMessage('', { messageElement:$msg.clone().show(), transient: false, position: { my: 'bottom left', at: 'top center', offsetTop: -7 }, dismissable: false, relativeToBody: true }); }, function() { StackExchange.helpers.removeMessages(); } ); }); }); Aug 26 '17 at 23:02

• Hint: construct an injection $\{ 0, 1 \}^{\mathbb{N}} \to X$. Intuitively, this construction can be thought of as finding infinitely many properties of a function $f \in X$ such that every combination of these properties is represented by some function $f \in X$. – Adayah Aug 26 '17 at 22:11
• You already have "an injective function from $\{f \in \mathbb{N^N} \: | \:f \:$is strictly increasing $\}$ to $\mathbb R$", by your own admission, from the bijection between $\Bbb N^{\Bbb N}$ to $\Bbb R$, composed with inclusion. What your want it's an injective function the other way. This means take a number in $\Bbb R$ (or even easier: in $[0,1)$), and construct an increasing element of $\Bbb N^{\Bbb N}$ from that number in an injective way. – Arthur Aug 26 '17 at 22:12

The $\mathscr{P}(\mathbb{N})$, set of all subsets of $\mathbb{N}$, has the same cardinality as $\mathbb{R}$. Let $Y$ be the collection of all infinite subsets of $\mathbb{N}$. Since the collection of all finite subsets of $\mathbb{N}$ is countable, $Y$ has the same cardinality as $\mathscr{P}(\mathbb{N})$.

Let $X$ be the collection of all strictly increasing sequences from $\mathbb{N}$ to $\mathbb{N}$. A bijection of $X$ to $Y$ is given by $f \in X$ is mapped to $\mathrm{rang}(f) \in Y$.

Hint: Try to encode each $f$ as a sequence of $0$s and $1$s.

• That would give us an injection $X \to \{ 0, 1 \}^{\mathbb{N}}$ which is opposite to what we need. – Adayah Aug 26 '17 at 22:12
• No, it is a bijection. – user357980 Aug 26 '17 at 22:29
• Encoding each $f$ as a sequence of $0$s and $1$s sounds like assigning to each $f$ a distinct infinite binary sequence, but nothing in the answer seems to imply this assignment should be surjective. At least it wasn't clear to me. – Adayah Aug 27 '17 at 7:33
• Since $f$ is strictly increasing, you can write $f$ exactly as a sequence of zeros and ones like as in this example: If $f = 1, 3, 4, 7, \dots,$ then the sequence is $1, 0, 1, 1, 0, 0, 1, \dots$. – user357980 Aug 28 '17 at 3:55
• So it is not surjective, because the sequence $0, 0, 0, 0, 0, \ldots$ is not encoded. Anyway, I only meant to point out that the wording of the answer doesn't indicate that we want a surjective mapping. – Adayah Aug 28 '17 at 6:32

An infinite subset $A$ of $\mathbb{N}$ can be coded by a strictly increasing function: Define $f(0) = \min(A)$, and recursively $f(n+1) = \min(A \setminus f[\{0,\ldots,n])$

• An infinite subset, mind you, as long as you want functions with all of $\Bbb N$ as domain for your function. – Arthur Aug 26 '17 at 22:28
• @Arthur sure, but we miss countable many sets – Henno Brandsma Aug 26 '17 at 22:29