Theorem 7.2.3
##### Claim

$\mathbb{N}$ is an infinite set.

##### Proof

For sake of contradiction, assume $\mathbb{N}$ is finite. By definition there exists a 1-1 correspondence $f:\mathbb{N}\to \{1,2,3,\dots,k\}$ for some $k$. Consider each $f^{-1}(\{i\})$ for each $i =1, \dots, k$. Since $f$ is 1-1, each $f^{-1}(\{i\})$ is a single element. Say each $f^{-1} (\{i\})= n_i$. Let $n= n_1+n_2+\cdots+n_k$. Since $n\in\mathbb{N}$, $f(n)$ equals some value in $\{1,2,3,\dots,k\}$, say $f(n)=j$. Then $f^{-1}(\{j\})=n$, but $f^{-1}(\{j\})= n_j$, as well. So, $n=n_j$ because $f$ is 1-1. Then

(1)
\begin{align} 0= n_1+n_2+\cdots + n_{j-1}+ n_{j+1}+\cdots+n_k. \end{align}

This is a contradiction since $0 \notin \mathbb{N}$. Therefore, $\mathbb{N}$ is infinite.

$\blacksquare$

Add a New Comment
page revision: 19, last edited: 01 Dec 2009 22:05