Cointerpretability
Encyclopedia
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 proves every formula whose translation is a theorem
of T. The "translation" here is required to preserve the logical structure of formulas.
This concept, in a sense dual to interpretability
, was introduced by Japaridze in 1993, who also proved that, for theories Peano arithmetic and any stronger theories with effective axiomatizations, cointerpretability is equivalent to
-conservativity.
See also: tolerance, cotolerance, interpretability logic
.
Mathematical logic
Mathematical logic is a subfield of mathematics with close connections to foundations of mathematics, theoretical computer science and philosophical logic. The field includes both the mathematical study of logic and the applications of formal logic to other areas of mathematics...
, cointerpretability is a binary relation
Binary relation
In mathematics, a binary relation on a set A is a collection of ordered pairs of elements of A. In other words, it is a subset of the Cartesian product A2 = . More generally, a binary relation between two sets A and B is a subset of...
on formal theories
Formal theory
Formal theory can refer to:* Another name for a theory which is expressed in formal language.* An axiomatic system, something representable by symbols and its operators...
: a formal theory
Formal theory
Formal theory can refer to:* Another name for a theory which is expressed in formal language.* An axiomatic system, something representable by symbols and its operators...
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 proves every formula whose translation is a theorem
Theorem
In mathematics, a theorem is a statement that has been proven on the basis of previously established statements, such as other theorems, and previously accepted statements, such as axioms...
of T. The "translation" here is required to preserve the logical structure of formulas.
This concept, in a sense dual to interpretability
Interpretability
In mathematical logic, 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...
, was introduced by Japaridze in 1993, who also proved that, for theories Peano arithmetic and any stronger theories with effective axiomatizations, cointerpretability is equivalent to
-conservativity.See also: tolerance, cotolerance, interpretability logic
Interpretability logic
Interpretability logics comprise a family of modal logics that extend provability logic to describe interpretability and/or various related metamathematical properties and relations such as weak interpretability, Π1-conservativity, cointerpretability, tolerance, cotolerance and arithmetic...
.