In
mathematical 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 ...
, 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. Slightly simplified, ''T'' is said to be ''interpretable'' in ''S'' if and only if the language of ''T'' can be
translate
Translation is the communication of the meaning of a source-language text by means of an equivalent target-language text. The English language draws a terminological distinction (which does not exist in every language) between ''transla ...
d into the
language
Language is a structured system of communication. The structure of a language is its grammar and the free components are its vocabulary. Languages are the primary means by which humans communicate, and may be conveyed through a variety of ...
of ''S'' in such a way that ''S'' proves the translation of every
theorem
In mathematics, a theorem is a statement that has been proved, or can be proved. The ''proof'' of a theorem is a logical argument that uses the inference rules of a deductive system to establish that the theorem is a logical consequence of ...
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.
This concept, together with
weak interpretability, 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,
logical tolerance, and
cotolerance, introduced by
Giorgi Japaridze in 1992–93.
See also
*
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)
*
Interpretability logic
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 is perhaps best remembered for the Mostowski collapse lemma.
Biography
Born in Lemberg, Austria-Hungary, Mostowski entered University of Warsaw in 1931. He was ...
, 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 Cal ...
(1953) ''Undecidable Theories''. North-Holland.
Proof theory
{{logic-stub