Tarski's axiomatization of the reals

Last updated

In 1936, Alfred Tarski gave an axiomatization of the real numbers and their arithmetic, consisting of only the eight axioms shown below and a mere four primitive notions: [1] the set of reals denoted R, a binary relation over R, denoted by infix <, a binary operation of addition over R, denoted by infix +, and the constant 1.

Contents

Tarski's axiomatization, which is a second-order theory, 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 avoiding multiplication altogether and using unorthodox variants of standard algebraic axioms and other subtle tricks. Tarski did not supply a proof that his axioms are sufficient or a definition for the multiplication of real numbers in his system.

Tarski also studied the first-order theory of the structure (R, +, ·, <), leading to a set of axioms for this theory and to the concept of real closed fields.

The axioms

Axioms of order (primitives: R, <)

Axiom 1
If x < y, then not y < x.
[That is, "<" is an asymmetric relation. This implies that "<" is irreflexive, i.e., for all x, not x < x.]
Axiom 2
If x < z, there exists a y such that x < y and y < z.
Axiom 3
For all subsets 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, if x  z and y  z, then x < z and z < y.
[In other words, "<" is Dedekind-complete, or informally: "If a set of reals X precedes another set of reals Y, then there exists at least one real number z separating the two sets."
This is a second-order axiom as it refers to sets and not just elements.]

Axioms of addition (primitives: R, <, +)

Axiom 4
x + (y + z) = (x + z) + y.
[Note that this is an unorthodox mixture of associativity and commutativity.]
Axiom 5
For all x, y, there exists a z such that x + z = y.
[This allows subtraction and also gives a 0.]
Axiom 6
If x + y < z + w, then x < z or y < w.
[This is the contrapositive of a standard axiom for ordered groups.]

Axioms for 1 (primitives: R, <, +, 1)

Axiom 7
1  R.
Axiom 8
1 < 1 + 1.

Discussion

Tarski stated, without proof, that these axioms turn the relation < into a total ordering. The missing component was supplied in 2008 by Stefanie Ucsnay. [2]

The axioms then imply that R is a linearly ordered abelian group under addition with distinguished positive element 1, and that this group is Dedekind-complete, divisible, and Archimedean.

Tarski never proved that these axioms and primitives imply the existence of a binary operation called multiplication that has the expected properties, so that R becomes a complete ordered field under addition and multiplication. It is possible to define this multiplication operation by considering certain order-preserving homomorphisms of the ordered group (R,+,<). [3]

Related Research Articles

<span class="mw-page-title-main">Axiom of choice</span> Axiom of set theory

In mathematics, the axiom of choice, abbreviated AC or AoC, 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 collection of sets, each containing at least one element, it is possible to construct a new set by choosing one element from each set, even if the collection is infinite. Formally, it states that for every indexed family of nonempty sets, there exists an indexed set such that for every . The axiom of choice was formulated in 1904 by Ernst Zermelo in order to formalize his proof of the well-ordering theorem.

Naive set theory is any of several theories of sets used in the discussion of the foundations of mathematics. Unlike axiomatic set theories, which are defined using formal logic, naive set theory is defined informally, in natural language. It describes the aspects of mathematical sets familiar in discrete mathematics, and suffices for the everyday use of set theory concepts in contemporary mathematics.

First-order logic—also known as predicate logic, quantificational logic, and first-order predicate calculus—is a collection of formal systems used in mathematics, philosophy, linguistics, and computer science. First-order logic uses quantified variables over non-logical objects, and allows the use of sentences that contain variables, so that rather than propositions such as "Socrates is a man", one can have expressions in the form "there exists x such that x is Socrates and x is a man", where "there exists" is a quantifier, while x is a variable. This distinguishes it from propositional logic, which does not use quantifiers or relations; in this sense, propositional logic is the foundation of first-order logic.

In mathematical logic, the Peano axioms, also known as the Dedekind–Peano axioms or the Peano postulates, are axioms for the natural numbers presented by the 19th-century Italian mathematician Giuseppe Peano. These axioms have been used nearly unchanged in a number of metamathematical investigations, including research into fundamental questions of whether number theory is consistent and complete.

In mathematics, equality is a relationship between two quantities or, more generally, two mathematical expressions, asserting that the quantities have the same value, or that the expressions represent the same mathematical object. Equality between A and B is written A = B, and pronounced "A equals B". The symbol "=" is called an "equals sign". Two objects that are not equal are said to be distinct.

In set theory, Zermelo–Fraenkel set theory, named after mathematicians Ernst Zermelo and Abraham Fraenkel, is an axiomatic system that was proposed in the early twentieth century in order to formulate a theory of sets free of paradoxes such as Russell's paradox. Today, Zermelo–Fraenkel set theory, with the historically controversial axiom of choice (AC) included, is the standard form of axiomatic set theory and as such is the most common foundation of mathematics. Zermelo–Fraenkel set theory with the axiom of choice included is abbreviated ZFC, where C stands for "choice", and ZF refers to the axioms of Zermelo–Fraenkel set theory with the axiom of choice excluded.

In mathematics, there are several equivalent ways of defining the real numbers. One of them is that they form a complete ordered field that does not contain any smaller complete ordered field. Such a definition does not prove that such a complete ordered field exists, and the existence proof consists of constructing a mathematical structure that satisfies the definition.

In abstract algebra, a semiring is an algebraic structure. It is a generalization of a ring, dropping the requirement that each element must have an additive inverse. At the same time, it is a generalization of bounded distributive lattices.

Tarski's axioms are an axiom system for Euclidean geometry, specifically for that portion of Euclidean geometry that is formulable in first-order logic with identity. As such, it does not require an underlying set theory. The only primitive objects of the system are "points" and the only primitive predicates are "betweenness" and "congruence". The system contains infinitely many axioms.

In mathematics, Robinson arithmetic is a finitely axiomatized fragment of first-order Peano arithmetic (PA), first set out by Raphael M. Robinson in 1950. It is usually denoted Q. Q is almost PA without the axiom schema of mathematical induction. Q is weaker than PA but it has the same language, and both theories are incomplete. Q is important and interesting because it is a finitely axiomatized fragment of PA that is recursively incompletable and essentially undecidable.

In mathematical logic, second-order arithmetic is a collection of axiomatic systems that formalize the natural numbers and their subsets. It is an alternative to axiomatic set theory as a foundation for much, but not all, of mathematics.

In mathematics and abstract algebra, a relation algebra is a residuated Boolean algebra expanded with an involution called converse, a unary operation. The motivating example of a relation algebra is the algebra 2X 2 of all binary relations on a set X, that is, subsets of the cartesian square X2, with RS interpreted as the usual composition of binary relations R and S, and with the converse of R as the converse relation.

Axiomatic constructive set theory is an approach to mathematical constructivism following the program of axiomatic set theory. The same first-order language with "" and "" of classical set theory is usually used, so this is not to be confused with a constructive types approach. On the other hand, some constructive theories are indeed motivated by their interpretability in type theories.

Tarski–Grothendieck set theory is an axiomatic set theory. It is a non-conservative extension of Zermelo–Fraenkel set theory (ZFC) and is distinguished from other axiomatic set theories by the inclusion of Tarski's axiom, which states that for each set there is a Grothendieck universe it belongs to. Tarski's axiom implies the existence of inaccessible cardinals, providing a richer ontology than ZFC. For example, adding this axiom supports category theory.

In mathematics, point-free geometry is a geometry whose primitive ontological notion is region rather than point. Two axiomatic systems are set out below, one grounded in mereology, the other in mereotopology and known as connection theory.

General set theory (GST) is George Boolos's (1998) name for a fragment of the axiomatic set theory Z. GST is sufficient for all mathematics not requiring infinite sets, and is the weakest known set theory whose theorems include the Peano axioms.

In mathematics, a residuated Boolean algebra is a residuated lattice whose lattice structure is that of a Boolean algebra. Examples include Boolean algebras with the monoid taken to be conjunction, the set of all formal languages over a given alphabet Σ under concatenation, the set of all binary relations on a given set X under relational composition, and more generally the power set of any equivalence relation, again under relational composition. The original application was to relation algebras as a finitely axiomatized generalization of the binary relation example, but there exist interesting examples of residuated Boolean algebras that are not relation algebras, such as the language example.

<span class="mw-page-title-main">Real number</span> Number representing a continuous quantity

In mathematics, a real number is a number that can be used to measure a continuous one-dimensional quantity such as a distance, duration or temperature. Here, continuous means that pairs of values can have arbitrarily small differences. Every real number can be almost uniquely represented by an infinite decimal expansion.

In mathematical logic, Tarski's high school algebra problem was a question posed by Alfred Tarski. It asks whether there are identities involving addition, multiplication, and exponentiation over the positive integers that cannot be proved using eleven axioms about these operations that are taught in high-school-level mathematics. The question was solved in 1980 by Alex Wilkie, who showed that such unprovable identities do exist.

References

  1. Tarski, Alfred (24 March 1994). Introduction to Logic and to the Methodology of Deductive Sciences (4 ed.). Oxford University Press. ISBN   978-0-19-504472-0.
  2. Ucsnay, Stefanie (Jan 2008). "A Note on Tarski's Note". The American Mathematical Monthly. 115 (1): 66–68. JSTOR   27642393.
  3. Arthan, Rob D. (2001). "An Irrational Construction of ℝ from ℤ" (PDF). Theorem Proving in Higher Order Logics. Lecture Notes in Computer Science. Berlin, Heidelberg: Springer: 43–58. doi:10.1007/3-540-44755-5_5. Section 4