Decidability of first-order theories of the real numbers

Last updated

In mathematical logic, a first-order language of the real numbers is the set of all well-formed sentences of first-order logic that involve universal and existential quantifiers and logical combinations of equalities and inequalities of expressions over real variables. The corresponding first-order theory is the set of sentences that are actually true of the real numbers. There are several different such theories, with different expressive power, depending on the primitive operations that are allowed to be used in the expression. A fundamental question in the study of these theories is whether they are decidable: that is, whether there is an algorithm that can take a sentence as input and produce as output an answer "yes" or "no" to the question of whether the sentence is true in the theory.

The theory of real closed fields is the theory in which the primitive operations are multiplication and addition; this implies that, in this theory, the only numbers that can be defined are the real algebraic numbers. As proven by Tarski, this theory is decidable; see Tarski–Seidenberg theorem and Quantifier elimination. Current implementations of decision procedures for the theory of real closed fields are often based on quantifier elimination by cylindrical algebraic decomposition.

Tarski's decidable algorithm was implemented on electronic computers in the 1950s. Its runtime is too slow for it to reach any interesting results. [1]

Tarski's exponential function problem concerns the extension of this theory to another primitive operation, the exponential function. It is an open problem whether this theory is decidable, but if Schanuel's conjecture holds then the decidability of this theory would follow. [2] [3] In contrast, the extension of the theory of real closed fields with the sine function is undecidable since this allows encoding of the undecidable theory of integers (see Richardson's theorem).

Still, one can handle the undecidable case with functions such as sine by using algorithms that do not necessarily terminate always. In particular, one can design algorithms that are only required to terminate for input formulas that are robust, that is, formulas whose satisfiability does not change if the formula is slightly perturbed. [4] Alternatively, it is also possible to use purely heuristic approaches. [5]

See also

Related Research Articles

In mathematics and computer science, the Entscheidungsproblem is a challenge posed by David Hilbert and Wilhelm Ackermann in 1928. The problem asks for an algorithm that considers, as input, a statement and answers "yes" or "no" according to whether the statement is universally valid, i.e., valid in every structure.

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.

Mathematical logic is the study of formal logic within mathematics. Major subareas include model theory, proof theory, set theory, and recursion theory. Research in mathematical logic commonly addresses the mathematical properties of formal systems of logic such as their expressive or deductive power. However, it can also include uses of logic to characterize correct mathematical reasoning or to establish foundations of mathematics.

In mathematical logic, model theory is the study of the relationship between formal theories, and their models. The aspects investigated include the number and size of models of a theory, the relationship of different models to each other, and their interaction with the formal language itself. In particular, model theorists also investigate the sets that can be defined in a model of a theory, and the relationship of such definable sets to each other. As a separate discipline, model theory goes back to Alfred Tarski, who first used the term "Theory of Models" in publication in 1954. Since the 1970s, the subject has been shaped decisively by Saharon Shelah's stability theory.

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.

<span class="mw-page-title-main">Alfred Tarski</span> Polish–American mathematician (1901–1983)

Alfred Tarski was a Polish-American logician and mathematician. A prolific author best known for his work on model theory, metamathematics, and algebraic logic, he also contributed to abstract algebra, topology, geometry, measure theory, mathematical logic, set theory, and analytic philosophy.

In mathematics, an expression is in closed form if it is formed with constants, variables and a finite set of basic functions connected by arithmetic operations and function composition. Commonly, the allowed functions are nth root, exponential function, logarithm, and trigonometric functions. However, the set of basic functions depends on the context.

In logic, a true/false decision problem is decidable if there exists an effective method for deriving the correct answer. Zeroth-order logic is decidable, whereas first-order and higher-order logic are not. Logical systems are decidable if membership in their set of logically valid formulas can be effectively determined. A theory in a fixed logical system is decidable if there is an effective method for determining whether arbitrary formulas are included in the theory. Many important problems are undecidable, that is, it has been proven that no effective method for determining membership can exist for them.

In 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.

In mathematics, a nonelementary antiderivative of a given elementary function is an antiderivative that is, itself, not an elementary function. A theorem by Liouville in 1835 provided the first proof that nonelementary antiderivatives exist. This theorem also provides a basis for the Risch algorithm for determining which elementary functions have elementary antiderivatives.

Quantifier elimination is a concept of simplification used in mathematical logic, model theory, and theoretical computer science. Informally, a quantified statement " such that " can be viewed as a question "When is there an such that ?", and the statement without quantifiers can be viewed as the answer to that question.

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, Richardson's theorem establishes the undecidability of the equality of real numbers defined by expressions involving integers, π, and exponential and sine functions. It was proved in 1968 by mathematician and computer scientist Daniel Richardson of the University of Bath.

In model theory, Tarski's exponential function problem asks whether the theory of the real numbers together with the exponential function is decidable. Alfred Tarski had previously shown that the theory of the real numbers is decidable.

A timeline of mathematical logic; see also history of logic.

In mathematics, the Tarski–Seidenberg theorem states that a set in (n + 1)-dimensional space defined by polynomial equations and inequalities can be projected down onto n-dimensional space, and the resulting set is still definable in terms of polynomial identities and inequalities. The theorem—also known as the Tarski–Seidenberg projection property—is named after Alfred Tarski and Abraham Seidenberg. It implies that quantifier elimination is possible over the reals, that is that every formula constructed from polynomial equations and inequalities by logical connectives (or), (and), ¬ (not) and quantifiers (for all), (exists) is equivalent to a similar formula without quantifiers. An important consequence is the decidability of the theory of real-closed fields.

In mathematical logic, a formula is satisfiable if it is true under some assignment of values to its variables. For example, the formula is satisfiable because it is true when and , while the formula is not satisfiable over the integers. The dual concept to satisfiability is validity; a formula is valid if every assignment of values to its variables makes the formula true. For example, is valid over the integers, but is not.

In mathematical logic, computational complexity theory, and computer science, the existential theory of the reals is the set of all true sentences of the form

References

  1. A. Burdman Fefferman and S. Fefferman, Alfred Tarski: Life and Logic (Cambridge: Cambridge University Press, 2008).
  2. Macintyre, A.J.; Wilkie, A.J. (1995), "On the decidability of the real exponential field", in Odifreddi, P.G. (ed.), Kreisel 70th Birthday Volume, CLSI
  3. Kuhlmann, S. (2001) [1994], "Model theory of the real exponential function", Encyclopedia of Mathematics , EMS Press
  4. Ratschan, Stefan (2006). "Efficient Solving of Quantified Inequality Constraints over the Real Numbers". ACM Transactions on Computational Logic. 7 (4): 723–748. arXiv: cs/0211016 . doi:10.1145/1183278.1183282. S2CID   16781766.
  5. Akbarpour, Behzad; Paulson, Lawrence Charles (2010). "MetiTarski: An Automatic Theorem Prover for Real-Valued Special Functions". Journal of Automated Reasoning. 44 (3): 175–205. doi:10.1007/s10817-009-9149-2. S2CID   16215962.