# [FOM] "Mathematician in the street" on AC

Vaughan Pratt pratt at cs.stanford.edu
Sun Aug 16 01:38:26 EDT 2009

```freek wrote:
> I would ask "is the union of a countable number of countable
> sets countable?"
>
> Of course only a weak version of AC is needed for that,
> but I would be surprised if in the answer to that question
> "a mathematician in the street" would be even aware that
> AC is involved.

Better that they remain unaware that it is involved, or they'll use it
as prima facie evidence that foundations is irrelevant to mathematical
practice.

Look at

http://pirate.shu.edu/~wachsmut/ira/infinity/proofs/combctbl.html

for example.  This is from Bert Wachsmut's "Interactive Real Analysis,"
which bills itself as an online, interactive textbook for Real Analysis
or Advanced Calculus dealing with sets, sequences, series, continuity,
differentiability, integrability, topology, etc.  Wachsmut, an associate
professor of mathematics and CS at Seton College, says "The proof of the
next statement - that the countable union of countable sets is again
countable - is very similar" [to the proof that N^2 is countable].

Another example: Proposition A.4 of

http://www.math.unl.edu/~webnotes/classes/classAppA/classAppA.htm

This is from John Lindsay Orr's class notes for an analysis course at
the University of Nebraska--Lincoln.  Same deal.

Choice is never even mentioned.  And why should it be when ordinary
mathematical reasoning can give a completely deterministic, i.e.
choice-free, enumeration of the elements of such a union?

Define a countable set to be a pair (X,f) consisting of a set X and an
injection f: X --> N.  (If you have some other definition of "countable
set," why is yours better?)  Given a countable family (X_i,f_i) of
countable sets indexed by natural numbers i, construct an injection
q: U --> N where U is the union of the family as follows.

1.  Let g: U --> N be defined by g(x) = the least i such that x is in
X_i.  The definition of U and the well-ordering of N make g well-defined.

2.  Let h: U --> N be defined by h(x) = f_{g(x)}(x).

3.  Let k = gxh: UxU --> NxN be the evident product k(x,y) =
(g(x),h(y)).  (My categorical proclivities are showing here.)

4.  Let d: U --> UxU be the diagonal d(x) = (x,x).  (Ok, I'm being
pedantic here---I could have defined k: U --> NxN more directly as k(x)
= (g(x),h(x))---but better that than to be accused of some kind of
sloppiness in this context!)

5.  Let p: NxN --> N be any injection, e.g. p(i,j) = 2^i * 3^j.  (For a
totally unrelated reason this particular injection played a central role
in my Ph.D. thesis, whence my attachment to it.)

CLAIM: The composite q = pkd: U --> N is an injection.  That is, U as
the union of an arbitrary countable family of countable sets is countable.

If any of steps 1-5 of this elementary reasoning is outside ZF then I
would submit that ZF is not representative of mathematical practice.  If
the problem is with your definition of "countable set" then you need to
convince me (and I imagine Wachsmut, Orr, and presumably many other
mathematicians) that your definition confers some benefit.

Vaughan Pratt
```