Franklin's Notes


Satisfaction in First-order Logic

In First-order logic , it is a bit more difficult than in sentential logic to specify exactly what we mean by "the formula $\varphi$ is true in the model $\mathfrak{A}$". This notion can be defined recursively in three steps, starting by defining the value of a term, and then satisfaction of atomic formulas, and finally satisfaction of formulas which are built up from atomic formulas.

If the free variables of a term $t$ are among $v_0,...,v_q$, then the value of the term $t$ at $x_0,...,x_q\in A$ is denoted $t[x_0...x_q]$ and defined recursively as follows:
1. If $t=v_i$, then $t[x_0...x_q]=x_i$.
2. If $t$ is a constant symbol, then $t[x_0...x_q]$ is the interpretation of that constant symbol in $A$.
3. If $t=F(t_1...t_m)$ where $F$ is an $m$-placed function symbol, then where $G$ is the interpretation of $F$ in $\mathfrak{A}$.

Notice that terms reside within the formal language $\mathscr{L}$, but their values reside within a model $\mathfrak{A}$. We can think of terms as "names" or "labels" and their values as the "things" or "entities" that they refer to.

We may now define satisfaction of atomic formulas $\varphi$ as follows.
1. If $\varphi(v_0...v_q)$ is the atomic formula $t_1\equiv t_2$, where $t_1(v_0...v_q)$ and $t_2(v_0...v_q)$ are terms, then $x_0,...,x_q$ satisfies $\varphi$ iff
2. If $\varphi(v_0...v_q)$ is the atomic formula $P(t_1...t_n)$ where $P$ is an $n$-placed relation symbol and $t_1(v_0...v_q)$,...,$t_n(v_0...v_q)$ are terms, then $x_0...x_q$ satisfies $\varphi$ iff where $R$ is the interpretation of $P$ in $\mathfrak{A}$.

If $x_0,...,x_q$ satisfies $\varphi$ in $\mathfrak{A}$, we may write $\mathfrak{A}\vDash \varphi[x_0...x_q]$ for brevity.

Finally, we may define satisfaction of general formulas recursively:
1. If $\varphi$ is the formula $\theta_1\land\theta_2$, then $\mathfrak{A}\vDash\varphi[x_0...x_q]$ if and only if both $\mathfrak{A}\vDash\theta_1[x_0...x_q]$ and $\mathfrak{A}\vDash\theta_2[x_0...x_q]$.
2. If $\varphi$ is the formula $\neg\theta$, then $\mathfrak{A}\vDash\varphi[x_0...x_q]$ if and only if it is not the case that $\mathfrak{A}\vDash\theta[x_0...x_q]$.
3. If $\varphi$ is $(\forall v_i)\psi$ where $i\leq q$, then $\mathfrak{A}\vDash\varphi[x_0...x_q]$ if and only if, for all $x\in A$, it holds that $\mathfrak{A}\vDash\psi[x_0...x_{i-1}xx_{i+1}...x_q]$.

Note that the question of whether or not $\varphi$ is satisfied by the sequence $x_0,...,x_q$ depends only on the values of the $x_i$ for which $v_i$ is a free variable in $\varphi$. In particular, if $\varphi$ is a sentence (i.e. a formula with no free variables), then its satisfaction does not depend at all on $x_0,...,x_q$. In other words, if a sentence evaluation $\varphi[x_0,...,x_q]$ holds for some sequence $x_0,...,x_q$, then it holds for all $x_0,...,x_q\in A$. This can be shown using an easy but tedious proof by induction.

Further, we may also formulate a kind of "substitution rule" for formulas $\varphi(v_0...v_p)$ and sequences of terms $t_0(v_0...v_p),...,t_p(v_0...v_p)$. If no variable occurring in any of the terms $t_0,...,t_p$ occurs bound in $\varphi$, then if $\varphi(t_0...t_p)$ is the formula obtained by substituting $t_i$ for $v_i$ in $\varphi(v_0...v_p)$, then

model-theory

first-order-logic

back to home page