In
mathematics
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
, Tarski's theorem, proved by , states that in
ZF the theorem "For every infinite set
, there is a
bijective map
In mathematics, a bijection, also known as a bijective function, one-to-one correspondence, or invertible function, is a function between the elements of two sets, where each element of one set is paired with exactly one element of the other s ...
between the sets
and
" implies the
axiom of choice
In mathematics, the axiom of choice, or AC, is an axiom of set theory equivalent to the statement that ''a Cartesian product of a collection of non-empty sets is non-empty''. Informally put, the axiom of choice says that given any collectio ...
. 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 Paris,
Fréchet and
Lebesgue
Henri Léon Lebesgue (; June 28, 1875 – July 26, 1941) was a French mathematician known for his theory of integration, which was a generalization of the 17th-century concept of integration—summing the area between an axis and the curve of ...
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
".
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 orde ...
is equivalent to the axiom of choice; thus it is enough to show that the statement implies that for every set
there exists a
well-order
In mathematics, a well-order (or well-ordering or well-order relation) on a set ''S'' is a total order on ''S'' with the property that every non-empty subset of ''S'' has a least element in this ordering. The set ''S'' together with the well-orde ...
.
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 that every element can be mapped from element so that . In other words, every element of the function's codomain is the image of one element of i ...
from
to the ordinal is a set, there exists an infinite ordinal,
such that there is no
surjective function
In mathematics, a surjective function (also known as surjection, or onto function) is a function that every element can be mapped from element so that . In other words, every element of the function's codomain is the image of one element of i ...
from
to
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 indicate ...
that the sets
and
are
disjoint.
By the initial assumption,
thus there exists a
bijection
In mathematics, a bijection, also known as a bijective function, one-to-one correspondence, or invertible function, is a function between the elements of two sets, where each element of one set is paired with exactly one element of the other s ...
For every
it is impossible that
because otherwise we could define a surjective function from
to
Therefore, there exists at least one ordinal
such that
so the set
is not empty.
We can define a new function:
This function is well defined since
is a non-empty set of ordinals, and so has a minimum.
For every
the sets
and
are disjoint.
Therefore, we can define a well order on
for every
we define
since the image of
that is,