[FOM] A proof of Friedman's theorem
Ali Enayat
enayat at american.edu
Mon Feb 14 20:44:13 EST 2005
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).
More information about the FOM
mailing list