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 \}$

I am not sure if I am going about this correctly.

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?

  • $\begingroup$ How have you had the natural numbers defined? $\endgroup$ – Tobias Kildetoft May 24 '13 at 18:37
  • $\begingroup$ Erm. $1\in \left\{0\right\}$ is most likely false. You have $1=\left\{0\right\}$ so $0 \in 1$... $\endgroup$ – xavierm02 May 24 '13 at 18:40
  • $\begingroup$ @TobiasKildetoft i just put in an edit now defining the natural numbers as 0, 1, 2, 3, ... $\endgroup$ – sarah jamal May 24 '13 at 18:40
  • $\begingroup$ 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. $\endgroup$ – Tobias Kildetoft May 24 '13 at 18:41
  • $\begingroup$ @TobiasKildetoft sorry I left out the definition that $1 = \{ 0 \} = \{ \emptyset \} $ $\endgroup$ – 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.