NetNews Usenet Archive 1993 #3/NN_1993_3.iso/spool/sci/math/18645

Internet Message Format | 1993-01-22 | 3.2 KB

Path: sparky!uunet!pipex!doc.ic.ac.uk!uknet!comlab.ox.ac.uk!mbeattie
From: [e-mail] (Malcolm Beattie)
Newsgroups: sci.math
Subject: Re: Alephs again
Message-ID: <[e-mail]>
Date: 22 Jan 93 13:52:10 GMT
References: <[e-mail]> <[e-mail]> <[e-mail]>
Organization: Oxford University Computing Service, 13 Banbury Rd, Oxford, U
Lines: 63
Originator: mbeattie@black

In article <[e-mail]> [e-mail] (Dennis Paul Himes) writes:
>In article <[e-mail]> [e-mail] (Allen Knutson) writes:
>>[e-mail] (David Yann) greets us, and asks a bunch of
>>set-theory questions. I'll state at the beginning: if one has the
>>Axiom of Choice, much cardinal arithmetic becomes trivial.
>>Without it, most things are hard (a countable union of countable
>>sets can be uncountable, for instance).
>>
>     Is this true?  What is wrong with the following enumeration?
>     Let f(i,j) be the i^th element of the j^th set, both indices starting
>at zero.  Enumerate the union as follows:
>n = 0;
>for (i0 = 0; ; ++i0) {
>    for (i1 = 0; i1 <= i0; ++i1) {
>       enumeration[n++] = f (i1, i0 - i1);
>    }
>}
>    Or, for those of you who don't know C,
>f (0, 0),
>f (0, 1), f (1, 0),
>f (0, 2), f (1, 1), f (2, 0),
>f (0, 3), f (1, 2), f (2, 1), f (3, 0),
>etc.
>    Some work would have to be done to eliminate duplicates, but I don't
>see how this depends on AC or how this would not apply to any countable
>union of countable sets.

Here is the problem: what do you mean by *the* $i$th
of *the* $j$th set?
The explanation is going to hinge on the difference
between a set being _countable_ and a set being _counted_.
For a set to be _countable_ just tells us that there _exists_
some bijection with \omega; whereas a set being _counted_ (*)
means that we are _given_ such a bijection.

You may well be able to fill in the details for yourself now,
but if not, let's start from scratch.
Let {A_j | j \in J} be a family of countable sets such that
J is countable too.
Certainly, we can pick and fix a bijection of J with \omega
(there is only one `choice' to make) and use this bijection
to enumerate the family of A_j as A_1, A_2, A_3, ...
Now we have an infinite number of A_j, each of which is
countable. Howeverm, there is no _given_ bijection of each
A_j with \omega. This means that to enumerate each A_j
as {a_j1, a_j2, a_j3, ...} we have to _pick_ a bijection
of that A_j with \omega. This involves an infinite number
of choices (i.e. one for each j \in J) and cannot be done
without some form of Choice axiom.
I think one can get by with an axiom of `countable choice'
but I'm not sure.

(*) The use of the word `counted' isn't very common, but it
makes a useful distinction here which helps to explain things.
I can't remember where I saw the distinction presented this way.

--Malcolm

--
Malcolm Beattie <[e-mail]> | I'm not a kernel hacker
Oxford University Computing Services      | I'm a kernel hacker's mate
13 Banbury Road, Oxford, OX2 6NN (U.K.)   | And I'm only hacking kernels
Tel: [phone] Fax: [phone]   | 'Cos the kernel hacker's late