Axiomatic system

Last updated

In mathematics and logic, an axiomatic system is any set of axioms from which some or all axioms can be used in conjunction to logically derive theorems. A theory is a consistent, relatively-self-contained body of knowledge which usually contains an axiomatic system and all its derived theorems. [1] An axiomatic system that is completely described is a special kind of formal system. A formal theory is an axiomatic system (usually formulated within model theory) that describes a set of sentences that is closed under logical implication. [2] A formal proof is a complete rendition of a mathematical proof within a formal system.

Contents

Properties

An axiomatic system is said to be consistent if it lacks contradiction. That is, it is impossible to derive both a statement and its negation from the system's axioms. Consistency is a key requirement for most axiomatic systems, as the presence of contradiction would allow any statement to be proven (principle of explosion).

In an axiomatic system, an axiom is called independent if it is not a theorem that can be derived from other axioms in the system. A system is called independent if each of its underlying axioms is independent. Unlike consistency, independence is not a necessary requirement for a functioning axiomatic system — though it is usually sought after to minimize the number of axioms in the system.

An axiomatic system is called complete if for every statement, either itself or its negation is derivable from the system's axioms (equivalently, every statement is capable of being proven true or false). [3]

Relative consistency

Beyond consistency, relative consistency is also the mark of a worthwhile axiom system. This describes the scenario where the undefined terms of a first axiom system are provided definitions from a second, such that the axioms of the first are theorems of the second.

A good example is the relative consistency of absolute geometry with respect to the theory of the real number system. Lines and points are undefined terms (also called primitive notions) in absolute geometry, but assigned meanings in the theory of real numbers in a way that is consistent with both axiom systems.[ citation needed ]

Models

A model for an axiomatic system is a well-defined set, which assigns meaning for the undefined terms presented in the system, in a manner that is correct with the relations defined in the system. The existence of a concrete model proves the consistency of a system[ disputed ]. A model is called concrete if the meanings assigned are objects and relations from the real world[ clarification needed ], as opposed to an abstract model which is based on other axiomatic systems.

Models can also be used to show the independence of an axiom in the system. By constructing a valid model for a subsystem without a specific axiom, we show that the omitted axiom is independent if its correctness does not necessarily follow from the subsystem.

Two models are said to be isomorphic if a one-to-one correspondence can be found between their elements, in a manner that preserves their relationship. [4] An axiomatic system for which every model is isomorphic to another is called categorial (sometimes categorical). The property of categoriality (categoricity) ensures the completeness of a system, however the converse is not true: Completeness does not ensure the categoriality (categoricity) of a system, since two models can differ in properties that cannot be expressed by the semantics of the system.

Example

As an example, observe the following axiomatic system, based on first-order logic with additional semantics of the following countably infinitely many axioms added (these can be easily formalized as an axiom schema):

(informally, there exist two different items).
(informally, there exist three different items).

Informally, this infinite set of axioms states that there are infinitely many different items. However, the concept of an infinite set cannot be defined within the system — let alone the cardinality of such as set.

The system has at least two different models – one is the natural numbers (isomorphic to any other countably infinite set), and another is the real numbers (isomorphic to any other set with the cardinality of the continuum). In fact, it has an infinite number of models, one for each cardinality of an infinite set. However, the property distinguishing these models is their cardinality — a property which cannot be defined within the system. Thus the system is not categorial. However it can be shown to be complete.

Axiomatic method

Stating definitions and propositions in a way such that each new term can be formally eliminated by the priorly introduced terms requires primitive notions (axioms) to avoid infinite regress. This way of doing mathematics is called the axiomatic method. [5]

A common attitude towards the axiomatic method is logicism. In their book Principia Mathematica , Alfred North Whitehead and Bertrand Russell attempted to show that all mathematical theory could be reduced to some collection of axioms. More generally, the reduction of a body of propositions to a particular collection of axioms underlies the mathematician's research program. This was very prominent in the mathematics of the twentieth century, in particular in subjects based around homological algebra.

The explication of the particular axioms used in a theory can help to clarify a suitable level of abstraction that the mathematician would like to work with. For example, mathematicians opted that rings need not be commutative, which differed from Emmy Noether's original formulation. Mathematicians decided to consider topological spaces more generally without the separation axiom which Felix Hausdorff originally formulated.

The Zermelo-Fraenkel axioms, the result of the axiomatic method applied to set theory, allowed the "proper" formulation of set-theory problems and helped avoid the paradoxes of naïve set theory. One such problem was the continuum hypothesis. Zermelo–Fraenkel set theory, with the historically controversial axiom of choice included, is commonly abbreviated ZFC, where "C" stands for "choice". Many authors use ZF to refer to the axioms of Zermelo–Fraenkel set theory with the axiom of choice excluded. [6] Today ZFC is the standard form of axiomatic set theory and as such is the most common foundation of mathematics.

History

Mathematical methods developed to some degree of sophistication in ancient Egypt, Babylon, India, and China, apparently without employing the axiomatic method.

Euclid of Alexandria authored the earliest extant axiomatic presentation of Euclidean geometry and number theory. [7] Many axiomatic systems were developed in the nineteenth century, including non-Euclidean geometry, the foundations of real analysis, Cantor's set theory, Frege's work on foundations, and Hilbert's 'new' use of axiomatic method as a research tool. For example, group theory was first put on an axiomatic basis towards the end of that century. Once the axioms were clarified (that inverse elements should be required, for example), the subject could proceed autonomously, without reference to the transformation group origins of those studies.

Issues

Not every consistent body of propositions can be captured by a describable collection of axioms. In recursion theory, a collection of axioms is called recursive if a computer program can recognize whether a given proposition in the language is a theorem. Gödel's first incompleteness theorem then tells us that there are certain consistent bodies of propositions with no recursive axiomatization. Typically, the computer can recognize the axioms and logical rules for deriving theorems, and the computer can recognize whether a proof is valid, but to determine whether a proof exists for a statement is only soluble by "waiting" for the proof or disproof to be generated. The result is that one will not know which propositions are theorems and the axiomatic method breaks down. An example of such a body of propositions is the theory of the natural numbers, which is only partially axiomatized by the Peano axioms (described below).

In practice, not every proof is traced back to the axioms. At times, it is not even clear which collection of axioms a proof appeals to. For example, a number-theoretic statement might be expressible in the language of arithmetic (i.e. the language of the Peano axioms) and a proof might be given that appeals to topology or complex analysis. It might not be immediately clear whether another proof can be found that derives itself solely from the Peano axioms.

Any more-or-less arbitrarily chosen system of axioms is the basis of some mathematical theory, but such an arbitrary axiomatic system will not necessarily be free of contradictions, and even if it is, it is not likely to shed light on anything. Philosophers of mathematics sometimes assert that mathematicians choose axioms "arbitrarily", but it is possible that although they may appear arbitrary when viewed only from the point of view of the canons of deductive logic, that appearance is due to a limitation on the purposes that deductive logic serves.

Example: The Peano axiomatization of natural numbers

The mathematical system of natural numbers 0,1, 2, 3, 4, ... is based on an axiomatic system first devised by the mathematician Giuseppe Peano in 1889. He chose the axioms, in the language of a single unary function symbol S (short for "successor"), for the set of natural numbers to be:

Axiomatization

In mathematics, axiomatization is the process of taking a body of knowledge and working backwards towards its axioms. [8] It is the formulation of a system of statements (i.e. axioms) that relate a number of primitive terms — in order that a consistent body of propositions may be derived deductively from these statements. Thereafter, the proof of any proposition should be, in principle, traceable back to these axioms.

See also

Related Research Articles

Axiom of choice axiom of set theory

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 collection of bins, each containing at least one object, it is possible to make a selection of exactly one object from each bin, even if the collection is infinite. Formally, it states that for every indexed family of nonempty sets there exists an indexed family of elements 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.

An axiom, postulate or assumption is a statement that is taken to be true, to serve as a premise or starting point for further reasoning and arguments. The word comes from the Greek axíōma (ἀξίωμα) 'that which is thought worthy or fit' or 'that which commends itself as evident.'

In mathematics, a finite set is a set that has a finite number of elements. Informally, a finite set is a set which one could in principle count and finish counting. For example,

Gödels completeness theorem Fundamental theorem in mathematical logic

Gödel's completeness theorem is a fundamental theorem in mathematical logic that establishes a correspondence between semantic truth and syntactic provability in first-order logic.

Mathematical logic, also called formal logic, is a subfield of mathematics exploring the applications of formal logic to mathematics. It bears close connections to metamathematics, the foundations of mathematics, philosophy, and theoretical computer science. The unifying themes in mathematical logic include the study of the expressive power of formal systems and the deductive power of formal proof systems.

Set theory Branch of mathematics that studies sets

Set theory is the branch of mathematical logic that studies sets, which can be informally described as collections of objects. Although objects of any kind can be collected into a set, set theory, as a branch of mathematics, is mostly concerned with those that are relevant to mathematics as a whole.

Gödel's incompleteness theorems are two theorems of mathematical logic that are concerned with the limits of provability in formal axiomatic theories. These results, published by Kurt Gödel in 1931, are important both in mathematical logic and in the philosophy of mathematics. The theorems are widely, but not universally, interpreted as showing that Hilbert's program to find a complete and consistent set of axioms for all mathematics is impossible.

In classical deductive logic, a consistent theory is one that does not entail a contradiction. The lack of contradiction can be defined in either semantic or syntactic terms. The semantic definition states that a theory is consistent if it has a model, i.e., there exists an interpretation under which all formulas in the theory are true. This is the sense used in traditional Aristotelian logic, although in contemporary mathematical logic the term satisfiable is used instead. The syntactic definition states a theory is consistent if there is no formula such that both and its negation are elements of the set of consequences of . Let be a set of closed sentences and the set of closed sentences provable from under some formal deductive system. The set of axioms is consistent when for no formula .

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.

Foundations of mathematics is the study of the philosophical and logical and/or algorithmic basis of mathematics, or, in a broader sense, the mathematical investigation of what underlies the philosophical theories concerning the nature of mathematics. In this latter sense, the distinction between foundations of mathematics and philosophy of mathematics turns out to be quite vague. Foundations of mathematics can be conceived as the study of the basic mathematical concepts and how they form hierarchies of more complex structures and concepts, especially the fundamentally important structures that form the language of mathematics also called metamathematical concepts, with an eye to the philosophical aspects and the unity of mathematics. The search for foundations of mathematics is a central question of the philosophy of mathematics; the abstract nature of mathematical objects presents special philosophical challenges.

Ernst Zermelo

Ernst Friedrich Ferdinand Zermelo was a German logician and mathematician, whose work has major implications for the foundations of mathematics. He is known for his role in developing Zermelo–Fraenkel axiomatic set theory and his proof of the well-ordering theorem.

Proof theory is a major branch of mathematical logic that represents proofs as formal mathematical objects, facilitating their analysis by mathematical techniques. Proofs are typically presented as inductively-defined data structures such as plain lists, boxed lists, or trees, which are constructed according to the axioms and rules of inference of the logical system. As such, proof theory is syntactic in nature, in contrast to model theory, which is semantic in nature.

In mathematics, two sets or classes A and B are equinumerous if there exists a one-to-one correspondence between them, that is, if there exists a function from A to B such that for every element y of B, there is exactly one element x of A with f(x) = y. Equinumerous sets are said to have the same cardinality. The study of cardinality is often called equinumerosity (equalness-of-number). The terms equipollence (equalness-of-strength) and equipotence (equalness-of-power) are sometimes used instead.

In set theory and related branches of mathematics, the von Neumann universe, or von Neumann hierarchy of sets, denoted by V, is the class of hereditary well-founded sets. This collection, which is formalized by Zermelo–Fraenkel set theory (ZFC), is often used to provide an interpretation or motivation of the axioms of ZFC. The concept is named after John von Neumann, although it was first published by Ernst Zermelo in 1930.

In classical logic, intuitionistic logic and similar logical systems, the principle of explosion, or the principle of Pseudo-Scotus, is the law according to which any statement can be proven from a contradiction. That is, once a contradiction has been asserted, any proposition can be inferred from it; this is known as deductive explosion.

In mathematics, Hilbert's program, formulated by German mathematician David Hilbert in the early part of the 20th century, was a proposed solution to the foundational crisis of mathematics, when early attempts to clarify the foundations of mathematics were found to suffer from paradoxes and inconsistencies. As a solution, Hilbert proposed to ground all existing theories to a finite, complete set of axioms, and provide a proof that these axioms were consistent. Hilbert proposed that the consistency of more complicated systems, such as real analysis, could be proven in terms of simpler systems. Ultimately, the consistency of all of mathematics could be reduced to basic arithmetic.

In mathematics, Robinson arithmetic is a finitely axiomatized fragment of first-order Peano arithmetic (PA), first set out by R. 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.

An approach to the foundations of mathematics that is of relatively recent origin, Scott–Potter set theory is a collection of nested axiomatic set theories set out by the philosopher Michael Potter, building on earlier work by the mathematician Dana Scott and the philosopher George Boolos.

A mathematical theory is a mathematical model of a branch of mathematics that is based on a set of axioms. It can also simultaneously be a body of knowledge, and so in this sense can refer to an area of mathematical research within the established framework.

References

  1. "The Definitive Glossary of Higher Mathematical Jargon — Theory". Math Vault. 2019-08-01. Retrieved 2019-10-31.
  2. Weisstein, Eric W. "Theory". mathworld.wolfram.com. Retrieved 2019-10-31.
  3. Weisstein, Eric W. "Complete Axiomatic Theory". mathworld.wolfram.com. Retrieved 2019-10-31.
  4. Hodges, Wilfrid; Scanlon, Thomas (2018), "First-order Model Theory", in Zalta, Edward N. (ed.), The Stanford Encyclopedia of Philosophy (Winter 2018 ed.), Metaphysics Research Lab, Stanford University, retrieved 2019-10-31
  5. "Set Theory and its Philosophy, a Critical Introduction S.6; Michael Potter, Oxford, 2004
  6. Weisstein, Eric W. "Zermelo-Fraenkel Axioms". mathworld.wolfram.com. Retrieved 2019-10-31.
  7. "Euclid - Hellenistic Mathematics - The Story of Mathematics". www.storyofmathematics.com. Retrieved 2019-10-31.
  8. "The Definitive Glossary of Higher Mathematical Jargon — Axiom". Math Vault. 2019-08-01. Retrieved 2019-10-31.

Further reading