The interpretation translation

We give a precise account of what it means to interpret one mathematical structure in another, and show how this leads to the interpretation translation.

In mathematics we can often interpret one mathematical structure within another, finding a definable copy of the first structure within the second in such a way that enables us to express all the features of the original structure in terms of the language and structural features only of the host structure.

In the post on Interpretability last week, we discussed numerous examples of this phenomenon, including:

• Interpreting the integer order ⟨ℤ, < ⟩ inside the natural numbers ⟨ℕ, + ⟩.

• Interpreting set-theoretic mereology ⟨V,⊆⟩ inside a given model of set theory ⟨V,∈⟩.

• Interpreting the countable random graph in a countable model of set theory ⟨M,∈⟩.

• Interpreting modular arithmetic ⟨ℕ, ≡ₙ⟩ in Presburger arithmetic ⟨ℕ, +, 0, 1⟩.

• Interpreting the lattice of finite sets ⟨P_fin(ℕ), ⊆ ⟩ in arithmetic ⟨ℕ, +, ·, 0, 1, < ⟩.

• Interpreting the integer ring ⟨ℤ, +, ·⟩ inside the semi-ring of natural numbers ⟨ℕ, +, ·⟩.

• Interpreting the rational field ⟨ℚ, +, ·⟩ in the ring of integers ⟨ℤ, +, ·⟩.

• Interpreting the complex field ℂ in the real field ℝ.

• Interpreting hereditarily finite set theory ⟨HF,∈⟩ in arithmetic ⟨ℕ,+,·,0,1,<⟩.

• Interpreting urelement set theory in pure set theory.

• and several others…

In this post, I should like to provide a fuller and more precise account of what it means to interpret one structure within another. After doing so, we shall discuss the interpretation translation, by which one can express all the features of the interpreted structure entirely in terms of the resources and structural features of the host structure.

Enjoy this installment from A Panorama of Logic, an introduction to topics in logic for philosophers, mathematicians, and computer scientists. Fresh content each week.

This is the second in a series of posts on interpretability.

Please consider subscribing as a free or paid subscriber.

The formal definition of interpretation

Let us be a bit more precise with the interpretation terminology. We say that