cardinality of functions from N to N using Schröder–Bernstein theorem

171 Views Asked by At

Im trying to prove that $\left|A\right|=\aleph$ for the following group: $A=\left\{f\in\mathbb{N}\rightarrow\left.\mathbb{N}\right|\forall n\le m\ .f\left(n\right)\le f\left(m\right)\right\}$ using Schröder–Bernstein theorem

To prove that $\left|A\right|\le\aleph$ I used the fact that $A\subseteq\mathbb{N}\rightarrow\mathbb{N}$ and therefore $\left|A\right|\le\left|\mathbb{N}\rightarrow\mathbb{N}\right|=\aleph_0^{\aleph_0}=\aleph$

For the other side I think I found an injective function $f\in P\left(\mathbb{N}\right)\rightarrow(\mathbb{N}\rightarrow\mathbb{N})$ which given a set $B\in P\left(\mathbb{N}\right)$ it will return the identity on $B$. In that case i will get $\aleph=2^{\aleph_0}=\left|P\left(\mathbb{N}\right)\right|\le\left|A\right|$

Is that correct or I missed something in the way?

1

There are 1 best solutions below

0
On BEST ANSWER

Hint: to get an injection of $\Bbb{P}(\Bbb{N})$ into $A$, define $f(X)$ to the function such that $f(0) = 0$ and:

$$f(x + 1) = \left\{ \begin{array}{l@{\quad}l} f(x) & \mbox{$x \not\in X$}\\ f(x) + 1 & \mbox{$x \in X$} \end{array}\right.$$

Now show how you can recover $X$ from $f(X)$.