# Let $\mathfrak F$ be the set of injective mappings $f:\Bbb N\to\Bbb N$. Then $|\mathfrak F|=2^{\aleph_0}$

Let $$\mathfrak F$$ be the set of injective mappings $$f:\Bbb N\to\Bbb N$$. Then $$|\mathfrak F|=2^{\aleph_0}$$.

This is an alternative proof to one in my textbook. Does it look fine or contain flaws? Thank you for your help.

My attempt:

Lemma 1: Let $$\mathfrak A$$ be the set of finite subsets of $$\Bbb N$$. Then $$|\mathfrak A|=\aleph_0$$.

Proof

It's clear that $$\mathfrak A$$ can not be finite and thus $$|\mathfrak A|\ge \aleph_0$$.

It's clear that every nonempty finite subset of $$\Bbb N$$ has a greatest element.

Let $$\mathfrak A_n$$ be the set of subsets of $$\Bbb N$$ where the greatest element for each of these subsets is $$n$$. Then $$\mathfrak A_n$$ is finite and thus countable for all $$n\in\Bbb N$$.

As a result, $$\mathfrak A=\{\emptyset\}\cup \bigcup_{n\in\Bbb N} \mathfrak A_n$$ is countable. Thus $$|\mathfrak A|\le\aleph_0$$.

Hence $$|\mathfrak A|=\aleph_0$$.$$\quad \blacksquare$$

Lemma 2: Let $$\mathfrak B$$ be the set of infinite subsets of $$\Bbb N$$. Then $$|\mathfrak B|=2^{\aleph_0}$$.

Proof

Let $$\mathfrak A$$ be the set of finite subsets of $$\Bbb N$$. Then $$|\mathfrak A|=\aleph_0$$ by Lemma 1

We have $$\mathfrak A \bigcup \mathfrak B=\mathcal{P}(\Bbb N)$$, $$\mathfrak A \bigcap \mathfrak B=\emptyset$$, $$\mathcal{P}(\Bbb N)=2^{\aleph_0}$$, and $$|\mathfrak A|=\aleph_0<2^{\aleph_0}$$. Then $$|\mathfrak B|=2^{\aleph_0}$$.$$\quad \blacksquare$$

We proceed to prove our main theorem.

First, $$|\mathfrak F|\le |{\Bbb N}^{\Bbb N}|={\aleph_0}^{\aleph_0}=2^{\aleph_0}$$.

Second, we can assign each infinite subset of $$\Bbb N$$ to an unique injective mapping $$f:\Bbb N\to\Bbb N$$. Thus $$2^{\aleph_0}=|\mathfrak B|\le |\mathfrak F|$$. Notice that $$|\mathfrak B|=2^{\aleph_0}$$ by Lemma 2.

Hence $$2^{\aleph_0}\le |\mathfrak F| \le 2^{\aleph_0}$$ and thus $$|\mathfrak F|=2^{\aleph_0}$$.$$\quad \blacksquare$$

That looks great, well done. You might want to be a little clearer about the injective mapping $$\mathfrak B \to \mathfrak F$$.