- #1
dmuthuk
- 41
- 1
I am trying to prove that the set of natural numbers is well-ordered using induction. I am assuming of course that the natural numbers are defined as as the smallest inductive set (of the type specified by the Axiom of Infinity) and that the usual order is defined by [tex]n<m[/tex] iff [tex]n\in m[/tex]. I have an argument in mind, but since I am still getting used to induction, I am not sure sometimes if I am using it the right way. I mean I have used it a lot before, but have never thought about it seriously.
So, let [tex]S\subset\mathbb{N}[/tex] be defined as follows: [tex]n\in S[/tex] iff every subset of [tex]\mathbb{N}[/tex] that contains [tex]n[/tex] as an element has a smallest element. Then, since [tex]0=\emptyset[/tex] is an element of every number, it is the smallest element of every set that contains it. Next, we can assume that [tex]n\in S[/tex] and prove that every set containing [tex]n^+[/tex] also has a smallest element. I will leave out the details here, but I was wondering if I can use induction in this manner.
The reason I am a little unsure about this is because I am used to using induction to prove statements like "the sum of the first [tex]n[/tex] numbers is always [tex]\frac{n(n+1)}{2}[/tex]".
So, let [tex]S\subset\mathbb{N}[/tex] be defined as follows: [tex]n\in S[/tex] iff every subset of [tex]\mathbb{N}[/tex] that contains [tex]n[/tex] as an element has a smallest element. Then, since [tex]0=\emptyset[/tex] is an element of every number, it is the smallest element of every set that contains it. Next, we can assume that [tex]n\in S[/tex] and prove that every set containing [tex]n^+[/tex] also has a smallest element. I will leave out the details here, but I was wondering if I can use induction in this manner.
The reason I am a little unsure about this is because I am used to using induction to prove statements like "the sum of the first [tex]n[/tex] numbers is always [tex]\frac{n(n+1)}{2}[/tex]".
Last edited: