10. Semantics of First Order Logic

In Chapter 6, we emphasized a distinction between the syntax and the semantics of propositional logic. Syntactic questions have to do with the formal structure of formulas and the conditions under which different types of formulas can be derived. Semantic questions, on the other hand, concern the truth of a formula relative to some truth assignment.

As you might expect, we can make a similar distinction in the setting of first order logic. The previous two chapters have focused on syntax, but some semantic ideas have slipped in. Recall the running example with domain of interest \({\mathbb N}\), constant symbols 0, 1, 2, 3, function symbols \(\mathit{add}\) and \(\mathit{mul}\), and predicate symbols \(\mathit{even}, \mathit{prime}, \mathit{equals}, \mathit{le}\), etc. We know that the sentence \(\forall y \; \mathit{le}(0, y)\) is true in this example, if \(\mathit{le}\) is interpreted as the less-than-or-equal-to relation on the natural numbers. But if we consider the domain \({\mathbb Z}\) instead of \({\mathbb N}\), that same formula becomes false. The sentence \(\forall y \; \mathit{lt}(0,y)\) is also false if we consider the domain \({\mathbb N}\), but (somewhat perversely) interpret the predicate \(\mathit{lt}(x, y)\) as the relation “\(x\) is greater than \(y\)” on the natural numbers.

This indicates that the truth or falsity or a first order sentence can depend on how we interpret the quantifiers and basic relations of the language. But some formulas are true under any interpretation: for instance, \(\forall y \; (\mathit{le}(0, y) \to \mathit{le}(0, y))\) is true under all the interpretations considered in the last paragraph, and, indeed, under any interpretation we choose. A sentence like this is said to be valid; this is the analogue of a tautology in propositional logic, which is true under every possible truth assignment.

We can broaden the analogy: a “model” in first order logic is the analogue of a truth assignment in propositional logic. In the propositional case, choosing a truth assignment allowed us to assign truth values to all formulas of the language; now, choosing a model will allow us to assign truth values to all sentences of a first order language. The aim of the next section is to make this notion more precise.

10.1. Interpretations

The symbols of the language in our running example—0, 1, \(\mathit{add}\), \(\mathit{prime}\), and so on—have very suggestive names. When we interpret sentences of this language over the domain \({\mathbb N}\), for example, it is clear for which elements of the domain \(\mathit{prime}\) “should” be true, and for which it “should” be false. But let us consider a first order language that has only two unary predicate symbols \(\mathit{fancy}\) and \(\mathit{tall}\). If we take our domain to be \({\mathbb N}\), is the sentence \(\forall x \; (\mathit{fancy}(x) \to \mathit{tall}(x))\) true or false?

The answer, of course, is that we don’t have enough information to say. There’s no obvious meaning to the predicates \(\mathit{fancy}\) or \(\mathit{tall}\), at least not when we apply them to natural numbers. To make sense of the sentence, we need to know which numbers are fancy and which ones are tall. Perhaps multiples of 10 are fancy, and even numbers are tall; in this case, the formula is true, since every multiple of 10 is even. Perhaps prime numbers are fancy and odd numbers are tall; then the formula is false, since 2 is fancy but not tall.

We call each of these descriptions an interpretation of the predicate symbols \(\mathit{fancy}\) and \(\mathit{tall}\) in the domain \({\mathbb N}\). Formally, an interpretation of a unary predicate \(P\) in a domain \(D\) is the set of elements of \(D\) for which \(P\) is true. For an example, the standard interpretation of \(\mathit{prime}\) in \({\mathbb N}\) that we used above was just the set of prime natural numbers.

We can interpret constant, function, and relation symbols in a similar way. An interpretation of constant symbol \(c\) in domain \(D\) is an element of \(D\). An interpretation of a function symbol \(f\) with arity \(n\) is a function that maps \(n\) elements of \(D\) to another element of \(D\). An interpretation of a relation symbol \(R\) with arity \(n\) is the set of \(n\) tuples of elements of \(D\) for which \(R\) is true.

It is important to emphasize the difference between a syntactic predicate symbol (or function symbol, or constant symbol) and the semantic predicate (or function, or object) to which it is interpreted. The former is a symbol, relates to other symbols, and has no meaning on its own until we specify an interpretation. Strictly speaking, it makes no sense to write \(\mathit{prime}(3)\), where \(\mathit{prime}\) is a predicate symbol and 3 is a natural number, since the argument to \(\mathit{prime}\) is supposed to be a syntactic term. Sometimes we may obscure this distinction, as above when we specified a language with constant symbols 0, 1, and 2. But there is still a fundamental distinction between the objects of the domain and the symbols we use to represent them.

Sometimes, when we interpret a language in a particular domain, it is useful to implicitly introduce new constant symbols into the language to denote elements of this domain. Specifically, for each element \(a\) of the domain, we introduce a constant symbol \(\bar a\), which is interpreted as \(a\). Then the expression \(\mathit{prime}(\bar 3)\) does make sense. Interpreting the predicate symbol \(\mathit{prime}\) in the natural way, this expression will evaluate to true. We think of \(\bar 3\) as a linguistic “name” that represents the natural number 3, in the same way that the phrase “Aristotle” is a name that represents the ancient Greek philosopher.

10.2. Truth in a Model

Fix a first-order language. Suppose we have chosen a domain \(D\) in which to interpret the language, along with an interpretation in \(D\) of each of the symbols of that language. We will call this structure—the domain \(D\), paired with the interpretation—a model for the language. A model for a first-order language is directly analogous to a truth assignment for propositional logic, because it provides all the information we need to determine the truth value of each sentence in the language.

The procedure for evaluating the truth of a sentence based on a model works the way you think it should, but the formal description is subtle. Recall the difference between terms and assertions that we made earlier in Chapter 4. Terms, like \(a\), \(x + y\), or \(f(c)\), are meant to represent objects. A term does not have a truth value, since (for example) it makes no sense to ask whether 3 is true or false. Assertions, like \(P(a)\), \(R(x, f(y))\), or \(a + b > a \wedge \mathit{prime}(c)\), apply predicate or relation symbols to terms to produce statements that could be true or false.

The interpretation of a term in a model is an element of the domain of that model. The model directly specifies how to interpret constant symbols. To interpret a term \(f(t)\) created by applying a function symbol to another term, we interpret the term \(t\), and then apply the interpretation of \(f\) to this term. (This process makes sense, since the interpretation of \(f\) is a function on the domain.) This generalizes to functions of higher arity in the obvious way. We will not yet interpret terms that include free variables like \(x\) and \(y\), since these terms do not pick out unique elements of the domain. (The variable \(x\) could potentially refer to any object.)

For example, suppose we have a language with two constant symbols, \(a\) and \(b\), a unary function symbol \(f\), and a binary function symbol \(g\). Let \({\mathcal M}\) be the model with domain \({\mathbb N}\), where \(a\) and \(b\) are interpreted as \(3\) and \(5\), respectively, \(f(x)\) is interpreted as the function which maps any natural number \(n\) to \(n^2\), and \(g\) is the addition function. Then the term \(g(f(a),b)\) denotes the natural number \(3^2+5 = 14\).

Similarly, the interpretation of an assertion is a value \(\mathbf{T}\) or \(\mathbf{F}\). For the sake of brevity, we will introduce new notation here: if \(A\) is an assertion and \({\mathcal M}\) is a model of the language of \(A\), we write \({\mathcal M} \models A\) to mean that \(A\) evaluates to \(\mathbf{T}\) in \({\mathcal M}\), and \({\mathcal M} \not\models A\) to mean that \(A\) evaluates to \(\mathbf{F}\). (You can read the symbol \(\models\) as “models” or “satisfies” or “validates.”)

To interpret a predicate or relation applied to some terms, we first interpret the terms as objects in the domain, and then see if the interpretation of the relation symbol is true of those objects. To continue with the example, suppose our language also has a relation symbol \(\mathit{R}\), and we extend \({\mathcal M}\) to interpret \(R\) as the greater-than-or-equal-to relation. Then we have \({\mathcal M} \not \models R(a, b)\), since 3 is not greater than 5, but \({\mathcal M} \models R(g(f(a),b),b)\), since 14 is greater than 5.

Interpreting expressions using the logical connectives \(\wedge\), \(\vee\), \(\to\), and \(\neg\) works exactly as it did in the propositional setting. \({\mathcal M} \models A \wedge B\) exactly when \({\mathcal M} \models A\) and \({\mathcal M} \models B\), and so on.

We still need to explain how to interpret existential and universal expressions. We saw that \(\exists x \; A\) intuitively meant that there was some element of the domain that would make \(A\) true, when we “replaced” the variable \(x\) with that element. To make this a bit more precise, we say that \({\mathcal M} \models \exists x A\) exactly when there is an element \(a\) in the domain of \({\mathcal M}\) such that, when we interpret \(x\) as \(a\), then \({\mathcal M} \models A\). To continue the example above, we have \({\mathcal M} \models \exists x \; (R(x, b))\), since when we interpret \(x\) as 6 we have \({\mathcal M} \models R(x, b)\).

More concisely, we can say that \({\mathcal M} \models \exists x \; A\) when there is an \(a\) in the domain of \({\mathcal M}\) such that \({\mathcal M} \models A[\bar a / x]\). The notation \(A[\bar a / x]\) indicates that every occurrence of \(x\) in \(A\) has been replaced by the symbol \(\bar a\).

Finally, remember, \(\forall x \; A\) means that \(A\) is true for all possible values of \(x\). We make this precise by saying that \({\mathcal M} \models \forall x \; A\) exactly when for every element \(a\) in the domain of \({\mathcal M}\), interpreting \(x\) as \(a\) gives that \({\mathcal M} \models A\). Alternatively, we can say that \({\mathcal M} \models \forall x \; A\) when for every \(a\) in the domain of \({\mathcal M}\), we have \({\mathcal M} \models A[\bar a / x]\). In our example above, \({\mathcal M} \not\models \forall x \; (R(x, b))\), since when we interpret \(x\) as 2 we do not have \({\mathcal M} \models R(x, b)\).

These rules allow us to determine the truth value of any sentence in a model. (Remember, a sentence is a formula with no free variables.) There are some subtleties: for instance, we’ve implicitly assumed that our formula doesn’t quantify over the same variable twice, as in \(\forall x \; \exists x \; A\). But for the most part, the interpretation process tells us to “read” a formula as talking directly about objects in the domain.

10.3. Examples

Take a simple language with no constant symbols, one relation symbol \(\leq\), and one binary function symbol \(+\). Our model \({\mathcal M}\) will have domain \({\mathbb N}\), and the symbols will be interpreted as the standard less-than-or-equal-to relation and addition function.

Think about the following questions before you read the answers below. Remember, our domain is \({\mathbb N}\), not \({\mathbb Z}\) or any other number system.

  1. Is it true that \({\mathcal M} \models \exists x \; (x \leq x)\)? What about \({\mathcal M} \models \forall x \; (x \leq x)\)?

  2. Similarly, what about \({\mathcal M} \models \exists x \; (x + x \leq x)\)? \({\mathcal M} \models \forall x \; (x + x \leq x)\)?

  3. Do the sentences \(\exists x \; \forall y \; (x \leq y)\) and \(\forall x \; \exists y \; (x \leq y)\) mean the same thing? Are they true or false?

  4. Can you think of a formula \(A\) in this language, with one free variable \(x\), such that \({\mathcal M} \models \forall x \; A\) but \({\mathcal M} \not \models \exists x \; A\)?

These questions indicate a subtle, and often tricky, interplay between the universal and existential quantifiers. Once you’ve thought about them a bit, read the answers:

  1. Both of these statements are true. For the former, we can (for example) interpret \(x\) as the natural number 0. Then, \({\mathcal M} \models x \leq x\), so the existential is true. For the latter, pick an arbitrary natural number \(n\); it is still the case that when we interpret \(x\) as \(n\), we have \({\mathcal M} \models x \leq x\).

  2. The first statement is true, since we can interpret \(x\) as 0. The second statement, though, is false. When we interpret \(x\) as 1 (or, in fact, as any natural number besides 0), we see that \({\mathcal M} \not \models x + x \leq x\).

  3. These sentences do not mean the same thing, although in the specified model, both are true. The first expresses that some natural number is less than or equal to every natural number. This is true: 0 is less than or equal to every natural number. The second sentence says that for every natural number, there is another natural number at least as big. Again, this is true: every natural number \(a\) is less than or equal to \(a\). If we took our domain to be \({\mathbb Z}\) instead of \({\mathbb N}\), the first sentence would be false, while the second would still be true.

  4. The situation described here is impossible in our model. If \({\mathcal M} \models \forall x A\), then \({\mathcal M} \models A [\bar 0 / x]\), which implies that \({\mathcal M} \models \exists x A\). The only time this situation can happen is when the domain of our model is empty.

Now consider a different language with constant symbol 2, predicate symbols \(\mathit{prime}\) and \(\mathit{odd}\), and binary relation \(<\), interpreted in the natural way over domain \({\mathbb N}\). The sentence \(\forall x \; (2 < x \wedge \mathit{prime}(x) \to \mathit{odd}(x))\) expresses the fact that every prime number bigger than 2 is odd. It is an example of relativization, discussed in Section 7.4. We can now see semantically how relativization works. This sentence is true in our model if, for every natural number \(n\), interpreting \(x\) as \(n\) makes the sentence true. If we interpret \(x\) as 0, 1, or 2, or as any non-prime number, the hypothesis of the implication is false, and thus \(2 < x \wedge \mathit{prime}(x) \to \mathit{odd}(x)\) is true. Otherwise, if we interpret \(x\) as a prime number bigger than 2, both the hypothesis and conclusion of the implication are true, and \(2 < x \wedge \mathit{prime}(x) \to \mathit{odd}(x)\) is again true. Thus the universal statement holds. It was an example like this that partially motivated our semantics for implication back in Chapter 3; any other choice would make relativization impossible.

For the next example, we will consider models that are given by a rectangular grid of “dots.” Each dot has a color (red, blue, or green) and a size (small or large). We use the letter \(R\) to represent a large red dot and \(r\) to represent a small red dot, and similarly for \(G, g, B, b\).

The logical language we use to describe our dot world has predicates \(\mathit{red}\), \(\mathit{green}\), \(\mathit{blue}\), \(\mathit{small}\) and \(\mathit{large}\), which are interpreted in the obvious ways. The relation \(\mathit{adj}(x, y)\) is true if the dots referred to by \(x\) and \(y\) are touching, not on a diagonal. The relations \(\mathit{same{\mathord{\mbox{-}}}color}(x, y)\), \(\mathit{same{\mathord{\mbox{-}}}size}(x, y)\), \(\mathit{same{\mathord{\mbox{-}}}row}(x, y)\), and \(\mathit{same{\mathord{\mbox{-}}}column}(x, y)\) are also self-explanatory. The relation \(\mathit{left{\mathord{\mbox{-}}}of}(x, y)\) is true if the dot referred to by \(x\) is left of the dot referred to by \(y\), regardless of what rows the dots are in. The interpretations of \(\mathit{right{\mathord{\mbox{-}}}of}\), \(\mathit{above}\), and \(\mathit{below}\) are similar.

Consider the following sentences:

  1. \(\forall x \; (\mathit{green}(x) \vee \mathit{blue}(x))\)

  2. \(\exists x, y \; (\mathit{adj}(x, y) \wedge \mathit{green}(x) \wedge \mathit{green}(y))\)

  3. \(\exists x \; ((\exists z \; \mathit{right{\mathord{\mbox{-}}}of}(z, x)) \wedge (\forall y \; (\mathit{left{\mathord{\mbox{-}}}of}(x, y) \to \mathit{blue}(y) \vee \mathit{small}(y))))\)

  4. \(\forall x \; (\mathit{large}(x) \to \exists y \; (\mathit{small}(y) \wedge \mathit{adj}(x, y)))\)

  5. \(\forall x \; (\mathit{green}(x) \to \exists y \; (\mathit{same{\mathord{\mbox{-}}}row}(x, y) \wedge \mathit{blue}(y)))\)

  6. \(\forall x, y \; (\mathit{same{\mathord{\mbox{-}}}row}(x, y) \wedge \mathit{same{\mathord{\mbox{-}}}column}(x, y) \to x = y)\)

  7. \(\exists x \; \forall y \; (\mathit{adj}(x, y) \to \neg \mathit{same{\mathord{\mbox{-}}}size}(x, y))\)

  8. \(\forall x \; \exists y \; (\mathit{adj}(x, y) \wedge \mathit{same{\mathord{\mbox{-}}}color}(x, y))\)

  9. \(\exists y \; \forall x \; (\mathit{adj}(x, y) \wedge \mathit{same{\mathord{\mbox{-}}}color}(x, y))\)

  10. \(\exists x \; (\mathit{blue}(x) \wedge \exists y \; (\mathit{green}(y) \wedge \mathit{above}(x, y)))\)

We can evaluate them in this particular model:

R

r

g

b

R

b

G

b

B

B

B

b

There they have the following truth values:

  1. false

  2. true

  3. true

  4. false

  5. true

  6. true

  7. false

  8. true

  9. false

  10. true

For each sentence, see if you can find a model that makes the sentence true, and another that makes it false. For an extra challenge, try to make all of the sentences true simultaneously. Notice that you can use any number of rows and any number of columns.

10.4. Validity and Logical Consequence

We have seen that whether a formula is true or false often depends on the model we choose. Some formulas, though, are true in every possible model. An example we saw earlier was \(\forall y \; (\mathit{le}(0, y) \to \mathit{le}(0, y))\). Why is this sentence valid? Suppose \({\mathcal M}\) is an arbitrary model of the language, and suppose \(a\) is an arbitrary element of the domain of \({\mathcal M}\). Either \({\mathcal M} \models \mathit{le}(0, \bar a)\) or \({\mathcal M} \models \neg \mathit{le}(0, \bar a)\). In either case, the propositional semantics of implication guarantee that \({\mathcal M} \models \mathit{le}(0, \bar a) \to \mathit{le}(0, \bar a)\). We often write \(\models A\) to mean that \(A\) is valid.

In the propositional setting, there is an easy method to figure out if a formula is a tautology or not. Writing the truth table and checking for any rows ending with \(\mathbf{F}\) is algorithmic, and we know from the beginning exactly how large the truth table will be. Unfortunately, we cannot do the same for first-order formulas. Any language has infinitely many models, so a “first-order” truth table would be infinitely long. To make matters worse, even checking whether a formula is true in a single model can be a non-algorithmic task. To decide whether a universal statement like \(\forall x \; P(x)\) is true in a model with an infinite domain, we might have to check whether \(P\) is true of infinitely many elements.

This is not to say that we can never figure out if a first-order sentence is a tautology. For example, we have argued that \(\forall y \; (\mathit{lt}(0, y) \to \mathit{lt}(0, y))\) was one. It is just a more difficult question than for propositional logic.

As was the case with propositional logic, we can extend the notion of validity to a notion of logical consequence. Fix a first-order language, \(L\). Suppose \(\Gamma\) is a set of sentences in \(L\), and \(A\) is a sentence of \(L\). We will say that \(A\) is a logical consequence of \(\Gamma\) if every model of \(\Gamma\) is a model of \(A\). This is one way of spelling out that \(A\) is a “necessary consequence” of \(A\): under any interpretation, if the hypotheses in \(\Gamma\) come out true, \(A\) is true as well.

10.5. Soundness and Completeness

In propositional logic, we saw a close connection between the provable formulas and the tautologies—specifically, a formula is provable if and only if it is a tautology. More generally, we say that a formula \(A\) is a logical consequence of a set of hypotheses, \(\Gamma\), if and only if there is a natural deduction proof of \(A\) from \(\Gamma\). It turns out that the analogous statements hold for first order logic.

The “soundness” direction—the fact that if \(A\) is provable from \(\Gamma\) then \(A\) is true in any model of \(\Gamma\)—holds for reasons that are similar to the reasons it holds in the propositional case. Specifically, the proof proceeds by showing that each rule of natural deduction preserves the truth in a model.

The completeness theorem for first order logic was first proved by Kurt Gödel in his 1929 dissertation. Another, simpler proof was later provided by Leon Henkin.

Theorem. If a formula \(A\) is a logical consequence of a set of sentences \(\Gamma\), then \(A\) is provable from \(\Gamma\).

Compared to the version for propositional logic, the first order completeness theorem is harder to prove. We will not go into too much detail here, but will indicate some of the main ideas. A set of sentences is said to be consistent if you cannot prove a contradiction from those hypotheses. Most of the work in Henkin’s proof is done by the following “model existence” theorem:

Theorem. Every consistent set of sentences has a model.

From this theorem, it is easy to deduce the completeness theorem. Suppose there is no proof of \(A\) from \(\Gamma\). Then the set \(\Gamma \cup \{ \neg A \}\) is consistent. (If we could prove \(\bot\) from \(\Gamma \cup \{ \neg A \}\), then by the reductio ad absurdum rule we could prove \(A\) from \(\Gamma\).) By the model existence theorem, that means that there is a model \({\mathcal M}\) of \(\Gamma \cup \{ \neg A \}\). But this is a model of \(\Gamma\) that is not a model of \(A\), which means that \(A\) is not a logical consequence of \(\Gamma\).

The proof of the model existence theorem is intricate. Somehow, from a consistent set of sentences, one has to build a model. The strategy is to build the model out of syntactic entities, in other words, to use terms in an expanded language as the elements of the domain.

The moral here is much the same as it was for propositional logic. Because we have developed our syntactic rules with a certain semantics in mind, the two exhibit different sides of the same coin: the provable sentences are exactly the ones that are true in all models, and the sentences that are provable from a set of hypotheses are exactly the ones that are true in all models of those hypotheses.

We therefore have another way to answer the question posed in the previous section. To show that a sentence is valid, there is no need to check its truth in every possible model. Rather, it suffices to produce a proof.

10.6. Exercises

  1. In a first-order language with a binary relation, \(R(x,y)\), consider the following sentences:

    • \(\exists x \; \forall y \; R(x, y)\)

    • \(\exists y \; \forall x \; R(x, y)\)

    • \(\forall x,y \; (R(x,y) \wedge x \neq y \to \exists z \; (R(x,z) \wedge R(z,y) \wedge x \neq z \wedge y \neq z))\)

    For each of the following structures, determine whether of each of those sentences is true or false.

    • the structure \((\mathbb N, \leq)\), that is, the interpretation in the natural numbers where \(R\) is \(\leq\)

    • the structure \((\mathbb Z, \leq)\)

    • the structure \((\mathbb Q, \leq)\)

    • the structure \((\mathbb N, \mid)\), that is, the interpretation in the natural numbers where \(R\) is the “divides” relation

    • the structure \((P(\mathbb N), \subseteq)\), that is, the interpretation where variables range over sets of natural numbers, where \(R\) is interpreted as the subset relation.

  2. Create a 4 x 4 “dots” world that makes all of the following sentences true:

    • \(\forall x \; (\mathit{green}(x) \vee \mathit{blue}(x))\)

    • \(\exists x, y \; (\mathit{adj}(x, y) \wedge \mathit{green}(x) \wedge \mathit{green}(y))\)

    • \(\exists x \; (\exists z \; \mathit{right{\mathord{\mbox{-}}}of}(z, x) \wedge \forall y \; (\mathit{left{\mathord{\mbox{-}}}of}(x, y) \to \mathit{blue}(y) \vee \mathit{small}(y)))\)

    • \(\forall x \; (\mathit{large}(x) \to \exists y \; (\mathit{small}(y) \wedge \mathit{adj}(x, y)))\)

    • \(\forall x \; (\mathit{green}(x) \to \exists y \; (\mathit{same{\mathord{\mbox{-}}}row}(x, y) \wedge \mathit{blue}(y)))\)

    • \(\forall x, y \; (\mathit{same{\mathord{\mbox{-}}}row}(x, y) \wedge \mathit{same\mathord{\mbox{-}} column}(x, y) \to x = y)\)

    • \(\exists x \; \forall y \; (\mathit{adj}(x, y) \to \neg \mathit{same{\mathord{\mbox{-}}}size}(x, y))\)

    • \(\forall x \; \exists y \; (\mathit{adj}(x, y) \wedge \mathit{same{\mathord{\mbox{-}}}color}(x, y))\)

    • \(\exists y \; \forall x \; (\mathit{adj}(x, y) \to \mathit{same{\mathord{\mbox{-}}}color}(x, y))\)

    • \(\exists x \; (\mathit{blue}(x) \wedge \exists y \; (\mathit{green}(y) \wedge \mathit{above}(x, y)))\)

  3. Fix a first-order language \(L\), and let \(A\) and \(B\) be any two sentences in \(L\). Remember that \(\vDash A\) means that \(A\) is valid. Unpacking the definitions, show that if \(\vDash A \wedge B\), then \(\vDash A\) and \(\vDash B\).

  4. Give a concrete example to show that \(\vDash A \vee B\) does not necessarily imply \(\vDash A\) or \(\vDash B\). In other words, pick a language \(L\) and choose particular sentences \(A\) and \(B\) such that \(A \vee B\) is valid but neither \(A\) nor \(B\) is valid.

  5. Consider the three formulas \(\forall x \; R(x, x)\), \(\forall x\; \forall y \; (R (x, y) \to R (y, x))\), and \(\forall x \; \forall y \; \forall z \; (R(x, y) \wedge R(y, z) \to R(x, z))\). These sentences say that \(R\) is reflexive, symmetric, and trainsitive. For each pair of sentences, find a model that makes those two sentences true and the third false. This shows that these sentences are logically independent: no one is entailed by the others.

  6. Show that if a set of formulas \(\{\psi_1, \ldots, \psi_n\}\) is semantically inconsistent, then it entails every formula \(\phi\). Does the converse also hold?

  7. Give a formula \(\psi\) such that the set \(\{P(c), \neg P(D), \psi \}\) is consistent, and so is the set \(\{P(c), \neg P(D), \neg \psi \}\).

  8. For each the following formulas, show whether the formula is valid, satisfiable, or unsatisfiable.

    • \(\exists x \; \forall y \; R (y, x) \wedge R (x, y)\)

    • \((\exists x \; \forall y \; R (x, y)) \to (\exists x \; \exists y \; R (x, y))\)

    • \((\exists x\; P (x)) \wedge (\exists x \; \neg P(x))\)