Results 1 to 2 of 2

Thread: partial ordering, linearization

  1. #1
    Newbie
    Joined
    Dec 2008
    Posts
    17

    partial ordering, linearization

    Every partial ordering $\displaystyle \leq$ on a set $\displaystyle P$ has a linearization, i.e., some linear ordering $\displaystyle \leq'$ of $\displaystyle P$ exists such that $\displaystyle 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 $\displaystyle S:=\{(A,\leq^*)\ ;\ A\subseteq P,\ (\leq\cap A^2)\subseteq\leq^*\ \text{and}\ \leq^*\ \text{is a total order on}\ A\}$ ordered by $\displaystyle (A_1,\leq_1^*)R(A_2,\leq_2^*)$ iff $\displaystyle A_1\subseteq A_2$ and $\displaystyle \leq_1^*\subseteq\leq_2^*$
    Prove $\displaystyle (S,R)$ is inductive, consider a maximal element $\displaystyle (M,\leq^*)$ and show we must have $\displaystyle M=P$ (for instance by contradiction, assume there is an $\displaystyle x\in P-M$ and extend $\displaystyle \leq^*$ into a total order of $\displaystyle 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: Jun 5th 2011, 10:39 PM
  2. Partial Ordering: Strings
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: Feb 25th 2010, 08:33 PM
  3. Linearization of f'(a).
    Posted in the Differential Geometry Forum
    Replies: 1
    Last Post: Oct 29th 2009, 08:02 PM
  4. partial ordering
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: Dec 7th 2008, 07:55 AM
  5. [SOLVED] Linearization
    Posted in the Calculus Forum
    Replies: 0
    Last Post: Feb 19th 2007, 06:08 PM

Search Tags


/mathhelpforum @mathhelpforum