Re: Countably infinite Hausdorff topology?

From: shedar (no_one_at_nonesuch.com)
Date: 09/17/04 

Date: Fri, 17 Sep 2004 12:04:04 GMT

"David C. Ullrich" <ullrich@math.okstate.edu> wrote in message
news:ir9gk0p7vvkua3budg8ems9n17ch4tqtg6@4ax.com...
> On Tue, 14 Sep 2004 14:04:39 GMT, "shedar" <nobody@nonesuch.com>
> wrote:
>
> >"Robert Israel" <israel@math.ubc.ca> wrote in message
> >news:ci50j1$hsf$1@nntp.itservices.ubc.ca...
> >> In article <fkl1d.6375$G03.1882402@news4.srv.hcvlny.cv.net>,
> >> Stephen J. Herschkorn <herschko@rutcor.rutgers.edu> wrote:
> >> >A standard exercise is to show that any infinite sigma-field has
> >> >cardinality at least 2^omega. That got me thinking about topologies.
> >>
> >> >Does there exist a Hausdorff space whose topology is countably
infinite?
> >>
> >> Suppose X is a Hausdorff space with an infinite topology. In
particular,
> >> X is infinite. Then, with at most one exception, each point of X has
> >> a neighbourhood whose complement is infinite (i.e. if there were
> >> two points x and y whose neighbourhoods all had finite complements,
they
> >> could not have disjoint neighbourhoods, violating the Hausdorff
> >> requirement). So let x_1 be a point of X with an open neighbourhood
U_1
> >> whose complement is infinite. Now X \ U_1 is also an infinite
Hausdorff
> >> space, and the same reasoning applies to it: there is x_2 in X \ U_1
> >> with an open neighbourhood U_2 such that X \ U_1 \ U_2 is infinite.
> >> Moreover, again using the Hausdorff property we may assume that x_1
> >> is not in U_2. Using induction
> >
> >[See comment (*) by Shedar below.]
> >
> >> we get sequences of points x_j of X
> >> and open sets U_j such that x_i is in U_j iff i = j. Then for any
> >> subset S of N, U_S = union {U_j: j in S} is an open set which contains
> >> x_i iff i is in S. These constitute a family of distinct open
> >> sets of cardinality c.
> >>
> >
> >Comment (*): Correct me if I wrong, but I think "induction" (or
technically,
> >recursion on the least limit ordinal)
>
> I don't think "or, technically" is quite right here - there's nothing
> imprecise or informal about just saying "by induction"; induction
> on the natural numbers is a perfectly respectable thing.
>
> >would not "cut it". I think one needs
> >to invoke AC (or at least the axiom of countable choice) to get the
> >sequences mentioned above.
>
> Seems to me that you may well be right that some sort of AC is
> required for the argument as stated. Seems like a slightly
> silly thing to point out, because people use AC without
> mentioning it this way all the time.
>
> Seems particularly silly in this case because it's trivial
> to convert the argument into one that does not use AC
> (at the expense of converting it into a proof by contradiction):
> Assume the topology is countable and fix an enumeration of
> the open sets. Now each time we need to choose an open
> set with a certain property choose the one with that
> property that comes first in the enumeration.
>
> ("Or technically", use the fact that the first infinite
> ordinal is well-ordered...)
>

1. On the Use of AC:

I agree that by re-casting the previous exposition in some form of Reductio
Ad Absurdum (RAA), one may be able to get away from the need to use AC. It's
just that I feel whenever AC is invoked, it should be explicitly mentioned,
regardless of whether it is being used in its "most intuitive" form (e.g.,
Russell's MP), or in any of its other forms--it's only fair. After all, it
is not customary to use ZL or WO without directly alerting the reader so. I
ask the same for Russell's MP as well.

     <Joke on the "equality of choices">
     Motto: All animals are equal but some are more equal than others.
(Orwell)
     Thus, we rank the animals as follows:
     1. ZL [perfectly fine with explicit mentioning]
     2. WO [Wow, it's awesome (secretly, crazy), but it's OK if I mention
it.]
     3. <add your own favorite version here and increase the numbering by 1>
     ...
     n. MP,AC (but, of course; no explicit mentioning is needed)
     </Joke>

Yet, there is another more subtle point. If one does not use AC, one will be
forced to face with the ugly details of "transfinite recursion". See point
#2 below.

2. On the Application of the Transfinite Recursion Theorem (specialized to
"omega" in this case):

(a) "Definition by induction" or "definition by recursion":

OK, it's just a name. I understand that many mathematicians have been
trained (and continue to be trained) to call this mode of defining a
function "definition by induction". Indeed, J.L. Kelly calls it so in the
"set theory" appendix to his General Topology (1955 Springer, pp.270-271).
Paul Halmos also calls this application of recursion "definition by
transfinite induction" in his Naive Set Theory (1974 Springer, p.71). While
Kelly did not explicitly label his Thm 128 with the moniker "Transfinite
Recursion", Halmos labels his version clearly so. Nevertheless, both authors
clearly state that "definition by induction" is really an application of the
Transfinite Recursion Theorem. (For a precise statement of this Theorem in
ZF, see, for example, pp25-27 of Kunen's Set Theory: An Introduction to
Independence Proofs, Elsevier 1980).

(b) Transfinite Recursion or AC "to-the-rescue":

It is then clear that when mathematicians define a function "by induction",
they are TECHNICALLY appealing to the Recursion Theorem (the proof of which,
incidentally, requires transfinite induction). Regardless of whether one
call it "by induction" or "by recursion", this begs the following question:

     When defining a function "by indcution", am I appealing to the
     Recursion Theorem (and hence, it would be more accurate to
     call it "defining a function by recursion"), or am I simply just
     waving my hands here because I don't really want to be bothered
     with the details of the recursion theorem?

In fact, the following 1997 message by Walter Felscher I found on
"math-history-list" seems to be saying that part of the history of the
various formulation of AC appears to be motivated by the desire to get away
from the ugly details of transfinite recursion:

http://mathforum.org/epigone/math-history-list/jeldclehzun/Pine.HPP.3.91.971204161212.10171A-100000@commlink.zdv.uni-tuebingen.de

A small paragraph of it is quoted below.
quote
     Up to this day, most mathematicians teaching topics from
     analysis or algebra (1) talk about sets and their
     formation (2) mention Zorn's lemma should they need to use
     it, but (3) assume in perfect naivity that recursively
     defined functions exist without requiring a proof of that
     fact. This should illustrate the difficulties arising
     when it came to understand the even more general
     principle of transfinite recursion.
unquote

3. On the equivalence of the Recursion Theorem and some form of "choice":

[I will use the following notation. CC: axiom of countable choice, DC: axiom
of dependent choice]

According to p.147 in Discovering Modern Set Theory I by Just and Weese
(1996 American Mathematical Society), the Recursion Theorem is not derivable
from (ZF + "CC"). In fact, under ZF, the Recursion Theorem is equivalent to
DC.

4. Final Thoughts: AC/DC?

Given the available choices for getting to my function, should one appeal to
AC (expedient) or to transfinite recursion (with all its "glorious" details
and still be bound to DC)? I think I personally will vote for expediency.
What do you think?

   Shedar

Relevant Pages

  • Re: Which axiom prohibits this kind of construction?
    ... one that pertains to an operation symbol across all sets. ... some a form of recursion other than the most ordinary recursion on w. ... That said, if I understand, you're defining a function S on w by ... That does suggest transfinite recursion, ...
    (sci.math)
  • Re: A recursion axiom for N?
    ... needs a stronger version of induction to do so." ... it, "It's valid using some basic axioms of set theory, or some basic ... recursion is defined in this system, ...
    (sci.math)
  • Re: Question about extensions of PA
    ... > Nothing but a trivial application of the recursion theorem is needed. ... What guarantees that the resulting fixed point is consistent? ... arithmetical sentences, i.e. the inconsistent theory, as follows from ...
    (sci.logic)
  • Re: The modern mathematical concept of infinity is indefensible
    ... Not what I think of as the recursion theorem, ... since mr. de Bruijn seems to have chosen not to answer this or any other of mny objections. ...
    (sci.math)
  • Re: A recursion axiom for N?
    ... Defining functions by induction, also called recursion. ... it, "It's valid using some basic axioms of set theory, or some basic ...
    (sci.math)