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