Interpretation

An interpretation (or interpretation function) assigns meaning to formulae by mapping every non-logical symbol (i.e. anything that isn’t a connective or a quantifier) to a universe, $\mathcal{U}$. Essentially, it assigns meaning to formulae.

Definition §

Interpretation

An interpretation function $\mathcal{I}$ is one that takes non-logical symbols from a formal language, $L$ and assigns meaning to them by relating it to a universe, $\mathcal{U}$. It does this by mapping:

• Mapping constants to some element in $\mathcal{U}$ : $c\mapsto u\in \mathcal{U}$

• Mapping predicates to relations in $\mathcal{U}$ : $P(t_1,t_2,\dots ,t_n)\mapsto R\subset {\mathcal{U}}^n$

  • That is, a predicate is satisfied (returns true) only when certain elements from ${\mathcal{U}}^n$ are given as inputs.

• Function to a function defined in $\mathcal{U}$ : Function from $\mathcal{U}\to \mathcal{U}$

A formula, $\phi$ under an interpretation, $\mathcal{I}$ is notated as:

$$[[\phi ]{]}_{\mathcal{I}}=\text{φ under the interpretation I}$$

Logical Constants

Technically, an interpretation can assign meaning to connectives and quantifiers. However, in predicate logic and propositional logic, we treat these symbols as logical constants. That is, they remain fixed under every interpretations.

In Propositional Logic §

If we operate under the assumption that connectives ($\wedge ,\vee ,\to ,\neg$) are logical constants, then a valuation is sufficient to be an interpretation, because we have mapped everything:

• Propositions are mapped under a valuation
• Connectives are treated as logical constants (so we didn’t need an interpretation function for it)

However, if assume that these connectives also need an interpretation, then, an interpretation is an extension of a valuation. A valuation only maps atoms, but we still, need to define our connectives.

Essentially, the universe is simply the two truth values $\{\perp ,\top \}$.

Examples §

• We can have the standard interpretation of $+,\times$ in the set $\mathbb{Z}$ which makes $+$ a function that maps $\mathbb{Z}\to \mathbb{Z}$

Example : Black & White §

Let $\mathcal{U}=\{\text{white, black}\}$ (all integers) and let $\mathcal{I}$ be the interpretation function mapping:

• the constants $b\mapsto \text{black},w\mapsto \text{white}$
• the predicate $W\mapsto \{\text{white}\}$ (is it white?)
• the function $S=\{\text{white}\mapsto \text{black},\text{black }\mapsto \text{white}\}$ (a ‘swapping’ function)

Under this interpretation, we have:

• $W(b)$ is false
• $W(w)$ is true
• $W(S(b))$ is true

While this is still useful, we are limited to only talking about constants. We can either:

• Use logical quantifiers: $\forall xW(x)$ is false but $\exists yW(y)$ is true
• Use variable assignment.