I don't understand what you mean by "seeing as it isn't in its usual ordering". Where are you told that it isn't?
Here's the exercise:
About well-ordering of , my text saysProve the well-ordering Property of by induction and prove the minimal element is unique.
This is some pretty basic stuff, but how can I show that is well-ordered, seeing as it isn't in its usual ordering? (The text hasn't covered different orderings.)(Well Ordering of ) If A is any nonempty subset of , there is some element such that , for all . (m is called the "minimal element" of A.)
My next question (assuming that I'm supposed to show the well ordering of ) is how to structure the induction? I want to use the fact, for example, that is isomorphic to but the text hasn't covered isomorphisms yet. Can anyone think of another approach?
Thanks!
-Dan
PS By the by, I know that A can be of the form {1, 2, 4, 5, 6, 100}. The proof should be essentially identical to the case {1, 2, 3, 4, 5, 6}. and I feel more comfortable with using the chain (is that the correct term?)
-Dan
The problem comes from "Abstract Algebra" by Dummit and Foote. It's an undergrad Group Theory/Abstract Algebra text. I am working through the "preliminary" section so I doubt that there's any ordering properties that are not "standard." By that I mean we can take 4 > 3 > 2 > 1 > 0 as opposed to other ordering schemes.
The problem statement is the first quote in the OP. The definition my text gives me for a definition of well-ordering is the second quote.
The point about the set of negative integers was my exact thought that the question is worded wrong. As you agree with me I won't sweat it any longer and just skip the problem.
Thanks to both of you.
-Dan
I have a old pre-publication review copy of the second edition of that book.
And you are correct that problem is exactly as you said. I spent some time looking at posted errata sheets for the book but no luck.
So I went back and reviewed their definition. It says, (Well ordering for ), if is a subset of then ....
Thus, I think that you are to show that every has a first term using induction.
Like so much else in Dummit/Foote, I find them to use confusing language here. But then I learned algebra from book by Herstein and then Mac Lane nearly a half century ago.
(See also StackExchange.) The proof is by strong induction. Let B be a nonempty subset of and suppose B does not have the least element. Let . We will show that . Indeed, because otherwise 1 would be the least element of B. Next, assume 1, ..., n ∈ J. If n+1 ∈ B, then n+1 is the least element of B (since 1, ..., n ∉ B), so n+1 ∈ J. Thus, and B is empty, a contradiction.
One can notice that the proof is by contradiction and we consider the complement of B. It can be shown that the contrapositive of strong induction for a predicate P is the well-ordering principle for the the set (see this post). Thus, strong induction and well-ordering principle are equivalent. Strong induction, in turn, can be proved from regular induction.