Semantics of First-Order Logic — Read

Standard arithmetic structure

A structure $M$source 45 for the language of arithmetic consists of a set, an element of $\left|M\right|$source 46, $0^M$source 46, as interpretation of the constant $0$source 47, a one-place function ${\prime }^M:\left|M\right|\to \left|M\right|$source 48, two two-place functions ${+}^M$source 49 and ${\times }^M$source 49, both ${\left|M\right|}^2\to \left|M\right|$source 50, and a two-place relation ${<}^M\subseteq {\left|M\right|}^2$source 51.

An obvious example of such a structure is the following:

1. $\left|N\right|=\mathbb{N}$source 55

2. $0^N=0$source 56

3. ${\prime }^N\left(n\right)=n+1$source 57 for all $n\in \mathbb{N}$source 57

4. ${+}^N(n,m)=n+m$source 58 for all $n,m\in \mathbb{N}$source 58

5. ${\times }^N(n,m)=n·m$source 59 for all $n,m\in \mathbb{N}$source 59

6. ${<}^N=\{⟨n,m⟩:n\in \mathbb{N},m\in \mathbb{N},n<m\}$source 60

The structure $N$source 63 for $L_A$source 63 so defined is called the standard model of arithmetic, because it interprets the non-logical constants of $L_A$source 65 exactly how you would expect.

However, there are many other possible structures for $L_A$source 67. For instance, we might take as the domain the set $\mathbb{Z}$source 68 of integers instead of $\mathbb{N}$source 69, and define the interpretations of $0$source 69, $\prime$source 70, $+$source 70, $\times$source 70, $<$source 70 accordingly. But we can also define structures for $L_A$source 71 which have nothing even remotely to do with numbers.

source 44

Structures for set theory

A structure $M$source 76 for the language $L_Z$source 76 of set theory requires just a set and a single two-place relation. (Reader correction TR017-SOURCE-PROSE-001: a structure for the set-theory language requires a set and a single two-place relation). So technically, e.g., the set of people plus the relation “$x$source 78 is older than $y$source 78” could be used as a structure for $L_Z$source 79, as well as $\mathbb{N}$source 79 together with $n\ge m$source 80 for $n,m\in \mathbb{N}$source 80.

A particularly interesting structure for $L_Z$source 82 in which the elements of the domain are actually sets, and the interpretation of $\in$source 84 actually is the relation “$x$source 84 is a element of $y$source 84” is the structure $\mathrm{HF}$source 85 of hereditarily finite sets:

1. $\left|\mathrm{HF}\right|=\varnothing \cup \wp \left(\varnothing \right)\cup \wp \left(\wp \left(\varnothing \right)\right)\cup \wp \left(\wp \left(\wp \left(\varnothing \right)\right)\right)\cup \dots$source 87;

2. ${\in }^{\mathrm{HF}}=\{⟨x,y⟩:x,y\in \left|\mathrm{HF}\right|,x\in y\}$source 89.

source 75

Covered arithmetic example

Let $L$source 37 be the language with constants $\mathrm{zero}$source 37, $\mathrm{one}$source 38, $\mathrm{two}$source 38, …, the binary predicate $<$source 38, and the binary functions $+$source 39 and $\times$source 39. Then a structure $M$source 39 for $L$source 40 is the one with domain $\left|M\right|=\{0,1,2,\dots \}$source 40 and assignments ${\mathrm{zero}}^M=0$source 41, ${\mathrm{one}}^M=1$source 42, ${\mathrm{two}}^M=2$source 42, and so forth. For the binary relation symbol $<$source 43, the set ${<}^M$source 43 is the set of all pairs $⟨c_1,c_2⟩\in {\left|M\right|}^2$source 44 such that $c_1$source 45 is less than $c_2$source 45: for example, $⟨1,3⟩\in {<}^M$source 45 but $⟨2,2⟩\notin {<}^M$source 46. For the binary function $+$source 47, define ${+}^M$source 47 in the usual way—for example, ${+}^M(2,3)$source 48 maps to $5$source 48, and similarly for the binary function $\times$source 49. Hence, the value of $\mathrm{four}$source 49 is just $4$source 50, and the value of $\times (\mathrm{two},+(\mathrm{three},\mathrm{zero}\left)\right)$source 50 (or in infix notation, $\mathrm{two}\times (\mathrm{three}+\mathrm{zero})$source 51) is Evaluation of a compound closed term $$\begin{array}{c}{\mathrm{Val}}^M\left(\times (\mathrm{two},+(\mathrm{three},\mathrm{zero}\left)\right)\right)=\\ \begin{array}{cc}& ={\times }^M({\mathrm{Val}}^M\left(\mathrm{two}\right),{\mathrm{Val}}^M\left(+(\mathrm{three},\mathrm{zero})\right))\\ & ={\times }^M({\mathrm{Val}}^M\left(\mathrm{two}\right),{+}^M({\mathrm{Val}}^M\left(\mathrm{three}\right),{\mathrm{Val}}^M\left(\mathrm{zero}\right)\left)\right)\\ & ={\times }^M({\mathrm{two}}^M,{+}^M({\mathrm{three}}^M,{\mathrm{zero}}^M\left)\right)\\ & ={\times }^M(2,{+}^M(3,0\left)\right)\\ & ={\times }^M(2,3)\\ & =6\end{array}\end{array}$$source 53

source 36

Worked satisfaction model

Let $L=\{a,b,f,R\}$source 180 where $a$source 180 and $b$source 180 are constants, $f$source 181 is a two-place function, and $R$source 181 is a two-place predicate. Consider the structure $M$source 182 defined by:

1. $\left|M\right|=\{1,2,3,4\}$source 184

2. $a^M=1$source 185

3. $b^M=2$source 186

4. $f^M(x,y)=x+y$source 187 if $x+y\le 3$source 187 and $f^M(x,y)=3$source 187 Reader correction: The source writes only equals three after already naming the interpreted function value in the same sentence. The reader repeats f superscript M of x comma y so the isolated occurrence has its actual left-hand side. otherwise.

5. $R^M=\{⟨1,1⟩,⟨1,2⟩,⟨2,3⟩,⟨2,4⟩\}$source 188

The function $s\left(x\right)=1$source 190 that assigns $1\in \left|M\right|$source 190 to every variable is a variable assignment for $M$source 191.

Then Worked term-value calculation $$\begin{array}{ccccc}{\mathrm{Val}}_s^M\left(f(a,b)\right)& =f^M({\mathrm{Val}}_s^M\left(a\right),{\mathrm{Val}}_s^M\left(b\right)).\text{Since}a\text{and}b\text{are !!}\mathrm{constant}\text{s,}{\mathrm{Val}}_s^M\left(a\right)=a^M=1\text{and}{\mathrm{Val}}_s^M\left(b\right)=b^M=2\text{. So}{\mathrm{Val}}_s^M\left(f(a,b)\right)& =f^M(1,2)=1+2=3.\text{To compute the value of}f\left(f\right(a,b),a)\text{we have to consider}{\mathrm{Val}}_s^M\left(f\left(f\right(a,b),a)\right)& =f^M({\mathrm{Val}}_s^M\left(f(a,b)\right),{\mathrm{Val}}_s^M\left(a\right))=f^M(3,1)=3,\text{since}3+1>3\text{. Since}s\left(x\right)=1\text{and}{\mathrm{Val}}_s^M\left(x\right)=s\left(x\right)\text{, we also have}{\mathrm{Val}}_s^M\left(f\left(f\right(a,b),x)\right)& =f^M({\mathrm{Val}}_s^M\left(f(a,b)\right),{\mathrm{Val}}_s^M\left(x\right))=f^M(3,1)=3,\end{array}$$source 194

An atomic formula $R(t_1,t_2)$source 208 is satisfied if the tuple of values of its arguments, i.e., $⟨{\mathrm{Val}}_s^M\left(t_1\right),{\mathrm{Val}}_s^M\left(t_2\right)⟩$source 209, is a element of $R^M$source 210. So, e.g., we have $M,s\models R(b,f(a,b\left)\right)$source 211 since $⟨{\mathrm{Val}}^M\left(b\right),{\mathrm{Val}}^M\left(f(a,b)\right)⟩=⟨2,3⟩\in R^M$source 211, but $M,s⊭R(x,f(a,b\left)\right)$source 213 since $⟨1,3⟩\notin R^M$source 213 Reader correction: The source appends the assignment marker s to the interpreted relation rather than to a satisfaction statement. The reader omits that stray assignment marker..

To determine if a non-atomic formula $A$source 215 is satisfied, you apply the clauses in the inductive definition that applies to the main connective. For instance, the main connective in $R(a,a)\to \left(R\right(b,x)\vee R(x,b\left)\right)$source 217 is the $\to$source 218, and Worked conditional satisfaction calculation $$\begin{array}{cc}& M,s\models R(a,a)\to \left(R\right(b,x)\vee R(x,b\left)\right)\text{iff}\\ & M,s⊭R(a,a)\text{or}M,s\models R(b,x)\vee R(x,b)\text{Since}M,s\models R(a,a)\text{(because}⟨1,1⟩\in R^M\text{) we can't yet determine the answer and must first figure out if}M,s\models R(b,x)\vee R(x,b)\text{:}& M,s\models R(b,x)\vee R(x,b)\text{iff}\\ & M,s\models R(b,x)\text{or}M,s\models R(x,b)\text{And this is the case, since}M,s\models R(x,b)\text{(because}⟨1,2⟩\in R^M\text{).}\end{array}$$source 219

Recall that an $x$source 232-variant of $s$source 232 is a variable assignment that differs from $s$source 233 at most in what it assigns to $x$source 233. For every element of $\left|M\right|$source 234, there is an $x$source 234-variant of $s$source 234: Four x variants of an assignment $$\begin{array}{cccc}{s}_1& =s[1/x],& s_2& =s[2/x],\\ s_3& =s[3/x],& s_4& =s[4/x].\end{array}$$source 235 So, e.g., $s_2\left(x\right)=2$source 241 and $s_2\left(y\right)=s\left(y\right)=1$source 241 for all variables $y$source 241 other than $x$source 242. These are all the $x$source 242-variants of $s$source 242 for the structure $M$source 243, since $\left|M\right|=\{1,2,3,4\}$source 243. Note, in particular, that $s_1=s$source 244 ($s$source 244 is always an $x$source 244-variant of itself).

To determine if an existentially quantified formula $\exists xA\left(x\right)$source 247 is satisfied, we have to determine if $M,s[m/x]\models A\left(x\right)$source 248 for at least one $m\in \left|M\right|$source 248. So, $$M,s\models \exists x\left(R\right(b,x)\vee R(x,b\left)\right),$$source 250 since $M,s[1/x]\models R(b,x)\vee R(x,b)$source 253 ($s[3/x]$source 254 would also fit the bill). But, $$M,s⊭\exists x\left(R\right(b,x)\wedge R(x,b\left)\right)$$source 255 since, whichever $m\in \left|M\right|$source 258 we pick, $M,s[m/x]⊭R(b,x)\wedge R(x,b)$source 258.

To determine if a universally quantified formula $\forall xA\left(x\right)$source 261 is satisfied, we have to determine if $M,s[m/x]\models A\left(x\right)$source 262 for all $m\in \left|M\right|$source 262. So, $$M,s\models \forall x\left(R\right(x,a)\to R(a,x\left)\right),$$source 263 since $M,s[m/x]\models R(x,a)\to R(a,x)$source 266 for all $m\in \left|M\right|$source 266. For $m=1$source 267, we have $M,s[1/x]\models R(a,x)$source 267 so the consequent is true; for $m=2$source 268, $3$source 268, and $4$source 268, we have $M,s[m/x]⊭R(x,a)$source 269, so the antecedent is false. But, $$M,s⊭\forall x\left(R\right(a,x)\to R(x,a\left)\right)$$source 271 since $M,s[2/x]⊭R(a,x)\to R(x,a)$source 274 (because $M,s[2/x]\models R(a,x)$source 275 and $M,s[2/x]⊭R(x,a)$source 275).

For a more complicated case, consider $$\forall x\left(R\right(a,x)\to \exists yR(x,y)).$$source 325 Since $M,s[3/x]⊭R(a,x)$source 328 and $M,s[4/x]⊭R(a,x)$source 329, the interesting cases where we have to worry about the consequent of the conditional are only $m=1$source 330 and $m=2$source 331 Reader correction: The source omits m from the second case in the phrase 'm equals one and m equals two.' The reader supplies m before equals two.. Does $M,s[1/x]\models \exists yR(x,y)$source 331 hold? It does if there is at least one $n\in \left|M\right|$source 332 so that $M,s[1/x][n/y]\models R(x,y)$source 333. In fact, if we take $n=1$source 334, we have $s[1/x][n/y]=s[1/y]=s$source 334. Since $s\left(x\right)=1$source 335, $s\left(y\right)=1$source 335, and $⟨1,1⟩\in R^M$source 335, the answer is yes.

To determine if $M,s[2/x]\models \exists yR(x,y)$source 338, we have to look at the variable assignments $s[2/x][n/y]$source 340. Here, for $n=1$source 340, this assignment is $s_2=s[2/x]$source 341, which does not satisfy $R(x,y)$source 341 ($s_2\left(x\right)=2$source 341, $s_2\left(y\right)=1$source 342, and $⟨2,1⟩\notin R^M$source 342). However, consider $s[2/x][3/y]=s_2[3/y]$source 343. $M,s_2[3/y]\models R(x,y)$source 344 since $⟨2,3⟩\in R^M$source 344, and so $M,s_2\models \exists yR(x,y)$source 345.

So, for all $n\in \left|M\right|$source 347 (Reader correction TR017-SOURCE-PROSE-002: for every m in the domain of M, either the antecedent fails or the existential consequent holds), either $M,s[m/x]⊭R(a,x)$source 348 (if $m=3$source 348, $4$source 348) or $M,s[m/x]\models \exists yR(x,y)$source 349 (if $m=1$source 349, $2$source 349), and so $$M,s\models \forall x\left(R\right(a,x)\to \exists yR(x,y)).$$source 350 On the other hand, $$M,s⊭\exists x\left(R\right(a,x)\wedge \forall yR(x,y)).$$source 354 We have $M,s[m/x]\models R(a,x)$source 357 only for $m=1$source 357 and $m=2$source 357. But for both of these values of $m$source 358, there is in turn an $n\in \left|M\right|$source 358, namely $n=4$source 359, so that $M,s[m/x][n/y]⊭R(x,y)$source 360 and so $M,s[m/x]⊭\forall yR(x,y)$source 361 for $m=1$source 361 and $m=2$source 361. In sum, there is no $m\in \left|M\right|$source 362 such that $M,s[m/x]\models R(a,x)\wedge \forall yR(x,y)$source 362.

source 179