Tarski's theorem about choice

The goal is to prove that the axiom of choice is implied by the statement "for every infinite set ${\displaystyle A}$: ${\displaystyle |A|=|A\times A|}$". It is known that the well-ordering theorem is equivalent to the axiom of choice; thus it is enough to show that the statement implies that for every set ${\displaystyle B}$ there exists a well-order.

For finite sets this is trivial, so we assume that ${\displaystyle B}$ is infinite.

Since the collection of all ordinals such that there exists a surjective function from ${\displaystyle B}$ to the ordinal is a set, there exists a minimal non-zero ordinal, ${\displaystyle \beta }$, such that there is no surjective function from ${\displaystyle B}$ to ${\displaystyle \beta }$. We assume without loss of generality that the sets ${\displaystyle B}$ and ${\displaystyle \beta }$ are disjoint. By the initial assumption, ${\displaystyle |B\cup \beta |=|(B\cup \beta )\times (B\cup \beta )|}$, thus there exists a bijection ${\displaystyle f:B\cup \beta \to (B\cup \beta )\times (B\cup \beta )}$.

For every ${\displaystyle x\in B}$, it is impossible that ${\displaystyle \beta \times \{x\}\subseteq f[B]}$, because otherwise we could define a surjective function from ${\displaystyle B}$ to ${\displaystyle \beta }$. Therefore, there exists at least one ordinal ${\displaystyle \gamma \in \beta }$ such that ${\displaystyle f(\gamma )\in \beta \times \{x\}}$, so the set ${\displaystyle S_{x}=\{\gamma |f(\gamma )\in \beta \times \{x\}\}}$ is not empty.

We can define a new function: ${\displaystyle g(x)=\min S_{x}}$. This function is well defined since ${\displaystyle S_{x}}$ is a non-empty set of ordinals, and so has a minimum. For every ${\displaystyle x,y\in B,x\neq y}$ the sets ${\displaystyle S_{x}}$ and ${\displaystyle S_{y}}$ are disjoint. Therefore, we can define a well order on ${\displaystyle B}$, for every ${\displaystyle x,y\in B}$ we define ${\displaystyle x\leq y\iff g(x)\leq g(y)}$, since the image of ${\displaystyle g}$, i.e. ${\displaystyle g[B]}$, is a set of ordinals and therefore well ordered.

• Rubin, Herman; Rubin, Jean E. (1985), Equivalents of the Axiom of Choice II, North Holland/Elsevier, ISBN 0-444-87708-8
• Mycielski, Jan (2006), "A system of axioms of set theory for the rationalists" (PDF), Notices of the American Mathematical Society, 53 (2): 209
• Tarski, A. (1924), "Sur quelques theorems qui equivalent a l'axiome du choix", Fundamenta Mathematicae, 5: 147–154