From: hook@nas.nasa.gov (Ed Hook) Subject: Re: Axiom of Choice Date: 7 Jul 2000 20:55:07 GMT Newsgroups: sci.math Summary: [missing] In article <2qep4k5sgf7f@forum.mathforum.com>, cs93@cornell.edu (Chan-Ho Suh) writes: |> Jim Heckman wrote: |> |> " I'm sure I've read that it's possible to prove that R is uncountable |> using only its order properties, as opposed to the way it's usually |> done using its algebraic properties, via infinite binary series, etc." |> Yes, I've seen a proof on R's uncountability relying only on its |> properties as a linear continuum. The general theorem says: An |> infinite compact Haussdorf space with every pt. a limit pt. is |> uncountable. I think. More generally, if X is a complete metric space and P is a nonempty perfect subset of X, then P is uncountable. |> Then you show an interval in R, i.e [0,1](in the order topology) to be |> such a space. |> The proof (as I recall) is in Munkres--Topology: A first course, if |> you're interested. To prove the above theorem, you can construct an injection of the sequence space 2^|N into P -- since the usual Cantor set is uncountable, that proves it. (Of course, the original poster might want to object at this point, since the proof that the Cantor set is uncountable probably uses that 2^\aleph_0 = c in some way ... ) The "construction" depends on two results: (1) if p is a limit point of A \subseteq X, where X is a Hausdorff space, then every neighborhood of p contains infinitely many points of A (2) If { A_n }_{n > 0} is a nested sequence of nonempty closed sets in the complete metric space X with the property that diam(A_n) --> 0 as n --> \infinity, then \bigcap_{n > 0} A_n is a singleton. Then P is infinite (by (1)), so you can pick distinct points p_0, p_1 in P. Let eps_1 = min(1/2, d(p_0,p_1)/3) and define P(i) = { x \in P | d(x,p_i) <= eps_1 } for i=0, 1. Then P(0), P(1) are disjoint closed sets with diameter <= 1 ... and each contains infinitely many points. Now you proceed inductively -- if you've managed to define pairwise-disjoint closed sets P(a_1,a_2,...,a_n) with diameter <= 1/n for every n-tuple of 0,s and 1's with each set containing infinitely many points of P, just imitate the above procedure "inside" each of these sets. That is, given P(a_1,a_2,...,a_n), pick distinct points p_{a_1,...,a_n,0} and p_{a_1,...,a_n,1} in there (different from any points that may have been chosen at an earlier stage -- probably unnecessary) and define P(a_1,a_2,...,a_n,i) for i=0, 1 to be the closed set { x \in P(a_1,...,a_n) | d(x,p_{a_1,...,a_n,i}) <= eps } where eps is chosen to guarantee that these two closed sets are disjoint and have diameter <= 1/(n+1). This shows that the construction can be carried out for sequences of length n+1 if it can be done for sequences of length n and completes the induction. Having constructed all of these sets, it's then pretty clear what to do next. Given (a_1, a_2, ... ) in 2^|N, the intersection P(a_1) \cap P(a_1,a_2) \cap P(a_1,a_2,a_3) ... is a singleton, say { f(a_1,a_2, ...) }. This defines (you can check this) a function f: 2^|N --> P which is clearly one-to-one ... |> The proof, to me, is very interesting because it uses a different |> approach than the now old diagonalization argument. Check carefully, though -- as I noted up above, it may well _still_ be using the "now old diagonalization argument" ... After all, in order to prove that some set is uncountable, you have to be able to recognize an uncountable set. Most people (specifically excluding the local cranks) first acquire that skill by exposure to Cantor's diagonal argument -- I'm not sure there's any other way to easily produce a set *known* to be uncountable ... (I'm sure that last claim is sufficiently provocative that someone who actually knows what he's talking about will chime in -- lookin' forward to it ...) -- Ed Hook | Copula eam, se non posit Computer Sciences Corporation | acceptera jocularum. NAS, NASA Ames Research Center | All opinions herein expressed are Internet: hook@nas.nasa.gov | mine alone