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$

page revision: 19, last edited: 01 Dec 2009 22:05

This looks perfect now. David, thanks for taking the time to post the original content. Pat, thanks for letting us log in under you. Everyone, thanks for helping edit it.

ReplyOptions