h2g2 The Hitchhiker's Guide to the Galaxy: Earth Edition

I've been reading up on infinte cardinals, and the continuum hypotheis. I'm stuck at a particualr problem - ordering the Real numbers. Can anyone shed some light on how on earth this is possible? I get lost in the short proofs I've seen.
[My interest in this is that it's a stepping stone in an argument about 'throwing darts' at the real line, which suggests the continuum hypothesis is false. (Frieling's argument).Which is mind-bending.]

Any online reference to this? (The ordering or Frieling's argument)

I assume you mean a well-ordering of R as opposed to its usual ordering?

I could hazard a guess at how ordering of R is supposed to happen - will have to use Zorn's Lemma, or transfinite induction. I think the idea is that you can always add one more point at the end of your ordering, and by Zorn, you can carry on to get the whole of R.

Yes indeed I do mean a well ordering of the Reals.
There's a description of Freiling's argument about 2/3 way down this page (clearly titled).
http://www.u.arizona.edu/~chalmers/notes/continuum.html
It's easy to follow if you accept the well-ordering part - hence my frustration.
Can you explain more about using Zorn's lemma please? The proof I have got stuck is that every set can be well-orderede. It can be found here:
http://br.crashed.net/~loner/settheory/axiomofchoice/ac.html
(although I can't get it to open at the moment -hope it's still there.)

I have huge exams coming up in less than 3 weeks, so I can't really spare much time, plus its been a while since I did the set theory...is there a specific point you get stuck on?

Thanks for your reply - I've been away from the computer for a few days.
The key point I'm stuck at is the proof of Zermelo's well-ordering principle (as seen on that link which is working now http://br.crashed.net/~loner/settheory/axiomofchoice/ac.html)
It seems to be saying given a set A you can well-order it as follows. Take a point, then a point from what's left, then repeat until you've exhausted the set A, by breaking it into the union of the points you've chosen. This is then the well-order of the points. i.e. construct an arbirary well-order one point at a time. What's confusing is imagining this exhausting the Real numbers. But is that basically what the proof is saying?
Any comments or pointers would be great, but I don't want to distract you from revision - you have the washing up and hoovering to do that already

Yeah, you do it one point at a time...perhaps thats not the best way to think about it really. You need to believe that transfinite induction works, and I think the way to do that is to think about the ordinal B (say) consisting of all ordinals for which the well-ordering process gives a place. (Remember that we think of ordinals as the set containing all smaller ordinals) Then if R\B is not empty, we have all the things we need to be able to put B itself into the ordering, so we get a contradiction with the fact that B is not in B.

So R/B must be empty, and we have well ordered R.

(Note I'm making slight abuses of notation here - R/B being empty really means R=B, but theyre not really the same set, because B has the well ordering and R doesnt (appear to). There's a bijection between the sets that I'm supressing)

That make sense?

That helps a lot. What is perhaps the stumbling block is trying to think of ordinals that are 'bigger' than aleph-0 but 'less than' the cardinality of the Reals. (I think that is not technically correct - I'm mixing cardinals and ordinals). So it seems we have to imagine ordinals that are not natural numbers, nor finite decimals. I suppose that's the point of trans-finite induction?
Thanks again - I think I get it now, which means I can look at Freiling's argument again - did you have a look at the link? It seems quite convincing that there is an aleph between aleph-0 and the cardinality of the Reals. (What exams have you got by the way? finals? beyond?)

Some of the ordinals are cardinals, but there are an awful lot more ordinals than cardinals. Here's a good way to think about ordinals bigger than aleph_0 (also known as w (omega)):

Draw yourself a real line, then mark a sequence of points on it that look like: 1/2, 3/4, 7/8, 15/16, ..., (2^n-1)/2^n, ....

Now the point '1' on the real line corresponds to w. Now start again, mark a point at '2', which corresponds to w+1 (which is not equal to 1+w). '2+1/2' is w+2, '2+3/4' is w+3, ..., '(2+((2^n-1)/2^n))' ,...

You can fit in another infinite sequence before you get to '3', which is 2*w (which is not equal to w*2). Next you can start reducing the length of the real line you use to get to your limit - say get to another limit at '3+1/2' (3*w), then the next limit at '3+3/4' (4*w), next at '3+7/8 (5*w)' etcetera, then by the time you get to '4', you are at (w*w).

You can keep going, defining w^w, w^w^w, etcetera, it all gets a bit silly and you are still only working with countable ordinals (the same *cardinality* as aleph_0 though not the same *ordinal*). There's more to this, worth reading up on if you're interested.

I looked at Freiling's argument, but I'm not so sure its that intuitive. It seems like you couldn't mostly fill up the reals with countable stuff, but I think much of that is to do with the actual countable subsets of the reals we work with, which are all pretty small. Don't need continuum hypothesis type sets in normal analysis.

I have PhD qualifying exams (end of the first year) (eek!)

That's interesting - I haven't seen that before. Getting to w^w is the suprise, as it's bigger than 2^w and so you've used w to get up to the ordinals for the power set, (which corresponds to the cardinality of the Reals.)
The step in Freiling's argument that seems odd is when it defines the function f as f(r_x)={r_y: y<=x} and f maps R onto countable subsets of R. I don't see why f(r_x) must always be countable. If x is an ordinal greater than w then I don't see how {r_y; y<=x} can be countable.
Isn't the point of ordinals greater than w that they are ordinals of sets with cardinality greater than w? I'm confused!

I'll think about the rest of your reply in due course. I'm off on holiday for a while. Any other good conversations out there you can recommend? And can we look forward to more entries from you after you exams? Again, good luck, and thanks for your replies...

Hmm, I'm a bit confused as well. I think it might be a notational thing, its certainly not true that you can get up to the cardinality of the reals by taking lots of sequences (countably many). However, this webpage:

http://members.shaw.ca/quadibloc/math/inf01.htm

talks about w^w as a countable set. I'll see if I can check on this sometime...my guess is that w^w as an ordinal is a different sort of way of defining powers with infinite sets from 2^(aleph_0) (which is uncountable).

Ordinals greater than w can still be countable. aleph_1 is the first ordinal with a bigger *cardinality* than aleph_0, but theres plenty of ordinals that are countable but bigger (in the well ordering sense rather than the can-you-find-an-injection-from-A-into-B sense) than w, the smallest (in the well order sense) infinite ordinal.

Does that make sense?

Yes that does make sense. That link is excellent. It's helped with my understanding of ordinals which was the source of a lot of my confusion. I have only half read it but will return to it tomorrow!

The real numbers are not countable so how do you expect to order them?
http://www.shef.ac.uk/~daj/112/box.pdf has a proof of this on page 9.

Depends what you mean by 'order'... In one sense the reals are already ordered, with the ordering by where they are in the real line. Given two reals x and y, we can always say if x=y, xy. That's an ordering. It's not the same ordering that we're talking about - the ordinals give you a way to order any set of any cardinality in such a way that given any subset of the elements, you can find a smallest element. That's what we're talking about. The usual ordering on the reals doesn't give you that because (for example) the open unit interval (0,1) has no smallest element. It might look like it should be 0, but that isn't in the set.