[FOM] A proof of Friedman's theorem

[Ali Enayat]

This is a reply to Saeed Salehi [Mon Feb 14 08:50:44 EST 2005], who has 
reiterated a question of Shipman by asking:

>The main question proposed earlier by
>Shipman still remains unanswered to me:
>Where [is] the proof of Friedman's theorem [that a linearly ordered set is
>isomorphic to the real ordering iff it is unbounded below and above, has
>the least upper bound property and for which there exists a continuous
>middle-value function] has been published/appeared?

I suspect that Friedman's theorem is unpublished since he gave no reference 
in his original posting. Below I have outlined a proof that I came up with. 
I would be curious to know if it is the same as Friedman's. I was surprised 
about having to employ infinitary combinatorics (Fodor's lemma, in 
particular) for the proof, and I am therefore curious about the 
metamathematics of the theorem vis-a-vis reverse mathematics.

Theorem (H. Friedman). Suppose L is a dense linear order without end points 
with the lub property and which supports a continuous "betweeness function" 
F. Then F is order isomorphic to the real line.

Proof: It suffices to verify that L has a countable dense subset. Towards 
this goal, we first prove a key lemma:

Lemma: cf(L)and cf*(L) are both equal to aleph_0.

Here cf(L) is the smallest ordinal theta such that there is a subset S of L 
that is unbounded above in L, and is of order type theta.
cf*(L) is defined similarly, and is the smallest ordinal kappa such that 
there is a subset T of L that is unbounded below in L and is of order type 
kappa.
It is well-known that cf(L) and cf*(L) are always cardinals.

To see that cf(L) is aleph_0 we argue by contradiction: suppose cf(L) is at 
least aleph_1.
Using this assumption, and the fact that L has the lub property, we can 
construct a *continuous* increasing chain of elements {m_alpha: 
alpha<omega_1) := M.

The function F(m_0, x) := g(x) is clearly a continuous function. By Fodor's 
pressing down lemma, and the continuity of f,  there must exist a c.u.b. 
(closed unbounded subset) C_0 of M such that g(x) is below some b_0 in M, 
for all x in C_0.

Similarly, by looking at the function F(b_0, x) := h(x) ,  there is a c.u.b. 
C_1 of M such that h(x) is below some b_1 in M, for all x in C_1.

Continue this process "omega times" to obtain the countable sequence {b_n: n 
in omega} of members of M, and a countable sequence of c.u.b.'s {C_n: n in 
omega} of M such that:

(*) For all n in omega, F(b_n, x) < b_(n+1) for all x in C_n.

Note that the seqence b_n is strictly increasing and that if s := lub{b_n: n 
in omega}, then s = lim{b_n: n in omega}.

Let C be the intersection of the C_n's (n in omega). It is easy to see that 
C is also a c.u.b. [this is classical].

Let c be in C with s<c. On one hand s< F(s,c). On the other hand, by the 
continuity of F,

F(s,c) = lim {F(b_n, c): n in omega}. But by (*), F(b_n, c)< s for all n. 
Therefore F(s,c)<= s.

This contradiction shows that cf(L) is aleph_0. A similar reasoning 
establishes cf*(L) is aleph_0.

QED (Lemma)

By the lemma, there is a countable subset M of L that is unbounded below and 
above. Let D be the closure of M under the function F. Clearly D is also 
countable.

Claim. D is dense in L.

Proof of Claim: Suppose (a,b) is open interval L, and that on the contrary, 
(a,b) and D are disjoint. Using the lub property, we can extend (a,b) to 
(a*, b*) such that (a*, b*) is the maximal open interval containing (a,b) 
that is disjoint from D. Here we are using the fact that there are members d 
and d' of D such that d<a<b<d' to ensure that a* and b* are well-defined.

Case I: If a* and b* are both in D, then F(a*,b*) is in D by closure of D 
under F. This contradicts the disjointness of (a*, b*) and D.

Case II: If neither a* nor b* is in D, then there are points of D 
arbitrarily close to a* and to its left, and similarly, there are points of 
D arbitrarily close to b* and to its right.

Therefore, by continuity of F, F(a*,b*)  is a limit point of the set S: = 
{F(x,y): x <a* and x in D, y >b* and y in D}. But S is a subset of the 
closed set (-infinity,a*] union [b*,infinity) by the assumption of 
disjointness of D and (a*,b*). Therefore F(a*,b*) is not between a* and b*, 
contradiction again.

Case III: If only one of {a*,b*} is in D, then the argument is similar to 
that of Case II above.

QED (Theorem).