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$

---

Looking good!

Dana Ernst 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.