Equivalent to Axiom of Choice?

11 views
Skip to first unread message

Thomas Andrews

unread,
Nov 1, 2007, 2:00:08 PM11/1/07
to
Theorem: Every partially ordered set can be extended to a total order.

The easy proof I've found of this uses the axiom of choice (well,
specifically, Zorn's Lemma.)

Is it equivalent to the axiom of choice?

=thomas


Fred Galvin

unread,
Nov 2, 2007, 3:29:59 AM11/2/07
to

No, it's called the order extension principle, and it's weaker than
the axiom of choice, or so I've been told. I can't tell you any more
about it, but now that you know what it's called it will be easy to
look up the relevant literature.

Stefan Wehmeier

unread,
Nov 2, 2007, 8:03:14 AM11/2/07
to
Thomas Andrews wrote:

no, it does not even imply that every Boolean algebra has a prime ideal. See

http://citeseer.ist.psu.edu/87611.html


--
Stefan Wehmeier
ste...@math.upb.de

Bill Taylor

unread,
Nov 2, 2007, 10:59:15 PM11/2/07
to
> > Theorem: Every partially ordered set can be extended to a total order.
>
> it does not even imply that every Boolean algebra has a prime ideal.

How about the following kind-of-dual variant - where does it fit into
the one-way implications above:


### Every partial order can be RESTRICTED to a maximal total order.


"Maximal" here refers to order-preserving inclusions.

Bill Taylor

Thomas Andrews

unread,
Nov 3, 2007, 1:08:52 PM11/3/07
to
On Nov 2, 8:03 am, Stefan Wehmeier <stef...@math.upb.de> wrote:
> Thomas Andrewswrote:
> stef...@math.upb.de

Thanks Stefan, Fred. It was my intuition that it couldn't be
equivalent to AC, but I was curious.

Thomas Andrews

unread,
Nov 3, 2007, 2:30:17 PM11/3/07
to
On Nov 2, 8:03 am, Stefan Wehmeier <stef...@math.upb.de> wrote:
> Thomas Andrews wrote:
> >Theorem: Every partially ordered set can be extended to a total order.
>
> > The easy proof I've found of this uses the axiom of choice (well,
> > specifically, Zorn's Lemma.)
>
> > Is it equivalent to the axiom of choice?
>
> no, it does not even imply that everyBooleanalgebra has aprimeideal. See> stef...@math.upb.de

I did like the proof in that paper of the Order Extension Theorem from
the Well Ordering Principle.

If (P,<=) is a partial order, and we have a well-ordering on the set
P, then we define:

l(x)={z<=x: z in P}

And extend <= by defining:

xRy if x=y or if the least element of the symmetric difference
between l(x) and l(y) (under the well-ordering of P) is a member of y.

Now R is a total order and x<=y implies xRy.

Much nicer than the Zorn Lemma proof, which feels 'less constructive'
on an intuitive level, even if it isn't logically any different.

William Elliot

unread,
Nov 4, 2007, 12:48:46 AM11/4/07
to
On Sat, 3 Nov 2007, Thomas Andrews wrote:
> On Nov 2, 8:03 am, Stefan Wehmeier <stef...@math.upb.de> wrote:

Typo noted below at **.

> > Thomas Andrews wrote:
> > >Theorem: Every partially ordered set can be extended to a total order.
> >

> > http://citeseer.ist.psu.edu/87611.html


> >
> I did like the proof in that paper of the Order Extension Theorem from
> the Well Ordering Principle.
>
> If (P,<=) is a partial order, and we have a well-ordering on the set
> P, then we define:
>

> l(x) = {z<=x: z in P}


>
> And extend <= by defining:
>
> xRy if x=y or if the least element of the symmetric difference
> between l(x) and l(y) (under the well-ordering of P) is a member of y.

** is a member of l(y).
or
** is <= y.

Harald Hanche-Olsen

unread,
Nov 4, 2007, 3:35:04 AM11/4/07
to
+ Bill Taylor <w.ta...@math.canterbury.ac.nz>:

That would be the Hausdorff maximal principle, which is equivalent to
the axiom of choice.

To be sure, the Hausdorff maximal principle states that any totally
ordered subset (chain) of a given partially ordered set (poset) is
contained in a maximal chain. To deduce this from your version,
restrict your attention to those members of the given poset that are
comparable with every member of the given chain.

--
* Harald Hanche-Olsen <URL:http://www.math.ntnu.no/~hanche/>
- It is undesirable to believe a proposition
when there is no ground whatsoever for supposing it is true.
-- Bertrand Russell

William Elliot

unread,
Nov 8, 2007, 1:22:40 AM11/8/07
to
On Sat, 3 Nov 2007, William Elliot wrote:
> On Sat, 3 Nov 2007, Thomas Andrews wrote:
> > On Nov 2, 8:03 am, Stefan Wehmeier <stef...@math.upb.de> wrote:
> > > Thomas Andrews wrote:

> > > >Theorem: Every partially ordered set can be extended to a total order.

> > If (P,<=) is a partial order, and we have a well-ordering on the set


> > P, then we define:
> >
> > l(x) = {z<=x: z in P}
> >
> > And extend <= by defining:
> >
> > xRy if x=y or if the least element of the symmetric difference

> > between l(x) and l(y) (under the well-ordering of P) is <= y.


>
> > Now R is a total order and x<=y implies xRy.

Interesting. Once you get into it, it's straight forward except
for the transitivity of R. How is that handled?

jinhyun

unread,
Nov 18, 2007, 6:11:11 AM11/18/07
to
> for the transitivity of R. How is that handled?- Hide quoted text -
>
> - Show quoted text -

Not sure a proof that every partial order can be extended to a total
order needs the result the every set can be well-ordered, merely that
every set can be given a total order, which of course, is assured by
the well-ordering theorem as every well-ordering is a total ordering.
Afterwards, it is plain sailing using the dictionary order as we
discussed on the other forum; this other proof which uses the peculiar
properties of a well ordering seems needlessly complicated to me.

Thomas Andrews

unread,
Nov 18, 2007, 1:15:01 PM11/18/07
to

For distinct x,y,z (non-distinct transitivity is easy), proof by
contradiction.
We'll use "P" for the poset order and < for our well-order.

Assume: xRy and yRz and zRx.

Then the smallest element u (in the well-ordering) of i(x) delta i(y)
is in i(y)
The smallest element v of i(y) delta i(z) is in i(z).
The smallest element w of i(x) delta i(z) is in i(x).

Now, if w is in i(y), then, since w is not in i(z), w is in i(y) delta
i(z). So v<w, since the smallest element of i(y) delta i(z) is in
i(z).
So we know that v is in i(x), or v would be a smaller element of i(x)
delta i(z).
Since v in i(x)-i(y), then v has to be greater than u. So u<v<w.

If w is not in i(y), then w is in i(x) delta i(y). So u < w.

In both cases, we see that u<w.

But then, xRy and yRz and zRx is symmetric. So this means that u<w,
w<v, v<u.

Contradiction.

William Elliot

unread,
Nov 19, 2007, 7:56:22 AM11/19/07
to

Whew, that is much detail to pick through. In the mean time another proof
was presented in sci.math. This one apears even more 'constructive' and
is much simplier using known constructions and theorems of order theory.

Let (P,<=) be an (partial) ordered set.
Let down a = { x | x <= a }
Let (P,<=_w) be a well ordering of P.

Let C = { 0,1 }^P and for A subset P,
let c_A = f:P -> {0,1}, x -> 0 if x not in A, 1 if x in A.
Let (C,<=_lex) be C lexicographically ordered by 0 < 1 and <=_w.
for f,g in C, let m(f,g) = least_<<= { x | f(x) /= g(x) }
and define f <_lex g when f(m(f,g)) < g(m(f,g))
least_<<= A is the least element of A by the well order <<=

c_A is the characteristic function for A subset P.
C is the collection of characteristic function for subsets of P.
C is given the dictionary order, which is linear order.

For x,y in P, define x <<= y when c_down x <=_lex c_down y

<<= is a total order extension of <= for P. Useful to show this is:

lex C linear order. A subset B ==> c_A <=_lex c_B
c_A = c_B ==> A = B; c_down x = c_down y ==> x = y

Christopher J. Henrich

unread,
Nov 26, 2007, 9:00:05 AM11/26/07
to
In article <fgd478$ll8$1...@news.ks.uiuc.edu>, Thomas Andrews
<thom...@gmail.com> wrote:

The book /Equivalents/ /of/ /the/ /Axiom/ /of/ /Choice/, by Herman
Rubin and Jean E. Rubin, is likely to be helpful.

--
Chris Henrich
http://www.mathinteract.com
God just doesn't fit inside a single religion.

Reply all
Reply to author
Forward
0 new messages