Well-ordered subsets of real numbers

factor

1. The problem statement, all variables and given/known data
Prove that any well-ordered subset (under the natural order) of the real numbers is countable.


2. Relevant equations
None.


3. The attempt at a solution
My attempt thus far has been to prove by contradiction. I didn't see a very clear way to get from well-ordered subset to countable so I decided to assume that I have a set A which is uncountable. The best I've been able to come up with is this:

Since the set is uncountable and contained in R, it must contain at least one irrational number, and in fact, uncountably many irrationals. I recall another result, that is that the real line can only be covered by countably many disjoint intervals, meaning that at least one of these intervals contains uncountably many elements from my set A. Now, my intuition tells me that there is a way to essentially "shrink" this interval down to a very tiny neighborhood so that I can find my subset of A that is not well-ordered by the natural order as it behaves something like (0,1) or the like. I'm not sure how well this idea works, if at all, and was wondering if anyone thinks this idea is at all in the right direction or if there's another way to view the problem that might work better.

Dick

That's pretty vague. You are just making the interval smaller. That's not making it easier to solve. Think about this. Let the uncountable set be S. For every x in S there is a unique successor (the smallest element of S greater than x), unless, of course, x is the largest element of S. Call the successor s(x). Try thinking about that for a while.

Hurkyl

Sure. But then he can do it again.... I expect this line of reasoning can be made into a perfectly good argument, but I don't see the detail yet.

The main obstacle to it, I think, is that there can be infinite increasing sequences in the set, which have limits.

factor

Dick, all I can get from that right off the bat is perhaps a contradiction with the fact that S is uncountable. Because if S is well ordered, it certainly has a smallest element a. So now I pick the immediate successor to a, s(a). As a result any subset of S, which does not include a, has s(a) as its least element. Now I do it again for s(a) taking s(s(a)) and have the same line of logic. But then that is a countable sequence of numbers in S which accounts for all of S somehow.


Then again, this argument doesn't seem to account for the reason why this is peculiar to only the natural order on R, so I'm still way off I assume.

Dick

The problem is proving that your countable set of successors of a is ALL of S. It isn't necessarily. Think about the set of open intervals (x,s(x)) for all x in S. You'll have to deal somehow with a possible largest element. But it's not very important how you do that.

factor

Those intervals should have empty intersections with S by the definition of the function s(.).

But it seems like at least one of them should have a non-empty intersection by the uncountability of the set S.

Dick

I'm not sure how uncountability proves that. The hint I'm trying to give you is that if you have a collection of disjoint intervals in R, then that collection is countable. Can you prove that? Can you show the collection (x,s(x)) is disjoint?

factor

The proof that they're disjoint seems simple enough.

Pick any x and y, where x =/= y, in S and then look at the intervals (x,s(x)) and (y,s(y)), and suppose the contrary. We can assume without loss of generality that x < y. Then there exists some a which belongs to both intervals. But since this is a singleton in two open sets on the real line, it must be the case that y is also in (x,s(x)). But y is in S and as a result y < s(x) which implies that s(x) is not the immediate successor to x as we defined it to be, a contradiction.

Dick

Sure, if they overlap and x<y, then y is in (x,s(x)). That looks good. Can you finish it now?

factor

This has to do with defining an equivalence relation on the set right? Defining two elements to be equivalent if and only if there is some open interval in your set that they share?

The relation partitions the points of the set into open intervals which must contain rational points by their density in R, which are certainly countable.

Dick

The idea is that you now have a 1-1 mapping from the points x in S to the disjoint open intervals (x,s(x)). Except for that pesky possible largest element. If you can show the intervals are countable that means S is countable, right? Show me that the collection of intervals must be countable. Hint: as you said, every interval contains a rational point.

factor

Well if they all contain rational points, then by the fact that they're all disjoint we can choose one from each (by the axiom of choice) and this rational uniquely identifies the set because it's only in that single set. So this list of points in S is at worst countably infinite.

Dick

That's it. BTW you can also prove any set of disjoint open intervals in R is countable without using the axiom of choice by using a measure argument. But that's fine with me.