Tarski's Theorem About Choice
   HOME

TheInfoList



OR:

In
mathematics Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many ar ...
, Tarski's theorem, proved by , states that in ZF the theorem "For every infinite set A, there is a
bijective map In mathematics, a bijection, bijective function, or one-to-one correspondence is a function between two sets such that each element of the second set (the codomain) is the image of exactly one element of the first set (the domain). Equivale ...
between the sets A and A\times A" implies the
axiom of choice In mathematics, the axiom of choice, abbreviated AC or AoC, is an axiom of set theory. Informally put, the axiom of choice says that given any collection of non-empty sets, it is possible to construct a new set by choosing one element from e ...
. The opposite direction was already known, thus the theorem and axiom of choice are equivalent. Tarski told that when he tried to publish the theorem in '' Comptes Rendus de l'Académie des Sciences de Paris'', 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.


Proof

The goal is to prove that the axiom of choice is implied by the statement "for every infinite set A: , A, = , A \times A, ". It is known that the
well-ordering theorem In mathematics, the well-ordering theorem, also known as Zermelo's theorem, states that every set can be well-ordered. A set ''X'' is ''well-ordered'' by a strict total order if every non-empty subset of ''X'' has a least element under the order ...
is equivalent to the axiom of choice; thus it is enough to show that the statement implies that for every set B there exists a
well-order In mathematics, a well-order (or well-ordering or well-order relation) on a set is a total ordering on with the property that every non-empty subset of has a least element in this ordering. The set together with the ordering is then calle ...
. Since the collection of all ordinals such that there exists a
surjective function In mathematics, a surjective function (also known as surjection, or onto function ) is a function such that, for every element of the function's codomain, there exists one element in the function's domain such that . In other words, for a ...
from B to the ordinal is a set, there exists an infinite ordinal, \beta, such that there is no
surjective function In mathematics, a surjective function (also known as surjection, or onto function ) is a function such that, for every element of the function's codomain, there exists one element in the function's domain such that . In other words, for a ...
from B to \beta. We assume
without loss of generality ''Without loss of generality'' (often abbreviated to WOLOG, WLOG or w.l.o.g.; less commonly stated as ''without any loss of generality'' or ''with no loss of generality'') is a frequently used expression in mathematics. The term is used to indicat ...
that the sets B and \beta are disjoint. By the initial assumption, , B \cup \beta, = , (B \cup \beta) \times (B \cup \beta), , thus there exists a
bijection In mathematics, a bijection, bijective function, or one-to-one correspondence is a function between two sets such that each element of the second set (the codomain) is the image of exactly one element of the first set (the domain). Equival ...
f : B \cup \beta \to (B \cup \beta) \times (B \cup \beta). For every x \in B, it is impossible that \beta \times \ \subseteq f because otherwise we could define a surjective function from B to \beta. Therefore, there exists at least one ordinal \gamma \in \beta such that f(\gamma) \in \beta \times \, so the set S_x = \ is not empty. We can define a new function: g(x) = \min S_x. This function is well defined since S_x is a non-empty set of ordinals, and so has a minimum. For every x, y \in B, x \neq y the sets S_x and S_y are disjoint. Therefore, we can define a well order on B, for every x, y \in B we define x \leq y \iff g(x) \leq g(y), since the image of g, that is, g /math> is a set of ordinals and therefore well ordered.


References

* * * {{Set theory Axiom of choice Cardinal numbers Set theory Theorems in the foundations of mathematics fr:Ordinal de Hartogs#Produit cardinal