Results 1 to 2 of 2

Math Help - partial ordering, linearization

  1. #1
    Newbie
    Joined
    Dec 2008
    Posts
    17

    partial ordering, linearization

    Every partial ordering \leq on a set P has a linearization, i.e., some linear ordering \leq' of P exists such that x \leq y \Rightarrow x \leq' y.

    This exercise indicates to use the axiom of choice. I do not see how to prove this. I know that a partial ordered set is reflexive, transitive, and antisymmetric. However, I don't see how this has a linearization. I need a few pointers. Thanks.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member
    Joined
    Nov 2008
    From
    Paris
    Posts
    354
    Hi

    The form of the problem can suggest the use of Zorn's lemma. Now the point is to find a good set where to apply it, and I suggest you to try to find one before reading what follows!


    But here may be a solution (I did not check it properly):
    Consider S:=\{(A,\leq^*)\ ;\ A\subseteq P,\ (\leq\cap A^2)\subseteq\leq^*\ \text{and}\ \leq^*\ \text{is a total order on}\ A\} ordered by (A_1,\leq_1^*)R(A_2,\leq_2^*) iff A_1\subseteq A_2 and \leq_1^*\subseteq\leq_2^*
    Prove (S,R) is inductive, consider a maximal element (M,\leq^*) and show we must have M=P (for instance by contradiction, assume there is an x\in P-M and extend \leq^* into a total order of M\cup\{x\})
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Partial ordering
    Posted in the Differential Geometry Forum
    Replies: 3
    Last Post: June 5th 2011, 11:39 PM
  2. Partial Ordering: Strings
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: February 25th 2010, 09:33 PM
  3. Linearization of f'(a).
    Posted in the Differential Geometry Forum
    Replies: 1
    Last Post: October 29th 2009, 09:02 PM
  4. partial ordering
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: December 7th 2008, 08:55 AM
  5. [SOLVED] Linearization
    Posted in the Calculus Forum
    Replies: 0
    Last Post: February 19th 2007, 07:08 PM

Search Tags


/mathhelpforum @mathhelpforum