Results 1 to 8 of 8

Math Help - Maximal element of a linearly ordered set

  1. #1
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    9,962
    Thanks
    349
    Awards
    1

    Maximal element of a linearly ordered set

    First, this is the definition of Zorn's Lemma in my text. (Just in case it's not a standard way of defining it.)
    If A is a non-empty partially ordered set such that every chain in A (a sequence a_1 \leq a_2 \leq ~..~\leq a_n where a_i \in A) has an upper bound in A then A contains a maximal element.
    The problem is:
    Let (A, \leq ) be a linearly ordered set. The immediate successor of a \in A (if it exists) is the least element in the set \{ x \in A | a < x\}. Prove that if A is well ordered by \leq, then at most one element of A has no immediate successor.
    So. The proof.

    If (A, \leq) is a linear order then by Zorn's Lemma all chains (a, b, ..., z) in A have a maximal element. Since all elements of A are comparable in a linearly ordered set (and therefore all elements of A form a single chain) then there exists a single element z in A such that a < z for all a \in A. Thus z has no immediate successor. That is \{ x | z < x \} is empty.

    I think the proof looks good, but the trouble is I have what I think is a counter-example. Define the set A to be the natural numbers, N, linearly ordered by the usual definition of \leq on the real numbers. I can find no (infinite) chain in N that has a maximal element.

    My proof evidently missed something, but I can't tell what is missing.

    -Dan
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Joined
    Nov 2010
    From
    Staten Island, NY
    Posts
    451
    Thanks
    2
    Quote Originally Posted by topsquark View Post
    If (A, \leq) is a linear order then by Zorn's Lemma all chains (a, b, ..., z) in A have a maximal element.
    -Dan
    This very first sentence is incorrect. Zorn's Lemma does NOT say "for every linear ordered set every chain has a maximal element." It says "IF a linearly ordered set has that property, then..."


    Your "counterexample" isn't a counterexample at all. The naturals do not satisfy the hypothesis of Zorn's Lemma. So Zorn's Lemma says NOTHING about the naturals with its usual order.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    9,962
    Thanks
    349
    Awards
    1
    Quote Originally Posted by DrSteve View Post
    This very first sentence is incorrect. Zorn's Lemma does NOT say "for every linear ordered set every chain has a maximal element." It says "IF a linearly ordered set has that property, then..."


    Your "counterexample" isn't a counterexample at all. The naturals do not satisfy the hypothesis of Zorn's Lemma. So Zorn's Lemma says NOTHING about the naturals with its usual order.
    Oh dear. Now look what you've done. You're making me think...

    Thanks for the help.
    -Dan
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    9,962
    Thanks
    349
    Awards
    1
    This problem can't be as complicated as I am making it....

    To recap:
    Let A be a linearly ordered set, that is (A, \leq ). Assume further that \leq well orders A.

    My most recent attack on this is to note that A may be separated by \{ x \in A| x \leq a \} and \{ x \in A|a < x \}. I need to show that there exists an element a of A that is maximal (and unique.) My idea is to show that there exists an a in A such that \{ x \in A|a < x \} is empty. That means that a is maximal and since A is linearly ordered a is also unique.

    It sounds good, but I keep getting gnarled up in the logic and arguing in circles. The "example set" I am working with here is the well ordered set of integers
    1, 2, 3, 4, ...., -1, -2, -3, -4, ...., 0 (in order from left to right. It's a weird one, but it serves its purpose.)
    I can easily "see" that my argument works, it's just that convincing myself isn't a proof.

    Any thoughts/contradictions? Thanks.
    -Dan
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,706
    Thanks
    1637
    Awards
    1
    Quote Originally Posted by topsquark View Post
    This problem can't be as complicated as I am making it....
    The "example set" I am working with here is the well ordered set of integers
    1, 2, 3, 4, ...., -1, -2, -3, -4, ...., 0 (in order from left to right. It's a weird one, but it serves its purpose.)
    What is the exact statement of the 'root' question that you are working on?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    9,962
    Thanks
    349
    Awards
    1
    Quote Originally Posted by Plato View Post
    What is the exact statement of the 'root' question that you are working on?
    I mentioned it in the first post of the thread. There is a last part, all I have to do is show an example, but as soon as I have a proof for the first part the example should not be that difficult. Here is the whole original:
    Let (A, \leq ) be a linearly ordered set. The immediate successor of a \in A (if it exists) is the least element in the set \{ x \in A | a < x \}. Prove that if A is well ordered by \leq, then at most one element of A has no immediate successor. Give an example of a linearly ordered set in which precisely two elements have no immediate successor.
    -Dan
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,706
    Thanks
    1637
    Awards
    1
    Quote Originally Posted by topsquark View Post
    I mentioned it in the first post of the thread. There is a last part, all I have to do is show an example, but as soon as I have a proof for the first part the example should not be that difficult. Here is the whole original:
    If \left( {A, \ll } \right) is totally well ordered set-relation.
    Suppose that \alpha~\&~\beta are two maximal elements.
    Because of the total order one of those precedes the other.
    Let's say \alpha\ll\beta, thus \{x\in A:\alpha\ll x\} is nonempty.
    Doesn't well ordering give you a contradiction?
    Last edited by Plato; March 20th 2011 at 04:59 PM.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    9,962
    Thanks
    349
    Awards
    1
    Quote Originally Posted by Plato View Post
    If \left( {A, \ll } \right) is totally well ordered set-relation.
    Suppose that \alpha~\&~\beta are two maximal elements.
    Because of the total order one of those precedes the other.
    Let's say \alpha\ll\beta, thus \{x\in A:\alpha\ll x\} is nonempty.
    Doesn't well ordering give you a contradiction?
    Oh for the love of... Thanks.

    -Dan
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Maximal Element
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: May 22nd 2011, 09:07 AM
  2. Replies: 1
    Last Post: December 13th 2010, 02:21 AM
  3. Partially ordered set with no maximal element
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: March 9th 2010, 12:37 AM
  4. Finding element of maximal order in symmetric group
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: December 13th 2009, 10:20 PM
  5. A partial order set with a non-unique maximal element
    Posted in the Differential Geometry Forum
    Replies: 3
    Last Post: August 29th 2009, 07:57 AM

/mathhelpforum @mathhelpforum