Tarski's axioms
Encyclopedia
Tarski's axioms, due to Alfred Tarski
, are an axiom set for the substantial fragment of Euclidean geometry
, called "elementary
," that is formulable in first-order logic
with identity
, and requiring no set theory
. Other modern axiomizations of Euclidean geometry are those by Hilbert
and George Birkhoff
.
Givant's then says "with typical thoroughness" Tarski devised his system:
Like other modern axiomatizations of Euclidean geometry, Tarski's employs a formal system
consisting of symbol strings, called sentence
s, whose construction respects formal syntactical rules
, and rules of proof that determine the allowed manipulations of the sentences. Unlike some other modern axiomatizations, such as Birkhoff's
and Hilbert's
, Tarski's axiomatization has no primitive objects other than points, so a variable or constant cannot refer to a line or an angle. Because points are the only primitive objects, and because Tarski's system is a first-order theory, it is not even possible to define lines as sets of points. The only primitive relations (predicates) are "betweenness" and "congruence" among points.
Tarski's axiomatization is shorter than its rivals, in a sense Tarski and Givant (1999) make explicit. It is more concise than Pieri's because Pieri had only two primitive notions while Tarski introduced three: point, betweenness, and congruence. Such economy of primitive and defined notions means that Tarski's system is not very convenient for doing Euclidian geometry. Rather, Tarski designed his system to facilitate its analysis via the tools of mathematical logic
, i.e., to facilitate deriving its metamathematical properties. Tarski's system has the unusual property that all sentences can be written in universal-existential form, a special case of the prenex normal form
. This form has all universal quantifiers
preceding any existential quantifiers
, so that all sentences can be recast in the form
This fact allowed Tarski to prove that Euclidean geometry is decidable
: there exists an algorithm
which can determine the truth or falsity of any sentence. Tarski's axiomatization is also complete. This does not contradict Gödel's first incompleteness theorem, because Tarski's theory lacks the expressive power needed to interpret Robinson arithmetic
.
worked on the axiomatization and metamathematics of Euclidean geometry
intermittently from 1926 until his 1983 death, with Tarski (1959) heralding his mature interest in the subject. The work of Tarski and his students on Euclidean geometry culminated in the monograph Schwabhäuser, Szmielew, and Tarski (1983), which set out the 10 axiom
s and one axiom schema
shown below, the associated metamathematics
, and a fair bit of the subject. Gupta (1965) made important contributions, and Tarski and Givant (1999) discuss the history.
. This objective required reformulating that geometry as a first-order theory
. Tarski did so by positing a universe
of point
s, with lower case letters denoting variables ranging over that universe. He then posited two primitive relations:
Betweenness captures the affine
aspect of Euclidean geometry; congruence, its metric
aspect. The background logic includes identity
, a binary relation
. The axioms invoke identity (or its negation) on five occasions.
The axioms below are grouped by the types of relation they invoke, then sorted, first by the number of existential quantifiers, then by the number of atomic sentences. The axioms should be read as universal closures; hence any free variables should be taken as tacitly universally quantified.
The distance from x to y is the same as that from y to x. This axiom asserts a property very similar to symmetry
for binary relation
s.
Identity of Congruence:
If xy is congruent with a segment that begins and ends at the same point, x and y are the same point. This is closely related to the notion of reflexivity for binary relation
s.
Transitivity
of Congruence:
Two line segments both congruent to a third segment are congruent to each other; all three segments have the same length. This axiom asserts that congruence is Euclidean
, in that it respects the first of Euclid's
"common notions." Hence this axiom could have been named "Congruence is Euclidean." The transitivity of congruence is an easy consequence of this axiom and Reflexivity.
It is not possible for a point to be "between" a point; points are indivisible.
Axiom of Pasch
Draw line segments connecting any two vertices
of a given triangle
with the sides opposite the vertices. These two line segments must then intersect at some point inside the triangle.
Axiom schema
of Continuity
Let φ(x) and ψ(y) be first-order formulae containing no free instances of either a or b. Let there also be no free instances of x in ψ(y) or of y in φ(x). Then all instances of the following schema are axioms:
Let r be a ray with endpoint a. Let the first order formulae φ and ψ define subsets X and Y of r, such that every point in Y is to the right of every point of X (with respect to a). Then there exists a point b in r lying between X and Y. This is essentially the Dedekind cut
construction, carried out in a way that avoids quantification over sets.
Lower Dimension
In short, there exist three noncollinear points, and any model
of these axioms must have dimension
> 1.
Three points equidistant from two distinct points form a line. Hence any model
of these axioms must have dimension
< 3.
Axiom of Euclid
Each of the three variants of this axiom, all equivalent over the remaining Tarski's axioms to Euclid's parallel postulate
, has an advantage over the others:
Let a line segment join the midpoint of two sides of a given triangle
. That line segment will be half as long as the third side. This is equivalent to the interior angles of any triangle summing to two right angles.
Given any triangle
, there exists a circle
that includes all of its vertices.
Given any angle
and any point v in its interior, there exists a line segment including v, with an endpoint on each side of the angle.
Five Segment
Begin with two triangle
s, xuz and x'u'z'. Draw the line segments yu and y'u', connecting a vertex of each triangle to a point on the side opposite to the vertex. The result is two divided triangles, each made up of five segments. If four segments of one triangle are each congruent
to a segment in the other triangle, then the fifth segments in both triangles must be congruent.
Segment Construction
Given any two line segments, the second can be "extended" by a line segment congruent
to the first.
whose fields are a dense universe
of point
s, Tarski built a geometry of line segment
s. According to Tarski and Givant (1999: 192-93), none of the above axiom
s is fundamentally new. The first four axioms establish some elementary properties of the two primitive relations. For instance, Reflexivity and Transitivity of Congruence establish that congruence is an equivalence relation
over line segments. The Identity of Congruence and of Betweenness govern the trivial case when those relations are applied to nondistinct points. The theorem xy≡zz ↔ x=y ↔ Bxyx extends these Identity axioms.
A number of other properties of Betweenness are derivable as theorems including:
The last two properties totally order
the points making up a line segment.
Upper and Lower Dimension together require that any model of these axioms have a specific finite dimension
ality. Suitable changes in these axioms yield axiom sets for Euclidean geometry
for dimension
s 0, 1, and greater than 2 (Tarski and Givant 1999: Axioms 8(1), 8(n), 9(0), 9(1), 9(n) ). Note that solid geometry
requires no new axioms, unlike the case with Hilbert's axioms
. Moreover, Lower Dimension for n dimensions is simply the negation of Upper Dimension for n - 1 dimensions.
When dimension > 1, Betweenness can be defined in terms of congruence
(Tarski and Givant, 1999). First define the relation "≤" in terms of Congruence:
In the case of two dimensions, the intuition is as follows. For all points v on the perpendicular bisector of zu, there is a point w on the perpendicular bisector of xy such that yw is congruent to vu.
Betweenness can than be defined as
The Axiom Schema of Continuity assures that the ordering of points on a line is complete (with respect to first-order definable properties). The Axioms of Pasch
and Euclid are well known. Remarkably, Euclidean geometry requires but two more axioms:
Let wff stand for a well-formed formula
(or syntactically correct formula) of elementary geometry. Tarski and Givant (1999: 175) proved that elementary geometry is:
Gupta (1965) proved the above axioms independent, Pasch and Reflexivity of Congruence excepted.
Negating the Axiom of Euclid yields hyperbolic geometry
, while eliminating it outright yields absolute geometry
. Full (as opposed to elementary) Euclidean geometry requires giving up a first order axiomatization: replace φ(x) and ψ(y) in the axiom schema of Continuity with x ∈ A and y ∈ B, where A and B are universally quantified variables ranging over sets of points.
for plane geometry number 16, and include Transitivity of Congruence and a variant of the Axiom of Pasch. The only notion from intuitive geometry invoked in the remarks to Tarski's axioms is triangle
. (Versions B and C of the Axiom of Euclid refer to '"circle" and "angle," respectively.) Hilbert's axioms also require "ray," "angle," and the notion of a triangle "including" an angle. In addition to betweenness and congruence, Hilbert's axioms require a primitive binary relation
"on," linking a point and a line. The Axiom schema
of Continuity plays a role similar to Hilbert's two axioms of Continuity. This schema is indispensable; Euclidean geometry in Tarski's (or equivalent) language cannot be finitely axiomatized as a first-order theory
. Hilbert's axioms do not constitute a first-order theory because his continuity axioms require second-order logic
.
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...
, are an axiom set for the substantial fragment of Euclidean geometry
Euclidean geometry
Euclidean geometry is a mathematical system attributed to the Alexandrian Greek mathematician Euclid, which he described in his textbook on geometry: the Elements. Euclid's method consists in assuming a small set of intuitively appealing axioms, and deducing many other propositions from these...
, called "elementary
Elementary theory
In mathematical logic, an elementary theory is one that involves axioms using only finitary first-order logic, without reference to set theory or using any axioms which have consistency strength equal to set theory....
," that is formulable in first-order logic
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...
with identity
Identity (mathematics)
In mathematics, the term identity has several different important meanings:*An identity is a relation which is tautologically true. This means that whatever the number or value may be, the answer stays the same. For example, algebraically, this occurs if an equation is satisfied for all values of...
, and requiring no set theory
Set theory
Set theory is the branch of mathematics that studies sets, which are collections of objects. Although any type of object can be collected into a set, set theory is applied most often to objects that are relevant to mathematics...
. Other modern axiomizations of Euclidean geometry are those by Hilbert
Hilbert's axioms
Hilbert's axioms are a set of 20 assumptions proposed by David Hilbert in 1899 in his book Grundlagen der Geometrie , as the foundation for a modern treatment of Euclidean geometry...
and George Birkhoff
Birkhoff's axioms
In 1932, G. D. Birkhoff created a set of four postulates of Euclidean geometry sometimes referred to as Birkhoff's axioms. These postulates are all based on basic geometry that can be confirmed experimentally with a scale and protractor. Since the postulates build upon the real numbers, the...
.
Overview
Early in his career Tarski taught geometry and researched set theory. His coworker Steven Givant (1999) explained Tarski's take-off point:- From Enriques, Tarski learned of the work of Mario PieriMario PieriMario Pieri was an Italian mathematician who is known for his work on foundations of geometry.Pieri was born in Lucca, Italy, the son of Pellegrino Pieri and Ermina Luporini. Pellegrino was a lawyer. Pieri began his higher education at University of Bologna where he drew the attention of Salvatore...
, an Italian geometer who was strongly influenced by Peano. Tarski preferred Pieri's system [of his Point and Sphere memoir], where the logical structure and the complexity of the axioms were more transparent.
Givant's then says "with typical thoroughness" Tarski devised his system:
- What was different about Tarski's approach to geometry? First of all, the axiom system was much simpler than any of the axiom systems that existed up to that time. In fact the length of all of Tarski's axioms together is not much more than just one of Pieri's 24 axioms. It was the first system of Euclidean geometry that was simple enough for all axioms to be expressed in terms of the primitive notionPrimitive notionIn 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 only, without the help of defined notions. Of even greater importance, for the first time a clear distinction was made between full geometry and its elementary — that is, its first order — part.
Like other modern axiomatizations of Euclidean geometry, Tarski's employs a formal system
Formal system
In formal logic, a formal system consists of a formal language and a set of inference rules, used to derive an expression from one or more other premises that are antecedently supposed or derived . The axioms and rules may be called a deductive apparatus...
consisting of symbol strings, called sentence
Sentence (mathematical logic)
In mathematical logic, a sentence of a predicate logic is a boolean-valued well formed formula with no free variables. A sentence can be viewed as expressing a proposition, something that may be true or false...
s, whose construction respects formal syntactical rules
Syntax (logic)
In logic, syntax is anything having to do with formal languages or formal systems without regard to any interpretation or meaning given to them...
, and rules of proof that determine the allowed manipulations of the sentences. Unlike some other modern axiomatizations, such as Birkhoff's
Birkhoff's axioms
In 1932, G. D. Birkhoff created a set of four postulates of Euclidean geometry sometimes referred to as Birkhoff's axioms. These postulates are all based on basic geometry that can be confirmed experimentally with a scale and protractor. Since the postulates build upon the real numbers, the...
and Hilbert's
Hilbert's axioms
Hilbert's axioms are a set of 20 assumptions proposed by David Hilbert in 1899 in his book Grundlagen der Geometrie , as the foundation for a modern treatment of Euclidean geometry...
, Tarski's axiomatization has no primitive objects other than points, so a variable or constant cannot refer to a line or an angle. Because points are the only primitive objects, and because Tarski's system is a first-order theory, it is not even possible to define lines as sets of points. The only primitive relations (predicates) are "betweenness" and "congruence" among points.
Tarski's axiomatization is shorter than its rivals, in a sense Tarski and Givant (1999) make explicit. It is more concise than Pieri's because Pieri had only two primitive notions while Tarski introduced three: point, betweenness, and congruence. Such economy of primitive and defined notions means that Tarski's system is not very convenient for doing Euclidian geometry. Rather, Tarski designed his system to facilitate its analysis via the tools of mathematical logic
Mathematical logic
Mathematical logic is a subfield of mathematics with close connections to foundations of mathematics, theoretical computer science and philosophical logic. The field includes both the mathematical study of logic and the applications of formal logic to other areas of mathematics...
, i.e., to facilitate deriving its metamathematical properties. Tarski's system has the unusual property that all sentences can be written in universal-existential form, a special case of the prenex normal form
Prenex normal form
A formula of the predicate calculus is in prenex normal form if it is written as a string of quantifiers followed by a quantifier-free part .Every formula in classical logic is equivalent to a formula in prenex normal form...
. This form has all universal quantifiers
Universal quantification
In predicate logic, universal quantification formalizes the notion that something is true for everything, or every relevant thing....
preceding any existential quantifiers
Existential quantification
In predicate logic, an existential quantification is the predication of a property or relation to at least one member of the domain. It is denoted by the logical operator symbol ∃ , which is called the existential quantifier...
, so that all sentences can be recast in the form
This fact allowed Tarski to prove that Euclidean geometry is decidableDecidability (logic)
In logic, the term decidable refers to the decision problem, the question of the existence of an effective method for determining membership in a set of formulas. Logical systems such as propositional logic are decidable if membership in their set of logically valid formulas can be effectively...
: there exists an algorithm
Algorithm
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
which can determine the truth or falsity of any sentence. Tarski's axiomatization is also complete. This does not contradict Gödel's first incompleteness theorem, because Tarski's theory lacks the expressive power needed to interpret Robinson arithmetic
Robinson arithmetic
In mathematics, Robinson arithmetic, or Q, is a finitely axiomatized fragment of Peano arithmetic , first set out in R. M. Robinson . Q is essentially PA without the axiom schema of induction. Since Q is weaker than PA, it is incomplete...
.
The axioms
Alfred TarskiAlfred 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...
worked on the axiomatization and metamathematics of Euclidean geometry
Euclidean geometry
Euclidean geometry is a mathematical system attributed to the Alexandrian Greek mathematician Euclid, which he described in his textbook on geometry: the Elements. Euclid's method consists in assuming a small set of intuitively appealing axioms, and deducing many other propositions from these...
intermittently from 1926 until his 1983 death, with Tarski (1959) heralding his mature interest in the subject. The work of Tarski and his students on Euclidean geometry culminated in the monograph Schwabhäuser, Szmielew, and Tarski (1983), which set out the 10 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 and one axiom schema
Axiom schema
In mathematical logic, an axiom schema generalizes the notion of axiom.An axiom schema is a formula in the language of an axiomatic system, in which one or more schematic variables appear. These variables, which are metalinguistic constructs, stand for any term or subformula of the system, which...
shown below, the associated metamathematics
Metamathematics
Metamathematics is the study of mathematics itself using mathematical methods. This study produces metatheories, which are mathematical theories about other mathematical theories...
, and a fair bit of the subject. Gupta (1965) made important contributions, and Tarski and Givant (1999) discuss the history.
Fundamental relations
These axioms are a more elegant version of a set Tarski devised in the 1920s as part of his investigation of the metamathematical properties of Euclidean plane geometryPlane geometry
In mathematics, plane geometry may refer to:*Euclidean plane geometry, the geometry of plane figures,*geometry of a plane,or sometimes:*geometry of a projective plane, most commonly the real projective plane but possibly the complex projective plane, Fano plane or others;*geometry of the hyperbolic...
. This objective required reformulating that geometry as 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...
. Tarski did so by positing a universe
Universe (mathematics)
In mathematics, and particularly in set theory and the foundations of mathematics, a universe is a class that contains all the entities one wishes to consider in a given situation...
of point
Point (geometry)
In geometry, topology and related branches of mathematics a spatial point is a primitive notion upon which other concepts may be defined. In geometry, points are zero-dimensional; i.e., they do not have volume, area, length, or any other higher-dimensional analogue. In branches of mathematics...
s, with lower case letters denoting variables ranging over that universe. He then posited two primitive relations:
- Betweeness, a triadic relationTriadic relationIn mathematics, a ternary relation or triadic relation is a finitary relation in which the number of places in the relation is three. Ternary relations may also be referred to as 3-adic, 3-ary, 3-dimensional, or 3-place....
. The atomic sentenceAtomic sentenceIn logic, an atomic sentence is a type of declarative sentence which is either true or false and which cannot be broken down into other simpler sentences...
Bxyz denotes that y is "between" x and z, i.e., that x, y, and z are collinear with y "between" them; - CongruenceCongruence (geometry)In geometry, two figures are congruent if they have the same shape and size. This means that either object can be repositioned so as to coincide precisely with the other object...
(or "equidistance"), a tetradic relation. Let xy denote the line segmentLine segmentIn geometry, a line segment is a part of a line that is bounded by two end points, and contains every point on the line between its end points. Examples of line segments include the sides of a triangle or square. More generally, when the end points are both vertices of a polygon, the line segment...
whose endpoints are x and y. The atomic sentenceAtomic sentenceIn logic, an atomic sentence is a type of declarative sentence which is either true or false and which cannot be broken down into other simpler sentences...
wx ≡ yz has two intuitive meanings:- wx is congruentCongruence (geometry)In geometry, two figures are congruent if they have the same shape and size. This means that either object can be repositioned so as to coincide precisely with the other object...
to yz; - The distanceDistanceDistance is a numerical description of how far apart objects are. In physics or everyday discussion, distance may refer to a physical length, or an estimation based on other criteria . In mathematics, a distance function or metric is a generalization of the concept of physical distance...
from w to x equals the distance from y to z.
- wx is congruent
Betweenness captures the affine
Affine geometry
In mathematics affine geometry is the study of geometric properties which remain unchanged by affine transformations, i.e. non-singular linear transformations and translations...
aspect of Euclidean geometry; congruence, its metric
Metric space
In mathematics, a metric space is a set where a notion of distance between elements of the set is defined.The metric space which most closely corresponds to our intuitive understanding of space is the 3-dimensional Euclidean space...
aspect. The background logic includes identity
Identity (mathematics)
In mathematics, the term identity has several different important meanings:*An identity is a relation which is tautologically true. This means that whatever the number or value may be, the answer stays the same. For example, algebraically, this occurs if an equation is satisfied for all values of...
, a binary relation
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...
. The axioms invoke identity (or its negation) on five occasions.
The axioms below are grouped by the types of relation they invoke, then sorted, first by the number of existential quantifiers, then by the number of atomic sentences. The axioms should be read as universal closures; hence any free variables should be taken as tacitly universally quantified.
Congruence axioms
Reflexivity of Congruence:
The distance from x to y is the same as that from y to x. This axiom asserts a property very similar to symmetry
Symmetry
Symmetry generally conveys two primary meanings. The first is an imprecise sense of harmonious or aesthetically pleasing proportionality and balance; such that it reflects beauty or perfection...
for binary relation
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...
s.
Identity of Congruence:
If xy is congruent with a segment that begins and ends at the same point, x and y are the same point. This is closely related to the notion of reflexivity for binary relation
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...
s.
Transitivity
Transitivity
-In grammar:* Intransitive verb* Transitive verb, when a verb takes an object* Transitivity -In logic and mathematics:* Arc-transitive graph* Edge-transitive graph* Ergodic theory, a group action that is metrically transitive* Vertex-transitive graph...
of Congruence:
Two line segments both congruent to a third segment are congruent to each other; all three segments have the same length. This axiom asserts that congruence is Euclidean
Euclidean relation
In mathematics, Euclidean relations are a class of binary relations that satisfy a weakened form of transitivity that formalizes Euclid's "Common Notion 1" in The Elements: things which equal the same thing also equal one another.-Definition:...
, in that it respects the first of Euclid's
Euclid's Elements
Euclid's Elements is a mathematical and geometric treatise consisting of 13 books written by the Greek mathematician Euclid in Alexandria c. 300 BC. It is a collection of definitions, postulates , propositions , and mathematical proofs of the propositions...
"common notions." Hence this axiom could have been named "Congruence is Euclidean." The transitivity of congruence is an easy consequence of this axiom and Reflexivity.
Betweenness axioms
Identity of Betweenness
It is not possible for a point to be "between" a point; points are indivisible.
Axiom of Pasch
Draw line segments connecting any two vertices
Vertex (geometry)
In geometry, a vertex is a special kind of point that describes the corners or intersections of geometric shapes.-Of an angle:...
of a given triangle
Triangle
A triangle is one of the basic shapes of geometry: a polygon with three corners or vertices and three sides or edges which are line segments. A triangle with vertices A, B, and C is denoted ....
with the sides opposite the vertices. These two line segments must then intersect at some point inside the triangle.
Axiom schema
Axiom schema
In mathematical logic, an axiom schema generalizes the notion of axiom.An axiom schema is a formula in the language of an axiomatic system, in which one or more schematic variables appear. These variables, which are metalinguistic constructs, stand for any term or subformula of the system, which...
of Continuity
Let φ(x) and ψ(y) be first-order formulae containing no free instances of either a or b. Let there also be no free instances of x in ψ(y) or of y in φ(x). Then all instances of the following schema are axioms:
Let r be a ray with endpoint a. Let the first order formulae φ and ψ define subsets X and Y of r, such that every point in Y is to the right of every point of X (with respect to a). Then there exists a point b in r lying between X and Y. This is essentially the Dedekind cut
Dedekind cut
In mathematics, a Dedekind cut, named after Richard Dedekind, is a partition of the rationals into two non-empty parts A and B, such that all elements of A are less than all elements of B, and A contains no greatest element....
construction, carried out in a way that avoids quantification over sets.
Lower Dimension
Dimension
In physics and mathematics, the dimension of a space or object is informally defined as the minimum number of coordinates needed to specify any point within it. Thus a line has a dimension of one because only one coordinate is needed to specify a point on it...
In short, there exist three noncollinear points, and any model
Model theory
In mathematics, model theory is the study of mathematical structures using tools from mathematical logic....
of these axioms must have dimension
Dimension
In physics and mathematics, the dimension of a space or object is informally defined as the minimum number of coordinates needed to specify any point within it. Thus a line has a dimension of one because only one coordinate is needed to specify a point on it...
> 1.
Congruence and betweenness
Upper DimensionDimension
In physics and mathematics, the dimension of a space or object is informally defined as the minimum number of coordinates needed to specify any point within it. Thus a line has a dimension of one because only one coordinate is needed to specify a point on it...
Three points equidistant from two distinct points form a line. Hence any model
Model theory
In mathematics, model theory is the study of mathematical structures using tools from mathematical logic....
of these axioms must have dimension
Dimension
In physics and mathematics, the dimension of a space or object is informally defined as the minimum number of coordinates needed to specify any point within it. Thus a line has a dimension of one because only one coordinate is needed to specify a point on it...
< 3.
Axiom of Euclid
Each of the three variants of this axiom, all equivalent over the remaining Tarski's axioms to Euclid's parallel postulate
Parallel postulate
In geometry, the parallel postulate, also called Euclid's fifth postulate because it is the fifth postulate in Euclid's Elements, is a distinctive axiom in Euclidean geometry...
, has an advantage over the others:
- A dispenses with existential quantifiers;
- B has the fewest variables and atomic sentenceAtomic sentenceIn logic, an atomic sentence is a type of declarative sentence which is either true or false and which cannot be broken down into other simpler sentences...
s; - C requires but one primitive notion, betweenness. This variant is the usual one given in the literature.
- A:
Let a line segment join the midpoint of two sides of a given triangle
Triangle
A triangle is one of the basic shapes of geometry: a polygon with three corners or vertices and three sides or edges which are line segments. A triangle with vertices A, B, and C is denoted ....
. That line segment will be half as long as the third side. This is equivalent to the interior angles of any triangle summing to two right angles.
- B:
Given any triangle
Triangle
A triangle is one of the basic shapes of geometry: a polygon with three corners or vertices and three sides or edges which are line segments. A triangle with vertices A, B, and C is denoted ....
, there exists a circle
Circle
A circle is a simple shape of Euclidean geometry consisting of those points in a plane that are a given distance from a given point, the centre. The distance between any of the points and the centre is called the radius....
that includes all of its vertices.
- C:
Given any angle
Angle
In geometry, an angle is the figure formed by two rays sharing a common endpoint, called the vertex of the angle.Angles are usually presumed to be in a Euclidean plane with the circle taken for standard with regard to direction. In fact, an angle is frequently viewed as a measure of an circular arc...
and any point v in its interior, there exists a line segment including v, with an endpoint on each side of the angle.
Five Segment
Begin with two triangle
Triangle
A triangle is one of the basic shapes of geometry: a polygon with three corners or vertices and three sides or edges which are line segments. A triangle with vertices A, B, and C is denoted ....
s, xuz and x'u'z'. Draw the line segments yu and y'u', connecting a vertex of each triangle to a point on the side opposite to the vertex. The result is two divided triangles, each made up of five segments. If four segments of one triangle are each congruent
Congruence (geometry)
In geometry, two figures are congruent if they have the same shape and size. This means that either object can be repositioned so as to coincide precisely with the other object...
to a segment in the other triangle, then the fifth segments in both triangles must be congruent.
Segment Construction
Given any two line segments, the second can be "extended" by a line segment congruent
Congruence (geometry)
In geometry, two figures are congruent if they have the same shape and size. This means that either object can be repositioned so as to coincide precisely with the other object...
to the first.
Discussion
Starting from two primitive relationsRelation (mathematics)
In set theory and logic, a relation is a property that assigns truth values to k-tuples of individuals. Typically, the property describes a possible connection between the components of a k-tuple...
whose fields are a dense universe
Universe (mathematics)
In mathematics, and particularly in set theory and the foundations of mathematics, a universe is a class that contains all the entities one wishes to consider in a given situation...
of point
Point (geometry)
In geometry, topology and related branches of mathematics a spatial point is a primitive notion upon which other concepts may be defined. In geometry, points are zero-dimensional; i.e., they do not have volume, area, length, or any other higher-dimensional analogue. In branches of mathematics...
s, Tarski built a geometry of line segment
Line segment
In geometry, a line segment is a part of a line that is bounded by two end points, and contains every point on the line between its end points. Examples of line segments include the sides of a triangle or square. More generally, when the end points are both vertices of a polygon, the line segment...
s. According to Tarski and Givant (1999: 192-93), none of the above 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 is fundamentally new. The first four axioms establish some elementary properties of the two primitive relations. For instance, Reflexivity and Transitivity of Congruence establish that congruence is an equivalence relation
Equivalence relation
In mathematics, an equivalence relation is a relation that, loosely speaking, partitions a set so that every element of the set is a member of one and only one cell of the partition. Two elements of the set are considered equivalent if and only if they are elements of the same cell...
over line segments. The Identity of Congruence and of Betweenness govern the trivial case when those relations are applied to nondistinct points. The theorem xy≡zz ↔ x=y ↔ Bxyx extends these Identity axioms.
A number of other properties of Betweenness are derivable as theorems including:
- Reflexivity: Bxxy ;
- SymmetrySymmetrySymmetry generally conveys two primary meanings. The first is an imprecise sense of harmonious or aesthetically pleasing proportionality and balance; such that it reflects beauty or perfection...
: Bxyz → Bzyx ; - TransitivityTransitivity-In grammar:* Intransitive verb* Transitive verb, when a verb takes an object* Transitivity -In logic and mathematics:* Arc-transitive graph* Edge-transitive graph* Ergodic theory, a group action that is metrically transitive* Vertex-transitive graph...
: (Bxyw ∧ Byzw) → Bxyz ; - Connectivity: (Bxyw ∧ Bxzw) → (Bxyz ∨ Bxzy).
The last two properties totally 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...
the points making up a line segment.
Upper and Lower Dimension together require that any model of these axioms have a specific finite dimension
Dimension
In physics and mathematics, the dimension of a space or object is informally defined as the minimum number of coordinates needed to specify any point within it. Thus a line has a dimension of one because only one coordinate is needed to specify a point on it...
ality. Suitable changes in these axioms yield axiom sets for Euclidean geometry
Euclidean geometry
Euclidean geometry is a mathematical system attributed to the Alexandrian Greek mathematician Euclid, which he described in his textbook on geometry: the Elements. Euclid's method consists in assuming a small set of intuitively appealing axioms, and deducing many other propositions from these...
for dimension
Dimension
In physics and mathematics, the dimension of a space or object is informally defined as the minimum number of coordinates needed to specify any point within it. Thus a line has a dimension of one because only one coordinate is needed to specify a point on it...
s 0, 1, and greater than 2 (Tarski and Givant 1999: Axioms 8(1), 8(n), 9(0), 9(1), 9(n) ). Note that solid geometry
Solid geometry
In mathematics, solid geometry was the traditional name for the geometry of three-dimensional Euclidean space — for practical purposes the kind of space we live in. It was developed following the development of plane geometry...
requires no new axioms, unlike the case with Hilbert's axioms
Hilbert's axioms
Hilbert's axioms are a set of 20 assumptions proposed by David Hilbert in 1899 in his book Grundlagen der Geometrie , as the foundation for a modern treatment of Euclidean geometry...
. Moreover, Lower Dimension for n dimensions is simply the negation of Upper Dimension for n - 1 dimensions.
When dimension > 1, Betweenness can be defined in terms of congruence
Congruence relation
In abstract algebra, a congruence relation is an equivalence relation on an algebraic structure that is compatible with the structure...
(Tarski and Givant, 1999). First define the relation "≤" in terms of Congruence:
In the case of two dimensions, the intuition is as follows. For all points v on the perpendicular bisector of zu, there is a point w on the perpendicular bisector of xy such that yw is congruent to vu.
Betweenness can than be defined as
The Axiom Schema of Continuity assures that the ordering of points on a line is complete (with respect to first-order definable properties). The Axioms of Pasch
Pasch's axiom
In geometry, Pasch's axiom is a result of plane geometry used by Euclid, but yet which cannot be derived from Euclid's postulates. Its axiomatic role was discovered by Moritz Pasch.The axiom states that, in the plane,...
and Euclid are well known. Remarkably, Euclidean geometry requires but two more axioms:
- Segment Construction. This axiom makes measurementMeasurementMeasurement is the process or the result of determining the ratio of a physical quantity, such as a length, time, temperature etc., to a unit of measurement, such as the metre, second or degree Celsius...
and the Cartesian coordinate systemCartesian coordinate systemA Cartesian coordinate system specifies each point uniquely in a plane by a pair of numerical coordinates, which are the signed distances from the point to two fixed perpendicular directed lines, measured in the same unit of length...
possible—simply assign the value of 1 to some arbitrary line segment; - Five Segments. This bears on the congruenceCongruence (geometry)In geometry, two figures are congruent if they have the same shape and size. This means that either object can be repositioned so as to coincide precisely with the other object...
of triangleTriangleA triangle is one of the basic shapes of geometry: a polygon with three corners or vertices and three sides or edges which are line segments. A triangle with vertices A, B, and C is denoted ....
s.
Let wff stand for a well-formed formula
Well-formed formula
In mathematical logic, a well-formed formula, shortly wff, often simply formula, is a word which is part of a formal language...
(or syntactically correct formula) of elementary geometry. Tarski and Givant (1999: 175) proved that elementary geometry is:
- ConsistentConsistencyConsistency can refer to:* Consistency , the psychological need to be consistent with prior acts and statements* "Consistency", an 1887 speech by Mark Twain...
: There is no wff such that it and its negation are both theorems; - CompleteComplete theoryIn mathematical logic, a theory is complete if it is a maximal consistent set of sentences, i.e., if it is consistent, and none of its proper extensions is consistent...
: Every sentence or its negation is a theorem provable from the axioms; - DecidableDecidability (logic)In logic, the term decidable refers to the decision problem, the question of the existence of an effective method for determining membership in a set of formulas. Logical systems such as propositional logic are decidable if membership in their set of logically valid formulas can be effectively...
: There exists an algorithmAlgorithmIn mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
that assigns a truth value to every sentence. This follows from Tarski's:- Decision procedure for the real closed fieldReal closed fieldIn mathematics, a real closed field is a field F that has the same first-order properties as the field of real numbers. Some examples are the field of real numbers, the field of real algebraic numbers, and the field of hyperreal numbers.-Definitions:...
, which he found by quantifier eliminationQuantifier eliminationQuantifier elimination is a concept of simplification used in mathematical logic, model theory, and theoretical computer science. One way of classifying formulas is by the amount of quantification...
; - Axioms admitting of a (multi-dimensional) faithful interpretationInterpretabilityIn mathematical logic, interpretability is a relation between formal theories that expresses the possibility of interpreting or translating one into the other.-Informal definition:Assume T and S are formal theories...
as a real closed fieldReal closed fieldIn mathematics, a real closed field is a field F that has the same first-order properties as the field of real numbers. Some examples are the field of real numbers, the field of real algebraic numbers, and the field of hyperreal numbers.-Definitions:...
.
- Decision procedure for the real closed field
Gupta (1965) proved the above axioms independent, Pasch and Reflexivity of Congruence excepted.
Negating the Axiom of Euclid yields hyperbolic geometry
Hyperbolic geometry
In mathematics, hyperbolic geometry is a non-Euclidean geometry, meaning that the parallel postulate of Euclidean geometry is replaced...
, while eliminating it outright yields absolute geometry
Absolute geometry
Absolute geometry is a geometry based on an axiom system for Euclidean geometry that does not assume the parallel postulate or any of its alternatives. The term was introduced by János Bolyai in 1832...
. Full (as opposed to elementary) Euclidean geometry requires giving up a first order axiomatization: replace φ(x) and ψ(y) in the axiom schema of Continuity with x ∈ A and y ∈ B, where A and B are universally quantified variables ranging over sets of points.
Comparison with Hilbert
Hilbert's axiomsHilbert's axioms
Hilbert's axioms are a set of 20 assumptions proposed by David Hilbert in 1899 in his book Grundlagen der Geometrie , as the foundation for a modern treatment of Euclidean geometry...
for plane geometry number 16, and include Transitivity of Congruence and a variant of the Axiom of Pasch. The only notion from intuitive geometry invoked in the remarks to Tarski's axioms is triangle
Triangle
A triangle is one of the basic shapes of geometry: a polygon with three corners or vertices and three sides or edges which are line segments. A triangle with vertices A, B, and C is denoted ....
. (Versions B and C of the Axiom of Euclid refer to '"circle" and "angle," respectively.) Hilbert's axioms also require "ray," "angle," and the notion of a triangle "including" an angle. In addition to betweenness and congruence, Hilbert's axioms require a primitive binary relation
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...
"on," linking a point and a line. The Axiom schema
Axiom schema
In mathematical logic, an axiom schema generalizes the notion of axiom.An axiom schema is a formula in the language of an axiomatic system, in which one or more schematic variables appear. These variables, which are metalinguistic constructs, stand for any term or subformula of the system, which...
of Continuity plays a role similar to Hilbert's two axioms of Continuity. This schema is indispensable; Euclidean geometry in Tarski's (or equivalent) language cannot be finitely axiomatized as 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...
. Hilbert's axioms do not constitute a first-order theory because his continuity axioms require second-order logic
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....
.