101.170.213.60: /* Morphological analysis */ deleted pointless reference to presentism~~~~

2015-01-05T09:32:21Z

Morphological analysis: deleted pointless reference to presentism~~~~

Show changes

124.169.84.116 at 05:56, 1 March 2014

2014-03-01T05:56:24Z

Show changes

en>WereSpielChequers: not cowboys

2014-01-19T21:54:42Z

not cowboys

New page

In [[mathematics]], the '''Tarski's theorem''', proved by [[Alfred Tarski]], 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.

When Tarski tried to publish the theorem in Comptes Rendus Acad. Sci. 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.
<ref>{{cite journal|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|author=Jan Mycielski|url=http://www.ams.org/notices/200602/fea-mycielski.pdf}}</ref>
== Proof ==
Our 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 exist a [[well-order]].

For finite sets it is trivial, thus we will assume that <math>B</math> is infinite.

Since the collection of all [[Ordinal number|ordinals]] such that there exist a [[surjective function]] from <math>B</math> to the ordinal is a set, there exist a minimal 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 our 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>, thus the set <math> S_x=\{\gamma | f(\gamma) \in \beta \times \{x\}\}</math> is not empty.

With this fact in our mind 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, hence it has a minimum.
Recall that 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 shall define <math>x \leq y \iff g(x) \leq g(y)</math>, since the image of <math>g</math>, i.e. <math>g[B]</math>, is a set of ordinals and therefore well ordered.

==References==
{{Reflist}}

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

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

Hand axe - Revision history

101.170.213.60: /* Morphological analysis */ deleted pointless reference to presentism~~~~

124.169.84.116 at 05:56, 1 March 2014

en>WereSpielChequers: not cowboys