Well-Ordering Property

Aug 2009
34
3
I'm getting a little confused about the logic behind a proof in a book. It is proving the well-ordering property using induction; it proves the contrapositive:
If T is a subset of the natural numbers which has no smallest element, then T is empty

Suppose T has no smallest element and let S be the complement of T. (*) Let n be a natural number such that for all m<n, m is in S. Then n is in S and so S is the set of natural numbers and T is empty.

(*) This is the step I don't understand. What if 1 is in T? Then no such n exists and S is empty? Where is the step that uses the fact T has no smallest element?
 

Plato

MHF Helper
Aug 2006
22,507
8,664
I think that you must post the complete proof in that text.
Along with some background from the textbook on W.O.
 
Aug 2009
34
3
This is from Peter Cameron's Introduction to Algebra. It's just the introduction chapter going through basic number systems in a relaxed way (ie no formal construction from some explicit set of axioms).
Also, that is the entire proof. I know it's not the best book to be contemplating about the well-ordering property, but some of the other books I have on set theory all assume the well-ordering property and use it to prove induction, so that doesn't help.
 

emakarov

MHF Hall of Honor
Oct 2009
5,577
2,017
I think everything just has to be written carefully.

Suppose T has no least element. We prove some statement by (strong) induction that will entail that T is empty. Let S be the complement of T.

Induction statement P[n]: for all m < n, m is in S.

P[0]: vacuously true.

Fix some n and suppose P[n]: for all m < n, m is in S.
Need to prove P[n+1]: for all m < n + 1, m is in S.

Since (m < n + 1) iff (m < n or m = n), we need to show that n is in S. Note that at this points we reached the stage "Let n be a natural number such that for all m<n, m is in S" in your proof. Then if n is not in S, n is in T (as T is the complement of S). However, n is the least element in T because for all m<n, m is in S. Contradiction. Therefore, n is in S and P[n+1] is proved.

Thus, we proved "for all n, P[n]". Therefore, T is empty because if n is in T, then n < n + 1 and P[n+1] says n is in S, i.e., not in T.
 
  • Like
Reactions: bleys
Aug 2009
34
3
Oh, wow, thanks! I realise now that I was getting confused because I didn't put together the fact that both induction AND contradiction were being used (I have only seen that kind of proof method a handful of times). I kept seeing them separate (Giggle)
Thanks a lot!