Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
For example, the theory of boolean algebras and the theory of boolean rings are bi-interpretable. –  Zhen Lin May 13 '12 at 18:34
    
The most famous example: non-euclidean geometry (more precisely, hyperbolic geometry) can be interpreted within euclidean geometry. Showing that attempts to prove the parallel postulate from the others can never succeed. (Unless euclidean geometry itself is inconsistent...) –  GEdgar May 13 '12 at 18:52
add comment

4 Answers 4

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.

share|improve this answer
add comment

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:

  • $0$ is interpreted as the empty set $\emptyset$
  • Every variable is interpreted as itself
  • Logical connectives are interpreted as themselves
  • $S(t)$, where $t$ is a term, is interpreted as $t' \cup \{t'\}$, where $t'$ is the interpretation of $t$.
  • The number quantifiers $(\forall n)$ and $(\exists n)$ are replaced with $(\forall x \in \omega)$ and $(\exists x \in \omega)$, respectively.

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.

share|improve this answer
add comment

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.

share|improve this answer
1  
I believe the question is about interpretations of theories, not about semantics. –  Carl Mummert May 14 '12 at 12:52
add comment

Let p and q stand for metavariables. Suppose you have the following formation rules for T:

  1. If p is a formula, then pN is a formula.
  2. If p and q are formulas, then pqC is a formula.

The deduction rules of T are those of conditional proof and the following:

  1. p, q |-p
  2. pqrCC, pqC, p|-r
  3. qNpNC, p|-q

T qualifies as interpretable in S with S having the formation rules:

  1. If p is a formula, then Np is a formula.
  2. If p and q are formulas, then Cpq is a formula.

And also the rules of conditional proof and the following deduction rules:

  1. p, q, |-p
  2. CpCqr, Cpq|-r
  3. CNqNp, p|-q

I think you can see here how every proof in S can get translated into a proof in T and vice versa.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.