7
$\begingroup$

Let $I$ be some non-empty set of indexes and for every $i \in I$ let $A_i$ be a set with cardinality $\aleph_0$. Is the following proof that the cartesian product $\prod_{i \in I}A_i$ is non-empty valid without the axiom of choice?

By definition, since $|A_i| = \aleph_0$ for every $i \in I$, then there are bijections $f_i: \mathbb{N} \rightarrow A_i$ for every $i \in I$. Let’s define explicitly the function of choice $g: I \rightarrow \bigcup_{i \in I}A_i$ by: $g(i) = f_i(0)$. It’s clearly a function of choice, hence $\prod_{i \in I} A_i \ne \emptyset$. QED.

If it is valid, can it be generalized to any cartesian product of sets with equal cardinality? If it is not valid, why?

$\endgroup$
  • 3
    $\begingroup$ Why do you need $f_i$ to be a bijection? Can't you do the same with an arbitrary map $f_i:\mathbb N\to A_i$ or even just $f_i:\{0\}\to A_i$? So you don't need the sets $A_i$ to be countable, just nonempty. And why bother with functions? Instead of "there are bijections $\mathbb N\to A_i$ for every $i\in I$" why not just say "there are elements $a_i\in A_i$ for every $i\in I$"? $\endgroup$ – bof Mar 17 '17 at 22:55
22
$\begingroup$

Your argument does invoke choice, albeit in a subtle way: when you choose a family of bijections $\{f_i: i\in I\}$. Just because, for each $i$, the set $F_i$ of bijections from $A_i$ to $\mathbb{N}$ is nonempty, doesn't mean that you can pick one for each $i$; this is exactly the axiom of choice applied to the family $\{F_i: i\in I\}$. In order to define $g(i)$, you need to refer to a specific $f_i$, so this use of choice is not easy to remove from your argument; and in fact it can be proved that the statement you are seeking to prove is not provable in ZF (= set theory without choice) alone.

In fact, this holds in the most powerful way possible: even choice for families of two-element sets is not provable in ZF!

$\endgroup$
8
$\begingroup$

There is absolutely no general way to pick a canonical bijection $f_i$. Sure, it's possible when all your sets are in fact sets of natural numbers or something. But in general, why would you prefer $f_0$ over a different bijection which maybe maps $f_i(0)$ to $f_i(1)$ and vice versa?

This is where you used the axiom of choice. You said that for all $i$, the set of bijections is non-empty, and therefore you can choose one from each of these sets, and that's how you got an element of the product.

Of course, it is consistent without the axiom of choice that a countable product of sets of size $2$ can be empty.

$\endgroup$
  • 1
    $\begingroup$ Your final paragraph contains a misprint, surely? (Either "It is inconsistent..." or "It is consistent with ZF without choice that...") $\endgroup$ – TonyK Mar 17 '17 at 19:23
  • 1
    $\begingroup$ Whoops, yes. Thank you. $\endgroup$ – Asaf Karagila Mar 17 '17 at 20:39
  • 1
    $\begingroup$ @YoungFrog: No, this is the problem. We can easily prove that the product of all the infinite subsets of $\Bbb N$ is non-empty. Despite the fact that the product is uncountable. This is because given any infinite $A\subseteq\Bbb N$, there is a canonical and uniquely determined bijection between $A$ and $\Bbb N$ (and $f_A(0)$ is indeed the minimal element of $A$). This gives us a choice function, which is fine and dandy without the axiom of choice. Why could we do it? Because there was a uniform way of choosing these bijections. Without a uniform choice of bijection, it does not work. $\endgroup$ – Asaf Karagila Mar 18 '17 at 9:30
  • 1
    $\begingroup$ @Colin: I have no idea why you made this comment, or why you'd think I'm unaware of the intricacies of using choice. $\endgroup$ – Asaf Karagila Mar 18 '17 at 15:28
  • 1
    $\begingroup$ @Colin: Addressing the comment to me directly sure make it seem like you're trying to clarify it to me. $\endgroup$ – Asaf Karagila Mar 18 '17 at 16:00
1
$\begingroup$

When you think you're defining g 'explicitly' , well, in fact you are not. You can do such 'explicit' definitions' e.g. when you give an explicit formula on real numbers because you're manipulating only one or a few symbols (usually just 'x').

Here you're manipulating an arbitrary number of symbols $f_i$. Just because you think of them as indexed by i does not mean you really can refer to them all... until you have an axiom which says that you can do so. That's AC. It allows you to use an arbitrary number of symbols in that specific situation. In fact, it's more of a workaround than really using arbitrary number of symbols.

Remember that g is an object of set theory, which must be constructed using axioms. There's no such axiom as 'explicitly define a function'.

$\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.