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

48 Views Asked by At

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$

1

There are 1 best solutions below

0
On BEST ANSWER

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