3
$\begingroup$

As you all know, cardinality of $\mathbb{R} = 2^{\aleph_0}$ can be proved in ZF, since cardinality of $\mathbb{N} \times \mathbb{N} = \aleph_0$ can be proved in ZF.

I know that the statement 'For any infinite set $A$, $|A\times A|=|A|$ is weaker than A.C.

I wonder if there is a way to prove in ZF that $|A\times A|=|A|$ when $|A|=2^{\aleph_0}$ specifically.

  • 0
    I wrote two answers about this issue which you may want to read: [This](http://math.stackexchange.com/questions/53770/defining-cardinality-in-the-absence-of-choice) and [That](http://math.stackexchange.com/questions/53752/theres-non-aleph-transfinite-cardinals-without-the-axiom-of-choice).2012-07-18

2 Answers 2

7

Yes, you can prove this in ZF. One way of seeing this is to note that $2^{\aleph_0}$ is the size of $A=\{0,1\}^{\mathbb N}$ (the set of functions from ${\mathbb N}$ to $\{0,1\}$), and $A\times A$ is easily seen to be in bijection with $\{0,1\}^{\mathbb N\sqcup\mathbb N}$, where $\sqcup$ denote disjoint union. But $\mathbb N\sqcup\mathbb N$ is in bijection with $\mathbb N$ (think even and odd numbers).


In fact, Cantor's classical proofs that $\mathbb R^2$ and $\mathbb R$ are in bijection do not use choice. For example, $\mathbb R$ and $(0,1)$ are easily seen to be in bijection (think $\arctan$ or somesuch), and one can find a bijection between $(0,1)^2$ and $(0,1)$ by looking at decimal expansions and intertwining. (Usually one needs to treat a small (countable) set a bit differently in these arguments.)

In general, the cardinal $2^\kappa$ is the size of the set of functions from a set of size $\kappa$ to $\{0,1\}$, so $2^\kappa\times 2^\kappa$ is $2^{\kappa+\kappa}$ (as with exponentiation of finite numbers), where the sum denotes the size of a disjoint union of two sets of size $\kappa$. So, it is enough to know that $\kappa+\kappa=\kappa$ to conclude that $2^\kappa\times 2^\kappa =2^\kappa$.

It is consistent with ZF to have infinite sets $A$ such that $A\times A$ is not in bijection with $A$. In fact, as already pointed out in Martin's answer, if there are no such exceptions, choice holds. It is also consistent to have sets $A$ such that $A\sqcup A$ and $A$ are in bijection, but $A\times A$ and $A$ are not. In that case, ${\mathcal P}(A)$ and ${\mathcal P}(A)\times{\mathcal P}(A)$ would be in bijection, as explained above.

Note that if $A$ is infinite and $A\times A$ and $A$ are in bijection, then so are $A\sqcup A$ and $A$ (by Schröder-Bernstein, which does not need choice). For the case you are asking, already $\mathbb N\times\mathbb N$ is in bijection with $\mathbb N$, so things work out nicely.

5

All you need here is $2^{\aleph_0}\cdot 2^{\aleph_0} = 2^{\aleph_0+\aleph_0}=2^{\aleph_0}.$ There is no choice involved.

BTW the fact that $|A\times A|=|A|$ is equivalent to Axiom of Choice, this is a result due to Tarski (if I remember correctly). See this question: For every infinite $S$, $|S|=|S\times S|$ implies the Axiom of choice.

  • 0
    @celtschk: This is actually a fairly new result by A. Miller, it is consistent that there is a Dedekind-finite sets of real numbers which is Borel, and Dedekind-finite do not have the property that $|A|^2=|A|$.2012-07-17