Tarski's theorem about choice
In mathematics, Tarski's theorem, proved by Alfred Tarski (1924), states that in ZF the theorem "For every infinite set , there is a bijective map between the sets and " implies the axiom of choice. The opposite direction was already known, thus the theorem and axiom of choice are equivalent.
Tarski told Jan Mycielski (2006) 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 ". 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 there exists a well-order.
Since the collection of all ordinals such that there exists a surjective function from to the ordinal is a set, there exists an infinite ordinal, such that there is no surjective function from to We assume without loss of generality that the sets and are disjoint. By the initial assumption, thus there exists a bijection
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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:6011/en.wikipedia.org/v1/":): {\displaystyle S_x} and are disjoint. Therefore, we can define a well order on for every we define since the image of that is, is a set of ordinals and therefore well ordered.
References
- 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, doi:10.4064/fm-5-1-147-154
- v
- t
- e
- Axiom
- Cardinality
- First-order logic
- Formal proof
- Formal semantics
- Foundations of mathematics
- Information theory
- Lemma
- Logical consequence
- Model
- Theorem
- Theory
- Type theory
and paradoxes
Traditional | |
---|---|
Propositional | |
Predicate |
|
| |
Types of sets |
|
---|---|
Maps and cardinality |
|
Set theories |
language and syntax
| |
Example axiomatic systems (list) |
---|
- Interpretation
- function
- of models
- Model
- equivalence
- finite
- saturated
- spectrum
- submodel
- Non-standard model
- Diagram
- Categorical theory
- Model complete theory
- Satisfiability
- Semantics of logic
- Strength
- Theories of truth
- T-schema
- Transfer principle
- Truth predicate
- Truth value
- Type
- Ultraproduct
- Validity
![icon](http://upload.wikimedia.org/wikipedia/commons/thumb/3/3e/Nuvola_apps_edu_mathematics_blue-p.svg/16px-Nuvola_apps_edu_mathematics_blue-p.svg.png)