From wikipedia:
In mathematical logic, interpretability is a relation between formal theories that expresses the possibility of interpreting or translating one into the other.
...
Slightly simplified, T is said to be interpretable in S if and only if the language of T can be translated into the language of S in such a way that S proves the translation of every theorem of T.
Please can you provide an example about interpretability?
On
Perhaps the simplest example is when S extends T by definitions. For a less trivial example consider the theories of Boolean algebras and Boolean rings, which are bi-intepretable (both interpretable in each other); for details see e.g. Ch.IV of Burris and Sankapannavar, A course in unversal algebra.
On
One of the simplest examples of interpretability is interpretability of propositional calculus (sentential logic) in class of boolean algebras. The interpretation is set up by valuations. Generally take any at least homomorfic structures and you get example of interpretablity.
On
Let p and q stand for metavariables. Suppose you have the following formation rules for T:
The deduction rules of T are those of conditional proof and the following:
T qualifies as interpretable in S with S having the formation rules:
And also the rules of conditional proof and the following deduction rules:
I think you can see here how every proof in S can get translated into a proof in T and vice versa.
Maybe the best known example is the interpretation of Peano arithmetic into ZFC. Peano arithmetic has a language with a constant symbol $0$ and a unary function symbol $S$. The language of ZFC has neither of these. But we can interpret Peano arithmetic into ZFC as follows:
These rules allow every formula $\phi$ of PA to be replaced by a formula $\phi'$ of ZFC. For example the formula $(\exists m)(n = S(m))$ becomes $(\exists m \in \omega)(n = m \cup \{m\})$. Similarly, the induction axiom $$ (0 \in X) \land (\forall m)[m \in X \to S(m) \in X] \to (\forall m)[m \in X] $$ becomes $$ (\emptyset \in X) \land (\forall m \in \omega)[m \in X \to m \cup \{m\} \in X] \to (\forall m \in \omega)[m \in X]. $$
This interpretation is sound: if $\phi$ is a formula in the language of arithmetic that is provable in PA, the corresponding formula $\phi'$ is provable in ZFC.
One role of interpretations is to prove relative consistency results. Because of the fact in the previous sentence, if a contradiction $\psi$ is provable in PA then a different contradiction $\psi'$ is provable in ZFC. Thus if ZFC is consistent, so it proves no contradictions, then the soundness of the interpretation means that PA is a also consistent.
Other examples of interpretations include:
The interpretation of the (theory of the) field of complex numbers into the (theory of the) field of real numbers, where each complex number is represented by a pair of real numbers and the operations on complex numbers are defined appropriately in terms of the components.
Interpretations of non-Euclidean geometry into Euclidean geometry, for example by interpreting "lines" as great circles on a sphere.
The interpretation of Euclidean geometry into the field of real numbers, where each "point" is a pair of real numbers and each "line" is a pair of points, with an appropriate equivalence relation on the lines. This gives a relative consistency proof of Euclidean geometry.