Editing Tarski's theorem about choice

{{Short description|Theorem equivalent to the Axiom of Choice}}
In [[mathematics]], '''Tarski's theorem''', proved by {{harvs|txt|first=Alfred|last= Tarski|authorlink=Alfred Tarski|year=1924}}, states that in [[Zermelo–Fraenkel set theory|ZF]] the theorem "For every infinite set <math>A</math>, there is a [[bijective map]] between the sets  <math>A</math> and <math>A\times A</math>" implies the [[axiom of choice]]. The opposite direction was already known, thus the theorem and axiom of choice are equivalent.

Tarski told {{harvs|first=Jan|last=Mycielski|authorlink=Jan Mycielski|year=2006|txt}} that when he tried to publish the theorem in ''[[Comptes Rendus de l'Académie des Sciences de Paris]]'', [[Maurice René Fréchet|Fréchet]] and [[Henri Lebesgue|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.

==Proof==

The goal is to prove that the axiom of choice is implied by the statement "for every infinite set <math>A:</math> <math>|A| = |A \times A|</math>". 
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 <math>B</math> there exists a [[well-order]].

Since the collection of all [[Ordinal number|ordinals]] such that there exists a [[surjective function]] from <math>B</math> to the ordinal is a set, there exists an infinite ordinal, <math>\beta,</math> such that there is no [[surjective function]] from <math>B</math> to <math>\beta.</math> 
We assume [[without loss of generality]] that the sets <math>B</math> and <math>\beta</math> are [[Disjoint sets|disjoint]]. 
By the initial assumption, <math>|B \cup \beta| = |(B \cup \beta) \times (B \cup \beta)|,</math> thus there exists a [[bijection]] <math>f : B \cup \beta \to (B \cup \beta) \times (B \cup \beta).</math>

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

We can define a new function: <math>g(x) = \min S_x.</math> 
This function is well defined since <math>S_x</math> is a non-empty set of ordinals, and so has a minimum. 
For every <math>x, y \in B, x \neq y</math> the sets <math>S_x</math> and <math> S_y</math> are disjoint. 
Therefore, we can define a well order on <math>B,</math> for every <math>x, y \in B</math> we define <math>x \leq y \iff g(x) \leq g(y),</math> since the image of <math>g,</math> that is, <math>g[B]</math> is a set of ordinals and therefore well ordered.

==References==

{{reflist}}

* {{citation|first1= Herman|last1= Rubin|first2= Jean E.|last2= Rubin|author2-link= Jean E. Rubin|title= Equivalents of the Axiom of Choice II|publisher= North Holland/Elsevier|year= 1985|isbn= 0-444-87708-8|title-link= Equivalents of the Axiom of Choice}}
* {{citation|title=A system of axioms of set theory for the rationalists|journal=[[Notices of the American Mathematical Society]]|volume=53|issue=2|pages=209|year=2006|first=Jan|last=Mycielski|authorlink=Jan Mycielski|url=http://www.ams.org/notices/200602/fea-mycielski.pdf}}
* {{citation|last=Tarski|first= A.|title= Sur quelques theorems qui equivalent a l'axiome du choix|journal=[[Fundamenta Mathematicae]] |volume= 5 |year=1924|pages= 147–154 |doi= 10.4064/fm-5-1-147-154|url=http://pldml.icm.edu.pl/pldml/element/bwmeta1.element.bwnjournal-article-fmv5i1p18bwm|doi-access= free}}

{{Mathematical logic}}
{{Set theory}}

[[Category:Axiom of choice]]
[[Category:Cardinal numbers]]
[[Category:Set theory]]
[[Category:Theorems in the foundations of mathematics]]

[[fr:Ordinal de Hartogs#Produit cardinal]]