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


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


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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