0
$\begingroup$

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?

$\endgroup$

marked as duplicate by Clement C., Henning Makholm elementary-set-theory Aug 26 '17 at 23:02

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.

  • $\begingroup$ 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$. $\endgroup$ – Adayah Aug 26 '17 at 22:11
  • $\begingroup$ 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. $\endgroup$ – Arthur Aug 26 '17 at 22:12
2
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ That would give us an injection $X \to \{ 0, 1 \}^{\mathbb{N}}$ which is opposite to what we need. $\endgroup$ – Adayah Aug 26 '17 at 22:12
  • $\begingroup$ No, it is a bijection. $\endgroup$ – user357980 Aug 26 '17 at 22:29
  • $\begingroup$ 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. $\endgroup$ – Adayah Aug 27 '17 at 7:33
  • $\begingroup$ 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$. $\endgroup$ – user357980 Aug 28 '17 at 3:55
  • $\begingroup$ 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. $\endgroup$ – Adayah Aug 28 '17 at 6:32
0
$\begingroup$

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])$

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

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