Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Help! Well-ordering principle

  1. Aug 26, 2011 #1
    Hi!
    First ever class of Modern Algebra today. I have a question about the well-ordering principle, introduced in class. This seems awfully foreign to me, as I haven't had a single theoretical math class. I'm worried that this question is super stupid so I elected to post it anonymously to the forum rather than ask the professor.

    Here are my notes (they may not be what he wrote, maybe leading to my confusion. It was a stressful class):

    well-ordering princ:

    Every non empty subset of [itex]Z[/itex] that is bounded below contains a minimal element.
    (I interpreted this as every set of numbers in z that is bounded below has a smallest number).
    What does it mean to be bounded below????

    he then said {n [itex]\in[/itex] [itex]Z[/itex] I (what does this vertical bar mean?)n3>7}

    Ok, this seemed pretty straightforward. But then he said it's bounded below by 0! In other words, 0 is the smallest number that satisfies n^3>7??? Or did he just arbitrarily choose 0 as the bound?

    So then I have written 0[itex]\in[/itex]S (I'm assuming S is the set n^3>0). And then he said 2 is the minimal element...I suppose that makes sense. I just don't understand where he pulled 0 as the bounded below value. Wouldn't 2 be the bounded below value, as 0^3 is obviously not larger than 7?

    He then wrote {r[itex]\in[/itex]R I r^3 >7}. the first thing he throws out is that 7^(1/3) would satisfy the inequality, but it's not in the set because it's not rational. Perhaps I accidentally wrote '>' in place of "=", because it makes no sense that 7>7.

    He then started the division algorithm in Z, which you'll probably hear about tomorrow.

    So, the summary of my questions is:

    Why 0 as the bounded below value?
    What's the vertical bar?
    Why 7^(1/3) as something in the second set if, in fact, I correctly wrote '<'?
    Also, can anybody give me a brief preview of how this principle will be important in Modern Algebra, just so I can get a jump?

    Thanks a million,

    Blue
     
  2. jcsd
  3. Aug 26, 2011 #2

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    Alright, let's see what we can do here

    Your questions aren't stupid, however. It's normal to have these kind of questions in the beginning.

    Well, being bounded below means that you have a lower bound. And a lower bound is simply an element smaller than everything in the set.

    Examples:

    {1,2,3} is bounded below by 1, indeed 1 is smaller than 1, 2 and 3. So 1 is a lower bound. However, 0 is also a lower bound (and 0 is not in the set!): indeed, 0 is smaller than 1, 2, 3

    ]0,1] is bounded below by 0. But 0 is not in the set!!

    {...,-8,-7,-6,-5,-4} (imagine that all integers smaller than -8 is also in the set) is not bounded below. Indeed, there is no element smaller than all these numbers.

    The bar means "such that". So [itex]\{n\in \mathbb{Z}~\vert~n^3>7\}[/itex] means that you "take the set of all integers n such that [itex]n^3>7[/itex]".

    Nonono. He says that 0 is a lower bound of the set. This does not mean that 0 is actually in the set. So it does not mean that 0 is actually the smallest number such that [itex]n^3>7[/itex]. It just means that all numbers n such that [itex]n^3>7[/itex] will be larger than 0. Or equivalently: all numbers smaller than 0 will not satisfy [itex]n^3>7[/itex]

    2 is the minimal element and is a lower bound. But 0 is also a lower bound. Again: being a lower bound does not mean that you're actually in the set!!

    No, this makes no sense. I think he meant to write [itex]\geq[/itex] here. And I also think he meant to write Q instead of R there.

    This is a hard question to answer just like that. I could probably make up a bunch of results here that use the theorem, but I doubt this will mean much to you.

    However, in short: the well-ordering principle is used in establishing "proofs by induction" and in proving the division algorithm. You'll see soon enough why it is important.
     
  4. Aug 26, 2011 #3

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    A "lower bound" on a set of numbers, X, is a number that is less than or equal to every member of X. X is "bounded below" as long as it has a lower bound. Of course, if a is a lower bound for X, and b< a, then b is also a lower bound.

    The vertical line can be read as "such that". [itex]\{n\in Z | n^3> 7\}[/itex] is "the set of all integers whose cube is greater than 7. Since [itex]2^3= 8[/itex], that is exactly the same as "the set of all itegers greater than or equal to 2.

    No. A lower bound for a set is not necessarily in the set. (In fact, at most one member of any set can be a lower bound for that set.) A lower bound is a number less than or equal to any number in the set. 2 happens to be a lower bound and, as I said before, so is any number less than 2.

    Well, not "arbitrarily". But he did choose one of the infinite collection of lower bounds.

    What? where did "S" come from? You hadn't mentioned "S" before. Is S the set you were talking about before?

    Again, a "lower bound" on a set is any number that is lower than or equal to any member of the set. It does not have to be a member of the set itself. And, as I said before, there can be at most one lower bound actually in the set. If the set has a "minimum" or smallest member, then it is the only lower bound in the set. But there are sets that have no minimum. If we were talking about the set of all real numbers, x, such that [itex]x^3> 7[/itex] ... (Oh, wait, that's exactly what your teacher does next!

    I think you did! Also"[itex]\in R[/itex]" does not require that it be rational. Or perhaps you misheard and he said that [itex]7^{1/3}[/itex] does not satisfy that and so the set has NO lowest or "minimum" member. It does, however, still have a "greatest lower bound". [itex]7^{1/3}[/itex] is less than or equal than anything in the set but any number, x, less than that would not satisfy [itex]x^3> 7[/itex] so there is no lower bound greater4 than [itex]7^{1/3}[/itex].

    You are being introduced to the "least upper bound" and "greatest lower bound" principles. The only thing distinguishing the "field of rational numbers" and the "field of real numbers" (algebraically, they have pretty much the same properties) is that if a set of rational numbers has an "upper bound", thenit has a "least upper bound" while there exists sets of rational numbers, having an upper bound, that have no (rational number) least upper bound.

     
  5. Aug 28, 2011 #4
    I really appreciate both your answers, they cleared a lot up for me.

    When you say the least upper bound/greatest lower bound principles, it reminds me of something I just read in my textbook, Abstract Algebra: A Concrete Introduction by Robert H. Redfield.

    "While the set of real numbers whose square is strictly greater than 2 is bounded below (by 1, among other numbers), it does not contain a minimal element. On the other hand, the same subset of integers, i.e., all those integers whose squares are strictly greater than 2, is also bounded below (also by 1), but in this case the subset does contain a minimal element, namely, 2."

    I'm not completely sure what this means, but I'm assuming it means something like this:

    1.92>2, as is 1.82, or 1.792, etc.. In other words, because you can think of an infinite set of possibilities that satisfy the constraint, there's no minimal element. Is this correct?

    Then, because the integers must be complete numbers, you basically just have 0,1,2 to work with. 22 is obviously the smallest one that works, so there is a minimal element.

    Is this correct? Does it relate to the principle mentioned at the end of the last post?

    Also, I'm going to create a new post on the division algorithm.

    Thanks for all the help.
     
  6. Aug 29, 2011 #5

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    Indeed, the set of numbers whose square is strictly larger than 2 is [itex]]\sqrt{2},+\infty[[/itex]. The only possible choice for minimal element is [itex]\sqrt{2}[/itex], but this does not belong to the set. Indeed, the square of [itex]\sqrt{2}[/itex] is not strictly larger than 2. Thus there is no minimal element...
     
  7. Aug 29, 2011 #6
    Just to add a few points :

    What you are working with is a particular case of the properties of an ordered set,
    i.e., a set S, together with a binary relation < , defined on it; an order relation on
    a set S , in which, for each pair (x,y) either x=y, x<y , y<x , or elements are not
    comparable, and the relation is transitive.

    In ii) below, not all elements are
    comparable, while in i) below, they are. In ii) , then, we have a partial order, since
    we do not always have, for any two sets that they are either equal or one is contained
    in the other, and in i) we have a total order.

    Examples :
    i) (R,<) ; R is the reals, with < as the standard "less than or equal to"
    ii) (P(S), Subset of ); where S is a non-empty set , and P(S) is the collection
    of subsets, then A<B means " A is a subset of B"


    A set S is well-ordered if (definition) if every subset of S has a least element;
    a least element in a pair (X,<) is an element L in S with L<x , for all x in X; note
    that this element--if it exists--is not necessarily unique. In (P(S),<) as above
    , singletons are non-unique elements (maybe it is better to start with S a finite set),
    while , in the reals, an interval (a,b) :={x in R: a<x<b } does not have a least element.

    Look up terms like lower bound, upper bound, etc.

    HTH

    .

    Look up the concepts of least element
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook