8 Semantics

We now explain how to interpret the language of quantificational logic. We will not use assignments of truth values to interpret the language but rather models, which will assign a semantic value to the simplest constituents of a formula. A model for quantificational logic must specify:

The domain of discourse determines the truth conditions of quantified formulas in much the way in which the truth value of a natural language sentence such as ‘I packed everything into my suitcase’ depends on what is the domain of objects over which we take the quantifier ‘everything’ to range. In what follows, we will use a non-empty set of objects as the domain of a model. There are no restrictions on the domain of discourse other than it must contain at least one object.

We will let a model specify denotations for the constants of the language. Constants are formal counterparts of names in natural language, which are generally taken to denote an object in the domain of discourse, e.g., ‘Los Angeles’ denotes a city in Southern California, and ‘Silver Lake’ denotes an area of Los Angeles. A model will assign a member of the domain to each constant of the language as a denotation.

The case of predicates is more subtle. Predicates are formal counterparts of predicate expressions in natural language, which are true of some objects and not of others. Let us begin with one-place predicates such as ‘is red’, which applies to red objects and does not apply to non-red objects. One suggestion at this point is to identify the interpretation of ‘red’ with the set of objects to which the predicate applies. The set of objects to which a given predicate applies is known as the extension of the predicate. Thus the extension of the predicate ‘red’ is the set of red objects and the extension of the predicate ‘human being’ is the set of human beings.

The case of two-place predicates is more complicated. The predicate ‘is south of’ applies to Los Angeles and San Francisco in that order but it fails to apply to San Francisco and Los Angeles in that order. This raises the question of how to specify the extension of the predicate. The answer is to use sets of ordered pairs of objects in the domain, e.g., \(\langle LA, SF \rangle\) is the ordered pair of Los Angeles and San Francisco in that order whereas \(\langle SF, LA \rangle\) is the ordered pair of San Francisco and Los Angeles in that order. The extension of the two-place predicate ‘is south of’ will be a set of ordered pairs, which contains \(\langle LA, SF \rangle\) but not \(\langle SF, LA \rangle\). The solution generalizes to predicates with even more argument places. The interpretation of a three-place predicate is a set of ordered triples, and more generally, the interpretation of an \(n\)-place predicate is a set of ordered \(n\)-tuples.

Models

Given an argument in the language of quantificational logic, we will often consider the question of whether there is an interpretation of the language on which the premises are true and the conclusion false. That amounts to the question whether there is a model for quantificational logic, which verifies the premises but not the conclusion of the argument.

⊕Model

Model: A model \(M\) for quantificational logic is an ordered pair \(\langle D, I\rangle\), where:

\(D\) is a non-empty set of objects, and
\(I\) interprets constants and predicates in accordance to the requirements:
- If \(a\) is a constant, \(I(a)\) is a member of \(D\).
- If \(P\) is a one-place predicate, \(I(P)\) is a set of members of \(P\).
- If \(R\) is an \(n\)-place predicate, \(I(R)\) is a set of \(n\)-tuples of members of \(D\).

Example 8.1 Consider the argument given below.

\((Pa \wedge Qb) \to Rab\)
\(\neg Rba\)
\(\exists x (Px \wedge Rxa)\)

We may evaluate the premises and conclusion of the argument in a model \(M\) given by \(\langle D, I\rangle\), where:

\(D = \{1, 2\}\)
\(I(a) = 1\)
\(I(b) = 2\)
\(I(P) = \{1, 2\}\)
\(I(Q) = \{2\}\)
\(I(R) = \{\langle 1, 2\rangle\}\)

We will eventually explain that the model verifies the premises but not the conclusion of the argument.

One heuristic you may find helpful for the specification of a model is to use a diagrams as partial representation of the model. The diagram should come accompanied with a key designed to help us specify the interpretation of the relevant constants and predicates.

⊕
\(P : \text{enclosed by a circle}\)
\(Q : \text{enclosed by a dark grey figure}\)
\(R : \text{points to}\)
\(a : p_1\)
\(b : p_2\)

Example 8.2 The diagram included in the margin encodes the partial specification of a model \(\langle D, I\rangle\), where:

\(D = \{p_1, p_2\}\)
\(I(a) = p_1\)
\(I(b) = p_2\)
\(I(P) = \text{enclosed by a circle}\)
\(I(Q) = \text{enclosed by a dark grey figure}\)
\(I(R) = \text{points to}\)

Notice that the diagram comes with a key designed to explain how to interpret each predicate and constant in the diagram.

This heuristic comes with severe limitations, since some models, e.g., models with an infinite domain, are much too complex to be represented by means of a finite diagram. The method will, however, suffice for some purposes; it will enable us to establish the invalidity of a broad family of arguments in quantificational logic.

Truth Relative to a Variable Assignment

The definition of a model makes sure that models provide a semantic value for constants and predicates, but they remain silent when it comes to variables. If constants are the formal counterparts of names in natural language, variables resemble pronouns like ‘he’ or ‘she’, which do not appear to receive a denotation when used in a sentence like ‘If a person likes opera, then she likes classical music.’ For this reason, models do not assign a denotation to variables.

Instead, variables will be treated as temporary labels for members of the domain. That will allow us to evaluate an open formula \(Px \wedge Rxy\) relative to an assignment of values to the variables that occur in it. More generally, given a model \(M\), we now explain what is an assignment of members of \(M\) to the variables of the language.

Variable Assignment: A variable assignment \(\alpha\) over a model \(M\) is a map from the range of variables to a members of the domain \(D\).

Example 8.3 Each of the maps depicted below are variable assignments over a model \(M\) with domain \(\{p_1, p_2\}\): \[ \begin{array}{cccccccccc} x & y & z & x_1 & y_1 & z_1 & x_2 & y_2 & z_2 & \dots \\ \hline p_1 & p_2 & p_1 & p_2 & p_1 & p_2 & p_1 & p_1 & p_2 & \dots \\ \end{array} \]

\[ \begin{array}{cccccccccc} x & y & z & x_1 & y_1 & z_1 & x_2 & y_2 & z_2 & \dots \\ \hline p_2 & p_1 & p_2 & p_1 & p_2 & p_1 & p_2 & p_1 & p_2 & \dots \\ \end{array} \] \[ \begin{array}{cccccccccc} x & y & z & x_1 & y_1 & z_1 & x_2 & y_2 & z_2 & \dots \\ \hline p_1 & p_2 & p_2 & p_2 & p_2 & p_1 & p_2 & p_1 & p_2 & \dots \\ \end{array} \]

Once variable assignments are in place, we are in a position to assign a semantic value to a variable \(x\) in a model \(M\) relative to an assignment \(\alpha\), which is just \(\alpha(x)\).

For technical reasons, we want to assign semantic values to open formulas in a model relative to a variable assignment over the model. The definition of truth in a model relative to a variable assignment will be inductive: we will define the truth conditions of complex formulas in terms of the truth conditions of simpler ones in much the way with did with the definition of truth under an assignment of truth values to propositional variables in the case of propositional logic. We will begin with an account of the truth conditions of atomic formulas, and we will explain how to assign truth values to more complex sentences in a model relative to an assignment.

Denotation: If \(\tau\) is either a constant \(c\) or a variable \(x\), the denotation of \(\tau\) in a model \(M\) under assignment \(\alpha\) is \(I(c)\) if \(\tau\) is a constant \(c\) and \(\alpha(x)\) if \(\tau\) is a variable \(x\).
Atomic Formulas: \(P\tau\) is true in \(M\) under \(\alpha\) if the denotation of \(\tau\) in \(M\) under \(\alpha\) is in the extension of \(P\), e.g., \(Px\) is true in \(M\) under \(\alpha\) if \(\alpha(x) \in I(P)\) and \(Pc\) is true in \(M\) under \(\alpha\) if \(I(c) \in I(P)\). More generally, \(R\tau_1 \cdots \tau_n\) is true in \(M\) under \(\alpha\) if the denotations of \(\tau_1 \cdots \tau_n\) are in that order in the extension of \(R\), e.g., \(Rax\) is true in \(M\) under \(\alpha\) if \(\langle I(a), \alpha(x)\rangle \in I(R)\) .

Example 8.4 ⊕\(D = \{1, 2\}\)
\(I(P) = \{1, 2\}\)
\(I(Q) = \{2\}\)
\(I(R) = \{\langle 1, 2\rangle\}\)
\(I(a) = 1\)
\(I(b) = 2\)

Let \(\alpha\) be an assignment for the model \(M\): \[ \begin{array}{cccccccccc} x & y & z & x_1 & y_1 & z_1 & \dots \\ \hline 1 & 2 & 2 & 2 & 2 & 1 & \dots \\ \end{array} \] Then:

The formula \(Rxy\) is true in \(M\) relative to \(\alpha\) because \(\langle \alpha(x), \alpha(y)\rangle = \langle 1, 2\rangle\), which is in \(I(R)\).

The formula \(Ray\) is true in \(M\) relative to \(\alpha\) because \(\langle I(a), \alpha(y)\rangle = \langle 1, 2\rangle\), which is in \(I(R)\).

The formula \(Px_1\) is true in \(M\) relative to \(\alpha\) because \(\alpha(x_1) \in I(P)\), that is, \(2 \in I(P)\).

The evaluation of atomic formulas is similar when we use a diagram to specify a model.

⊕
\(P : \text{enclosed by a circle}\)
\(Q : \text{enclosed by a dark grey figure}\)
\(R : \text{points to}\)
\(a : p_1\)
\(b : p_2\)

Example 8.5 Consider a model \(M\) depicted by the diagram, and let \(\alpha\) be an assignment of the form: \[ \begin{array}{ccccccc} x & y & z & x_1 & y_1 & z_1 & \dots \\ \hline p_1 & p_2 & p_2 & p_2 & p_2 & p_1 & \dots \\ \end{array} \] Then:

The formula \(Rxy\) is true in \(M\) relative to \(\alpha\) because \(\alpha(x)\) points to \(\alpha(y)\). That is, \(p_1\) points to \(p_2\).

The formula \(Ray\) is true in \(M\) relative to \(\alpha\) because \(p_1\) points to \(\alpha(y)\). That is, \(p_1\) points to \(p_2\).

The formula \(Px_1\) is true in \(M\) relative to \(\alpha\) because \(\alpha(x_1)\), that is, \(p_2\), is enclosed by a circle.

If a complex formula is constructed from simpler formulas by an application of a connective such as \(\neg\), \(\wedge\). \(\vee\), \(\to\), and \(\leftrightarrow\), then its truth conditions in a model \(M\) relative to an assignment \(\alpha\) are given inductively in the style of the definition of truth for propositional logic. That is,

Negation: \(\neg \varphi\) is true in \(M\) relative to a variable asignment \(\alpha\) if, and only if, \(\varphi\) is not true in \(M\) relative to \(\alpha\).
Conjunction: \(\varphi \wedge \psi\) is true in \(M\) relative to a variable asignment \(\alpha\) if, and only if, \(\varphi\) is true in \(M\) relative to \(\alpha\) and \(\psi\) is true in \(M\) relative to \(\alpha\).
Disjunction: \(\varphi \vee \psi\) is true in \(M\) relative to a variable asignment \(\alpha\) if, and only if, \(\varphi\) is true in \(M\) relative to \(\alpha\) or \(\psi\) is true in \(M\) relative to \(\alpha\).
Conditional: \(\varphi \to \psi\) is true in \(M\) relative to a variable asignment \(\alpha\) if, and only if, \(\varphi\) is not true in \(M\) relative to \(\alpha\) or \(\psi\) is true in \(M\) relative to \(\alpha\).

Example 8.6 ⊕\(D = \{1, 2\}\)
\(I(P) = \{1, 2\}\)
\(I(Q) = \{2\}\)
\(I(R) = \{\langle 1, 2\rangle\}\)
\(I(a) = 1\)
\(I(b) = 2\)

Let \(\alpha\) be an assignment for the model \(M\): \[ \begin{array}{cccccccccc} x & y & z & x_1 & y_1 & z_1 & \dots \\ \hline 1 & 2 & 2 & 2 & 2 & 1 & \dots \\ \end{array} \] Then:

\(Pa \wedge Qb\) is true in \(M\) relative to \(\alpha\) because \(Pa\) is true in \(M\) relative to \(\alpha\) and \(Qb\) is true in \(M\) relative to \(\alpha\). The former is true because \(p_1 \in I(P)\) and the latter is true because \(p_2 \in I(Q)\).

\((Pa \wedge Qb) \to Rab\) is true in \(M\) relative to \(\alpha\) because \(Rab\) is true in \(M\) relative to \(\alpha\). This is because \(\langle I(a), I(b)\rangle = \langle p_1, p_2 \rangle \in I(R)\).

\(\neg Rba\) is in \(M\) relative to \(\alpha\) because \(Rba\) is not true in \(M\) relative to \(\alpha\). This is because \(\langle I(b), I(a)\rangle = \langle p_2, p_1 \rangle \notin I(R)\).

The situation is similar for diagramatic representations of a model:

⊕
\(P : \text{enclosed by a circle}\)
\(Q : \text{enclosed by a dark grey figure}\)
\(R : \text{points to}\)
\(a : p_1\)
\(b : p_2\)

Example 8.7 Consider a model \(M\) depicted by the diagram, and let \(\alpha\) be an assignment of the form: \[ \begin{array}{ccccccc} x & y & z & x_1 & y_1 & z_1 & \dots \\ \hline p_1 & p_2 & p_2 & p_2 & p_2 & p_1 & \dots \\ \end{array} \] Then:

\(Pa \wedge Qb\) is true in \(M\) relative to \(\alpha\) because \(Pa\) is true in \(M\) relative to \(\alpha\) and \(Qb\) is true in \(M\) relative to \(\alpha\). The former is true because \(p_1\) is enclosed by a circle and the latter is true because \(p_2\) is enclosed by a grey figure.

\((Pa \wedge Qb) \to Rab\) is true in \(M\) relative to \(\alpha\) because \(Rab\) is true in \(M\) relative to \(\alpha\). This is because \(I(a)\) points to \(I(b)\). That is, \(p_1\) points to \(p2\).

\(\neg Rba\) is in \(M\) relative to \(\alpha\) because \(Rba\) is not true in \(M\) relative to \(\alpha\). This is because \(I(b)\) does not point to \(I(b)\). That is, \(p_2\) does not point to \(p1\).

We now explain how to evaluate quantified formulas of the form \(\forall v \varphi\) and \(\exists v \varphi\) in a model \(M\) relative to a variable assignment over \(M\). We want a formula of the form \(\exists x P(x)\) to be true in \(M\) relative to \(\alpha\) if some member of the domain of \(M\) lies in the extension of \(P\). One way to achieve this is to declare the formula true in \(M\) relative to \(\alpha\) if there is an object in the domain of \(M\) that we can assign to \(x\) in order to verify \(P(x)\), which means that there is an assignment \(\beta\) which is just like \(\alpha\) except perhaps for the fact that it assigns a different object to \(x\) such that \(P(x)\) is true in \(M\) relative to \(\beta\). Similarly, we want a formula \(\forall x P(x)\) to be true in \(M\) relative to \(\alpha\) if every member of the domain of \(M\) lies in the extension of \(P\). In other words, \(P(x)\) is true in \(M\) no matter what we assign to \(x\) provided the new variable assignment remains just like \(\alpha\) in all other respects.

Existential Quantification: \(\exists v \varphi\) is true in \(M\) relative to a variable asignment \(\alpha\) if, and only if, there is an object \(p\) in the domain of \(M\) such that \(\varphi\) is true in \(M\) relative to \(\alpha[x/p]\), which is an assignment just like \(\alpha\) except perhaps for the fact that it assigns \(p\) to the variable \(x\).
Universal Quantification: \(\forall v \varphi\) is true in \(M\) relative to a variable asignment \(\alpha\) if, and only if, for every object \(p\) in the domain of \(M\), \(\varphi\) is true in \(M\) relative to \(\alpha[x/p]\), which is an assignment just like \(\alpha\) except perhaps for the fact that it assigns \(p\) to the variable \(x\).

Example 8.8 ⊕\(D = \{1, 2\}\)
\(I(P) = \{1, 2\}\)
\(I(Q) = \{2\}\)
\(I(R) = \{\langle 1, 2\rangle\}\)
\(I(a) = 1\)
\(I(b) = 2\)

Let \(\alpha\) be an assignment for the model \(M\): \[ \begin{array}{cccccccccc} x & y & z & x_1 & y_1 & z_1 & \dots \\ \hline 1 & 2 & 2 & 2 & 2 & 1 & \dots \\ \end{array} \] Then:

\(\exists x (Px \wedge \neg Rxa)\) is not true in \(M\) relative to \(\alpha\) because there is no member of \(D\) we can assign to the variable \(x\), where the new variable assignment remains just like \(\alpha\) in all other respects, in order to make \(Px \wedge \neg Rxa\) true:

\(\alpha[x/1]\): \(Px \wedge \neg Rxa\) is not true relative to that assignment because \(\langle 1, I(a)\rangle \notin I(R)\).
\(\alpha[x/2]\): \(Px \wedge \neg Rxa\) is not true relative to that assignment because \(\langle 2, I(a)\rangle \notin I(R)\).

\(\forall x Px\) is true in \(M\) relative to \(\alpha\) because no matter what member of \(D\) assign to the variable \(x\), where the new variable assignment remains just like \(\alpha\) in all other respects, we find that \(Px\) is true in \(M\) relative to the new assignment:

\(\alpha[x/1]\): \(Px\) is true relative to that assignment because \(1 \in I(P)\).
\(\alpha[x/2]\): \(Px\) is true relative to that assignment because \(2 \in I(P)\).

The situation is similar for diagramatic representations of a model \(M\) relative to \(\alpha\) because there is no member of \(D\) we can assign to the variable \(x\) making sure the new variable assignment remains just like \(\alpha\) in all other respects in order to make:

⊕
\(P : \text{enclosed by a circle}\)
\(Q : \text{enclosed by a dark grey figure}\)
\(R : \text{points to}\)
\(a : p_1\)
\(b : p_2\)

Example 8.9 Consider a model \(M\) depicted by the diagram, and let \(\alpha\) be an assignment of the form: \[ \begin{array}{ccccccc} x & y & z & x_1 & y_1 & z_1 & \dots \\ \hline p_1 & p_2 & p_2 & p_2 & p_2 & p_1 & \dots \\ \end{array} \] Then:

\(\exists x (Px \wedge \neg Rxa)\) is not true in \(M\) relative to \(\alpha\) because there is no member of \(D\) we can assign to the variable \(x\) making sure the new variable assignment remains just like \(\alpha\) in all other respects in order to make: \(Px \wedge \neg Rxa\):

\(\alpha[x/p_1]\): \(Px \wedge \neg Rxa\) is not true relative to that assignment because \(p_1\) does not point to \(p_1\).
\(\alpha[x/p_2]\): \(Px \wedge \neg Rxa\) is not true relative to that assignment because \(p_2\) does not point to \(p_1\).

\(\alpha[x/p_1]\): \(Px\) is true relative to that assignment because \(p_1\) is enclosed by a circle.
\(\alpha[x/p_2]\): \(Px\) is true relative to that assignment because \(p_2\) is enclosed by a circle.

Truth in a Model

Once we define what is for a formula \(\varphi\) to be true in a model \(M\) relative to an assignment \(\alpha\), we are in a position to define what is for a formula \(\varphi\) to be true in a model \(M\).

Truth in a Model: A formula \(\varphi\) is true in a model \(M\) if, and only if, \(\varphi\) is true in \(M\) relative to all variable assignments over \(M\).

Models

Truth Relative to a Variable Assignment

Truth in a Model

Logical Truths

Equivalence and Consistency

Validity

Exercises