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. 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, 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
*
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)
*
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 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 (1953) ''Undecidable Theories''. North-Holland.
Proof theory
{{logic-stub