An uncountable well-ordered subset of the hyperreals

[AKG]

I have to prove that there exists an uncountable well-ordered subset of the hyperreals. Some definitions:

An ultrafilter on N is called free if it contains no singleton. We may suppose that some such free ultrafilter on N, U, exists. ^NR is the set of functions from the naturals to the reals, or equivalently, the set of real-valued (denumerable) sequences. We define an equivalence relation on these functions by saying f ~ g iff {i : f(i) = g(i)} is in U. The hyperreals are then defined to be ^NR/~ and are denoted *R. The equivalence class of a function f is denoted [f]. We define a total order (i.e. a linear order) < on the hyperreals by saying [f] < [g] iff {i : f(i) < g(i)} is in U. One can check that this is indeed a well-defined total order. There is a natural embedding of the reals into the hyperreals: let x be a real, and f_x be the function with constant value x, then $x \mapsto [f_x]$ is our natural embedding. We will often use x to denote [f_x].

How do I show that these hyperreals have an uncountable well-ordered subset. I've tried a few things. First, I thought of using Cantor Normal Form. In particular, I know that every ordinal can be expressed as a "polynomial" in w (w is the denumerable cardinal which is the set of naturals (including 0)) where the coefficients are non-negative integers and the exponents are arbitrary ordinals. I thought that the first uncountable cardinal might only contain elements whose Cantor Normal Form was a polynomial in w where the exponents were finite. Then for each ordinal in the first uncountable, there is a polynomial p and so my well-ordered set would consist of sequences of the form (p(1), p(2), p(3), ...). This would be well-ordered, except the elements of the first uncountable are not polynomials in w with finite exponents, i.e. the first uncountable (I'll just call it W for brevity) contains things like w^w.

I tried an indirect proof, assuming all well-ordered subsets of the hyperreals were countable and then deriving a contradiction. I wasn't successful with this. I naively thought I might be able to use Zorn's lemma to derive a contradiction, first proving that the set of all well-ordered subsets of the hyperreals has no maximal element (which is easy to prove) and then hoping to prove that every totally ordered subset thereof has a maximal element (which unfortunately can't be proved, in fact, it is easy to prove false).

I tried taking some infinitessimal e, and considering the set {r + ne: r in R, n in N} but this is easily seen to have problems because it contains the set {1, 1/2, 1/3, 1/4, ...} which has no least element. Although this approach wasn't close to working (it was the first thing I tried) I intially did it because it guaranteed me that I'd have an uncountable set, only later did I realize that it was not well-ordered.

Sticking with first trying to find an uncountable set, then making something well-ordered of it, I looked at the infinite strings of 1's and 0's. Then to each string (x_i), I associated the hyperreal:

[(2^x₀, 2^x₁3^x₀, 2^x₂3^x₁5^x₀, ...)]

I thought this might work better because I had the rough idea that it would give big differences between different elements, whereas in the previous attempt we could pick two elements with arbitrarily small differences. However, the subset of these elements associated to the set {011111..., 0011111..., 00011111111..., 0000111111..., 0000011111..., ...} is the subset:

{[(1,2,6,30,...)], [(1,1,2,6,30,...)], [(1,1,1,2,6,30,...)], [(1,1,1,1,2,6,30,...)], ...}

which has no least element (it's least element would be 1 - which, recall, is [(1,1,1,1,1,1,...)] - is not in the above set).

So I've tried a bunch of stuff, none of it worked. Any hints on how to prove this?

 

[Hurkyl]

I believe it suffices to show that any countable subset of *R has an upper bound.

Then, to show an uncountable well-ordered set exists, you can construct it, via transfinite induction. Well, I'm most adept at transfinite induction; some other AoC equivalent might work better for you.

To prove the lemma, you need to pick a representative of each element in your countable subset S. Then, construct a function f:N->R such that, for any finite collection of g's in S, f(n) <= g(n) finitely often..

You can accomplish that by picking a representative of each element in your set, and enumerating them in the sequence g_n. Then, f(n) := 1 + max{g_m(n) | m < n} should work.

 

[AKG]

I believe it suffices to show that any countable subset of *R has an upper bound.

Then, to show an uncountable well-ordered set exists, you can construct it, via transfinite induction.

Thanks, this was perfect!