# For every infinite $S$, $|S|=|S\times S|$ implies the Axiom of choice

How to prove the following conclusion:

[For any infinite set $S$,there exists a bijection $f:S\to S \times S$] implies the Axiom of choice.

Can you give a proof without the theory of ordinal numbers.

-
As pointed out on MathOverflow, what does it mean "without the theory of ordinal numbers"? Also, why do you wish to avoid it? If it is due to lack of knowledge on the topic, the proof does not use much of the theory of ordinals, nor I think that a proof directly trying to find a choice function would be any simpler. – Asaf Karagila Aug 9 '11 at 10:59

I will assume you are familiar with the definitions of cardinality and the ordering of cardinals, even in the absence of choice. If anything is unclear please let me know, and I will see to elaborate if needed.

Fact I: If $\kappa$ is a cardinal, and $\aleph$ is any $\aleph$-number (i.e. a well-orderable cardinal), if $\kappa\le\aleph$ then $\kappa$ can be well ordered as well.

(This is a very nice exercise, in case you do not see it right away).

Definition: (Hartogs number) For an infinite set $\kappa$ we denote $\aleph(\kappa)$ the least ordinal which cannot be injected into $\kappa$.

When assuming the axiom of choice, $\aleph(\kappa)$ is $|\kappa|^+$ (that is the successor cardinal of $|\kappa|$). we have, if so, that $\aleph(\omega)=\omega_1$.

Without the axiom of choice this gets slightly more complicated, since there are sets which cannot be well ordered. In a way, Hartogs number measures how much of the set can we well order.

Consider, for example, the case of $A$ being an amorphous set (that is, $A$ is infinite, and every $B\subseteq A$ is either finite or $A\setminus B$ is finite). Since $A$ is infinite every finite cardinal can be embedded into it. However $\aleph_0\nleq |A|$, therefore $\aleph(A)=\omega$.

Fact II: For every infinite set $A$, the ordinal $\aleph(A)$ is an initial ordinal, i.e. an $\aleph$ cardinal.

Otherwise there is $f\colon \aleph(A)\to\alpha$ which is a injection, and $g\colon\alpha\to A$ which is an injection. Composition of injective functions is injective, therefore $g\circ f\colon \aleph(A)\to A$ is an injection of $\aleph(A)$ into $A$, which is a contradiction to the definition of $\aleph(A)$.

Lemma: If $\kappa$ is an infinite cardinal and $\aleph_\alpha$ is an $\aleph$-number, and $$\kappa+\aleph_\alpha=\kappa\cdot\aleph_\alpha$$ Then $\kappa\le\aleph_\alpha$ or $\kappa\ge\aleph_\alpha$.

Before proving this lemma, let us consider this useful corollary:

Corollary: If $\kappa+\aleph(\kappa)=\kappa\cdot \aleph(\kappa)$ then $\kappa$ can be well ordered.

Proof: Since $\aleph(\kappa)$ cannot be injected into $\kappa$, in particular we have that $\aleph(\kappa)\nleq\kappa$, therefore $\kappa<\aleph(\kappa)$ and so it can be well ordered.

Proof of Lemma: Let $A$ be of cardinality $\kappa$ and $P$ of cardinality $\aleph_\alpha$, without loss of generality we can assume the two sets are disjoint.

Since $|A\times P|=|A\cup P|$, we can also assume there are two disjoint sets $|A'|=|A|$ and $|P'|=|P|$ such that $A\times P=A'\cup P'$.

Since we divide an infinite set into two parts, at least one of the following is bound to occur:

1. There exists some $a\in A$ such that $\langle a,p\rangle\in A'$ for every $p\in P$, and then we have that $\kappa\ge\aleph_\alpha$ (by the map $p\mapsto\langle a,p\rangle$).

2. If there is no $a$ as above, then for every $a\in A$ there is some $p\in P$ such that $\langle a,p\rangle\notin A'$. For every $a\in A$ let $p_a\in P$ be the minimal $p\in P$ such that $\langle a,p\rangle\in P'$, and so the injective function $a\mapsto\langle a,p_a\rangle$ is an injective function of $A$ into $P'$, and therefore $\kappa\le\aleph_\alpha$.

Now the main theorem, proved by Tarski.

Theorem: Suppose for every infinite set $A$ it holds $|A|=|A\times A|$, then every set can be well ordered.

Proof: Let $\kappa$ be an infinite cardinal. Consider $\kappa+\aleph(\kappa)$. Our assumption gives us:

$$\kappa+\aleph(\kappa)=(\kappa+\aleph(\kappa))^2=\kappa^2+2\kappa\cdot \aleph(\kappa)+\aleph(\kappa)^2\ge\kappa\cdot \aleph(\kappa)\ge\kappa+\aleph(\kappa)$$

Where the last $\ge$ sign is due to the function from $\kappa\cup \aleph(\kappa)$: $$x\mapsto\begin{cases} \langle x,0\rangle & x\in\kappa,x\neq k\\ \langle t,x\rangle & x\in \aleph(\kappa)\\ \langle k,1\rangle & x=k\end{cases}$$ (For fixed $t,k\in\kappa$ and $t\neq k$. Note that we use the fact $\kappa$ is infinite, therefore it has at least two elements).

By the Corollary we have that $\kappa$ can be well ordered.

Pointed out to me on the MathOverflow post of this question, that there was a request to avoid the ordinals. I did think about it, a little bit.

I do remember that studying this proof originally, as well as the proof that "If $\kappa$ is such that $|A|\le\kappa<|\mathcal P(A)|$, then $|A|=\kappa$" implies choice, offers no immediate intuition as for why does the proof works. The use of Hartogs number looks like a magic trick.

However, since the first time I had studied this proof I have gained more than a bite of intuition with regards to the axiom of choice. It seems that this is a good place to slightly give the intuitive explanation for this proof.

I will start by saying that I do not believe that any proof of this theorem will be both concise and reveal the intuition behind it. So even if I were to think really hard and transform this proof into a choice function sort of proof, I doubt it will be any more revealing in its intuition, which is why I have decided to write the following instead -- it seems more profitable to the reader.

It is a rather well known fact that the axiom of choice is equivalent to the assertion that every set can be well ordered. In the absence of choice there are sets that cannot be well ordered. Hartogs number is a way to measure how much out of the set can be well ordered.

The axiom of choice is equivalent, as well, to the assertions that the cardinalities of any two sets can be compared. This is exactly due to the idea of Hartogs number - if we can compare a cardinal with its Hartogs then it can be well ordered.

So essentially what we try to have is "enough" comparability to deduce the well ordering principle. This is exactly what the tricky lemma gives us.

The idea behind the proof of the lemma is that if we break the multiplication into a sum then we can find a way to compare the sets. We can replace the requirement that the second set is well ordered simply by "has a choice function on its power set" (this, however, is equivalent to saying that the set can be well ordered).

From this the theorem follows, proving that we can compare every infinite set with its Hartogs number, therefore implying the set can be well ordered.

-
This is a very nice result, with a completely understandable, albeit mysterious proof ^^. I have the feeling your injection $\kappa+H(\kappa)\leq\kappa\times H(\kappa)$ has a slight problem in that it sends both $1\in H(\kappa)$ and $k\in\kappa$ to the same place, but nothing that can't be fixed by taking $k\neq k'$ which is I believe what you meant to say (?). I was going to ask how you justify the existence of ordinals that don't inject into $\kappa$, but the wikipedia article you linked does a good job of it :) – Olivier Bégassat Nov 1 '11 at 21:43
@Olivier: Thank you very much! :-) As for the ordinals, well... I can do that, and I have done that in other answers as well. – Asaf Karagila Nov 1 '11 at 21:49
Do you have any idea how the lemma was conceived? – Olivier Bégassat Nov 1 '11 at 22:00
@Olivier: Not the slightest idea. However if you find some old cardinal arithmetics papers you can see that Tarski had a lot of definitions now generalized and cleaned up. I am most certain that he had a pretty good idea why. In fact, I once bought an old book of his about these things and it might be hidden in there. I will have to try and find it though... – Asaf Karagila Nov 1 '11 at 22:11

Let $A$ be an arbitrary infinite set. I will show that $A$ has a choice function, i.e., a function $a:\mathcal{P}(A)\setminus\{\varnothing\}\to A$ such that $a(X) \in X$ for every nonempty $X \subseteq A$.

First, pick a set $B$ such that:

• there is a choice function $b:\mathcal{P}(B)\setminus\{\varnothing\}\to B$, and

• there is no injection from $B$ into $A$.

(For example, take $B$ to be the set of all isomorphism classes of wellorderings of subsets of $A$.) Assume further that $A \cap B = \varnothing$.

By hypothesis, there is an injection $f:(A\cup B)^2\to(A\cup B)$. Given $x \in A$, there must be a $y \in B$ such that $f(x,y) \in B$, otherwise $y \in B \mapsto f(x,y)$ would be an injection from $B$ into $A$. We may thus define a function $g:A \to B^2$ by $g(x) = (y,f(x,y))$ where $y = b(\{u \in B : f(x,u) \in B\})$, i.e., for each $x \in A$, $g(x)$ picks a pair $(y,z) \in B^2$ such that $f(x,y) = z$. Note that $g$ must be an injection: if $g(x) = (y,z) = g(x')$ then $f(x,y) = z = f(x',y)$ and hence $x = x'$ since $f$ is an injection.

Now observe that $B^2$ has a choice function just like $B$. Namely, let $c:\mathcal{P}(B^2)\setminus\{\varnothing\}\to B^2$ be defined by $c(X) = (y,z)$ where $$y = b(\{u \in B : (\exists v \in B)((u,v) \in X)\})$$ and $$z = b(\{v \in B : (y,v) \in X \})$$ for every nonempty $X \subseteq B^2$. It follows that $A$ has a choice function too. Namely, let $a:\mathcal{P}(A)\setminus\{\varnothing\}\to A$ be defined by $$a(X) = g^{-1}(c(\{g(x) : x \in X\}))$$ for every nonempty $X \subseteq A$.

Remark. The proof of the existence of the set $B$ outlined above relies on the theory of wellorderings but not on the theory of ordinals. In fact, the above argument can be carried out in the theory Z (= ZF minus the Replacement Axiom). It is well known that there are models of Z with very few ordinals, e.g., $V_{\omega+\omega}$ is a model of Z.

-
So essentially this is the same thing as to take the proof in my answer and transform the use of Hartogs number and the fact well ordered sets into a well ordering. Very nice! :-) – Asaf Karagila Aug 9 '11 at 18:18
Yes, @Asaf. The argument is essentially the same as yours, but it avoids the use of ordinals as the OP requested. – François G. Dorais Aug 9 '11 at 18:35
@Asaf: I'm not used to the quality standards of this site, if you (or anyone else) want to flesh out my answer, please go right ahead... – François G. Dorais Aug 9 '11 at 23:05
Just a minor correction, the original Zermelo set theory did not have the axioms of replacement and foundation. Not only replacement was missing. – Asaf Karagila Aug 10 '11 at 13:07