A formal semantics for QL

In this chapter, we describe a formal semantics for QL. This corresponds to the discussion of interpretations and truth in SL given in Chapter 4. Like truth in SL, truth in QL is defined relative to a particular interpretation; entailment is a matter of truth in all interpretations. In SL, models corresponded to assignments of truth values to atomic sentences. For example, here is an SL model:

ℐ = {P = 0, Q = 1, R = 0}

Interpretation settles the truth value of any SL sentence one can construct from P, Q, and R. Because QL involves richer notions and a more complex vocabulary than SL, it requires correspondingly richer models and interpretations.

9.1 Interpretations in QL

What is an interpretation in QL? Like a symbolization key for QL, an interpretation requires a universe of discourse, a schematic meaning for each of the predicates, and an object that is picked out by each constant. For example:

UD: Marvel characters
Hx: x is a hero.
Sx: x has spider powers.
m: Miles Morales
p: Peter Parker
r: The Red Skull
s: Susan Storm
u: Ultimate Spider-Man

This interpretation is given in terms of English descriptions. To apply it, you need to know some details about the characters in question. For example, Sm is true on this interpretation, because Miles Morales does have spider powers. But the interpretation itself doesn't tell us that --- to get that information from this way of setting out the interpretation, you need to know some details about what happens in the story. You need to know, for example, that Miles Morales, like his more famous mentor Peter Parker, also has spider powers. If you do know a bit about Marvel comics, you may know that Miles Morales is actually the Ultimate Spider-Man. So u and m in this interpretation are two different names for the same member of the UD. There is no rule against having multiple names for the same member. (We'll discuss this issue in much more detail in Chapter 12.

We want our QL models to encode this kind of information too. Like a good SL model, a QL model shouldn't require prior knowledge of comic books. One way we could try to do this would be to just give a truth value assignment, as we did for SL. The truth value assignment would assign 0 or 1 to each atomic wff: Sm = 1, Sp = 1, Sr = 0, and so on. If we were to do that, however, we might just as well translate the sentences from QL to SL by replacing Sp and Sm with sentence letters. We could then rely on the definition of truth for SL, but at the cost of ignoring all the logical structure of predicates and terms. In writing a symbolization key for QL, we do not give separate definitions for Sp and Sm. Instead, we give meanings to the components S, p, and m. This is essential because we want to be able to reflect the logical relationships between e.g. Sp and ∃xSx.

Our interpretations should include explanations for predicates and names, not just for sentences. We cannot use a truth value assignment for this, because a predicate by itself is neither true nor false. In the interpretation given above, H is true of Peter Parker (i.e., Hp is true), but it makes no sense at all to ask whether H on its own is true. It would be like asking whether the English language fragment '…is a hero' is true.

What does an interpretation do for a predicate, if it does not make it true or false? An interpretation helps to pick out the objects to which the predicate applies. Interpreting Hx to mean 'x is a hero' picks out some characters as the things that are Hs. Formally, this is a set of members of the UD to which the predicate applies; this set is called the extensions of the predicate.

Some predicates have indefinitely large extensions. It would be impractical to try and write down all of the Marvel characters individually, so instead we use an English language expression to interpret the predicate. This is somewhat imprecise, because the interpretation alone does not tell you which members of the UD are in the extension of the predicate. In order to figure out whether a particular member of the UD is in the extension of the predicate (to figure out whether the Red Skull is a hero, for instance), you need to know about comic books. (As you might guess from his name, he's not.) In general, the extension of a predicate is the result of an interpretation along with some facts.

Sometimes it is possible to list all of the things that are in the extension of a predicate. Instead of writing a schematic English sentence, we can write down the extension as a set of things. Suppose we wanted to add a one-place predicate F to the key above, meaning 'x is a founding member of the Fantastic Four', so we write the extension as a set of characters:

extension(F) = {Reed Richards, Susan Storm, Johnny Storm, Ben Grimm}

You do not need to know anything about comic books to be able to determine that, on this interpretation, Fs is true: Susan Storm, whose name is given as s, is just specified to be one of the things that is F. Similarly, ∃xFx is obviously true on this interpretation: There is at least one member of the UD that is an F --- in fact, there are four of them.

What about the sentence ∀xFx? The sentence is false, because it is not true that all members of the UD are F. It requires the barest minimum of knowledge about comic books to know that there are other characters besides just these four. Although we specified the extension of F in a formally precise way, we still specified the UD with an English language description. Formally speaking, a UD is just a set of members.

The formal significance of a predicate is determined by its extension, but what should we say about constants like m and s? The meaning of a constant determines which member of the UD is picked out by the constant. The individual that the constant picks out is called the referent of the constant. Both m and u have the same referent, since they both refer to the same comic book character. You can think of a constant letter as a name and the referent as the thing named. In English, we can use the different names 'Miles' and 'Ultimate Spider-Man' to refer to the same comic book character. In this interpretation, we also use the different constants 'm' and 'u' to refer to the same member of the UD.

9.2 Sets

We use curly brackets '{' and '}' to denote sets. The members of the set can be listed in any order, separated by commas. This means that {foo, bar} and {bar, foo} are the same set.

It is possible to have a set with no members in it. This is called the empty set. The empty set is sometimes written as {}, but usually it is written as the single symbol ∅.

9.3 Models

As we have seen, an interpretation in QL is only formally significant insofar as it determines a UD, an extension for each predicate, and a referent for each constant. We call this formal structure a model for QL.

To see how this works, consider this symbolization key:

UD: The first ten natural numbers
Px: x is prime.
n₄: 4

Given some basic mathematical knowledge, it is obvious that Pn₄ is false. Let's consider the model this interpretation suggests, to show why it makes this wff false. Instead of just giving a description in the UD, we can list the members as a set. We also define the extension of the predicate P, and the referent of the constant n₄:

UD: {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
extension(P): {2, 3, 5, 7}
referent(n₄): 4

This is not a full model for this interpretation, but it is a detailed enough partial model to show that Pn₄ is false. You do not need to know anything about mathematics to see that this sentence is false in this model. The UD member named by n₄ is not in the extension of P. In this way, the model captures all of the formal significance of the interpretation.

Suppose we enrich this interpretation with more predicates:

UD: The first ten natural numbers
Ex: x is even.
Nx: x is negative.
Lxy: x is less than y.
Txyz: x times y equals z.

What do we need to add to the model for our new predicates?

The extension of E is the subset {2, 4, 6, 8, 10}. There are no negative numbers in the UD, so N has an empty extension; i.e. extension(N) = ∅.

Sometimes it will be convenient to represent extensions graphically, similar to the way we did with truth tables. We can represent the extensions just described for P, E, and N thus:

The members of the UD are listed as rows; the predicates are given as columns. The 0s and 1s indicate whether each member satisfies each predicate. Notice that the same information is conveyed in this chart as in the three sets of ordered pairs described above. Either is an acceptable way of indicating the extension of the predicates.

The extension of a two-place predicate like L is more complicated. No individual number falls under the extension of this predicate; it is about the relation between members. Note also that sets of pairs numbers aren't suitable for the extension of L either, because 1 is less than 8, but 8 is not less than 1. And the set {1,8} is the very same set as the set {8,1}. The solution is to have the extension of L consist in a set of ordered pairs of numbers. An ordered pair is like a set with two members, except that the order does matter. We write ordered pairs with angle brackets '⟨' and '⟩'. The ordered pair is different than the ordered pair . The extension of L is a collection of ordered pairs, all of the pairs of numbers in the UD such that the first number is less than the second. Writing this out completely:

extension(L) = {⟨1, 2⟩, ⟨1, 3⟩, ⟨1, 4⟩, ⟨1, 5⟩, ⟨1, 6⟩, ⟨1, 7⟩, ⟨1, 8⟩, ⟨1, 9⟩, ⟨1, 10⟩, ⟨2, 3⟩, ⟨2, 4⟩, ⟨2, 5⟩, ⟨2, 6⟩, ⟨2, 7⟩, ⟨2, 8⟩, ⟨2, 9⟩, ⟨2, 10⟩, ⟨3, 4⟩, ⟨3, 5⟩, ⟨3, 6⟩, ⟨3, 7⟩, ⟨3, 8⟩, ⟨3, 9⟩, ⟨3, 10⟩, ⟨4, 5⟩, ⟨4, 6⟩, ⟨4, 7⟩, ⟨4, 8⟩, ⟨4, 9⟩, ⟨4, 10⟩, ⟨5, 6⟩, ⟨5, 7⟩, ⟨5, 8⟩, ⟨5, 9⟩, ⟨5, 10⟩, ⟨6, 7⟩, ⟨6, 8⟩, ⟨6, 9⟩, ⟨6, 10⟩, ⟨7, 8⟩, ⟨7, 9⟩, ⟨7, 10⟩, ⟨8, 9⟩, ⟨8, 10⟩⟨9, 10⟩}

Formally, the extension of a two-place predicate is a set of ordered pairs. Sometimes we will find it easier to represent extensions in a chart, with the two variable positions represented on the two axes. For example, the extension above could be expressed via a table like the one below. The '0' in the first cell of the table says that is not in the extension of L; the next cell in the first row says that is. Etc. Sometimes drawing out a chart like this will be the easiest way to represent models for the extensions of two-place predicates.

The extension of a three-place predicate is a set of ordered triples where the predicate is true of those three things in that order. So the extension of T in this model will contain ordered triples like , because 2 × 4 = 8. Because the surface of a sheet of paper is for all intents and purposes two-dimensional, it is usually not convenient to represent 3-or-more place predicates with tables.

Generally, the extension of an n-place predicate is a set of all ordered n-tuples ⟨a₁, a₂, …, a_n⟩ such that a₁-a_n are members of the UD and the predicate is true of a₁-a_n in that order.

9.4 Extensions of 0-place predicates

What of a 0-place predicate? Recall from Chapter 8 that a 0-place predicate corresponds to an SL sentence letter --- it will take a truth value in an interpretation without reference to any particular objects. So a QL model will provide truth values to 0-place predicates directly, just like an SL valuation function did.

This actually follows from the general description of n-place predicates given in the previous section: the extension of an n-place predicate is a set of ordered n-tuples. In the special case where n = 0, the extension of the predicate will be a set of 0-tuples. But there is only one possible 0-tuple: the empty set, ∅. So there are only two possible extensions of a 0-place predicate, corresponding to the choice of whether ∅ is included in the extension or not. (Formally, the extension will either be the set containing the empty set --- {∅} --- or it will be the empty set ∅ itself.)

For clarity and convenience, when indicating the extension of 0-place predicates in QL models, we'll simply indicate the truth values for the sentences themselves, like we did in SL. So we might indicate the extensions of 0-place predicates, for instance, by writing

P = 1, Q = 0

instead of the more confusing

extension(P) = {∅}, extension(Q) = ∅

So in the special case where we are \emph{only} working with 0-place predicates, QL models directly provide SL valuation functions. This is another respect in which QL is simply a generalization of SL. If you ignore the UD and the extensions of higher-place predicates, a QL model provides the same information we were using to discuss SL models in Chapter 4.

9.5 Working with models

We will use the double turnstile symbol for QL much as we did for SL. 'Φ ⊨ Ψ' means that 'Φ entails Ψ': When Φ and Ψ are two sentences of QL, Φ ⊨ Ψ means that there is no model in which is true and is false.  ⊨ Φ is shorthand for ∅ ⊨ Φ, which means that is true in every model. This allows us to give definitions for various concepts in QL. In fact, we can use the same definitions offered in Chapter 4.

A tautology is a sentence that is true in every model; i.e.,  ⊨ Φ.

A contradiction is a sentence that is false in every model; i.e.,  ⊨ ¬Φ.

A sentence is contingent if and only if it is neither a tautology nor a contradiction.

An argument "𝒫₁, 𝒫₂, ⋯,∴Ω" is valid if and only if there is no model in which all of the premises are true and the conclusion is false; i.e., {𝒫₁, 𝒫₂, ⋯} ⊨ Ω. It is otherwise.

Two sentences Φ and Ψ are logically equivalent if and only if both Φ ⊨ Ψ and Ψ ⊨ Φ.

The set {Φ₁, Φ₂, Φ₃, ⋯} is consistent if and only if there is at least one model in which all of the sentences are true. The set is if and only if there is no such model.

9.6 Constructing models

Suppose we want to show that ∀xAxx ⊃ Bd is not a tautology. This requires showing that the sentence is not true in every model. If we can provide an example of a model in which the sentence is false, then we will have shown that the sentence is not a tautology.

What would such a model look like? In order for ∀xAxx ⊃ Bd to be false, the antecedent (∀xAxx) must be true, and the consequent (Bd) must be false.

To construct such a model, we start with a UD. It will be easier to specify extensions for predicates if we have a small UD, so start with a UD that has just one member. Formally, this single member might be anything. Let's say it is Miles Morales.

We want ∀xAxx to be true, so we want all members of the UD to be paired with themself in the extension of A; this means that the extension of A must be {⟨Miles Morales, Miles Morales⟩}.

We want Bd to be false, so the referent of d must not be in the extension of B. We give B an empty extension.

Since Miles is the only member of the UD, it must be the referent of d. The model we have constructed looks like this:

UD: {Miles Morales}
extension(A): {⟨Miles Morales, Miles Morales⟩}
extension(B): ∅
referent(d): Miles Morales.

Strictly speaking, a model specifies an extension for every predicate of QL and a referent for every constant. As such, it is generally impossible to write down a complete model. That would require writing down infinitely many extensions and infinitely many referents. However, we do not need to consider every predicate in order to show that there are models in which ∀xAxx ⊃ Bd is false. Predicates like H and constants like f₁₃ make no difference to the truth or falsity of this sentence. It is enough to specify extensions for A and B and a referent for d, as we have done. This provides a partial model in which the sentence is false.

Perhaps you are wondering: What does the predicate A mean in English? It doesn't really matter. For formal purposes, the existence of models like the ones described above are enough to show that ∀xAxx ⊃ Bd is not a tautology. But we can offer an interpretation in English if we like. How about this one?

UD: Miles Morales
Axy: x knows y's biggest secret.
Bx: x's powers derive from gamma radiation.
d: Miles Morales.

This is one way we can interpret the model above. Add is true, because Miles does know Miles's biggest secret. (It's that he's the Ultimate Spider-Man. Now you know it too!) Bd is false: Miles's powers came from a genetically enhanced spider bite, not from gamma radiation. But the partial model constructed above includes none of these interpretative details. All it says is that A is a predicate which is true of Miles and Miles, and that B is a predicate which does not apply to Miles. There are indefinitely many predicates in English that have this extension. Axy might instead translate 'x is the same size as y' or 'x and y live in the same city'; Bx might translate 'x is a billionaire' or 'x's uncle was killed by a robber' or 'Donald Trump has written a tweet about x'. In constructing a model and giving extensions for A and B, we do not specify what English predicates A and B should be used to translate. We are concerned with whether the ∀xAxx ⊃ Bd comes out true or false, and all that matters for truth and falsity in QL is the information in the model: the UD, the extensions of predicates, and the referents of constants.

We can just as easily show that ∀xAxx ⊃ Bd is not a contradiction. We need only specify a model in which ∀xAxx ⊃ Bd is true; i.e., a model in which either ∀xAxx is false or Bd is true. Here is one such partial model:

UD: {The Red Skull}
extension(A): {⟨The Red Skull, The Red Skull⟩}
extension(B): {The Red Skull}
referent(d): The Red Skull.

I've switched our object from Miles Morales to The Red Skull to emphasize that it doesn't matter what object you pick. (Changing the examples all back to Miles would make no difference.) On this model, ∀xAxx ⊃ Bd is true, because it is a conditional with a true consequent (as well as a true antecedent). We have now shown that ∀xAxx ⊃ Bd is neither a tautology nor a contradiction. By the definition of 'contingent in QL,' this means that ∀xAxx ⊃ Bd is contingent. In general, showing that a sentence is contingent will require two models: one in which the sentence is true and another in which the sentence is false.

Suppose we want to show that ∀xSx and ∃xSx are not logically equivalent. We need to construct a model in which the two sentences have different truth values; we want one of them to be true and the other to be false. We start by specifying a UD. Again, we make the UD reasonably small so that we can specify extensions easily. But this time we will need at least two members. If we only had one member of the domain, we wouldn't be able to illustrate the difference between all and some. Let's let our UD be {The Red Skull, Miles Morales}.

We can make ∃xSx true by including something in the extension of S, and we can make ∀xSx false by leaving something out of the extension of S. It does not matter which one we include and which one we leave out. Making Miles the only S, we get a partial model that looks like this:

UD: {Miles, The Red Skull}
extension(S): {Miles}

This partial model shows that the two sentences are not logically equivalent. ∃xSx is assigned 1 on this model, but ∀xSx is assigned 0.

Back in Chapter 8, we said that this argument would be invalid in QL:

1. (Rc & K₁c)&Tc
Tc & K₂c

Now we can prove that this is so. To show that this argument is invalid, we need to show that there is some model in which the premise is true and the conclusion is false. We can construct such a model deliberately. Here is one way to do it:

UD: {Reed Richards}
extension(T): {Reed Richards}
extension(K₁): {Reed Richards}
extension(K₂): ∅
extension(R): {Reed Richards}
referent(c): Reed Richards.

Similarly, we can show that a set of sentences is consistent by constructing a model in which all of the sentences are true.

9.7 Reasoning about all models

We can show that a sentence is not a tautology just by providing one carefully specified model: a model in which the sentence is false. To show that something is a tautology, on the other hand, it would not be enough to construct ten, one hundred, or even a thousand models in which the sentence is true. It is only a tautology if it is true in every model, and there are infinitely many models. This cannot be avoided just by constructing partial models, because there are infinitely many partial models.

Consider, for example, the sentence Raa ≡ Raa. There are two logically distinct partial models of this sentence that have a 1-member UD. There are 32 distinct partial models that have a 2-member UD. There are 1526 distinct partial models that have a 3-member UD. There are 262,144 distinct partial models that have a 4-member UD. And so on to infinity. In order to show that this sentence is a tautology, we need to show something about all of these models. There is no hope of doing so by dealing with them one at a time.

Nevertheless, Raa ≡ Raa is obviously a tautology. We can prove it with a simple argument:

There are two kinds of models: those with ⟨referent(a), referent(a)⟩ is in the extension of R and those in which it is not. In the first kind of model, Raa is true; by the truth table for the biconditional, Raa ≡ Raa is also true. In the second kind of model, Raa is false; this makes Raa ≡ Raa true. Since the sentence is true in both kinds of model, and since every model is one of the two kinds, Raa ≡ Raa is true in every model. Therefore, it is a tautology.

This is a sound argument; it should convince us of its conclusion. But note that it is not an argument in QL. Rather, it is an argument in English about QL; it is an argument in the metalanguage. There is no formal procedure for evaluating or constructing natural language arguments like this one. The imprecision of natural language is the very reason we began thinking about formal languages.

There are further difficulties with this approach.

Consider the sentence ∀x(Rxx⊃Rxx), another obvious tautology. It might be tempting to reason in this way: 'Rxx ⊃ Rxx is true in every model, so ∀x(Rxx⊃Rxx) must be true.' The problem is that Rxx ⊃ Rxx is not true in every model. It is not a sentence, and so it is neither true nor false. We do not yet have the vocabulary to say what we want to say about Rxx ⊃ Rxx. In the next section, we introduce the concept of satisfaction; after doing so, we will be better able to provide an argument that ∀x(Rxx⊃Rxx) is a tautology.

It is necessary to reason about an infinity of models to show that a sentence is a tautology. Similarly, it is necessary to reason about an infinity of models to show that a sentence is a contradiction, that two sentences are equivalent, that a set of sentences is inconsistent, or that an argument is valid. There are other things we can show by carefully constructing a model or two. Table 9.1 summarizes which things are which.

9.8 Truth in QL

For SL, we split the definition of truth into two parts: a truth value assignment (a) for sentence letters and a truth function (v) for all sentences. The truth function covered the way that complex sentences could be built out of sentence letters and connectives.

In the same way that truth for SL is always truth given a truth value assignment, truth for QL is truth in a model. The atomic sentences, again, are n-place predicates followed by n constants, like Pj. It is true in a model 𝕄 if and only if the referent of j is in the extension of P in 𝕄.

We could go on in this way to define truth for all atomic sentences that contain only predicates and constants: Consider any sentence of the form ℛ𝒶₁…𝒶_n where is an n-place predicate and the s are constants. It is true in 𝕄 if and only if ⟨referent(𝒶₁), …, referent(𝒶_n)⟩ is in extension(ℛ) in 𝕄.

We could then define truth for sentences built up with sentential connectives in the same way we did for SL. For example, the sentence (Pj⊃Mda) is true in 𝕄 if either Pj is false in 𝕄 or Mda is true in 𝕄.

Unfortunately, this approach will fail when we consider sentences containing quantifiers. Consider ∀xPx. When is it true in a model 𝕄? The answer cannot depend on whether Px is true or false in 𝕄, because the x in Px is a free variable. Px is not a sentence. It is neither true nor false.

We were able to give a recursive definition of truth for SL because every well-formed formula of SL has a truth value. This is not true in QL, so we cannot define truth by starting with the truth of atomic sentences and building up. We also need to consider the atomic formulae which are not sentences. In order to do this we will define satisfaction; every well-formed formula of QL will be satisfied or not satisfied, even if it does not have a truth value. We will then be able to define truth for sentences of QL in terms of satisfaction.

9.9 Satisfaction

The formula Px says, roughly, that x is one of the Ps. This cannot be quite right, however, because x is a variable and not a constant. It does not name any particular member of the UD. Instead, its meaning in a sentence is determined by the quantifier that binds it. The variable x must stand-in for every member of the UD in the sentence ∀xPx, but it only needs to stand-in for one member in ∃xPx. Since we want the definition of satisfaction to cover Px without any quantifier whatsoever, we will start by saying how to interpret a free variable like the x in Px.

We do this by introducing a variable assignment. Formally, this is a function that matches up each variable with a member of the UD. Call this function 'a'. (The 'a' is for 'assignment', but this is not the same as the truth value assignment that we used in defining truth for SL.)

The formula Px is satisfied in a model 𝕄 by a variable assignment a if and only if a(x), the object that a assigns to x, is in the extension of P in 𝕄.

When is ∀xPx satisfied? It is not enough if Px is satisfied in 𝕄 by a, because that just means that a(x) is in extension(P). ∀xPx requires that every other member of the UD be in extension(P) as well.

So we need another bit of technical notation: For any member π of the UD and any variable , let a[π|𝓍] be the variable assignment that assigns π to but agrees with a in all other respects. We have used π, the Greek letter pi, to underscore the fact that it is some member of the UD and not some symbol of QL. Suppose, for example, that the UD is presidents of the United States. The function a[Grover Cleveland|x] assigns Grover Cleveland to the variable x, regardless of what a assigns to x; for any other variable, a[Grover Cleveland|x] agrees with a.

We can now say concisely that ∀xPx is satisfied in a model by a variable assignment a if and only if, for every object π in the UD of , Px is satisfied in by a[π|x].

The intuitive thought here is that wff satisfaction is relative to a variable assignment. A variable assignment is a way of treating each variable as if it were a name for some object or other; a wff is satisfied by a in a given model iff, in that model, treating the variables the way a suggests would yield a true wff.

You may worry that our statement of satisfaction by a variable assignment in a model is circular, because it gives the satisfaction conditions for the sentence ∀xPx using the phrase 'for every object.' However, it is important to remember the difference between a logical symbol like '∀' and an English language word like 'every.' The word is part of the metalanguage that we use in defining satisfaction conditions for object language sentences that contain the symbol.

We can now give a general definition of satisfaction, extending from the cases we have already discussed. We define a function s (for 'satisfaction') in a model such that for any wff and variable assignment a, s(Φ,a) = 1 if is satisfied in by a; otherwise s(Φ,a) = 0.

1. If is an atomic wff of the form 𝒫𝓉₁…𝓉_n and π_i is the object picked out by t_i, then s(Φ,a) = 1 if ⟨π₁…π_n⟩ is in extension(𝒫) in 𝕄 and 0 otherwise. (For each term t_i: If t_i is a constant, then π_i = referent(t_i). If t_i is a variable, then π_i = a(t_i).)

2. If is ¬Ψ for some wff , then s(Φ,a) = 1 if s(Ψ,a) = 0 and 0 otherwise.

3. If is (Ψ&Ω) for some wffs Ψ, Ω, then s(Φ,a) = 1 if s(Ψ,a) = 1 and s(Ω,a) = 1, and 0 otherwise.

4. If is (Ψ∨Ω) for some wffs Ψ, Ω, then s(Φ,a) = 0 if s(Ψ,a) = 0 and s(Ω,a) = 0, and 1 otherwise.

5. If is (Ψ⊃Ω) for some wffs Ψ, Ω, then s(Φ,a) = 0 if s(Ψ,a) = 1 and s(Ω,a) = 0 and 1 otherwise.

6. If is (Ψ≡Ω) for some wffs Ψ, Ω, then s(Φ,a) = 1 if s(Ψ,a) = s(Ω,a) and 0 otherwise.

7. If is ∀𝓍Ψ for some wff Ψ and some variable 𝓍, then s(Φ,a) = 1if s(Ψ,a[π|𝓍]) = 1 for every member π of the UD and 0 otherwise.

8. If is ∃𝓍Ψ for some wff Ψ and some variable 𝓍, then s(Φ,a) = 1if s(Ψ,a[π|𝓍]) = 1 for at least one member π of the UD and 0 otherwise.

This definition follows the same structure as the definition of a wff for QL, so we know that every wff of QL will be covered by this definition. For a model and a variable assignment a, any wff will either be satisfied or not. No wffs are left out or assigned conflicting values.

9.10 Truth in QL

Consider a simple sentence like ∀xPx. By part 7 in the definition of satisfaction, this sentence is satisfied if a[π|x] satisfies Px in 𝕄 for every π in the UD. In other words, assign that x to any object in the UD you like, and the resultant wff will come out true. By part 1 of the definition, this will be the case if every π is in the extension of P. Whether ∀xPx is satisfied does not depend on the particular variable assignment a. If this sentence is satisfied, then it is true. This is a formalization of what we have said all along: ∀xPx is true if everything in the UD is in the extension of P.

The same thing holds for any sentence of QL. Because all of the variables are bound, a sentence is satisfied or not regardless of the details of the variable assignment. So we can define truth in this way: A sentence Φ is true in 𝕄 if and only if some variable assignment satisfies Φ in 𝕄; Φ is false in 𝕄 otherwise.

Truth in QL is truth in a model. Sentences of QL are not flat-footedly true or false as mere symbols, but only relative to a model. A model provides the meaning of the symbols, insofar as it makes any difference to truth and falsity.

9.11 Reasoning about all models (reprise)

At the end of section 9.6, we were stymied when we tried to show that ∀x(Rxx⊃Rxx) is a tautology. Having defined satisfaction, we can now reason in this way:

Consider some arbitrary model 𝕄. Now consider an arbitrary member of the UD; for the sake of convenience, call it π. It must be the case either that ⟨π, π⟩ is in the extension of R or that it is not. If ⟨π, π⟩ is in the extension of R, then Rxx is satisfied by a variable assignment that assigns π to x (by part 1 of the definition of satisfaction); since the consequent of Rxx ⊃ Rxx is satisfied, the conditional is satisfied (by part 5). If ⟨π, π⟩ is not in the extension of R, then Rxx is not satisfied by a variable assignment that assigns π to x (by part 1); since antecedent of Rxx ⊃ Rxx is not satisfied, the conditional is satisfied (by part 5). In either case, Rxx ⊃ Rxx is satisfied. This is true for any member of the UD, so ∀x(Rxx⊃Rxx) is satisfied by any truth value assignment (by part 7). So ∀x(Rxx⊃Rxx) is true in 𝕄 (by the definition of truth). This argument holds regardless of the exact UD and regardless of the exact extension of R, so ∀x(Rxx⊃Rxx) is true in any model. Therefore, it is a tautology.

Giving arguments about all possible models typically requires clever combination of two strategies:

1. Divide cases between two possible kinds, such that every case must be one kind or the other. In the argument in section 9.7, for example, we distinguished two kinds of models based on whether or not a specific ordered pair was in extension(R). In the argument above, we distinguished cases in which an ordered pair was in extension(R) and cases in which it was not.

2. Consider an arbitrary object as a way of showing something more general. In the argument above, it was crucial that π was just some arbitrary member of the UD. We did not assume anything special about it. As such, whatever we could show to hold of π must hold of every member of the UD --- if we could show it for π, we could show it for anything. In the same way, we did not assume anything special about 𝕄, and so whatever we could show about 𝕄 must hold for all models.

Consider one more example. The argument ∀x(Hx & Jx)∴ ∀xHx is obviously valid. We can only show that the argument is valid by considering what must be true in every model in which the premise is true.

Consider an arbitrary model 𝕄 in which the premise ∀x(Hx & Jx) is true. The conjunction Hx & Jx is satisfied regardless of what is assigned to x, so Hx must be also (by part 3 of the definition of satisfaction). As such, ∀xHx is satisfied by any variable assignment (by part 7 of the definition of satisfaction) and true in 𝕄 (by the definition of truth). Since we did not assume anything about 𝕄 besides ∀x(Hx & Jx) being true, ∀xHx must be true in any model in which ∀x(Hx & Jx) is true. So ∀x(Hx & Jx) ⊨ ∀xHx.

Even for a simple argument like this one, the reasoning is somewhat complicated. For longer arguments, the reasoning can be insufferable. The problem arises because talking about an infinity of models requires reasoning things out in English. What are we to do? The answer won't surprise readers of the first half of the book: we'll make use of some formal proof systems. We have seen two kinds of proof systems for SL: the tree method, and natural deduction proofs. In the coming chapters, we'll extend both kinds of systems to QL as well.

Practice Exercises

Part A Determine whether each sentence is true or false in the model given.

UD: {Corwin, Benedict}
extension(A): {Corwin, Benedict}
extension(B): {Benedict}
extension(N): ∅
referent(c): Corwin

1. Bc

2. Ac ≡ ¬Nc

3. Nc ⊃ (Ac∨Bc)

4. ∀xAx

5. ∀x¬Bx

6. ∃x(Ax&Bx)

7. ∃x(Ax⊃Nx)

8. ∀x(Nx∨¬Nx)

9. ∃xBx ⊃ ∀xAx

Part B Determine whether each sentence is true or false in the model given.

UD: {Waylan, Willy, Johnny}
extension(H): {Waylan, Willy, Johnny}
extension(W): {Waylan, Willy}
extension(R): {⟨Waylan, Willy⟩, ⟨Willy, Johnny⟩, ⟨Johnny, Waylan⟩}
referent(m): Johnny

1. ∃x(Rxm&Rmx)

2. ∀x(Rxm∨Rmx)

3. ∀x(Hx≡Wx)

4. ∀x(Rxm⊃Wx)

5. ∀x((Wx⊃(Hx&Wx)))

6. ∃xRxx

7. ∃x∃yRxy

8. ∀x∀yRxy

9. ∀x∀y(Rxy∨Ryx)

10. ∀x∀y∀z[(Rxy&Ryz) ⊃ Rxz]

Part C Determine whether each sentence is true or false in the model given.

UD: {Lemmy, Courtney, Eddy}
extension(G): {Lemmy, Courtney, Eddy}
extension(H): {ourtney}
extension(M): {Lemmy, Eddy}
referent(c): Courtney
referent(e): Eddy

1. Hc

2. He

3. Mc ∨ Me

4. Gc ∨ ¬Gc

5. Mc ⊃ Gc

6. ∃xHx

7. ∀xHx

8. ∃x¬Mx

9. ∃x(Hx&Gx)

10. ∃x(Mx&Gx)

11. ∀x(Hx∨Mx)

12. ∃xHx&∃xMx

13. ∀x(Hx≡¬Mx)

14. ∃xGx&∃x¬Gx

15. ∀x∃y(Gx&Hy)

Part D Write out the model that corresponds to the interpretation given.

UD: natural numbers from 10 to 13
Ox: x is odd.
Sx: x is less than 7.
Tx: x is a two-digit number.
Ux: x is thought to be unlucky.
Nxy: x is the next number after y.

Part E Show that each of the following is contingent.

1. Da&Db

2. ∃xTxh

3. Pm&¬∀xPx

4. ∀zJz ≡ ∃yJy

5. ∀x(Wxmn∨∃yLxy)

6. ∃x(Gx⊃∀yMy)

Part F Show that the following pairs of sentences are not logically equivalent.

1. Ja, Ka

2. ∃xJx, Jm

3. ∀xRxx, ∃xRxx

4. ∃xPx ⊃ Qc, ∃x(Px⊃Qc)

5. ∀x(Px⊃¬Qx), ∃x(Px&¬Qx)

6. ∃x(Px&Qx), ∃x(Px⊃Qx)

7. ∀x(Px⊃Qx), ∀x(Px&Qx)

8. ∀x∃yRxy, ∃x∀yRxy

9. ∀x∃yRxy, ∀x∃yRyx

Part G Show that the following sets of sentences are consistent.

1. Ma, Na, Pa, Qa

2. {Lee, Lef, ¬Lfe, ¬Lff}

3. {¬(Ma&∃xAx), Ma ∨ Fa, ∀x(Fx⊃Ax)}

4. {Ma ∨ Mb, Ma ⊃ ∀x¬Mx}

5. {∀yGy, ∀x(Gx⊃Hx), ∃y¬Iy}

6. {∃x(Bx∨Ax), ∀x¬Cx, ∀x[(Ax&Bx) ⊃ Cx]}

7. {∃xXx, ∃xYx, ∀x(Xx≡¬Yx)}

8. {∀x(Px∨Qx), ∃x¬(Qx&Px)}

9. {∃z(Nz&Ozz), ∀x∀y(Oxy⊃Oyx)}

10. {¬∃x∀yRxy, ∀x∃yRxy}

Part H Construct models to show that the following arguments are invalid.

1. ∀x(Ax⊃Bx),  ∴ ∃xBx

2. ∀x(Rx⊃Dx), ∀x(Rx⊃Fx),  ∴ ∃x(Dx&Fx)

3. ∃x(Px⊃Qx), ∴ ∃xPx

4. Na&Nb&Nc,  ∴ ∀xNx

5. Rde, ∃xRxd,  ∴ Red

6. ∃x(Ex&Fx), ∃xFx ⊃ ∃xGx,  ∴ ∃x(Ex&Gx)

7. ∀xOxc, ∀xOcx,  ∴ ∀xOxx

8. ∃x(Jx&Kx), ∃x¬Kx, ∃x¬Jx,  ∴ ∃x(¬Jx&¬Kx)

9. Lab ⊃ ∀xLxb, ∃xLxb,  ∴ Lbb

Part I

1. Many logic books define consistency and inconsistency in this way: " A set {Φ₁, Φ₂, Φ₃, ⋯} is inconsistent if and only if {Φ₁, Φ₂, Φ₃, ⋯} ⊨ (Ψ & ¬Ψ) for some sentence . A set is consistent if it is not inconsistent." Does this definition lead to any different sets being consistent than the definition in Chapter 4? Explain your answer.

2. Our definition of truth says that a sentence Φ is true in 𝕄 if and only if some variable assignment satisfies Φ in 𝕄. Would it make any difference if we said instead that Φ is true in 𝕄 if and only if every variable assignment satisfies Φ in 𝕄? Explain your answer.