Show that $\mathbb{N}$ is infinite

Question

I've tried to show that $\mathbb N$ is an infinite set.

Proof. By contradiction: assume that exists a bijeciton $f$ from $\mathbb N$ to $I_n = \{1, \dots, n-1\}$. We know that $f{\restriction_{I_n}}$ is injective and its image is a proper subset of $I_n$. From here, we can show that, by restricting the codomain of $f{\restriction_{I_n}}$ to $f{\restriction_{I_n}}(I_n)$, we obtain a bijection from a proper subset of $I_n$, that is, $f{\restriction_{I_n}}(I_n)$, to $I_n$ itself. But this is a contradiction. $\square$

Is it a correct proof?

EDIT: I'm using Peano's definition for $\mathbb N$, where $I_n$ is the set $\{0, S(0), \dots, S^{n-1}(0)\}$. For infinite set, I mean a set for which there is no bijection between it and any $I_n$, $n \in \mathbb N$.

Answer 1

Yes. Your proof is correct.

Indeed, if $f\colon\Bbb N\to\{0,\ldots,n-1\}$ is injective, then restricting the function to $\{0,\ldots,n\}$ would be an injection from a finite set into a proper subset, which is a contradiction to the pigeonhole principle.

One can argue in several other ways, e.g. using Peano axioms, or other axioms from which you can obtain (in a second-order) the natural numbers in a relatively natural way. These ways lend themselves to slightly different proofs. But your suggested proof is correct, and is a fairly standard proof in elementary set theory courses.

Answer 2

Why not proceed by contradiction by Peano's axioms assuming that $\mathbb N$ is finite and thus it should have a maximum $M$?

Answer 3

I once learned that a set is infinite iff there exists an injection into a proper subset of itself, and this is pretty trivial for N. A mapping like n->(n+n) does what one wants, depending of course on what you know about N.

With less knowledge: $f|I_n$ is injective (as restriction of bijective mapping), which means we have an injective mapping $f|I_n: I_n -> I_n$. Our friend $I_n$ is finite, hence the mapping is actually bijective. Which is already the contradiction, n+1 would have to be mapped to something in $I_n$ violating the injectivity of $f$.

Answer 4

Suppose $\Bbb N $ has cardinal $n $, then $$\begin {align}\Bbb N &= \{0,S (0),... ,S^{n-1} (0)\}\\ &:= \{0,1,...,n-1\}\end{align}$$ Since $S(n-1) \in \Bbb N$, $\exists 0 <i \leq n-1$ such that $S(n-1) = i $ and so $n-1=i-1$, contradicting that $\Bbb N $ has cardinal $n $.