Exactly which parts of mathematics would have to be discarded if we threw out the axiom of choice?

In article <401@phoenix.PRINCETON.EDU>, mjlarsen@phoenix.PRINCETON.EDU
(Michael J. Larsen) writes:
>       I am interested in compiling a list of counter-intuitive
> theorems.  What are your favorites?  Why do you think they are
> counter-intuitive?

My favorite counter-intuitive theorem is due to Banach and Tarski
(based on an earlier result of Hausdorff):

The unit ball in the 3-dimensional space can be "cut" into finitely
many pieces, which can then be rotated and moved (and perhaps
reflected, I am not sure if that is necessary) and put together to
form _two_ disjoint unit balls.  (Of course, the "cutting" is highly
irregular; the construction relies on the axiom of choice.)

See Banach and Tarski, Fundamenta Mathematicae 6 (1924), 244-277.

The theorem is counter-intuitive because our intuition about cutting
and putting together 3-dimensional bodies is based on cuts that are
smooth in some sense (not necessarily differentiable, but not too
wild), and the unit ball cannot be made into two by means of such cuts.

-- Jan Pachl, University of Waterloo, Canada

I've found "Zermelo's Axiom of Choice" by Gregory Moore to be an
excellent introduction to what AC means to mathematics, what the
controversies have been, etc.  It's a good read: it requires a
reasonably high level of mathematical literacy to follow, but is more a
history than anything else.  There are more standard mathematical
texts, e.g., Rubin and Rubin "Equivalents of the Axiom of Choice," and
Jech "The Axiom of Choice".

Here are some theorems of classical mathematics (outside of set theory)
that you lose if you throw out AC:

Equivalent to AC:

1)  Every vector space has a basis.
2)  The Tychonoff Product Theorem (Every product of compact topological
    spaces is compact).
3)  Every filter on a topological space can be extended to an
    ultrafilter.

Weaker than AC, but not theorems of ZF:

4)  The compactness theorem for first-order logic.
5)  Every field has an algebraic closure.
6)  There is no translation invariant, countably additive measure on
    the reals.
7)  The Hahn-Banach Theorem.
8)  The reals are not a countable union of countable sets(!).

There are a number of set-theoretic principles that are equivalent to
AC which are routinely used in mathematics, e.g.,

9)  If A and B are nonempty sets, then there is either a 1-1 function
    from A into B, or a 1-1 function from B into A.
10) Every set can be well-ordered.
11) Every set can be placed into a 1-1 correspondence with a cardinal.

There are, of course, many other consequences, these are merely some
favorites.

The controversy surrounding AC at the turn of the century was based in
large part on the worry that AC was inconsistent with ZF set theory.
Mathematical logicians had been burned by poorly motivated attempts to
formalize set theory, and were understandably loathe to admit a
powerful principle such as AC.

Early set theories accepted as axioms a number of principles that "were
obviously true," without any clear idea as to what the overall
structure of sets "looked like."  This approach is extremely dangerous,
and in retrospect it is not surprisingly that Frege's axiom of
comprehension (any definable collection of objects is a set) fell
victim to Russell's paradox.

Zermelo followed a different strategy: he described a specific abstract
structure (the cumulative hierarchy of sets), and selected as axioms
the most important properties of that structure.  [Note that there are
alternative "designs" for set-theory, cf., Aczel's CSLI notes
"Non-well-founded sets" in which the axiom of foundation is false, and
there are perfectly well-behaved sets that are members of themselves.]
Zermelo's contribution was to bring common-sense to the foundation of
set-theory: have some idea as to what you're talking about before you
start talking about it.

AC *was* controversial because Zermelo couldn't provide a compelling
argument as to why AC should be true in the cumulative hierarchy; nor
could his contemporaries give a compelling argument as to why it should
be false.

Now, of course, we know a lot more about AC than was known at the turn
of the century: it is consistent with, but not a consequence of, the
other axioms of set theory.  Thus, the logical status of AC vis a vis
ZF is equivalent to the parallel postulate vis a vis the other axioms
of plane geometry.  We know that in at least one formal version of the
cumulative hierarchy (Godel's constructable universe, L), AC is *true*.

The foundational studies of mathematical logic have clarified that
there a number of plausible, albeit incompatible, choices for set
theory.  Mathematical logic can produce relative consistency results,
so we know that ZF is consistent if and only if ZFC and ZF + not AC are
consistent (indeed, there are a large number of relative consistency
results and independence results, cf.  Kunen's "Set Theory").
Mathematical logic cannot, having proven that two theories are
equiconsistant, argue that one is "right" and the other "wrong".

So, what's a mathematician to do?

It seems to me that unless there is an external criteria for rejecting
one model in favor of another, we should work *consistently* in what
ever theory is most comfortable to us.

Some mathematicians are interested in preserving the "computational"
nature of mid-19th century mathematics.  They have an external criteria
for rejecting ZF in favor of more constructive foundations.

Most mathematicians like to use nonconstructive techniques (notice that
AC is *not* synonymous with nonconstructive, in fact, AC is trivially
true in most presentations of constructive mathematics), and so prefer
a foundations that supports nonconstructive reasoning, specifically ZF.

Since mathematicians tend to use AC instinctively (e.g., in the proof
that R is not a countable union of countable sets -- can *you* figure
out where you're using AC), trying to do mathematics that does not
depend on AC isn't much fun: you have to be *extremely* careful in
dealing with any infinite set.  You need to be paranoid about extremely
inoffensive arguments; and even that isn't always enough.

I very much doubt that there will ever be a external good reason for a
mainstream nonconstructive mathematician to reject AC.  It is not as
though we expect to be able to perform a physical experiment that
enables us to conclusively accept or reject AC as a property of our
universe -- as we can pretty conclusively reject Euclidean geometry as
being *the* geometry of space-time.

So, AC is the game we naturally tend to play.  We know that if the
other rules we've agreed to play by are consistent, adding AC to the
mix won't introduce a new inconsistency.  Why fight our own nature?
Accept AC.

-- Stuart A. Kurtz <stuart@tartarus.uchicago.edu> (signed "Stu")

[ Editor: Kurtz corrected item 3 himself below: the ultrafilter theorem
is equivalent to the prime ideal theorem, not to AC. ]

In article <10838@phoenix.Princeton.EDU> tycchow@phoenix.Princeton.EDU
(Timothy Yi-chung Chow) writes:
>   Exactly which parts of mathematics would have to be discarded if we
>   threw out the axiom of choice?

We wouldn't have to discard whole parts of mathematics, but central
parts of e.g. analysis and algebra would have to look very different
without the axiom of choice (not to mention logic and set theory).  For
example, if we take Royden's "Real Analysis" and look for (essential)
applications of the Axiom of Choice, what do we find?  Well, there's
Tychonoff's theorem (a product of compact spaces is compact), described
by Royden as "probably the most important theorem in general topology",
which is in fact equivalent to the Axiom of Choice.  There's the
Hahn-Banach theorem, a cornerstone of functional analysis.  There are
theorems that need weaker versions of the axiom, such as the classical
result that R is sequentially compact.  Also, we have interesting
counterexamples, such as non-measurable subsets of R (in this case it
has been proved by Solovay that the (weaker) countable axiom of choice
is compatible with all subsets of R being measurable).  And no doubt
there are several other essential uses of the axiom in Royden's book.

I don't know of any systematic exposition of where and how the Axiom of
Choice is used in current mathematics, but no doubt there is some such
exposition.  Although many mathematicians apparently feel somewhat
uncomfortable with the Axiom of Choice from a philosophical point of
view, there is no proposed mathematical reform turning on just the
rejection of this axiom.  In constructive mathematics, in particular,
the axiom of choice in the form of the principle

          for all x there is a y such that p(x,y) ==>
             there is a function f such that for all x, p(x,f(x))

is just as valid as in classical mathematics, because of the
constructive interpretation of the quantifiers.  Of course the
classical theorems mentioned above fail constructively either on
logical grounds or because the concepts used in formulating the
theorems don't make any obvious constructive sense.  Thus a wholesale
reconstruction of analysis such as Bishop's or Brouwer's (very
different!) doesn't at all center on uses of the Axiom of Choice.

[ Editor: unsigned in the collected copy. ]

tycchow@phoenix.Princeton.EDU () wrote:
> Exactly which parts of mathematics would have to be discarded if we
> threw out the axiom of choice?

Jech's "The Axiom of Choice" has a chapter on this; for a lot more
detail, see Rubin & Rubin, "Equivalents of the Axiom of Choice", volume
2.  The biggie is Tikhonov's theorem; the weirdest stuff is in infinite
cardinal arithmetic.

Most of us computer science types could live without AC if we were
allowed to keep the Prime Ideal Theorem (a weaker form of it); but
throwing out the compactness theorem and its relatives (equivalent to
PIT) would *hurt*.  It'd clobber nonstandard analysis, too.

-- Jack Campin <jack@cs.glasgow.ac.uk>, Computing Science Department,
   Glasgow University

[ Editor: the exchange on the history of the axiom follows. ]

In article <5814@tank.uchicago.edu> stuart@tartarus.uchicago.edu
(Stuart A. Kurtz) writes:
>   The controversy surrounding AC at the turn of the century was based
>   in large part on the worry that AC was inconsistent with ZF set
>   theory.  [...]
>   Zermelo followed a different strategy: he described a specific
>   abstract structure (the cumulative hierarchy of sets), and selected
>   as axioms the most important properties of that structure.

Some historical nitpicking.  The controversy at the turn of the century
concerning the axiom of choice didn't have anything to do with the
question of its consistency with ZF set theory.  Indeed ZF didn't exist
at the time.  Also, what "poorly motivated attempts to formalize set
theory" had been made?  Frege's theory certainly wasn't "a set theory".
Also, if you read Zermelo's article of 1908, you'll find that his
approach was strictly pragmatic: he formulated axioms sufficient for
the derivation of (then current) set theory.  It was only in his 1930
article (after the replacement axioms had been first introduced by
Skolem) that the cumulative hierarchy of sets appeared.

[ Editor: unsigned in the collected copy; Kurtz's reply below
attributes it to Torkel Franzen ("TF"). ]

I've had a few replies to my earlier article on the axiom of choice.

Herman Rubin points out that the ultrafilter theorem is equivalent to
the prime ideal theorem, and not AC.  He's right, of course.  Mea
culpa.

Torkel Franzen questioned my history.  [ Editor: Kurtz quoted his own
paragraphs and Franzen's reply, both given above. ]

I'd like to respond to TF.  It is somewhat inconvenient to reply to the
points he raises in his order--be forewarned that I'll jump around a
bit.  I'll use van Heijenoort's numberings, so [1908] is the
well-ordering paper, and [1908b] is the foundations of set-theory
paper.

TF is right, Zermelo (let alone ZF) set theory didn't exist until 1908,
so my comment on the "turn of the century" is anachronistic.
Nevertheless, I *did* mean ZF set theory (well, Zermelo set theory,
anyway).  What I should have said was "The controversy surrounding AC
*early in this century* ..."

It is my perception that the controversy surrounding AC begins with
Hilbert's reaction to Zermelo [1908].  Of course, there were objections
before, but the well-ordering theorem crystalized the opposition, and
gave them an eloquent and influential voice in Hilbert.

In my original article, I claimed that Zermelo

        ... described a specific abstract structure (the cumulative
        hierarchy of sets), and selected as axioms the most important
        properties of that structure.

TF points out that this is incorrect: Zermelo did not describe the
cumulative hierarchy in [1908b].  Nevertheless, I believe that Zermelo
*did* base [1908b] on (some form of) this hierarchy, whether or not he
went public with it at that time.  In particular, I disagree with TF's
assessment that Zermelo's approach was "strictly pragmatic".  I have
three pieces of evidence: (1) Zermelo alludes to "the origin of these
principles" in the introduction, albeit in a somewhat ambiguous
context; (2) there is the form of the axioms themselves; and (3) there
is a brief passage in Zermelo's discussion of the axiom of separation
that is highly suggestive of a hierarchy.

(1) Zermelo [1908b]:

        ... The further, more philosophical, question about the origin
        of these principles and the extent to which they are valid will
        not be discussed here.

As I read this passage, it certain suggests to me that there was an
"origin of these principles".

(2) The axioms themselves all have the form of either (a) positing that
certain primitive sets exist (specifically, the empty set and a
nonempty set closed under successor), and (b) claiming that certain
constructions of sets from already existing sets are valid.  This
certainly suggests a hierarchy (albeit a hierarchy of height omega, in
which the empty set, omega, and therefore all integers, constitute
level 0).  It is only with the axiom of replacement that one needs to
index the hierarchy with infinite ordinals.

(3) Zermelo's denial in the introduction notwithstanding, the following
passage occurs after his introduction of Axiom III [Separation] (taken
from van Heijenoort):

        By giving us a large measure of freedom in defining new sets,
        Axiom III in a sense furnishes a substitute for the general
        definition of set that was cited in the introduction and
        rejected as untenable.  It differs from that definition in that
        it contains the following restrictions.  In the first place,
        sets may never be *independently defined* by means of this
        axiom but must be *separated* as subsets from sets already
        given.

The "general definition of a set" is, of course, Frege's axiom of
comprehension.  The italics in the quote are Zermelo's.  This
discussion looks to me as though it is based on the cumulative
hierarchy.  Indeed, I am at a loss to account for the phrase "separated
as subsets from sets already given" on the basis of pragmatic origin
position.

TF also criticizes my characterization of Frege's theory as "a set
theory".  Frege (and Peano) set out to formalize arithmetic, as opposed
to set theory.  Nevertheless, they did include the notion of higher
classes within their formal systems, and so (in anachronistic
terminology) are set-theories with natural-number urelements.
Russell's paradox is, after all, depends on the set-theoretic part of
the Peano/Frege system.

I'd like to thank Herman Rubin and Torkel Franzen for their corrections
and clarifications.

-- Stuart A. Kurtz (signed "Stu")

In article <5840@tank.uchicago.edu> stuart@tartarus.uchicago.edu
(Stuart A. Kurtz) writes:
>It is my perception that the controversy surrounding AC begins with
>Hilbert's reaction to Zermelo [1908].  Of course, there were
>objections before, but the well-ordering theorem crystalized the
>opposition

But Zermelo's first proof of the well-ordering theorem was in 1904.  In
his 1908 article giving the second proof he deals at length with
objections to the earlier proof, including objections to the Axiom of
Choice.  Even after 1908, I believe it's hard to find mathematicians
who expressed their objections to the axiom in terms of its doubtful
consistency with ZF or Z.

>Nevertheless, I believe that Zermelo
>*did* base [1908b] on (some form of) this hierarchy, whether or not he
>went public with it at that time.  In particular, I disagree with TF's
>assessment that Zermelo's approach was "strictly pragmatic".

Well, I think it's rather too easy for us with hindsight to read
between the lines in Zermelo's article.  Anyway, the confident,
profound, and, I think, unsurpassed presentation of the cumulative
hierarchy in his 1930 article is in marked contrast to the presentation
in 1908.

>TF also criticizes my characterization of Frege's theory as "a set
>theory".  Frege (and Peano) set out to formalize arithmetic, as
>opposed to set theory.  Nevertheless, they did include the notion of
>higher classes within their formal systems, and so (in anachronistic
>terminology) are set-theories with natural-number urelements.

What I had in mind was rather that Frege's logical system was not based
on the notion of set, but on his own rather difficult notion of
function.  He didn't much appreciate Cantor's work.

[ Editor: unsigned in the collected copy; it answers Kurtz's reply to
TF and speaks as TF. ]

In article <26984@cup.portal.com> Kevin_P_McCarty@cup.portal.com
writes:
>Are there any applications of logic and set theory which make use of
>an Axiom of Anti-Choice?  "Useful in applied logic" as illustrated
>for example by the applications Aczel and Barwise have found for
>Anti-Foundation Axioms?

There has been substantial work done on the axiom of determinacy (AD),
a strong axiom which contradicts the axiom of choice.  Also, there is a
body of research on infinite exponent partition relations (which again
imply the negation of the axiom of choice).  These two areas are
closely related.

-- Mitchell Spector <spector%sumax.uucp@beaver.cs.washington.edu>,
   Dept. of Computer Science and Software Engineering, Seattle
   University

[ Editor: see also logic/axiom.of.determinacy and
analysis/well.ordering. ]