Proof: $n < \aleph_0$

Question

I want to prove that any finite cardinality $n$ (basically $n$ is the number of elements of the finite set in question) is smaller than the cardinality of the set of natural numbers, in short: $n < \aleph_0$.

This is my proof: $n < \aleph_0$, because $|\{0, 1, …, n\}| < |\mathbb N|$, because $\exists f: \{0, 1, …, n\} \to \mathbb N$ injective, e.g. $f(x) = x$, but $\lnot \exists f: \{0, 1, …, n\}\to \mathbb N$ surjective, because $n+1 \in \mathbb N$ and $n+1 \notin \{0, 1, …, n\}$, so that there is always an additional element in $\mathbb N$ that cannot have a preimage in $\{0, 1, …, n\}$.

Would that be enough to be a proof accepted by mathematicians?

Or should one add: … because assume a bijective $f$ then we have $n$-pairs of $(x,y)$ but also $n+1$-pairs of $(x,y)$, contradiction.

Answer 1

What you've written for the second part is not enough as it stands, but you're close to an idea that works. You can prove by induction on $n$ that for any function $f:\{0,\ldots,n\}\to\mathbb{N}$, the image of $f$ has a maximum element. So any element in $\mathbb{N}$ greater than that maximum (for example its successor) is not in the image of $f$, and $f$ is not surjective.

Answer 2

Certainly the obvious map $f : \{1, \ldots, n\} \rightarrow \mathbb{N}$ is an injection, so $|\{1, \ldots, n\}| = n \leq |\mathbb{N}| = \aleph_0$.

There is an issue with your other step however, as another commenter noted: for example, the naturals and the even numbers are in bijection, even though there are natural numbers not in the set of even numbers.

What you need is something like the following. Let $\varphi : \mathbb{N} \rightarrow \{1, \ldots, n\}$. Then, the set $\{\varphi(1), \ldots, \varphi(n), \varphi(n+1)\}$ consists of $n+1$ elements from $\{1, \ldots, n\}$, an $n$ element set. Hence, by the pigeonhole principle, there must be $i \neq j$ such that $\varphi(i) = \varphi(j)$, and so $\varphi$ is not injective. This shows that $n < \aleph_0$.

The problem with your method, and the difference in what I've written here, is that you don't get to choose what the function from $\mathbb{N}$ to $\{1, \ldots, n\}$ is, you need to prove it cannot be injective for any function.

Answer 3

I would say that your proof is based too much on your intuition on those sets and not so much on the available axioms, what can be uncomfortable for the "mathematicians".

A formal argument might be given as follows:

Given $A, B$ sets, we say that $|A|\le |B|$ if there is $f:A\rightarrow B$ injective.

It is analogous to say that $|A|\ge |B|$ if there is $f:A\rightarrow B$ surjective.

Therefore, all you have to do to prove that $n<\aleph_0$ is to show that there is no surjective function $f:\{1, 2, \dots, n\}\rightarrow \Bbb N$. We can do that by induction.

Of course there is no surjective function from $\{1\}$ to $\Bbb N$ and that's out base step.

Suppose there is no surjective function from $\{1, 2,\dots, n\}$ to $\Bbb N$ (i.e., $n<\aleph_0$) and, by contradiction, that there is a surjective function $f:\{1, 2, \dots, n+1\}\rightarrow \Bbb N$. If $f(n+1) = a$, then $f$ restricted to $\{1, 2, \dots, n\}$ must be surjective on $\Bbb N-\{a\}$, so $n = |\{1, 2, \dots, n\}|\ge |\Bbb N - \{a\}|$. However, notice that the function $\phi:\Bbb N\rightarrow \Bbb N-\{a\}$ given by

• $\phi(1) = 1$

• $\phi(2) = 2$

  $\vdots$

• $\phi(a-1) = a-1$

• $\phi(a) = a+1$

• $\phi(a+1) = a+2$

  $\vdots$

is a bijection, so $\aleph_0 = |\Bbb N| = |\Bbb N-\{a\}|$. Therefore $\aleph_0\le n<\aleph_0$. Contradiction.

So there is no surjective function from $\{1, 2,\dots, n+1\}$ to $\Bbb N$ and the induction is complete.