Title: About a paper of Zermelo
Tags: set-theory;math-history;axiom-of-choice
Question: This about the famous article
Zermelo, E., Beweis, da&szlig; jede Menge wohlgeordnet werden kann, Math. Ann.59(4), 514&ndash;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.
[See also this interesting text by Dan Grayson.]
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&szlig; es mindestens eine solche Wohlordnung geben, und jede Menge, f&uuml;r welche die Gesamtheit der Teilmengen usw. einen Sinn hat, darf als eine wohlgeordnete, ihre M&auml;chtigkeit als ein &bdquo;Alef&ldquo; betrachtet werden. So folgt also f&uuml;r jede transfinite M&auml;chtigkeit
$$\mathfrak m=2\mathfrak m=\aleph_0\,\mathfrak m=\mathfrak m^2\text{ usw.,}$$
und je zwei Mengen sind miteinander &bdquo;vergleichbar&ldquo;, d.h. es ist immer die eine ein-eindeutig abbildbar auf die andere oder einen ihrer Teile.
Comment: The translation from German seems to be correct.

Comment: @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?

Comment: @Zhen Lin - Thanks! Could you spell out the contents of your last sentence? That’s precisely what I’m missing.

Comment: Thank you to joriki and Theo!

Comment: @Asaf Karagila - Thank you again for everything! I asked you a question about your proof, but then I saw how to answer it, and deleted the comment. I’m still studying your argument. I’m awfully slow, but if I have a question, I’ll ask you. Also I’ll tell you when I’m through.

Comment: @Pierre: Tarski's theorem is actually a meta-theorem: $\kappa = \kappa^2$ for all infinite cardinals $\kappa$ is equivalent to the axiom of choice. The axiom of choice is already present in Zermelo's work, which as I understand it, was motivated by the problem of *proving* the well-ordering principle in the first place! Once we have the well-ordering principle, $\kappa = \kappa^2$ follows by essentially the same argument which shows that $\mathbb{N}$ and $\mathbb{N}^2$ are in bijection.

Comment: @Asaf: I don't understand. How does one meaningful phrase a proposition of the form ‘... is equivalent to AC’ inside ZFC itself, without invoking some form of internalised logic?

Comment: 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.

Comment: @Zhen: This is not a metatheorem. It is fully expressible within the confines of ZFC.

Comment: @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$.

Comment: @Pierre: I saw that you left a comment, but deleted you it before I could reply. If there are points which needs to be clarified, do let me know. I will do my best to rectify.

Comment: @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.

Here is the accepted answer: 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&gt;\delta&gt;\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 pdelgado@example.org. Polish-American mathematician Jan Mycielsi relates in his article A System of Axioms of Set Theory for the Rationalists Notices AMS, February2006,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&eacute;chet and Lebesgue refused to present it. Fr&eacute;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.
Comment for this answer: 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$.
Comment for this answer: 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.
Comment for this answer: 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.
Comment for this answer: 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$...


{'source': 'StackExchangeDataset', 'subset': 'math.stackexchange.com', 'metadata': {'AnswerCount': 1, 'CommentCount': 12, 'ContentLicense': 'CC BY-SA 3.0', 'CreationDate': '2011:00:08/01/11', 'FavoriteCount': 13.0, 'PostTypeId': 1, 'Tags': '<set-theory><math-history><axiom-of-choice>', 'Title': 'About a paper of Zermelo', 'ViewCount': 4565, 'id': 54892, 'user_AboutMe': '<p>Email: pierre.yves.gaillard at gmail.com</p>\n<p>If you have any idea about this <a href="http://mathoverflow.net/q/162162/461">MathOverflow question</a>, thanks for letting me know.</p>\n', 'user_AccountId': 505126.0, 'user_DisplayName': 'Pierre-Yves Gaillard', 'user_Reputation': 18882.0, 'user_Views': 6252.0, 'user_id': 660.0}}