In
mathematical logic
Mathematical logic is the study of Logic#Formal logic, formal logic within mathematics. Major subareas include model theory, proof theory, set theory, and recursion theory (also known as computability theory). Research in mathematical logic com ...
, 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
Formal, formality, informal or informality imply the complying with, or not complying with, some set of requirements (forms, in Ancient Greek). They may refer to:
Dress code and events
* Formal wear, attire for formal events
* Semi-formal attire ...
. Slightly simplified, ''T'' is said to be ''interpretable'' in ''S'' if and only if the language of ''T'' can be translated into the
language
Language is a structured system of communication that consists of grammar and vocabulary. It is the primary means by which humans convey meaning, both in spoken and signed language, signed forms, and may also be conveyed through writing syste ...
of ''S'' in such a way that ''S'' proves the translation of every
theorem
In mathematics and formal logic, a theorem is a statement (logic), statement that has been Mathematical proof, proven, or can be proven. The ''proof'' of a theorem is a logical argument that uses the inference rules of a deductive system to esta ...
of ''T''. Of course, there are some natural conditions on admissible translations here, such as the necessity for a translation to preserve the logical structure of
formulas
In science, a formula is a concise way of expressing information symbolically, as in a mathematical formula or a ''chemical formula''. The informal use of the term ''formula'' in science refers to the general construct of a relationship betwe ...
.
This concept, together with
weak interpretability In mathematical logic, weak interpretability is a notion of translation of logical theories, introduced together with interpretability by Alfred Tarski in 1953.
Let ''T'' and ''S'' be formal theories. Slightly simplified, ''T'' is said to be weak ...
, was introduced by
Alfred Tarski
Alfred Tarski (; ; born Alfred Teitelbaum;School of Mathematics and Statistics, University of St Andrews ''School of Mathematics and Statistics, University of St Andrews''. January 14, 1901 – October 26, 1983) was a Polish-American logician ...
in 1953. Three other related concepts are
cointerpretability In mathematical logic, cointerpretability is a binary relation on formal theories: a formal theory ''T'' is cointerpretable in another such theory ''S'', when the language of ''S'' can be translated into the language of ''T'' in such a way that ''S ...
,
logical tolerance, and
cotolerance, introduced by
Giorgi Japaridze
Giorgi Japaridze (also spelled Giorgie Dzhaparidze) is a Georgian-American researcher in logic and theoretical computer science. He currently holds the title of Full Professor at the Computing Sciences Department of Villanova University. Japaridze ...
in 1992–93.
See also
*
Conservative extension
In mathematical logic, a conservative extension is a supertheory of a theory which is often convenient for proving theorems, but proves no new theorems about the language of the original theory. Similarly, a non-conservative extension is a superth ...
*
Interpretation (logic)
An interpretation is an assignment of meaning to the symbols of a formal language. Many formal languages used in mathematics, logic, and theoretical computer science are defined in solely syntactic terms, and as such do not have any meaning unt ...
*
Interpretation (model theory)
In model theory, interpretation of a structure ''M'' in another structure ''N'' (typically of a different signature) is a technical notion that approximates the idea of representing ''M'' inside ''N''. For example, every reduct or definitional e ...
*
Interpretability logic Interpretability logics comprise a family of modal logics that extend provability logic to describe interpretability or various related metamathematical properties and relations such as weak interpretability, Π1-conservativity, cointerpretabilit ...
References
* Japaridze, G., and De Jongh, D. (1998) "The logic of provability" in Buss, S., ed., ''Handbook of Proof Theory''. North-Holland: 476–546.
*
Alfred Tarski
Alfred Tarski (; ; born Alfred Teitelbaum;School of Mathematics and Statistics, University of St Andrews ''School of Mathematics and Statistics, University of St Andrews''. January 14, 1901 – October 26, 1983) was a Polish-American logician ...
,
Andrzej Mostowski
Andrzej Mostowski (1 November 1913 – 22 August 1975) was a Polish mathematician. He worked primarily in logic and foundations of mathematics and is perhaps best remembered for the Mostowski collapse lemma. He was a member of the Polish Academy ...
, and
Raphael Robinson
Raphael Mitchel Robinson (November 2, 1911 – January 27, 1995) was an American mathematician.
Born in National City, California, Robinson was the youngest of four children of a lawyer and a teacher. He was awarded from the University of Calif ...
(1953) ''Undecidable Theories''. North-Holland.
Proof theory
{{logic-stub