The full force of the semantics

Now that we have everything in place, we can start appreciating how expressive our language $\mathcal{L}_1$ is. So far, in our examples, we only considered ourselves with complex formulas without quantifiers, and with multiple quantifiers in front of an atomic formula, with some negations thrown in here and there. But of course, the real magic happens when we use the quantifiers and the connectives together to form complex sentences.

To make this more vivid, we may consider a possible real life application; a webshop’s database of items. The website sells clothing items in the following categories: shoes, bottoms, tops, and accessories. Moreover, each item has one or more associated color (black, white, red, green, blue), and one or more associated material (cotton, polyester, polycotton, leather). All in all, the database has information about 10 pieces of clothing items. These, we can refer to by their associated ‘code’: $1$, $2$, $3$, and so on.

All of this we can formally represent in a first-order structure. To make the particulars more easily readable, we will represent them in a table as follows:

Then, we can use the following predicates, with their interpretation specified relative to the table above:

1. Category predicates:

   1. $I(Top)=\{x \mid x\text{ is a top}\}$

   2. $I(Bot)=\{x \mid x\text{ is a bottom}\}$

   3. $I(Sho)=\{x \mid x\text{ is a pair of shoes}\}$

   4. $I(Acc)=\{x \mid x\text{ is an accessory}\}$

2. Color predicates:

   1. $I(Red)=\{x \mid x\text{ is red}\}$

   2. $I(Gre)=\{x \mid x\text{ is green}\}$

   3. $I(Blu)=\{x \mid x\text{ is blue}\}$

   4. $I(Whi)=\{x \mid x\text{ is white}\}$

   5. $I(Bla)=\{x \mid x\text{ is black}\}$

3. Fabric predicates:

   1. $I(Cot)=\{x \mid x\text{ is made of cotton}\}$

   2. $I(Pol)=\{x \mid x\text{ is made of polyester}\}$

   3. $I(Pc)=\{x \mid x\text{ is made of polycotton}\}$

   4. $I(Lea)=\{x \mid x\text{ is made of leather}\}$

Here is an interesting fabric fact. Some items are made out of polycotton, while some items are made out of polyester and cotton. We can distinguish between these two as follows. Polycotton is a fabric blend that is made out of both polyester and cotton. For example, many t-shirts are made entirely out of polycotton. But there are also some items that are made of pure cotton and pure polyester in some way combined. For example, you might buy some cotton shoes that have a polyester brand label. This does not make the shoes polycotton.

Let’s call the structure determined by the above information $\mathbf{W}$ (for a change). Once $\mathbf{W}$ is fixed, we can try and express a number of complex facts about $\mathbf{W}$, and in particular, about the various relations between these items and their properties.

Quantifier placement

Let’s start with some simple facts. First, you might want to express something like the following: “There is a red top and a white top”. You might hesitate between the following two options: $$\begin{gathered} \exists x ((Red (x) \wedge Top(x)) \wedge (Whi(x) \wedge Top(x)))\\ \exists x (Red(x) \wedge Top(x)) \wedge \exists x (Whi(x) \wedge Top(x)) \end{gathered}$$ In such cases, the correct option is the second one. For note that what the first option says is that there is a red and white top (that is a top). You can easily see this if you do the calculations explicitly, for in the first case, we need to find a single $x$-variant assignment that would satisfy the formula $((Red (x) \wedge Top(x)) \wedge (Whi(x) \wedge Top(x)))$. This is clearly impossible, for there is no one item that is a top, and both red and white. In the second case, however, we consider the two conjuncts separately, and thus we can consider two distinct $x$-variant assignments (two distinct objects). Accordingly, in $\mathbf{W}$, the first sentence is false, while the second is true. We can see how the second sentence is true in $\mathbf{W}$ as follows:

A similar problem arises if, for example, we change the conjunction to a disjunction, and the existential quantifier to a universal one. Suppose we want to express the fact that every item in the database is either made (at least partly) of polycotton, or made (at least partly) of cotton. Again, you have two options: $$\begin{gathered} \forall x (Pc(x) \vee Cot(x))\\ \forall x Pc(x) \vee \forall x Cot(x) \end{gathered}$$

Now the first sentence is the correct choice, and the second is the incorrect one. For note that what the second sentence says is really that either everything is made of polycotton, or everything is made of cotton. This sentence is a disjunction, so it is true if one of the disjuncts is true. But taken separately, it is not true that everything is made of polycotton, and it is also not true that everything is made of cotton. In particular, we can refer to the fact that $1$ is not made of polycotton, while $6$ is not made of cotton. Thus:

But again, we do have that $\mathbf{S} \models \forall x(Pc(x) \vee Cot(x))$, since for every $x$-variant assignment $\mathbf{a}'$, we have that $\mathbf{S} \models Pc(x) \vee Cot(x)[\mathbf{a}']$.

Restricted quantification

Let’s try and formulate some more interesting facts about our database. For example, we might want to capture some interrelations between various properties of our objects. One such fact would be the following: “If something is blue, then it is made of cotton”.

The first question here would be: which quantifier are we supposed to use? From the above formulation, this is not clear, and indeed, the use of ‘something’ might be misleading. Suppose you went with: $$\exists x (Blu(x) \rightarrow Cot(x))$$ This sentence is true in $\mathbf{W}$ if there is a value for $x$ relative to which $Blu(x) \rightarrow Cot(x)$ is satisfied. There are several problems with this option. First, since this is an existentially quantified sentence, it is sufficient for a single object to satisfy $Blu(x) \rightarrow Cot(x)$ for the sentence to be true. This does not seem like what we are trying to express, which is a general rule applying to every thing that is blue.

But there is another misleading element here: the use of a conditional after an existential quantifier. As mentioned several times already, a conditional is only unsatisfied (false) if its antecedent is satisfied (true), but its consequent is unsatisfied (false). In this case, this means that for any value for $x$, $Blu(x) \rightarrow Cot(x)$ is satisfied relative to that value provided either $Blu(x)$ and $Cot(x)$ are both satisfied, or $Blu(x)$ is not satisfied (regardless of whether $Cot(x)$ is satisfied or not). This means that item $6$ being red, white, and polycotton is by itself sufficient to make $\exists x (Blu(x) \rightarrow Cot(x))$ true in $\mathbf{W}$, for it is not made of cotton. This is usually not something we want to express. In general, if we wanted to express the fact that there is something that is blue and is made of cotton, then we can just say: $\exists x(Blu(x) \wedge Cot(x))$.

Returning to our initial fact under consideration, it was not that there is something that is blue and cotton, it was that whenever something is blue, then it is made of cotton. The correct way to capture this fact is with a universal quantifier. In particular: $$\forall x(Blu(x) \rightarrow Cot(x))$$ Interestingly, once we change the quantifier to a universal one, the use of a conditional proceeding it will capture precisely what we wanted to express. In particular, the only fact that would make this sentence false is if there were a blue item that was not cotton. In other words, as long as there is no item that is both blue and not cotton, the sentence is true, which seems to be what we wanted to express.

Let’s choose a blue and a non-blue item from the domain, and see how this functions. First, take item number $4$, which is blue. Then, we have that: $$\begin{aligned} \mathbf{W} \models& Blu(x)[\mathbf{a}^x_4]\\ \mathbf{W} \models& Cot(x)[\mathbf{a}^x_4]\\ \mathbf{W} \models& Cot \rightarrow Blu(x)[\mathbf{a}^x_4] \end{aligned}$$ But now taking item number $5$, which is not blue, we can reason, based on the definition of satisfaction as it relates to $\rightarrow$, that: $$\begin{aligned} \mathbf{W} \not\models& Blu(x)[\mathbf{a}^x_5]\\ \mathbf{W} \models& Cot(x)[\mathbf{a}^x_5]\\ \mathbf{W} \models& Cot \rightarrow Blu(x)[\mathbf{a}^x_5] \end{aligned}$$ Naturally, we would need to check whether $Blu(x) \rightarrow Cot(x)$ is satisfied in $\mathbf{W}$ relative to every possible $x$-variant assignment, not just these two. But it is easy to see that this will indeed hold, for again, every blue thing is cotton, and the non-blue things cannot make the sentence false.

If we zoom out for a bit, we can say that in sentences like $\forall x(Blu(x) \rightarrow Cot(x))$, the universal quantifier is restricted. What it is restricted to is the set of things satisfying the antecedent of the conditional. For in general, the universal quantifier ‘ranges over’ the whole domain. For example, if we had $\forall x Cot(x)$, the truth of this sentence depends on every possible assignment of value to $x$, so every object in the domain is relevant here. On the other hand, as mentioned, once we put $Blu(x)$ in front with a conditional, we are no longer concerned with the whole domain. Rather, we restrict our attention to just the blue things in the domain, and we say of them that each must be cotton. Once quantification is restricted, any member of the domain not captured by the antecedent condition becomes irrelevant.

As a rule, the universal quantification of $Z$, $\forall x Z$ is thus restricted (w.r.t. $Y$) with a conditional in the form $\forall x(Y \rightarrow Z)$. We can also talk about restricting the existential quantification of $Z$, $\exists x Z$ (w.r.t. $Y$), which is done with a conjunction (as mentioned briefly above), in the form $\exists x(Y \wedge Z)$.

One problematic aspect of this is vacuous quantification. Note that it may be the case that nothing satisfies the antecedent of the conditional after the universal quantifier. As demonstrated above, if something does not satisfy the antecedent of the conditional, the conditional as a whole is automatically satisfied. Unfortunately, this entails that if nothing satisfies the antecedent of the conditional, then relative to each value of $x$, the conditional as a whole is satisfied. So its universal quantification is true. For example, $\mathbf{W} \models \forall x ((Gre(x) \wedge Sho(x)) \rightarrow (Blu(x) \wedge \neg Blu(x)))$, for the sole (pun unintended) reason that there are no green shoes.

Quantifying into multiple positions

Finally, let’s add even more complexity by introducing a two-place predicate $Col$, defined such that: $$I(Col)=\{\langle x, y\rangle, \mid x\text{ is part of the same collection as } y\}.$$ Let’s further specify that in our structure $\mathbf{W}$, there are four collections:

1. Collection 1: items $2$, $6$, and $9$

2. Collection 2: items $4$, $7$ and $10$

3. Collection 3: items $1$, $3$, and $8$

4. Collection 4: item $5$

We can represent these collections in terms of the relation $I(Col)$ as follows:

As you can see, the relation allows us to separate the domain into 4 distinct, non-overlapping subsets, one for each collection, based on how the relation $I(Col)$ is distributed between the members (as represented by the arrows). The basic idea is that for any two members of the same collection, $I(Col)$ holds, while for any two items in distinct collections, they are never related in terms of $I(Col)$.

Note that as it is specified, $I(Col)$ is a reflexive, symmetric, and transitive relation. Reflexive, because everything is in the same collection as itself. Symmetric, because if $x$ is in the same collection as $y$, then $y$ is in the same collection as $x$. And transitive, because if $x$ is in the same collection as $y$, and $y$ is in the same collection as $z$, then $x$ is in the same collection as $z$. As it turns out, such relations always partition the domain into non-overlapping subsets, like our collections above.

We can then use multiple quantifiers to ‘quantify into’ the two ‘positions’ (argument places) of the binary predicate $Col$. For example, we might want to express the fact that there is an item for which it is true that if another item is in the same collection as it is, then that second item is white. Put another way, there is an item which is in a collection of white things. This can be captured as follows: $$\exists x \forall y(Col(x, y) \rightarrow Whi(y))$$ How is this sentence to be evaluated relative to $\mathbf{W}$? We need to check if we can find a value for $x$, such that for any value we can find for $y$, it is satisfied that if $x$ and $y$ are in the same collection, then $y$ is white.

Here is what’s not going to work. Suppose you choose for $x$ the value $4$. After all, other than $4$, every member of collection 2 is white. The problem here is that we have to check every item in the same collection as $4$, which includes $4$ itself. And $4$ is not white! So we have that: $$\begin{aligned} \mathbf{W} \not\models& \forall y(Col(x, y) \rightarrow Whi(y))[\mathbf{a}^x_4]\\ \mathbf{W} \not\models& Col(x, y) \rightarrow Whi(y)[(\mathbf{a}^x_4)^y_4]\\ \mathbf{W} \models& Col(x, y)[(\mathbf{a}^x_4)^y_4]\\ \mathbf{W} \not\models& Whi(y)[(\mathbf{a}^x_4)^y_4] \end{aligned}$$ (Note that we are not saying that $\mathbf{S} \not\models \exists x \forall y(Col(x, y) \rightarrow Whi(y))$, we are saying that choosing $4$ as the value for $x$ would not satisfy $\forall y(Col(x, y) \rightarrow Whi(y))$. This does not entail that the initial formula is false, and indeed, it is true, we just have to find the right value for $x$!)

On the other hand, we may choose any one item of collection 1, for there, it is guaranteed that every member of the collection will be white (including the chosen member). For example: $$\begin{aligned} \mathbf{W} \models& \exists x\forall y(Col(x, y) \rightarrow Whi(y))[\mathbf{a}]\\ \mathbf{W} \models& \forall y(Col(x, y) \rightarrow Whi(y))[\mathbf{a}^x_2]\\ \mathbf{W} \models& Col(x, y) \rightarrow Whi(y)[(\mathbf{a}^x_2)^y_2]\\ \mathbf{W} \models& Col(x, y) \rightarrow Whi(y)[(\mathbf{a}^x_2)^y_6]\\ \mathbf{W} \models& Col(x, y) \rightarrow Whi(y)[(\mathbf{a}^x_2)^y_9] \end{aligned}$$ As before, these are only the relevant $y$-variant assignments that could make a difference. In particular, if we were to send $y$ to any member other than $2$, $6$ or $9$, the conditional would immediately be satisfied by the fact that for no other assignment to $y$ do we have $Col(x, y)$ (when $x$ is sent to $2$).

Translating the untranslatable

As our final example, let’s try and capture something trickier. Suppose we want to capture the fact that there is a collection with a red and a blue item in it. At first glance, it seems like you could easy express this fact by using an existential quantifier and a predicate for ‘is a collection’. The problem is that we have no such predicate! We have the predicate $Col$, but that predicate says not that something is a collection, but that two items are in the same collection. There is a reason for not including a predicate for ‘is a collection’. For note that one-place predicates are evaluated in our semantics as subsets of our domain, and our domain does not have collections as members in it. It only has clothing items! And if you check $Col(x, y)$, it applies to clothing items, and not the collections, for it says that two items $x$, $y$ are in the same collection.

On the other hand, we can capture the above fact without talking explicitly about collections, just by using the predicate $Col$. For there being a collection with a red and a blue item in it is equivalent to saying that there are two items, one red and blue, such that they are in the same collection. If this is true, then there is a collection with a red and a blue item in it. Conversely, if there is a collection with a red and a blue item in it, then there are two items, one red, one blue that are in the same collection. (For everything in this paragraph, you should remember that there may only be a single object that has both properties.)

First-order languages, though very expressive, are still in some respects limited. In particular, they are limited by the fact that the quantifiers only range over members of the domain, predicates only have as interpretations subsets of the domain, and so on. On the other hand, many times (though certainly not always!), there are clever ways to turn an ‘untranslatable’ claim into a translatable one. The touchstone for these is ‘truth-conditional equivalence’. All this means is that the two sentences should be true (false) under the the same circumstances.

Accordingly, we can represent the fact that there is a collection with a red and a blue item in it as: $$\exists x\exists y((Red(x) \wedge Blu(y)) \wedge Col(x, y))$$ In particular, item $1$ is red, item $3$ is blue, and they are both in collection 3. So we have:

Now you try it!