## Well Ordering an Infinite Set

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

dshizzle
Posts: 116
Joined: Thu Feb 09, 2012 3:45 am UTC

### Well Ordering an Infinite Set

Okay, so I'm taking a class in Set theory and Metric Spaces, today in class we were asked to prove that the cardinality of the well orderings of an infinite set D, who has cardinality d is 2^d. I've taken the tack of proving that there are at least 2^d partial orderings, and at most 2^d partial orderings, thereby giving exactly 2^d. Now showing that the number of well orderings is less than or equal to 2^d is trivial, since there are 2^d partial orderings on D, and there are clearly more partial orderings than well orderings. But showing that there at least 2^d partial orderings has stumped me. Is my strategy well founded ? Any ideas? Also sorry for the lack of latex and general poor formatting, I'm a noob I know. Also happy to any other set theory topics people are interested in.

Proginoskes
Posts: 313
Joined: Mon Nov 14, 2011 7:07 am UTC
Location: Sitting Down

### Re: Well Ordering an Infinite Set

2^d is the number of subsets of D. If I give you a subset S of D, can you produce a well-ordering of D? Make sure that if S and T are well-orderings of D, then they produce different well-orderings.

jestingrabbit
Factoids are just Datas that haven't grown up yet
Posts: 5967
Joined: Tue Nov 28, 2006 9:50 pm UTC
Location: Sydney

### Re: Well Ordering an Infinite Set

@dshizzle: If we let W be the cardinality of the set of well orderings, its seems easy to show W>=2^d, but you're saying that is the hard direction?

edit: ah, because you're applying a result about partial orderings. Fair enough.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.

dshizzle
Posts: 116
Joined: Thu Feb 09, 2012 3:45 am UTC

### Re: Well Ordering an Infinite Set

Well no luck so far, should get a solution today, will post it for anyone thats interested.
Reality must take precedence over public relations, for nature cannot be fooled. - Feynman

jestingrabbit
Factoids are just Datas that haven't grown up yet
Posts: 5967
Joined: Tue Nov 28, 2006 9:50 pm UTC
Location: Sydney

### Re: Well Ordering an Infinite Set

Fix a point and try to come up with a way to get a particular element of the power set from the well ordering. You might not be able to get every element of the power set but you only need most of them.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.

dshizzle
Posts: 116
Joined: Thu Feb 09, 2012 3:45 am UTC

### Re: Well Ordering an Infinite Set

Okay so I offered a proof, dont have the time to give the rigorous version, will do so on the weekend probably but it goes something like this. Note that are 2^d ways to make a chain of D. Note that some of these chains will have some subset without least element, let the cardinality of these chains be c. Assume that there are c>=2^d such chains. But this gives a clear contradiction since it implies that there is no well ordering on D, since well orderings are chains. Then 2^d > c then we can remove c from 2^d and 2^d-c=2^d. Then we are done. Actually stumbled on this myself and the prof said it was correct feels good to be right once in a while.
Reality must take precedence over public relations, for nature cannot be fooled. - Feynman

dshizzle
Posts: 116
Joined: Thu Feb 09, 2012 3:45 am UTC

### Re: Well Ordering an Infinite Set

and as to your approach jestingrabbit that was my prof's initial idea, but he gave up on it, it might well have worked but he can be an impatient man.
Reality must take precedence over public relations, for nature cannot be fooled. - Feynman

skeptical scientist
closed-minded spiritualist
Posts: 6142
Joined: Tue Nov 28, 2006 6:09 am UTC
Location: San Francisco

### Re: Well Ordering an Infinite Set

dshizzle wrote:Okay so I offered a proof, dont have the time to give the rigorous version, will do so on the weekend probably but it goes something like this. Note that are 2^d ways to make a chain of D. Note that some of these chains will have some subset without least element, let the cardinality of these chains be c. Assume that there are c>=2^d such chains. But this gives a clear contradiction since it implies that there is no well ordering on D, since well orderings are chains. Then 2^d > c then we can remove c from 2^d and 2^d-c=2^d. Then we are done. Actually stumbled on this myself and the prof said it was correct feels good to be right once in a while.

That doesn't work, because the bolded sentence is false. It is entirely possible that c=2^d, because a set of size 2^d with a set of size 2^d removed can be nonempty. In fact, c=2^d.
Spoiler:
You already showed that c ≤ 2^d. Note that c is also the cardinality of chains which are not the reverse of a well order, because reversing the chain puts chains which are not well-ordered in one-to-one correspondence with chains which are not the reverse of a well order. Since d is infinite, no chain can be both a well order and the reverse of a well order. So the set of all chains on D is the union of two sets of cardinality c, which means c+c ≥ 2^d. By cardinal arithmetic, c = 2^d.

Yet more evidence for the maxim that if you want to find the error in a proof, look for where the author says that something is "obvious" or "clear".

P.S. I went to some effort to come up with a nonconstructive proof that c=2^d, because the constructive ones can too easily be turned into solutions to your homework problem. Just me being evil.
I'm looking forward to the day when the SNES emulator on my computer works by emulating the elementary particles in an actual, physical box with Nintendo stamped on the side.

"With math, all things are possible." —Rebecca Watson

dshizzle
Posts: 116
Joined: Thu Feb 09, 2012 3:45 am UTC

### Re: Well Ordering an Infinite Set

I see. There's no cure for stupid is there.
Reality must take precedence over public relations, for nature cannot be fooled. - Feynman

Proginoskes
Posts: 313
Joined: Mon Nov 14, 2011 7:07 am UTC
Location: Sitting Down

### Re: Well Ordering an Infinite Set

dshizzle wrote:I see. There's no cure for stupid is there.

No, but it can be battled.