[FOM] "Mathematician in the street" on AC

[Vaughan Pratt]

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