satisfaction relation

Alfred Tarski was the first mathematician to give a formal definition of whatit means for a formula to be “true” in a structure. To do this, weneed to provide a meaning to terms, and truth-values to the formulas.In doing this, free variables cause a problem : what value are theygoing to have ? One possible answer is to supply temporary values for the free variables, and define our notions in terms of these temporary values.

Let $𝒜$ be a structure with signature $\tau$.Suppose $ℐ$ is an interpretation, and $\sigma$ is a function thatassigns elements of $A$ to variables, we define the function${\mathrm{Val}}_{ℐ,\sigma }$ inductively on the construction of terms :

${\mathrm{Val}}_{ℐ,\sigma }(c)$$=$$ℐ(c)\mathit{\hspace{1em}\hspace{1em}}c\text{a constant symbol}$

${\mathrm{Val}}_{ℐ,\sigma }(x)$$=$$\sigma (x)\mathit{\hspace{1em}\hspace{1em}}x\text{a variable}$

${\mathrm{Val}}_{ℐ,\sigma }(f(t_1,\mathrm{\dots },t_n))$$=$$ℐ(f)({\mathrm{Val}}_{ℐ,\sigma }(t_1),\mathrm{\dots },{\mathrm{Val}}_{ℐ,\sigma }(t_n))\mathit{\hspace{1em}\hspace{1em}}f\text{ an }n\text{-ary function symbol}$

Now we are set to define satisfaction. Again we have to take care of free variables by assigning temporary values to them via a function $\sigma$.We define the relation $𝒜,\sigma \vDash \phi$ by induction on the construction of formulas :

$𝒜,\sigma$$\vDash$$t_1=t_2\text{ if and only if }{\mathrm{Val}}_{ℐ,\sigma }(t_1)={\mathrm{Val}}_{ℐ,\sigma }(t_2)$

$𝒜,\sigma$$\vDash$$R(t_1,\mathrm{\dots },t_n)\text{ if and only if }({\mathrm{Val}}_{ℐ,\sigma }(t_1),\mathrm{\dots },{\mathrm{Val}}_{ℐ,\sigma }(t_1))\in ℐ(R)$

$𝒜,\sigma$$\vDash$$\mathrm{\neg }\phi \text{ if and only if }𝒜,\sigma \vDash ̸\phi$

$𝒜,\sigma$$\vDash$$\phi \vee \psi \text{ if and only if either }𝒜,\sigma \vDash \psi \text{ or }𝔄,\sigma \vDash \psi$

$𝒜,\sigma$$\vDash$$\exists x.\phi (x)\text{ if and only if for some }a\in A,𝒜,\sigma [x/a]\vDash \phi$

Here

In case for some $\phi$ of $L$, we have $𝒜,\sigma \vDash \phi$, we say that $𝒜$ models, or is a model of, or satisfies $\phi$. If $\phi$ has the free variables $x_1,\mathrm{\dots },x_n$, and $a_1,\mathrm{\dots },a_n\in A$, we also write $𝒜\vDash \phi (a_1,\mathrm{\dots },a_n)$ or $𝒜\vDash \phi (a_1/x_1,\mathrm{\dots },a_n/x_n)$ instead of $𝒜,\sigma [x_1/a_1]\mathrm{\cdots }[x_n/a_n]\vDash \phi$. In case $\phi$ is a sentence (formula with no free variables), we write $𝒜\vDash \phi$.