Question about understanding an Interpretation definition in First Order Logic

Question

I am trying to understand a definition within First Order Logic using interpretation. Below is the specific interpretation definition

We define the truth value of a formula A in an interpretation I. We write I $\vDash$ A to mean that I satisfies A, which means A is true in an interpretation I. For an interpretation I and J with domain D, and for a variable x, we say that I $\equiv$ J (mod x) iff A$^I$ and A$^J$ are identical for all function symbols and predicate symbols A and for all variables A distinct from variable x. We define $\vDash$ recursively as follows:

• I $\vDash$ ($\forall$x)A iff for all interpretations J such that J$\equiv$ I (mod x), J$\vDash$A.

• I $\vDash$ ($\exists$x)A iff there exist an interpretation J such that J$\equiv$ I (mod x), J$\vDash$A.

I learn best by clear and easy to understand examples. I am not following this interpretation definition. Can someone help me cook up a simple & easy to understand example that clearly explains what the definitions above mean? I'm also not understanding the modular piece in that definition or its role either.

Thanks in advance.

Answer 1

There are different way to define the satisfaction relation for a first-order logic formula.

If we an interpretation $I$ with domain (or universe) $D$, we need a way to assign a denotation to the free variables in a formula.

If we consider the domain $U = \{ 0,1,2 \}$ and a (binary) predicate $P$ such that $I(P) = \{ (0,1),(1,2) \}$, in order to evaluate the truth value of the atomic formula $P(x,y)$, we have to assign a denotation (or refernce) to $x$ and $y$.

If we assume that :

$I(x)=0$ and $I(y)=1$,

the formula $P(x,y)$ has now a truth value; this value is "calculated" using the elements of the domain that are the denotation assigned by $I$ to the variables $x,y$ occurring free in the formula.

In our case, we have that for the interpretation $I$, $P(x,y)$ is $P(0,1)$, that is true because $(0,1) \in I(P)$.

In this case, we write :

$I \vDash P(x,y)$

meaning that the formula $P(x,y)$ is satisfied by the interpretation $I$.

---

A slightly more "real" example is obtained for the language of first-order arithmetic.

Let $I$ the "usual" interpretation with domain $\mathbb N$ (the natural numbers) and with the "usual" interpretation for the (binary) predicate $<$, the (unary) function $S$ ("successor"), the (binary) functions $+$ ("sum") and $\times$ ("product") and the (individual) constant $0$ ("zero").

What is the truth value in this interpretation of a formula $A$, with a free occurrence of the variable $x$, like :

$x > 0$ ?

If we let $I$assign as denotation to the variable $x$ the element $0$ of the domain (i.e. $I(x)=0$), we obtain, for the interpretation $I$ :

$I \nvDash (x > 0)$,

because $0 > 0$ is false, while if we have $I(x)=1$, we obtain :

$I \vDash (x > 0)$,

because $1 > 0$ is true.

---

Consider now the clause for $\exists$ with the formula : $\exists x A$, i.e. $\exists x (x > 0)$.

If $I(x)=0$, as we have seen above : $I \nvDash A$, because $0 > 0$ is false.

But if we consider an interpretation $J$ that differs from $I$ only for the value (i.e. object od the domain $D$) assigned to the variable $x$, and thus $J \equiv I (\text {mod} \ x)$, such that $J(x)=1$, we have that $J \vDash A$, because $1 > 0$ is true.

This is the "gist" of the clause: a formal way to express the fact that we can found an element in the domain $D$ of the interpretation $I$ satisfying the formula $A$. If so, this is enough to conclude that $I$ satisfy $\exists xA$.