Tarski's axiomatization of the reals
Encyclopedia
In 1936, Alfred Tarski
set out an axiomatization of the real number
s and their arithmetic, consisting of only the 8 axiom
s shown below and a mere four primitive notion
s: the set of reals denoted R, a binary
total order
over R, denoted by infix <, a binary operation
of addition over R, denoted by infix +, and the constant 1.
The literature occasionally mentions this axiomatization but never goes into detail, notwithstanding its economy and elegant metamathematical properties. This axiomatization appears little known, possibly because of its second-order
nature. Tarski's axiomatization can be seen as a version of the more usual definition of real numbers as the unique Dedekind-complete ordered field
; it is however made much more concise by using unorthodox variants of standard algebraic axioms and other subtle tricks (see e.g. axioms 4 and 5, which combine together the usual four axioms of Abelian group
s).
The term "Tarski's axiomatization of real numbers" also refers to the theory of real-closed fields, which Tarski showed completely axiomatizes the first-order
theory of the structure 〈R, +, ·, <〉.
Axiom 1 :If x < y, then not y < x. That is, "<" is an asymmetric relation
.
Axiom 2 :If x < z, there exists a y such that x < y and y < z. In other words, "<" is dense
in R.
Axiom 3 :"<" is Dedekind-complete. More formally, for all X, Y ⊆ R, if for all x ∈ X and y ∈ Y, x < y, then there exists a z such that for all x ∈ X and y ∈ Y, x ≤ z and z ≤ y. Here, u ≤ v is a shorthand for "u < v or u = v".
To clarify the above statement somewhat, let X ⊆ R and Y ⊆ R. We now define two common English verbs in a particular way that suits our purpose:
Axiom 3 can then be stated as:
Axioms of addition (primitives: R, <, +):
Axiom 4 :x + (y + z) = (x + z) + y.
Axiom 5 :For all x, y, there exists a z such that x + z = y.
Axiom 6 :If x + y < z + w, then x < z or y < w.
Axioms for one (primitives: R, <, +, 1):
Axiom 7 :1 ∈ R.
Axiom 8 :1 < 1 + 1.
These axioms imply that R is a linearly ordered
Abelian group
under addition with distinguished element 1. R is also Dedekind-complete and divisible
.
This axiomatization does not give rise to a first-order theory
, because the formal statement of axiom 3 includes two universal quantifiers over all possible subsets of R. Tarski proved these 8 axioms and 4 primitive notions independent.
called multiplication and having the expected properties, so that R is a complete ordered field
under addition and multiplication. This proof builds crucially on addition being an abelian group over the integers and has its origins in Eudoxus'
definition of magnitude.
Alfred Tarski
Alfred Tarski was a Polish logician and mathematician. Educated at the University of Warsaw and a member of the Lwow-Warsaw School of Logic and the Warsaw School of Mathematics and philosophy, he emigrated to the USA in 1939, and taught and carried out research in mathematics at the University of...
set out an axiomatization of the real number
Real number
In mathematics, a real number is a value that represents a quantity along a continuum, such as -5 , 4/3 , 8.6 , √2 and π...
s and their arithmetic, consisting of only the 8 axiom
Axiom
In traditional logic, an axiom or postulate is a proposition that is not proven or demonstrated but considered either to be self-evident or to define and delimit the realm of analysis. In other words, an axiom is a logical statement that is assumed to be true...
s shown below and a mere four primitive notion
Primitive notion
In mathematics, logic, and formal systems, a primitive notion is an undefined concept. In particular, a primitive notion is not defined in terms of previously defined concepts, but is only motivated informally, usually by an appeal to intuition and everyday experience. In an axiomatic theory or...
s: the set of reals denoted R, a binary
Binary relation
In mathematics, a binary relation on a set A is a collection of ordered pairs of elements of A. In other words, it is a subset of the Cartesian product A2 = . More generally, a binary relation between two sets A and B is a subset of...
total order
Total order
In set theory, a total order, linear order, simple order, or ordering is a binary relation on some set X. The relation is transitive, antisymmetric, and total...
over R, denoted by infix <, a binary operation
Binary operation
In mathematics, a binary operation is a calculation involving two operands, in other words, an operation whose arity is two. Examples include the familiar arithmetic operations of addition, subtraction, multiplication and division....
of addition over R, denoted by infix +, and the constant 1.
The literature occasionally mentions this axiomatization but never goes into detail, notwithstanding its economy and elegant metamathematical properties. This axiomatization appears little known, possibly because of its second-order
Second-order logic
In logic and mathematics second-order logic is an extension of first-order logic, which itself is an extension of propositional logic. Second-order logic is in turn extended by higher-order logic and type theory....
nature. Tarski's axiomatization can be seen as a version of the more usual definition of real numbers as the unique Dedekind-complete ordered field
Ordered field
In mathematics, an ordered field is a field together with a total ordering of its elements that is compatible with the field operations. Historically, the axiomatization of an ordered field was abstracted gradually from the real numbers, by mathematicians including David Hilbert, Otto Hölder and...
; it is however made much more concise by using unorthodox variants of standard algebraic axioms and other subtle tricks (see e.g. axioms 4 and 5, which combine together the usual four axioms of Abelian group
Abelian group
In abstract algebra, an abelian group, also called a commutative group, is a group in which the result of applying the group operation to two group elements does not depend on their order . Abelian groups generalize the arithmetic of addition of integers...
s).
The term "Tarski's axiomatization of real numbers" also refers to the theory of real-closed fields, which Tarski showed completely axiomatizes the first-order
First-order logic
First-order logic is a formal logical system used in mathematics, philosophy, linguistics, and computer science. It goes by many names, including: first-order predicate calculus, the lower predicate calculus, quantification theory, and predicate logic...
theory of the structure 〈R, +, ·, <〉.
The axioms
Axioms of order (primitives: R, <):Axiom 1 :If x < y, then not y < x. That is, "<" is an asymmetric relation
Asymmetric relation
Asymmetric often means, simply: not symmetric. In this sense an asymmetric relation is a binary relation which is not a symmetric relation.That is,\lnot....
.
Axiom 2 :If x < z, there exists a y such that x < y and y < z. In other words, "<" is dense
Dense order
In mathematics, a partial order ≤ on a set X is said to be dense if, for all x and y in X for which x In mathematics, a partial order ≤ on a set X is said to be dense if, for all x and y in X for which x...
in R.
Axiom 3 :"<" is Dedekind-complete. More formally, for all X, Y ⊆ R, if for all x ∈ X and y ∈ Y, x < y, then there exists a z such that for all x ∈ X and y ∈ Y, x ≤ z and z ≤ y. Here, u ≤ v is a shorthand for "u < v or u = v".
To clarify the above statement somewhat, let X ⊆ R and Y ⊆ R. We now define two common English verbs in a particular way that suits our purpose:
- X precedes Y if and only if for every x ∈ X and every y ∈ Y, x < y.
- The real number z separates X and Y if and only if for every x ∈ X with x ≠ z and every y ∈ Y with y ≠ z, x < z and z < y.
Axiom 3 can then be stated as:
- "If a set of reals precedes another set of reals, then there exists at least one real number separating the two sets."
Axioms of addition (primitives: R, <, +):
Axiom 4 :x + (y + z) = (x + z) + y.
Axiom 5 :For all x, y, there exists a z such that x + z = y.
Axiom 6 :If x + y < z + w, then x < z or y < w.
Axioms for one (primitives: R, <, +, 1):
Axiom 7 :1 ∈ R.
Axiom 8 :1 < 1 + 1.
These axioms imply that R is a linearly ordered
Linearly ordered group
In abstract algebra a linearly ordered or totally ordered group is an ordered group G such that the order relation "≤" is total...
Abelian group
Abelian group
In abstract algebra, an abelian group, also called a commutative group, is a group in which the result of applying the group operation to two group elements does not depend on their order . Abelian groups generalize the arithmetic of addition of integers...
under addition with distinguished element 1. R is also Dedekind-complete and divisible
Divisible group
In mathematics, especially in the field of group theory, a divisible group is an abelian group in which every element can, in some sense, be divided by positive integers, or more accurately, every element is an nth multiple for each positive integer n...
.
This axiomatization does not give rise to a first-order theory
First-order logic
First-order logic is a formal logical system used in mathematics, philosophy, linguistics, and computer science. It goes by many names, including: first-order predicate calculus, the lower predicate calculus, quantification theory, and predicate logic...
, because the formal statement of axiom 3 includes two universal quantifiers over all possible subsets of R. Tarski proved these 8 axioms and 4 primitive notions independent.
How these axioms imply a field
Tarski sketched the (nontrivial) proof of how these axioms and primitives imply the existence of a binary operationBinary operation
In mathematics, a binary operation is a calculation involving two operands, in other words, an operation whose arity is two. Examples include the familiar arithmetic operations of addition, subtraction, multiplication and division....
called multiplication and having the expected properties, so that R is a complete ordered field
Ordered field
In mathematics, an ordered field is a field together with a total ordering of its elements that is compatible with the field operations. Historically, the axiomatization of an ordered field was abstracted gradually from the real numbers, by mathematicians including David Hilbert, Otto Hölder and...
under addition and multiplication. This proof builds crucially on addition being an abelian group over the integers and has its origins in Eudoxus'
Eudoxus of Cnidus
Eudoxus of Cnidus was a Greek astronomer, mathematician, scholar and student of Plato. Since all his own works are lost, our knowledge of him is obtained from secondary sources, such as Aratus's poem on astronomy...
definition of magnitude.