## Well Ordering an Infinite Set

**Moderators:** gmalivuk, Moderators General, Prelates

### 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:**5963**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.

edit: ah, because you're applying a result about partial orderings. Fair enough.

ameretrifle wrote:Magic space feudalism is therefore a viable idea.

### 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:**5963**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.

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

### 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:**

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

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

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

### Who is online

Users browsing this forum: Thesh and 13 guests