5
$\begingroup$

Two theorems:

$(1)$ Countable Union of Countable Sets is Countable

$(2)$ Cartesian Product of Countable Sets is Countable

Linked are the formal proofs on Proofwiki.

I do not understand why they had to use the Axiom of Countable Choice (ACC) the first proof but settled with "from the definition of countable" in the second. I think that $(1)$ should depend on ACC iff $(2)$ depends on it.

Improve this question
$\endgroup$
14
$\begingroup$

The difference is that in the second proof we need to make only two choices: for each of $S$ and $T$ we must choose an injection into $\Bbb N$. Making a finite number of choices does not require any axiom of choice. In the first proof, however, we must make infinitely many choices, since we must choose an injection of each of the sets $S_n$ into $\Bbb N$, and that does require some choice principle.

Improve this answer
$\endgroup$
  • $\begingroup$ Ok. So, Axiom of (Countable) Choice is only required when an (countably) infinite number of arbitrary choices are being made? I haven't taken set theory yet, in case this seems like a trivial question. $\endgroup$ – genepeer Apr 17 '13 at 21:58
  • 2
    $\begingroup$ @genepeer: That’s essentially right, yes. (And if you’ve not had any set theory, it’s a rather good question.) $\endgroup$ – Brian M. Scott Apr 17 '13 at 22:01
  • 1
    $\begingroup$ @Myke: The axiom of choice says that whenever there is a set of non-empty set, then we can choose one from each of its members. Id est, we can make infinitely many choices. $\endgroup$ – Asaf Karagila♦ Apr 17 '13 at 23:13
  • 2
    $\begingroup$ @Myke: AC certainly does not say that we can’t make one choice from an infinite number of elements. On the contrary, ZF without AC already guarantees that we can make such a choice. AC says that if $\{A_i:i\in I\}$ is a non-empty set of non-empty sets, then we can choose an element $a_i$ from each $A_i$. If $I$ is infinite, that’s infinitely many choices. $\endgroup$ – Brian M. Scott Apr 17 '13 at 23:16
  • 1
    $\begingroup$ @Myke: We don’t need AC, because we don’t need a mechanism. The moment you say that $X\ne\varnothing$, you’ve said that $\exists x(x\in X)$, and that’s all that you need in order to say that you can choose an element of $X$. This does not say that there is an effective procedure for choosing that element, and in general there is no effective procedure, with or without AC. $\endgroup$ – Brian M. Scott Apr 18 '13 at 6:37
9
$\begingroup$

I was also a little confused when I first saw this example. I think the situation is clarified by introducing the following terminology: say that a counted set is a countable set $S$ together with a bijection $\mathbb{N} \to S$. It is true, in ZF, that

The Cartesian product of two counted sets is counted.

Finite choice, which is true in ZF, then implies that a Cartesian product of two countable sets is countable. This in turn implies, again in ZF, that

A countable union of counted sets is counted.

From here, to pass to the claim that a countable union of countable sets is countable, we need to turn countably many counted sets into countable sets, and this requires some form of countable choice. But the above theorem is good enough for most applications anyway. You will rarely know that a family of sets is countable without being able to explicitly find bijections from each of those sets to $\mathbb{N}$.

Improve this answer
$\endgroup$
  • 4
    $\begingroup$ (Note that being countable is a property but being counted is a structure.) $\endgroup$ – Qiaochu Yuan Apr 17 '13 at 22:00
  • $\begingroup$ Do you need the axiom of choice if you have a collection of infinite singletons? $\endgroup$ – genepeer Apr 18 '13 at 23:46
  • $\begingroup$ Nope. It's really easy to choose an element from a one-element set. $\endgroup$ – Qiaochu Yuan Apr 19 '13 at 1:10
3
$\begingroup$

The axiom of choice allows us to make many choices at the same time.

It is true, without the axiom of choice, that if $(A_i,f_i)_{i\in\Bbb N}$ is a sequence of countable sets, and $f_i\colon A_i\to\Bbb N$ is an injection, then $\bigcup A_i$ is countable. This is because we are given the injections into $\Bbb N$.

However in the general case, one has to choose such injection (often a bijection). These injections are not at all definable that we can just write down some (perhaps very complex) formula witnessing their existence, and indeed without the axiom of choice it is possible that there is a family of countable (or even finite) sets whose union is not countable -- exactly because we cannot choose the injections in a uniform way.

On the other hand, when we take the product $A\times B$ we only have to make two choices, $f\colon A\to\Bbb N$ and $g\colon B\to\Bbb N$ - two injections - which is provably possible without the axiom of choice. And we already know how to find a bijection between $\Bbb N$ and $\Bbb{N\times N}$ in a very definable way, so that is enough.

The main issue here is that when we take products, or even unions, of infinitely many sets then we often need some uniformity in the way we order these sets (be it well-order, or otherwise). The axiom of choice allows to prove that such uniformity exists, because we can choose an ordering for each set; but without the axiom of choice it is sometimes the case that we may end up in a universe where such uniformity does not exist, i.e. without some form of the axiom of choice (or a weaker form) we cannot prove a particular statement.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.