Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
This was essentially answered by Arturo here. –  Asaf Karagila Jul 17 '12 at 19:03
    
@Asaf I have learned that set of all infinite cardinals is isomorphic with set of von Neumann ordinals, thus mark infinite cardinals as $\aleph_0,...,\aleph_\omega,...$. –  Katlus Jul 18 '12 at 7:10
    
Here, I don't understand what's the difference between 'aleph's' and infinite cardinals. –  Katlus Jul 18 '12 at 7:10
    
Katlus, if the real numbers cannot be well-ordered then $|\mathbb R|$ is not $\aleph_\alpha$. Aleph cardinals are those cardinals which are $\aleph$ numbers, and the axiom of choice is equivalent to the assertion that every infinite set has a cardinality of some $\aleph$. Without the axiom of choice there are other cardinals too. –  Asaf Karagila Jul 18 '12 at 7:13
    
I wrote two answers about this issue which you may want to read: This and That. –  Asaf Karagila Jul 18 '12 at 7:16
show 1 more comment

2 Answers 2

up vote 7 down vote accepted

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.

share|improve this answer
add comment

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.

share|improve this answer
    
You remember correctly. It is a result by Tarski, see my answer to this question. –  Asaf Karagila Jul 17 '12 at 18:03
2  
However, is there any "normal" set (i.e. any set which one would normally encounter) for which proving $\left|S\times S\right|=\left|S\right|$ would need the Axiom of Choice? –  celtschk Jul 17 '12 at 18:15
    
@celtschk: If you only deal with countable sets, and sets of size continuum, no. If you allow arbitrary subsets of the real line, or even just Borel, then yes. If you are a set theorist, in descriptive set theory and models of AD you may encounter them as well relatively often (e.g. $\aleph_1+\frak c$ has this property). –  Asaf Karagila Jul 17 '12 at 18:51
    
I'd consider Borel subsets of the real line as pretty "normal", so the answer is obviously "yes, it is needed". Thank you. –  celtschk Jul 17 '12 at 19:29
    
@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|$. –  Asaf Karagila Jul 17 '12 at 20:47
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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