# About a paper of Zermelo

Zermelo, E., Beweis, daß jede Menge wohlgeordnet werden kann, Math. Ann. 59 (4), 514–516 (1904),

available here. Edit: Springer link to the original (OCR'ed, may be behind a paywall)

An English translation can be found in the book Collected Works/Gesammelte Werke by Ernst Zermelo. Alternative source: the book From Frege to Gödel: a source book in mathematical logic, 1879-1931, by Jean Van Heijenoort.

I don't understand the paragraph on the last page whose English translation is

Accordingly, to every covering $\gamma$ there corresponds a definite well-ordering of the set $M$, even if the well-orderings that correspond to two distinct coverings are not always themselves distinct. There must at any rate exist at least one such well-ordering, and every set for which the totality of subsets, and so on, is meaningful may be regarded as well-ordered and its cardinality as an "aleph". It therefore follows that, for every transfinite cardinality, $$\mathfrak m=2\mathfrak m=\aleph_0\,\mathfrak m=\mathfrak m^2,\mbox{and so forth;}$$ and any two sets are "comparable"; that is, one of them can always be mapped one-to-one onto the other or one of its parts.

It seems to me Zermelo says that the fact that any set can be well-ordered immediately implies that any infinite cardinal equals its square. Is this interpretation correct? If it is, what is the argument?

Side question: What is, in a nutshell, the history of the statement that any infinite cardinal equals its square? Where was it stated for the first time? Where was it proved for the first time? (In a similar vein: where was the comparability of any two cardinal numbers proved for the first time?)

Edit: German original of the passage in question:

Somit entspricht jeder Belegung $\gamma$ eine ganz bestimmte Wohlordnung der Menge $M$, wenn auch nicht zwei verschiedenen Belegungen immer verschiedene. Jedenfalls muß es mindestens eine solche Wohlordnung geben, und jede Menge, für welche die Gesamtheit der Teilmengen usw. einen Sinn hat, darf als eine wohlgeordnete, ihre Mächtigkeit als ein „Alef“ betrachtet werden. So folgt also für jede transfinite Mächtigkeit $$\mathfrak m=2\mathfrak m=\aleph_0\,\mathfrak m=\mathfrak m^2\text{ usw.,}$$ und je zwei Mengen sind miteinander „vergleichbar“, d. h. es ist immer die eine ein-eindeutig abbildbar auf die andere oder einen ihrer Teile.

• It is a theorem of Tarski. Although this paper predates Tarski. I am not certain about how much choice Zermelo was assuming in his work, though. – Asaf Karagila Aug 1 '11 at 7:53
• @Asaf Karagila - Thanks for your comment! What is the theorem of Tarski you’re referring to? Is it the fact that infinite cardinals equal their square? In any case, do you have a reference? – Pierre-Yves Gaillard Aug 1 '11 at 8:04
• The translation from German seems to be correct. – joriki Aug 1 '11 at 8:08
• @Zhen: Tarski's theorem is in $ZF$, without choice. Of course it is also a theorem of $ZFC$, but that is less "impressive", as everything implies choice in $ZFC$. – Asaf Karagila Aug 1 '11 at 9:08
• @Zhen Lin: The statement "for all $\kappa$, $\kappa^2 = \kappa$" is a sentence of set theory, and AC is a sentence of set theory, so the formula that says they are equivalent is also a sentence of set theory. This "if and only if" statement is then provable in ZF, as Asaf Karagila says. – Carl Mummert Aug 1 '11 at 11:25

The following is a theorem of $ZF$:

The axiom of choice holds if and only if for every infinite set $A$, there exists a bijection of $A$ with $A\times A$. (i.e. $|A|=|A|^2$)

Let us overview the theorem of Zermelo, namely if the axiom of choice holds then $\kappa=\kappa^2$ for every infinite $\kappa$.

This is fairly simple, by the canonical well ordering of pairs.

Consider $\alpha\times\beta$, this can be well ordered as ordinal multiplication (that is $\beta$ copies of $\alpha$, i.e. lexicographical ordering), or it can be ordered as following:

$$(x,y)<(w,z)\iff\begin{cases} \max\{x,y\}<\max\{w,z\}\\ \max\{x,y\}=\max\{w,z\}\land x<w\\ \max\{x,y\}=\max\{w,z\}\land x=w\land y<z\end{cases}$$

This is a well-ordering (can you see why?). Now we will prove that $\kappa\times\kappa$ has the same order type as $\kappa$, this is a proof that the two sets have the same cardinality, since similar order types induce a bijection.

Firstly, it is obvious that $\kappa$ is at most of the order type of $\kappa\times\kappa$ since the order type of $\kappa$ can be simply be written as $\alpha\mapsto (\alpha,\alpha)$. The other direction we prove by induction on $\alpha$ that for the initial ordinal $\omega_\alpha$ it is true: $\omega_\alpha=\omega_\alpha\times\omega_\alpha$.

Fact: If $\delta<\omega_\alpha$ (where $\omega_\alpha$ is the $\alpha$-th initial ordinal) then $|\delta|<\aleph_\alpha$.

The claim is true for $\omega_0=\omega$ since for any $k$ the set $\{(n,m)\mid (n,m)<(k,k)\}$ is finite. Therefore the order type of $\omega\times\omega$ is the supremum of $\{k_n\mid n\in\omega\}$ and $k_n$ are finite. Simply put, the order type is $\omega$.

Now assume (by contradiction) $\alpha$ was the least ordinal such that $\omega_\alpha$ was a counterexample to this claim, i.e. $\omega_\alpha$ is strictly less than the order type of $\omega_\alpha\times\omega_\alpha$.

Let $(\gamma,\beta)<\omega_\alpha\times\omega_\alpha$ be the pair of ordinals such that the order type of $\{(\xi,\zeta)\mid (\xi,\zeta)<(\gamma,\beta)\}$ is $\omega_\alpha$.

Take $\delta$ such that $\omega_\alpha>\delta>\max\{\gamma,\beta\}$ then $(\gamma,\beta)<(\delta,\delta)$ and in particular $\{(\xi,\zeta)\mid (\xi,\zeta)<(\delta,\delta)\}$ has cardinality of at least $\omega_\alpha$, as it extends a well order of the type $\omega_\alpha$.

However, $\delta<\omega_\alpha$ by the fact above it is of smaller cardinality, and thus that set has the cardinality $|\delta|\times |\delta|=|\delta|<\omega_\alpha$ by our induction assumption. Hence, a contradiction.

The other direction, also known as Tarski's theorem (I managed to find that it was published around 1923, but I could not find a proper reference.) is as follows:

Suppose that for all infinite $A$, there exists a bijection of $A$ with $A\times A$ then the axiom of choice holds.

The proof (which I will not bring here, as it would require a few more notations and definitions - I did give it here) uses the concept of Hartogs number (the least ordinal which cannot be injected into $A$). The proof in its essence is:

If $\aleph(A)$ is the Hartog of $A$, $$A+\aleph(A)=(A+\aleph(A))^2=A^2+2\cdot A\cdot\aleph(A)+\aleph(A)^2\ge A\cdot\aleph(A)\ge A+\aleph(A)$$

We then use (or prove) a theorem that if $A+\aleph(A)=A\cdot\aleph(A)$ then $A$ can be well ordered.

Historically, Tarski came to publish this theorem. It was rejected at first. Polish-American mathematician Jan Mycielsi relates in his article A System of Axioms of Set Theory for the Rationalists Notices AMS, February 2006, p.209:

Tarski told me the following story. He tried to publish his theorem (stated above) in the Comptes Rendus Acad. Sci. Paris but Fréchet and Lebesgue refused to present it. Fréchet wrote that an implication between two well known propositions is not a new result. Lebesgue wrote that an implication between two false propositions is of no interest. And Tarski said that after this misadventure he never tried to publish in the Comptes Rendus.

Found via Wikipedia article on the axiom of choice.

• I tried proving $|X^2 | = |X|$ using Zorn's lemma and Cantor–Schröder–Bernstein Theorem and $|X \times \mathbb N | = |X|$ but failed. Wondering if all proofs put a well-ordering structure on $X$... – CopyPasteIt Oct 9 '17 at 12:51
• Since the Cantor–Bernstein theorem is provable without choice; and $|X\times\Bbb N|=|\Bbb X|$ does not imply choice by itself, you need to be clever about how you apply Zorn's lemma to your problem. In general, if you proved that $|X\times\Bbb N|=|X|$, then you're halfway there. There is a sharp parallel between proofs of addition and multiplication here, and you need the cardinal arithmetic results to "clean up" any leftovers when you have a maximal injection. – Asaf Karagila Oct 9 '17 at 12:54
• I digested this answer and here is my supplementary take for $\kappa^2 = \kappa$: Let $\kappa$ be the minimal counter-example, and let its representative ordinal be $\omega_\alpha$. Then, consider the set $S=\{(a,b,c) \in \omega_\alpha^3 \mid a = \max(b,c)\}$ well-ordered under lexicographical ordering. Let $S(a,b,c)$ denote $\{x \in S \mid x < (a,b,c)\}$. Let $S(a,b,c)$ be the initial segment of $S$ that is order-isomorphic to $\omega_\alpha$. – Kenny Lau Apr 8 '18 at 10:17
• Then: $$\begin{array}{rcll}\kappa&=&|\omega_\alpha| &\text{by definition of}~\omega_\alpha \\ &=&|S(a,b,c)| &\text{by definition of}~(a,b,c) \\&\le& |S(a^+,a^+,a^+)| &\text{since}~S(a,b,c) < S(a^+,a^+,a^+) \\ &&& \text{on the ordinal level}\\&=& |a^+|^2 & \text{construct a bijection by} \\ &&&\text{dropping the first coordinate} \\ &=& |a^+| & \text{by minimality of}~\kappa \\ &&& \text{and that}~\alpha^+ < \kappa \\ &<& \kappa &a^+ \in \omega_\alpha~\text{and}~\omega_\alpha~\text{is the smallest} \\ &&&\text{ordinal with cardinality}~\kappa \end{array}$$ i.e. $\kappa < \kappa$, contradiction. – Kenny Lau Apr 8 '18 at 10:18