[FOM] Another challenge to Pratt concrning AC

[Vaughan Pratt]

Arnon Avron wrote:
> Dear Vaughan,
> [...] I'll be interested how you
> would treat the following case.
> 
>   In all basic books on Set theory there is the theorem
> that every infinite set has a (proper) countable subset.
> The proof in all of them directly use AC (or some weaker version
> of it), even though usually this is not noted by the authors.
> Now for any specific infinite set I have encountered (and any
> such set which is of interest to our mathematicians in the street)
> one can easily show the existence of such a
> countable subset without using AC. Do you think that
> noting this last fact would suffice for the mathematicians in the street,
> and they would say here that foundationalists just make things 
> unnecesarily harder by insisting on formulating and proving
> the general theorem (that requires AC for its proof)?

Of course not.  But I wasn't the one making the point that people have 
been finding it hard to come up with examples of countable unions of 
countable sets that aren't countable unions of counted sets (though I 
was intrigued to learn of the difficulty).  My point was that 
practitioners tend to *focus* on the latter in this particular 
situation.  Presumably few if any do so when addressing whether the 
continuum can be well-ordered.

> And how
> would you reformulate the theorem (without trivializing it)
> so the use of AC will be avoided?

Since the very possibility of Choice being false seems to depend on 
defining mathematics so as to limit its propositions to finitary Boolean 
combinations of formulas, I would first ask the "street mathematician" 
whether they regarded the concept of set as necessarily tied to a 
particular formulation of mathematical language or whether sets had an 
existence of their own independent of language.  If they picked the 
former I would guess they'd previously given that question some thought, 
possibly in consultation with foundationalists or philosophers.

It seems to me that the naive answer (by those who haven't thought about 
it) ought to be that the mathematical existence of sets should not be 
tied to any particular formulation of language, especially one that 
involves a version of the concept of "Boolean algebra" entailing such a 
subtle notion of ultrafilter (in the sense of so many obscure ones). 
Why, the street mathematician might ask, shouldn't an idealist (as 
opposed to someone appealing to the finiteness of mathematicians as part 
of their reasoning) be allowed to form completely distributive arbitrary 
conjunctions and disjunctions when discussing infinite sets?

A foundationalist might answer this by saying that to do so would be to 
assume what was to be proved: complete distributivity builds in Choice.

But the free complete atomic Boolean algebra (CABA) on any set X of 
generators is a very simple thing, whose formulas are just the double 
power set 2^(2^X) under conjunctions and disjunctions of cardinality 
limited by that of X.  Why should anyone want to limit language in a 
complicated way based on an argument about mathematicians being finite 
when the complete ultrafilters of CABAs on X, namely X itself, are so 
simple by comparison with the ultrafilters on the countably generated 
free Boolean algebra?  Axioms should be simple, and the axiom (if you 
want to call it that) that allows complete distributivity of arbitrary 
conjunctions and disjunctions gives rise to a far simpler mathematical 
edifice than has been created by those foundationalists who insist that 
mathematics has to be limited by the finite limitations of mathematicians.

> Just to clarify: I do not like AC, and I remember 
> well  how suspicious I was of this particular 
> proof when I first learn it as a first year student
> in  our introductory course on set theory (only later 
> I came to know that what had bothered me was the use
> of AC in that proof - the lecturer of course has never mentioned AC).
> However, I do recognize that "mathematicians in the street"
> frequently use AC - sometimes without being aware that they do.

I fully sympathize.  You haven't been shown the "correct" proof of 
Choice, and therefore you have the right concern about it: why should it 
be true?

Like you I don't buy Choice as an axiom.  I do however accept it as a 
theorem.  For me the "correct" proof of choice is that, for *every* set 
X, the set of complete ultrafilters of the free CABA on X is (in a 
natural bijection with) X.  This is the profinite completion to the 
infinite case of what happens in the finite case.  The inductive 
completion, yielding Boolean algebras, creates a picture which is 
neither well motivated (other than by spurious arguments about people 
being finite) nor simple (many badly behaved ultrafilters).

The counterargument to *that* seems to be that by assuming otherwise one 
can populate mathematics with alternative axioms that contradict choice. 
  This seems like wanting to have one's cake and eat it too: on the one 
hand you object to Choice because you have an uneasy feeling about it, 
on the other you're willing to consider alternatives to 
Choice---shouldn't you feel at least as uneasy about those?

I have a strong objection to those alternatives: they entail giving up 
the very nice theorem that the ultrafilters on a free CABA are precisely 
its generators.  I don't see the point of complicating this simple 
scenario with the nonmathematical observation that mathematicians are 
only finite.  This seems like an axiom in itself: how do we know we're 
finite?  Granted you can create new theories that way, but how natural 
are those theories, and more significantly, what do they have to do with 
reality?  They are the complicated and subtle result of creating 
spurious ultrafilters by having those ultrafilters ignore infinite meets 
and joins.  Mathematically speaking those are ill-behaved ultrafilters.

A couple of years ago Hugh Woodin gave a talk at Stanford at the 
celebration of Paul Cohen's contributions where he seemed to be willing 
to take a small step in the direction I'm advocating by arguing the 
importance of sigma-algebras over Boolean algebras, in which one extends 
the latter's finite meets and joins to countable ones, as an improved 
approach to measuring the truth of the Continuum Hypothesis.  At the 
coffee break I asked him what the cardinality of the free countably 
generated sigma-algebra was.  He said he'd get back to me on that 
(anyone know the answer? I don't).  Since I knew the answer in the case 
of arbitrary meets and joins with matching distributivity, namely 
2^(2^X), I figured that if a world expert on this aspect of mathematical 
truth couldn't answer the corresponding question when he'd decided that 
countability instead of finiteness was the correct cardinality for 
mathematical truth, then he was playing by the opposite of the rules I'd 
learned.  Those rules are to formulate mathematics, first, in a natural 
way (what is natural about forbidding uncountable meets and joins while 
allowing countable ones?), and second (subject to the first), so as to 
make its questions answerable.

One doesn't need to be a mathematician to appreciate the common sense of 
this prioritization of strategies.  When searching for your dropped car 
keys in the dark, you should first search near where you think you 
dropped them, the natural place.  But if you don't know where you 
dropped them, then it makes good sense to start near the street lamp 
where your chances of success are greatest and work outwards from there.

The basic question should be, why should mathematics consider itself 
subject to the limitations of its mortal practitioners?  What would 
Erdos say?  Did he ever suggest that The Book in its infinite wisdom 
might limit itself to countable conjunctions and disjunctions?

Vaughan Pratt