Results 1 to 6 of 6

Math Help - Well Ordering Theorem

  1. #1
    Newbie
    Joined
    Nov 2009
    Posts
    5

    Well Ordering Theorem

    I try to understand the following proof of the well ordering theorem, by Halmos:

    Given the set X, consider the collection W of all well ordered subsets of X.
    Explicitly: an element of W is a subset A of X together with a well ordering of A.
    We partially order W by continuation.

    The collection W is not empty, because, for instance, is an element of W. If X unequals , less annoying elements of W can be exhibited; one such is {(x,x)}, for any particular element x of X. If C is a chain in W, then the union U of the sets in C has a unique well ordering that makes U "larger" than (or equal to) each set in C. This means that the principal hypothesis of Zorn's lemma has been verified; the conclusion
    is that there exist a maximal well ordered set, say M, in W. The set M must be equal to the entire set X.
    Reason: if x is an element of X not in M, then M can be enlarged by putting x after all the elements of M.

    Let A and B be two well ordered subsets of X. In my observation B is a continuation of A if and only if A is a subset of B and A is the initial segment of some element of B.

    The collection W could have well ordered subsets with different orders? The statement about the maximal well ordered set follows from Zorn's lemma. The point what is ambiguous for me is that M equals X.

    If we have found a maximal well ordered set with a given order, how can we say that adjoining a x (doesn't belong to M) to M leads to a well ordered set? Why is this element related (the given order) with all the elements of M?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    2
    Quote Originally Posted by octa01 View Post
    I try to understand the following proof of the well ordering theorem, by Halmos:

    Given the set X, consider the collection W of all well ordered subsets of X.
    Explicitly: an element of W is a subset A of X together with a well ordering of A.
    We partially order W by continuation.

    The collection W is not empty, because, for instance, is an element of W. If X unequals , less annoying elements of W can be exhibited; one such is {(x,x)}, for any particular element x of X. If C is a chain in W, then the union U of the sets in C has a unique well ordering that makes U "larger" than (or equal to) each set in C. This means that the principal hypothesis of Zorn's lemma has been verified; the conclusion
    is that there exist a maximal well ordered set, say M, in W. The set M must be equal to the entire set X.
    Reason: if x is an element of X not in M, then M can be enlarged by putting x after all the elements of M.

    Let A and B be two well ordered subsets of X. In my observation B is a continuation of A if and only if A is a subset of B and A is the initial segment of some element of B.

    The collection W could have well ordered subsets with different orders? The statement about the maximal well ordered set follows from Zorn's lemma. The point what is ambiguous for me is that M equals X.

    If we have found a maximal well ordered set with a given order, how can we say that adjoining a x (doesn't belong to M) to M leads to a well ordered set?


    Because "clearly" (can you actually see why?) every subset of M\cup\{x\} has a first element after "putting" x "after" any other element of M...

    Tonio


    Why is this element related (the given order) with all the elements of M?
    .
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Nov 2009
    Posts
    5
    The phrase "putting" x "after" any other element of M, I don't understand. How do you know that adjoining a {x} to M is consistent with respect to the order of the maximal well ordered set? In other words: is the adjoining {x} bigger (with respect to the order of M) than all elements of M?

    If this statement is clear, then I indeed see that {x} adjoined with M is well ordered.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    2
    Quote Originally Posted by octa01 View Post
    The phrase "putting" x "after" any other element of M, I don't understand. How do you know that adjoining a {x} to M is consistent with respect to the order of the maximal well ordered set? In other words: is the adjoining {x} bigger (with respect to the order of M) than all elements of M?

    If this statement is clear, then I indeed see that {x} adjoined with M is well ordered.

    I think "bigger" here means x is going to be a maximum element of M\cup \{x\}

    Tonio
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Nov 2009
    Posts
    5
    How is it possible to make a (arbitrary) x the maximum element of M U {x}?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Banned
    Joined
    Oct 2009
    Posts
    4,261
    Thanks
    2
    Quote Originally Posted by octa01 View Post
    How is it possible to make a (arbitrary) x the maximum element of M U {x}?

    Simple: determine that m\leq x\,\,\,\forall m\in M...this extends the well ordering of M, whatever it is.

    Tonio
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Well Ordering
    Posted in the Discrete Math Forum
    Replies: 9
    Last Post: September 8th 2010, 05:04 AM
  2. well-ordering
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: June 10th 2009, 11:24 AM
  3. Well-Ordering
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 15th 2008, 09:13 AM
  4. well ordering
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: July 17th 2008, 11:16 AM
  5. Well Ordering Principle
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: March 10th 2008, 09:16 AM

Search Tags


/mathhelpforum @mathhelpforum