0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I suppose that in the fifth line from top must be $I \equiv J (mod \ x)$ ... $\endgroup$ – Mauro ALLEGRANZA May 13 '15 at 19:08
  • $\begingroup$ If so, this symbols meand that the two interpretations "agree" on all function symbols and predicate symbols [and individual constants] of $A$ and for all variables [occurring free in] $A$, distinct from variable $x$. $\endgroup$ – Mauro ALLEGRANZA May 13 '15 at 19:11
  • $\begingroup$ Your edits are correct. I understand the high levels of what it means, but I'm still having problems coming up with an example, which to me means I don't fully understand it. As I only understand the higher level details but still lack the lower level detailed understanding of it. Also, don't really understand the significance of it needing to be distinct from variable x. Thanks for the edit corrections. $\endgroup$ – Quaternary May 13 '15 at 19:15
  • $\begingroup$ Still slightly confused by the definition. You need to define a domain D of I and the elements within D. Then define what the formula A is and its variables, function symbols or predicates are. From there you need to show how J satisfies I. I'm confused by how to how J $\vDash$ I (mod x) and what mod means/does here and whether if J needs to have the same domain D as I. I really would like to see an example to clear this confusion up if possible. $\endgroup$ – Quaternary May 13 '15 at 19:30
1
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ Few questions, as I am unfamiliar with some of this. Based on what you wrote in the first example I gather that a binary predicate is simply a predicate with two variables (e.g. x & y in your example). If so, then what purpose is the {(1,2)} in the definition of I(P)={(0,1),(1,2)}, if I(x)=0 and I(y)=1? What variables are assigned to (1,2), since x&y are taken? I(?)=1, I(?)=2-- hope my question makes sense here. Kind of wondering why you define I(P)={(1,0),(1,2)} and not I(P)={(1,0)}. I'll ask my second question in a separate comment. Thanks again for your response. $\endgroup$ – Quaternary May 13 '15 at 20:03
  • $\begingroup$ @Quaternary - $P$ is a binary predicae, i.e. a relation; the interpretation is a "sort of" $<$, because $(0,1) \in I(P)$ means that $P(0,1)$ is true in $I$. The values $I$ assigns to $x,y$ can be different; with $I(x)=2$ and $I(y)=1$, we have : $I \nvDash P(x,y)$, because $(2,1) \notin I(P)$. $\endgroup$ – Mauro ALLEGRANZA May 13 '15 at 20:17
  • $\begingroup$ Ok, P is a binary predicate P with the interpretation relation of <. But why is P defined as a 2-tuple set (i.e. (0,1), (1,2)) if there aren't any variables assigned to (1,2)? Second question: I now understand if I(x)=0 then I $\nvDash$ A, but if J differs from I only for the value x then J $\vDash$ A, since J(x)=1 and 1>0. But what does I (mod x) mean? Usually x is a number and not a variable, e.g. a $\equiv$ b (mod n). In our case a=J, b=I and n=x, but I'm still slightly confused by this. Sorry if my questions aren't totally clear. $\endgroup$ – Quaternary May 13 '15 at 20:41
  • $\begingroup$ Followup to my previous question... I believe I finally understand what mod x means, it means that the I,J differ in their treatment of x. I was confused because typically mod n means they differ by a multiple of n. $\endgroup$ – Quaternary May 14 '15 at 2:14
  • $\begingroup$ @Quaternary - Yes; I've never see in many many textbooks I've read that way tu use $mod$... so you are right to be confused. But the meaning is exactly that : the two int differ at most for the values they assign to $x$. $\endgroup$ – Mauro ALLEGRANZA May 14 '15 at 6:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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