# set of natural numbers

Prove each set of natural numbers is the set of all smaller natural numbers. IE $n =$ { $m \in N | m < n$ }

Hint: use induction to prove that all elements of a natural number are natural numbers.

The natural numbers are defined as : 0, 1, 2, ...etc.

The textbook I am using (Hrbacek and Jech) further defines:

$1 = \{ 0 \} = \{ \emptyset \}$

Step ONE: show it is true for the second smallest natural number 1

it is a given that $1 \in$ {$0$}

Step TWO: assume it is true for the natural number $k$ IE: $k =$ { $m \in N | m< k$ }

Step THREE: prove it is true for natural number $k + 1$

since $k = \{ m \in N | m < k \}$

and since $k < k + 1$

then $m < k + 1$

therefore $k + 1 = \{ m \in N | m < k + 1 \}$

am I correct?

• How have you had the natural numbers defined? – Tobias Kildetoft May 24 '13 at 18:37
• Erm. $1\in \left\{0\right\}$ is most likely false. You have $1=\left\{0\right\}$ so $0 \in 1$... – xavierm02 May 24 '13 at 18:40
• @TobiasKildetoft i just put in an edit now defining the natural numbers as 0, 1, 2, 3, ... – sarah jamal May 24 '13 at 18:40
• With that definition, there is no way to prove what you want to prove, unless you further define each of those symbols as some specific set. – Tobias Kildetoft May 24 '13 at 18:41
• @TobiasKildetoft sorry I left out the definition that $1 = \{ 0 \} = \{ \emptyset \}$ – sarah jamal May 24 '13 at 18:47

I suspect that you’ve actually defined $N$ to be the smallest set such that $0\in N$ and for all $n\in N$, $S(n)\in N$ or something very similar, and that you’ve defined $n+1$ to be $S(n)=n\cup\{n\}$ for $n\in N$. To show by induction that $n=\{k\in N:k<n\}$ for each $n\in N$, you must show two things:

1. $0=\{k\in N:k<0\}$, and
2. if $n\in N$ and $n=\{k\in N:k<n\}$, then $n+1=\{k\in N:k<n+1\}$.

Note that for (1) you want to start at $n=0$, not at $n=1$. (And what you have for $n=1$ isn’t correct: $1\notin 0$. In fact $1=0\cup\{0\}=\{0\}$, so $0\in 1$.) In order to prove (1) you must show that there is no $k\in N$ such that $k<0$. How you do this will depend on you you’ve defined the relation $<$; I don’t know your definition, so I can’t help here.

For (2), assume that $n=\{k\in N:k<n\}$. Then

$$n+1=S(n)=n\cup\{n\}=\{k\in N:k<n\}\cup\{n\}\;,$$

so to finish the induction step you must show that

$$\{k\in N:k<n\}\cup\{n\}=\{k\in N:k<n+1\}\;.$$

It’s very easy to see that

$$\{k\in N:k<n\}\cup\{n\}\subseteq\{k\in N:k<n+1\}\;,$$

so all that remains is to show that

$$\{k\in N:k<n+1\}\subseteq\{k\in N:k<n\}\cup\{n\}\;.$$

For this you’ll want the result from this question.