11 views

Skip to first unread message

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

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.

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

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

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

> Thomas Andrewswrote:

Thanks Stefan, Fred. It was my intuition that it couldn't be

equivalent to AC, but I was curious.

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> >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?

>

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.

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:

> 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.

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

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:

> 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?

Nov 18, 2007, 6:11:11 AM11/18/07

to

>

> - 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.

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.

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

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:

<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

Search

Clear search

Close search

Google apps

Main menu