I am doing a little exercise and would just like to double check that I have understood the tools I am working with. The exercise is:

Using that $|X\times Y|=|X|\cdot |Y|$ for any sets $X,Y$, show that the union of $\alpha$-many disjoint sets of size $\beta$ has size $\alpha\cdot \beta$, commenting on use of the axiom of choice.

My solution is: have a collection of disjoint sets $\{B_i:\;i\in I\}$ with $|I|=\alpha$, all of size $\beta$. As an intermediate step, through the natural projection, biject $B_i\to \{(i,x):\;x\in B_i\}=E_i$ (disjoint because the $B_i$ are). Take any set $B$ of $\beta$. For each $i\in I$, choose a bijection $E_i\to \{(i,b):\;b\in B\}$. Now because the $E_i$ were disjoint: $$\left|\bigcup_I B_i\right|=\left|\bigcup_I \{(i,b):\,b\in B\}\right|=\left|I\times B\right|=\alpha\cdot \beta$$ I think the proof works, on the surface at least. My questions are:

  • I know I used choice in choosing $\alpha$-many bijections from the $E_i$ (but not for $B_i\to E_i$ because in that case they were specified). Have I also used choice when I "took any set $B$ of size $\beta$"?
  • I am aware that without AC, we can have things like $\mathbb{R}$ being a countable union of countable sets. In the context of the statement above, is this particular statement equivalent to saying $2^{\aleph_0}=\aleph_0\cdot \aleph_0$, or instead that the size of the countable collection of countable sets is not necessarily $\aleph_0\cdot\aleph_0?$ If the former it's not clear to me why choice is necessary for the statement to be true.

In moving from $\bigcup\{B_i\mid i\in I\}$ to $I\times B$ you need to ensure that $B_i$ have a very specific form: $\{i\}\times B$.

But if you are only given an arbitrary family $\{C_i\mid i\in I\}$ such that $|C_i|=|B|$ for all $i$, you still need to choose for each $i$ a bijection between $C_i$ and $B$. There are might be many such bijections, and many could easily be "two".

Recall the definitions of cardinal arithmetic:

  1. $|A|+|B|=|A\times\{0\}\cup B\times\{1\}|$.
  2. $|A|\cdot|B|=|A\times B|$.
  3. $|A|^{|B|}=|\{f\mid f\colon B\to A\}|$.

The definition, therefore, of $|I|\cdot|B|$ is literally $|I\times B|$. So, if $\aleph_0=|\Bbb N|$, it means that $\aleph_0\cdot\aleph_0$ is literally defined as $|\Bbb{N\times N}|$, and we know how to explicitly match $\Bbb{N\times N}$ with $\Bbb N$, so we get that $\aleph_0\cdot\aleph_0=\aleph_0$ after all.

The problem, as it usually is with these things, is that moving from an infinite sum to a finite product, is not something that is grounded in the definitions. It is something nontrivial. It is something that we need to prove, if we can. And as you point out, we cannot without the axiom of choice because of the fact it is possible that $\Bbb R$ is the countable union of countable sets. But it doesn't change the finitary definitions, it just means that $|\bigcup\{B_i\mid i\in I\}|$ need not be equal to $|I|\cdot|B|$.

Finally, to your query, choosing one subset of $\beta$ of size $\beta$ does not require the axiom of choice, you can just take $\beta$ itself. It is the choosing of bijections that requires the axiom of choice.

  • $\begingroup$ Thank you, that clears it up! $\endgroup$ – K. 622 Nov 6 '16 at 16:50

Remember that $\aleph_0$ is a specific set - namely, it is the set of finite ordinals. (A cardinal is just an initial ordinal, and every ordinal is the set of smaller ordinals.) So $\aleph_0\times \aleph_0$ is again a specific set. Now look at one of the models you mention where $\mathbb{R}$ is a countable union of countable sets $S_i$ $(i\in\omega)$. Then $\vert \bigcup_{i\in\mathbb{N}}S_i\vert=2^{\aleph_0}$, but $\aleph_0\cdot\aleph_0=\vert\aleph_0\times\aleph_0\vert=\aleph_0$. So it is no longer true that the union of $\aleph_0$-many disjoint sets of size $\aleph_0$ has cardinality $\aleph_0\cdot \aleph_0$.

  • $\begingroup$ coughcoughcoughAcardinaldoesnothavetobeaninitialordinalinachoicelesscontextcoughcoughcough $\endgroup$ – Asaf Karagila Nov 6 '16 at 10:30

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.