Putting it all together

Peter Susanszky

Putting it all together

Using the above techniques, one can calculate the truth-value of any sentence in $\mathcal{L}_1$ , involving any number of quantifiers in any possible distribution. And in fact, one can also calculate the satisfaction of every formula of $\mathcal{L}_1$ relative to an initial assignment $\mathbf{a}$ in the structure $\mathbf{S}$ , involving open formulas with quantifiers. At each step, one just has to apply the relevant definition for the quantifier or connective until none are left, and then calculate the satisfiability of each resulting atomic formula relative to the relevant assignments. As we shall see soon, there are various techniques that make this easier than it first appears. But first, let’s formulate the semantics for our language $\mathcal{L}_1$ as a whole.

Again, the semantics is compositional, where the meaning of more complex expressions will always be calculable from the meaning of their constituent parts. Thus, parallel to how we introduced the semantics above, our definition will also start with assigning meaning to the predicates and terms of the language, then to atomic formulas, and then to more complex formulas.

Returning to satisfaction and truth once more, truth will be defined as a special case of satisfaction. Namely, satisfaction is relativized to structures and variable assignments, while truth will be assigned to those formulas in a structure that are satisfied under every possible variable assignment in the domain of that structure. In other words, only some formulas satisfiable in a structure will be said to be true, those that are satisfied under every variable assignment in the domain of the structure.

Definition 7.3 (Semantics of $\mathcal{L}_1$ ). A first-order structure $\mathbf{S}$ is a pair $\langle\mathbf{D}, I\rangle$ where $\mathbf{D}$ is a non-empty set called the domain, and $I$ is the interpretation function such that for every $c \in \mathsf{CONS}_{\mathcal{L}_1}$ , $I(c) \in \mathbf{D}$ , and for every predicate of arity $n$ , $I(P^n) \subseteq \mathbf{D}^n$ .

The function $\mathbf{a}: \textsf{VAR}_{\mathcal{L}_1} \to \mathbf{D}$ is a variable assignment in $\mathbf{D}$ . If $\mathbf{a}'$ is a variable assignment in $\mathbf{D}$ just like $\mathbf{a}$ , except possibly for some $x$ , $\mathbf{a}'(x)\neq \mathbf{a}(x)$ , we call $\mathbf{a}'$ an $x$ -variant variable assignment of $\mathbf{a}$ . If $\mathbf{a}'(x)=d$ ( $d \in \mathbf{D}$ ), i.e., $\mathbf{a}'$ is the $x$ -variant variable assignment of $\mathbf{a}$ such that $x$ is sent to $d$ by $\mathbf{a}'$ , we may also write $\mathbf{a}^x_d$ .

For each term $t \in \mathsf{TERM}_{\mathcal{L}_1}$ , we define the value of $t$ in the structure $\mathbf{S}$ relative to the variable assignment $\mathbf{a}$ as follows:

if $t=x$ for some $x \in \textsf{VAR}_{\mathcal{L}_1}$ , $I(t)[\mathbf{a}]=\mathbf{a}(x)$ ;
if $t=c$ for some $c \in \textsf{CONS}_{\mathcal{L}_1}$ , $I(t)[\mathbf{a}]=I(c)$ .

We define satisfaction for a formula $X$ relative to $\mathbf{S}$ under $\mathbf{a}$ , in symbols, $\mathbf{S} \models X[\mathbf{a}]$ as follows:

For the base: if $X=P^n(t_1, …, t_n)$ , then $\mathbf{S} \models X[\mathbf{a}]$ iff $\langle I(t_1)[\mathbf{a}], …, I(t_n)[\mathbf{a}]\rangle \in I(P^n)$ .
For the connectives:
1. if $X=\neg Y$ , $\mathbf{S} \models X[\mathbf{a}]$ iff $\mathbf{S} \not\models Y[\mathbf{a}]$ ;
2. if $X=(Y \wedge Z)$ , $\mathbf{S} \models X[\mathbf{a}]$ iff $\mathbf{S} \models Y[\mathbf{a}]$ and $\mathbf{S}\models Z[\mathbf{a}]$ ;
3. if $X=(Y \vee Z)$ , $\mathbf{S} \models X[\mathbf{a}]$ iff $\mathbf{S} \models Y[\mathbf{a}]$ or $\mathbf{S}\models Z[\mathbf{a}]$ (or both);
4. if $X=(Y \rightarrow Z)$ , $\mathbf{S} \models X[\mathbf{a}]$ iff if $\mathbf{S} \models Y[\mathbf{a}]$ , then $\mathbf{S}\models Z[\mathbf{a}]$ .
For the quantifiers:
1. if $X =\exists x Y$ , then $\mathbf{S} \models X[\mathbf{a}]$ iff there is an $x$ -variant assignment $\mathbf{a}'$ such that $\mathbf{S} \models Y[\mathbf{a}']$ ;
2. if $X =\forall x Y$ , then $\mathbf{S} \models X[\mathbf{a}]$ iff for every $x$ -variant assignment $\mathbf{a}'$ , $\mathbf{S} \models Y[\mathbf{a}']$ .

We say that a formula $X$ is true in (or relative to) $\mathbf{S}$ iff for every assignment $\mathbf{a}$ (in $\mathbf{D}$ of $\mathbf{S}$ ), $\mathbf{S} \models X[\mathbf{a}]$ . We say that a formula $X$ is false in (or relative to) $\mathbf{S}$ iff for every assignment $\mathbf{a}$ (in $\mathbf{D}$ of $\mathbf{S}$ ), $\mathbf{S} \not\models X[\mathbf{a}]$ .

You may see something strange with this definition of falsity. In particular, we defined a formula $X$ being false not as it not being true, but as a separate condition (namely, being unsatisfied under every assignment in $\mathbf{S}$ ). The reason why this is the case is precisely because some formulas cannot be said to be true or false, as they depend on the assignment function for their evaluation. Accordingly, if we specified that the formulas that are not true are false, we would have had to deem false those formulas that are sometimes satisfied, sometimes aren’t in $\mathbf{S}$ . It should be noted however that as far as sentences are concerned, a sentence not being true does entail it being false, so we are not violating the Law of Excluded Middle.

License

Icon for the Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License

License

Share This Book