In
mathematical logic, cointerpretability is a
binary relation
In mathematics, a binary relation associates elements of one set, called the ''domain'', with elements of another set, called the ''codomain''. A binary relation over Set (mathematics), sets and is a new set of ordered pairs consisting of ele ...
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 , who also proved that, for theories of
Peano arithmetic
In mathematical logic, the Peano axioms, also known as the Dedekind–Peano axioms or the Peano postulates, are axioms for the natural numbers presented by the 19th century Italian mathematician Giuseppe Peano. These axioms have been used nearly u ...
and any stronger theories with effective
axiomatization
In mathematics and logic, an axiomatic system is any Set (mathematics), set of axioms from which some or all axioms can be used in conjunction to logically derive theorems. A Theory (mathematical logic), theory is a consistent, relatively-self-co ...
s, cointerpretability is equivalent to
-conservativity.
See also
*
Cotolerance
*
Interpretability logic.
*
Tolerance (in logic)
References
*.
*.
Mathematical relations
Mathematical logic
{{logic-stub