17 Semantics

Constant Domain Models

We have provided a syntactic characterization of the simplest quantified modal logic, but we should now explain how to interpret the language in order to validate its axioms.

Definition 17.1 (Constant Domain Model) We define a constant domain model to be structure \(M\) of the form \((W, R, D, I)\), where:

  • \(W\) is a non-empty set of worlds.
  • \(R\) is a binary accessibility relation on \(W\)
  • \(D\) is a non-empty set of individuals, and
  • \(I\) is a function from worlds \(w\) into interpretations \(I_w\), which map each \(n\)-place predicate \(P^n\) into an \(n\)-place relation over \(D\).

Definition 17.2 (Variable Assignment for a Model) A variable assignment \(\alpha\) for a model \(M\) is a function from individual variables into members of \(D\).

We now define what is for a formula \(\varphi\) to be true at a world \(w\) in a model \(M\) relative to an assignment \(\alpha\). In what follows, \(\alpha[x/d]\) is an assignment just like \(\alpha\) except perhaps for assigning \(d\) to the variable \(x\).

Definition 17.3 (Truth at a World Relative to an Assignment) We use a recursive definition: \[ \begin{array}{lll} M, w, \alpha \Vdash P^n v_1 \dots v_n & & \text{if, and only if,} & & \langle \alpha(v_1), \dots, \alpha(v_n)\rangle \in I_w (P^n)\\ M, w, \alpha \Vdash v_1 = v_2 & & \text{if, and only if,} & & \alpha(v_1) = \alpha(v_2)\\ M, w, \alpha \Vdash \neg \varphi & & \text{if, and only if,} & & M, w, \alpha \nVdash \varphi \\ M, w, \alpha \Vdash (\varphi \to \psi) & & \text{if, and only if,} & & M, w, \alpha \nVdash \varphi \ \text{or} \ M, w, \alpha \Vdash \psi\\ M, w, \alpha \Vdash \forall x \ \varphi & & \text{if, and only if,} & & M, w, \alpha[x/d] \Vdash \varphi \ \text{for every} \ d\in D\\ M, w, \alpha \Vdash \Box \ \varphi & & \text{if, and only if,} & & M, u, \alpha \Vdash \varphi \ \text{for every} \ u \in W \ \text{such that} \ Rwu\\ \end{array} \]

We now define truth at a world in a model and truth in. a model respectively:

Definition 17.4 (Truth at a World) A formula \(\varphi\) is true at a world \(w\) in a model \(M\), in symbols \(M, w \Vdash \varphi\), if, and only if, for all assignments \(\alpha\) for \(M\), \(M, w, \alpha \Vdash \varphi\)

Definition 17.5 (Truth in a Model) A formula \(\varphi\) is true in a model \(M\), in symbols, \(M \Vdash \varphi\), if, and only. if, for all \(w \in W\), \(M, w \Vdash \varphi\).

Definition 17.6 (Validity in a Class of Models) A formula \(\varphi\) is valid with respect to a class \(\mathcal{C}\). of constant domain models, in symbols \(\models_{\mathcal{C}}\varphi\), if, and only if, for every constant domain model \(M \in \mathcal{C}\), \(M \Vdash \varphi\).

It will be helpful to provide some illustration. We explain first how to justify the fact that a certain formula is not valid with respect to the class of reflexive and euclidean models.

Example 17.1 \(\not \models_{\text{refl and eucl}} \exists x \neg \Box Fx \to \Diamond \forall x \neg Fx\)

Consider a constant domain model \(M\) of the form \(( W, R, D, I)\), where:

  • \(W = \{w_1, w_2\}\)

  • \(R = \{(w_1, w_1), ( w_1, w_2), (w_2, w_1), (w_2, w_2)\}\)

  • \(D = \{a, b\}\)

  • \(I_{w_1}(F) = \{a\}\)

    \(I_{w_2}(F) = \{b\}\)

Here is a diagram for the model:

Now:

  • \(M, w_1 \Vdash \exists x \neg \Box Fx\) because \(M, w_1, \alpha[b/x] \Vdash \neg \Box Fx\)

  • \(M, w_1 \nVdash \Diamond \forall x \neg Fx\) because \(M, w_1 \Vdash \forall x \neg Fx\) and \(Rw_1w_1\).

Example 17.2 \(\not \models_{\text{refl and eucl}} (\Box \exists x Fx \vee \forall x \Diamond Gx)\to \Diamond \exists x (Fx \wedge Gx)\)

Consider a constant domain model \(M\) of the form \(( W, R, D, I)\), where:

  • \(W = \{w_1, w_2\}\)

  • \(R = \{( w_1, w_1), ( w_1, w_2), (w_2, w_1), ( w_2, w_2) \}\)

  • \(D = \{a, b\}\)

  • \(I_{w_1}(F) = \{a\}\), \(I_{w_1}(G) = \{b\}\)

    \(I_{w_2}(F) = \{b\}\), \(I_{w_2}(G) = \{a\}\)

Here is a diagram for the model:

Now:

  • \(M, w_1 \Vdash \Box \exists x Fx\) since \(M, w_1 \Vdash \exists x Fx\) and \(M, w_2 \Vdash \exists x Fx\)

  • \(M, w_1 \nVdash \Diamond \exists x (Fx \wedge Gx)\) since \(M, w_1 \nVdash \exists x (Fx \wedge Gx)\) and \(M, w_2 \nVdash \exists s (Fx \wedge Gx)\)

Example 17.3 \(\not \models_{\text{refl and eucl}} \forall x (\Box Fx \vee \Box \neg Fx) \vee \forall x (\Diamond Fx \wedge \Diamond \neg Fx)\)

Consider a constant domain model \(M\) of the form \(( W, R, D, I)\), where:

  • \(W = \{w_1, w_2\}\)

  • \(R= \{(w_1, w_1), ( w_1, w_2), (w_2, w_1), ( w_2, w_2)\}\)

  • \(D = \{a, b\}\)

  • \(I_{w_1}(F) =\{a\}\)

    \(I_{w_2}(F) = \emptyset\)

Here is a diagram for the model:

Now:

  • \(M, w_1 \nVdash \forall x (\Box Fx \vee \Box \neg Fx)\) because \(M, w_1, \alpha[a/x] \nVdash \Box Fx \vee \Box \neg Fx\). Yet:

  • \(M, w_1 \nVdash \forall x (\Diamond Fx \wedge \Diamond \neg Fx)\) because \(M, w_1, \alpha[b/x]\nVdash \Diamond Fx \wedge \Diamond \neg Fx\).

On the other hand, we may verify that constant domain models validate both the Barcan Formula and the Converse Barcan Formula.

Example 17.4 \(\models \Diamond \ \exists x \ Fx \to \exists x \ \Diamond \ Fx\)

Given a constant domain model \(M\) and a world \(w\in W\) such that \(M, w \Vdash \Diamond \ \exists x \ Fx\), let \(u \in W\) be such that \(Rwu\) and \(M, u \Vdash \exists x \ Fx\). That means that there is a member \(d \in D\) such that for each assignment \(\alpha\), \(M, u, \alpha[d/x] \Vdash Fx\). But then \(M, w, \alpha[d/x]\Vdash \Diamond \ Fx\) and, moreover, \(M, w, \alpha \Vdash \exists x \ \Diamond \ Fx\). Since \(\alpha\) is arbitrary, \(M, w \Vdash \Diamond \ \exists x \ Fx\) as required.

Example 17.5 \(\models \Box \ \forall x \ Fx \to \forall x \ \Box \ Fx\)

Given a constant domain model \(M\) and a world \(w\in W\) such that \(M, w \Vdash \Box \ \forall x \ Fx\), we argue that \(M, w \Vdash \forall x \ \Box \ Fx\). For given an assignment \(\alpha\) and a member \(d \in D\), \(M, w, \alpha[d/x] \Vdash \Box Fx\). This is because given a world \(u\in W\) such that \(Rwu\), we have \(M, u \Vdash \forall x Fx\) and \(M, u, \alpha[d/x]\Vdash Fx\). Since \(u\) and \(d\) Are arbitrary, \(M, w \Vdash \forall x \ \Box \ Fx\) as required.

Variable Domain Models

We have considered different strategies to weaken the simplest quantified modal logic, but we should now explain how to interpret the langauge in order to validate the framework that emerges.

Definition 17.7 (Variable Domain Model) We define a variable domain model to be structure \(M\) of the form \((W, R, D, Q, I)\), where:

  • \(W\) is a non-empty set of worlds.
  • \(R\) is a binary accessibility relation on \(W\)
  • \(D\) is a non-empty set of individuals, which we will call the outer domain of the model
  • \(Q\) is a function from \(W\) into subsets of \(D\), and we will call \(Q(w)\) the inner domain of \(w\) for each \(w \in W\)
  • \(I\) is a function from worlds \(w\) into interpretations \(I_w\), which map each \(n\)-place predicate \(P^n\) into an \(n\)-place relation over \(D\).

Definition 17.8 (Variable Assignment for a Model) A variable assignment \(\alpha\) for a model \(M\) is a function from individual variables into members of \(D\).

The evaluation of an open formula such as \(Fx\) at a world \(w\) in \(W\) relative to an assignment \(\alpha\) raises an important question. What should we make of a case in which \(\alpha(x)\) is not in the inner domain of \(w\). Three broad strategies come to mind:

  1. Avoidance

    Find a way exclude such assignments in principle.

  2. Unsettled Truth Value

    Declare an open formula such as \(Fx\) to be neither true nor false in that circumstance.

  3. Defer to the Interpretation Function

    Defer to the interpretation function \(I\) in order to settle the truth value of open formulas such as \(Fx\).

In what follows, we will momentarily follow the third approach and let the interpretation function settle the truth value of the open formula at a world relative to that assignment. That means that a formula \(Fx\) can in principle be true at a world \(w\) in a model \(M\) relative to an assignment \(\alpha\) on which \(\alpha(x)\) is not even a member of \(Q(w)\).

We now define what is for a formula \(\varphi\) to be true at a world \(w\) in a model \(M\) relative to an assignment \(\alpha\). In what follows, \(\alpha[x/d]\) is an assignment just like \(\alpha\) except perhaps for assigning \(d\) to the variable \(x\).

Definition 17.9 (Truth at a World Relative to an Assignment) We use a recursive definition: \[ \begin{array}{lll} M, w, \alpha \Vdash P^n v_1 \dots v_n & & \text{if, and only if,} & & \langle \alpha(v_1), \dots, \alpha(v_n)\rangle \in I_w (P^n)\\ M, w, \alpha \Vdash v_1 = v_2 & & \text{if, and only if,} & & \alpha(v_1) = \alpha(v_2)\\ M, w, \alpha \Vdash \neg \varphi & & \text{if, and only if,} & & M, w, \alpha \nVdash \varphi \\ M, w, \alpha \Vdash (\varphi \to \psi) & & \text{if, and only if,} & & M, w, \alpha \nVdash \varphi \ \text{or} \ M, w, \alpha \Vdash \psi\\ M, w, \alpha \Vdash \forall x \ \varphi & & \text{if, and only if,} & & M, w, \alpha[x/d] \Vdash \varphi \ \text{for every} \ d\in Q(w)\\ M, w, \alpha \Vdash \Box \ \varphi & & \text{if, and only if,} & & M, u, \alpha \Vdash \varphi \ \text{for every} \ u \in W \ \text{such that} \ Rwu\\ \end{array} \]

We now define truth at a world in a model and truth in. a model respectively:

Definition 17.10 (Truth at a World) A formula \(\varphi\) is true at a world \(w\) in a model \(M\), in symbols \(M, w \Vdash \varphi\), if, and only if, for all assignments \(\alpha\) for \(M\), \(M, w, \alpha \Vdash \varphi\)

Definition 17.11 (Truth in a Model) A formula \(\varphi\) is true in a model \(M\), in symbols, \(M \Vdash \varphi\), if, and only. if, for all \(w \in W\), \(M, w \Vdash \varphi\).

Definition 17.12 (Validity in a Class of Models) A formula \(\varphi\) is valid with respect to a class \(\mathcal{C}\). of constant domain models, in symbols \(\models_{\mathcal{C}}\varphi\), if, and only if, for every constant domain model \(M \in \mathcal{C}\), \(M \Vdash \varphi\).

One important consequence of the choices we made above is that universal instantiation fails in variable domain models. Consider, for example, the evaluation of an instance of universal instantiation at a world \(w\) of a variable domain model: \[ \forall x Fx \to Fy \] relative to an assignment \(\alpha\), which maps \(y\) to an individual that is neither in the inner domain of \(w\) nor in the extension of \(F\) in \(w\). We now set out to look at specific examples of variable domain models that falsify universal instantiation and the Barcan and Converse Barcan Formula.

Example 17.6 \(\not \models \Box \forall x Fx \to \forall x \Box Fx\).

Consider a variable domain model \(M\) of the form \(( W, R, D, Q, I)\), where:

  • \(W = \{w_1, w_2\}\)
  • \(R= \{(w_1, w_1), (w_1, w_2), (w_2, w_1), (w_2, w_2)\}\)
  • \(D = \{a, b\}\)
  • \(Q(w_1) = \{a\}\)
  • \(Q(w_2) = \{b\}\)
  • \(I_{w_1}(F) = \{a\}\)
  • \(I_{w_2}(F) = \{b\}\)

Now:

  • \(M, w_1 \Vdash \Box \forall x Fx\).

    This is because for every assignment \(\alpha\) for \(M\), we have both \(M, w_1, \alpha \Vdash \forall x Fx\) and \(M, w_2, \alpha \Vdash \forall x Fx\).

  • \(M, w_1 \nVdash \forall x \Box Fx\)

    Given an assignment \(\alpha\) for which \(\alpha(x)= a\), \(M, w_1, \alpha \nVdash \Box Fx\), since \(M, w_2, \alpha \nVdash Fx\) and \(Rw_1w_2\).

Example 17.7 \(\not \models \forall x \Box Fx \to \Box \forall x Fx\).

Consider a variable domain model \(M\) of the form \(( W, R, D, Q, I)\), where:

  • \(W = \{w_1, w_2\}\)
  • \(R= \{(w_1, w_1), (w_1, w_2), (w_2, w_1), (w_2, w_2)\}\)
  • \(D = \{a, b\}\)
  • \(Q(w_1) = \{a\}\)
  • \(Q(w_2) = \{a, b\}\)
  • \(I_{w_1}(F) = \{a\}\)
  • \(I_{w_2}(F) = \{a\}\)

Now:

  • \(M, w_1 \Vdash \forall x \Box Fx\).

    This is because for every assignment \(\alpha\) for \(M\), for every \(d \in Q(w_1)\), we have both \(M, w_1, \alpha[d/x] \Vdash Fx\) and \(M, w_2, \alpha[d/x] \Vdash Fx\). In this case, \(a\) is the sole member of the inner domain of \(w_1\).

  • \(M, w_1 \nVdash \Box \forall x Fx\)

    Given an assignment \(\alpha\) , \(M, w_1, \alpha \nVdash \Box \forall Fx\), since \(M, w_2, \alpha \nVdash \forall x Fx\) and \(Rw_1w_2\).

The Inclusion and Converse Inclusion Requirement

Two broad constraints on variable domain models allow us to isolate the class of such models in which the Converse Barcan and the Barcan Formula are valid, respectively.

Definition 17.13 (Inclusion Requirement) A variable domain model \(M\) of the form \(( W, R, D, Q, I)\) satisfies the inclusion requirement if, and only if, for every \(w, u \in W\), if \(Rwu\), then. \(Q(w) \subseteq Q(u)\).

Definition 17.14 (Converse Inclusion Requirement) A variable domain model \(M\) of the form \(( W, R, D, Q, I)\) satisfies the inclusion requirement if, and only if, for every \(w, u \in W\), if \(Rwu\), then. \(Q(u) \subseteq Q(w)\).

That is, a variable domain model satisfies the inclusion requirement if the inner domains never decrease alongside the accessibility relation; and it satisfies the converse inclusion requirement if the inner domains never increase alongside the accessibility relation.

Proposition 17.1 The Converse Barcan Formula is valid in a variable domain models \(M\) if \(M\) satisfies the inclusion requirement.

Proof. Let \(M\) be a variable domain model of the form \(( W, R, D, I)\) satisfying the inclusion requirement. Choose a world \(w \in W\) and an assignment \(\alpha\) for \(M\). We argue that \(M, w, \alpha \Vdash \Box \forall x \varphi(x) \to \forall x \Box \varphi(x)\). Since the formula is a conditional, assume that \(M, w, \alpha \Vdash \Box \forall x \varphi(x)\). That means that \(M, u, \alpha \Vdash \forall x \varphi(x)\) for all \(u\in W\) such that \(Rwu\). We now argue that \(M, w, \alpha \Vdash \forall x \Box \varphi(x)\). That is that for every \(d\in Q(w)\), \(M, w, \alpha[d/x]\Vdash \Box \varphi(x)\). Pick a member \(d\in Q(w)\) and let \(u\in W\) be such that \(Rwu\). Because \(M\) satisfies the inclusion requirement, \(d\in Q(u)\). Since \(M, u, \alpha \Vdash \forall x \varphi(x)\) and \(d\in Q(u)\), \(M, u, \alpha[d/x]\Vdash \varphi(x)\). We conclude that \(M, w, \alpha \Vdash \Box \forall x \varphi(x) \to \forall x \Box \varphi(x)\) And, more generally, \(M, w \Vdash \Box \forall x \varphi(x) \to \forall x \Box \varphi(x)\)

Proposition 17.2 The Barcan Formula is valid in a variable domain models \(M\) if \(M\) satisfies the converse inclusion requirement.

Proof. Let \(M\) be a variable domain model of the form \(( W, R, D, I)\) satisfying the converse inclusion requirement. Choose a world \(w \in W\) and an assignment \(\alpha\) for \(M\). We argue that \(M, w, \alpha \Vdash \forall x \Box \varphi(x) \to \Box \forall x \varphi(x)\). Since the formula is a conditional, assume that \(M, w, \alpha \Vdash \forall x \Box \varphi(x)\). That means that \(M, u, \alpha[d/x] \Vdash \Box \varphi(x)\) for all \(d\in Q(w)\). We now argue that \(M, w, \alpha \Vdash \Box \forall x \varphi(x)\). That is that for every \(u\in W\) such that \(Rwu\), \(M, u, \alpha \Vdash \forall x \varphi(x)\). Pick a word \(u\in W\) such that \(Rwu\) and let \(d \in Q(u)\). Because \(M\) satisfies the converse inclusion requirement, \(d\in Q(w)\). Since \(M, w, \alpha[d/x] \Vdash \Box \varphi(x)\) and \(M, u, \alpha[d/x] \Vdash \varphi(x)\). So, generalizing, \(M, u, \alpha \Vdash \forall x \varphi(x)\) and \(M, w, \alpha \Vdash \Box \forall x \varphi(x)\). We conclude that \(M, w, \alpha \Vdash \forall x \Box \varphi(x) \to \Box \forall x \varphi(x)\) And \(M, w, \alpha \Vdash \forall x \Box \varphi(x) \to \Box \forall x \varphi(x)\).

Here are two more examples of validities in free quantified modal logic.

Example 17.8 \(\models Fx \to Fx\)

This formula is valid in every variable domain model \(M\) of the form \(( W, R, D, Q, I)\) because given a world \(w\in W\) and an assignment \(\alpha\), \(M, w, \alpha \Vdash Fx \to Fx\), regardless of whether \(\alpha(x)\) is in \(Q(w)\) or not.

Example 17.9 \(\models \Box \forall x Fx \to \forall x \Box (\exists y \ x=y \to Fx)\)

Let \(M\) be a variable domain model of the form \(( W, R, D, I)\). Choose a world \(w \in W\) and an assignment \(\alpha\) for \(M\). We argue that \(M, w, \alpha \Vdash \Box \forall x Fx \to \forall x \Box(\exists y \ x=y \to Fx)\). Since the formula is a conditional, assume that \(M, w, \alpha \Vdash \Box \forall x Fx\). That means that \(M, u, \alpha \Vdash \forall x Fx\) for all \(u\in W\) such that \(Rwu\). We now argue that \(M, w, \alpha \Vdash \forall x \Box (\exists y \ x =y \to Fx)\). That is, for every \(d\in Q(w)\), \(M, w, \alpha[d/x]\Vdash \Box (\exists y \ x = y \to Fx)\). Pick a member \(d\in Q(w)\) and let \(u\in W\) be such that \(Rwu\). There are two cases. If \(d\notin Q(u)\), then \(M, u, \alpha[d/x]\nVdash \exists y \ x=y\) and \(M, u, \alpha[d/x]\Vdash \exists y \ x=y \to Fx\). Otherwise, if \(d\in Q(u)\), then since \(M, u, \alpha \Vdash \forall x Fx\) and \(d\in Q(u)\), \(M, u, \alpha[d/x]\Vdash Fx\) and \(M, u, \alpha[d/x]\Vdash \exists y \ x=y \to Fx\). Either way, \(M, u, \alpha[d/x]\Vdash \exists y \ x=y \to Fx\), and \(M, w, \alpha \Vdash \Box (\exists y \ x =y \to Fx)\). We conclude that \(M, w, \alpha \Vdash \Box \forall x Fx \to \forall x \Box (\exists y \ x = y \to Fx)\) And, more generally, \(M, w \Vdash \Box \forall x Fx \to \forall x \Box (\exists y \ x = y \to Fx)\).