Thread: Well-Ordering Property

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?

I think that you must post the complete proof in that text.
Along with some background from the textbook on W.O.

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.

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.

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
Thanks a lot!