Compositionality Solves Carnap’s Problem

Abstract

The standard relation of logical consequence allows for non-standard interpretations of logical constants, as was shown early on by Carnap. But then how can we learn the interpretations of logical constants, if not from the rules which govern their use? Answers in the literature have mostly consisted in devising clever rule formats going beyond the familiar what follows from what. A more conservative answer is possible. We may be able to learn the correct interpretations from the standard rules, because the space of possible interpretations is a priori restricted by universal semantic principles. We show that this is indeed the case. The principles are familiar from modern formal semantics: compositionality, supplemented, for quantifiers, with topic-neutrality.

Appendix

Our first aim in this appendix is to prove (3) and (4) above. Claim (3) states that an interpretation Q for $\forall$ is consistent with $\vDash _L$ iff Q is a principal filter, closed under the interpretation of terms. As announced, we consider a language with predicate variables. Given a set M, we shall say that a set Q of subsets of M is a commutative filter if and only if it is a filter and is such that for all relations R on M,

$$ \{ a \in M | \,R(a) \in Q \} \in Q\,\,{\hbox{iff}}\,\,\{a \in M |\,R^{-1}(a) \in Q \} \in Q $$

where R(a) is $\{ b \in M | \,aRb \}$. We shall prove that the following are equivalent:

• (a) ${\mathcal {M}}, Q$ is consistent with $\vDash _L$,

• (b) Q is a commutative filter on M and, for any term $t(x_1,\ldots ,x_n)$,

  ${\mathcal {M}},Q\,\vDash\,\forall x Px \rightarrow \forall x_1\ldots \forall x_n Pt(x_1,\ldots ,x_n)$

• (c) Q is a principal filter on M which is closed under the interpretation of terms in ${\mathcal {M}}$.

(3) is the equivalence between (a) and (c). In a different context, the proof that commutative filters are principal can be found in Lambalgen (1992), and the connection with the interpretation of the universal quantifier is already made in Westerståhl (1996). We provide here a somewhat shorter proof for that part. It is inspired by the filter model given by Antonelli (2013), Theorem 6.10, to prove that some valid first-order formulas are not valid in some models where the universal quantifier is interpreted by a filter (of course, in those models, the filter is not principal).¹¹ And we provide proofs of the other parts.

Proof

(a) implies (b). The fact that Q is a filter is easily read off from some familiar first-order validities. Closure under finite intersection follows from the fact that $(\forall x \varphi \wedge \forall x \psi ) \rightarrow \forall x (\varphi \wedge \psi )$ is valid. The validity of $\forall x(\varphi \wedge \psi ) \rightarrow \forall x\varphi$ ensures closure under supersets. The empty set does not belong to Q because of $\forall x\varphi \rightarrow \lnot \forall x \lnot \varphi$. Moreover, Q is commutative because $\forall x \forall y \varphi \rightarrow \forall y \forall x \varphi$ is valid. Finally, ${\mathcal {M}}, Q\,\vDash\,\forall x Px \rightarrow \forall x_1\ldots \forall x_n Pt(x_1,\ldots ,x_n)$ simply because the formula is valid in first-order logic.

(b) implies (c). First, let Q be a non-principal filter; we show that Q is not commutative. Take any X in Q and consider (using Zorn’s Lemma) a maximal set $Q^{\prime }$ of subsets of X belonging to Q and totally ordered by inclusion. We define a parallel indexed family $\{ \Delta _Y \}_{Y \in Q^{\prime }}$ by setting $\Delta _Y = X - Y$ for $Y \in Q^{\prime }$. We shall furthermore consider the sets $Z = \bigcup _{Y \in Q^{\prime }} \Delta _Y$ and $Z^{\prime } = X - Z$. The intuition is the following. $Q^{\prime }$ can be thought of as dropping more and more elements out of X. The indexed family $\{ \Delta _Y \}_{Y \in Q^{\prime }}$ collects the elements which have been dropped at each stage. Z is then the set of elements which have been dropped at some stage and $Z^{\prime }$ is the set of those that are never dropped. We now define a relation $R \subseteq M \times M$ for which commutativity will fail, by

$$ R = \left(\bigcup_{Y \in Q^{\prime }} (\Delta _Y \times Y)\right) \cup (Z^{\prime } \times X) $$

First, note that $\{ a \in M |\, R(a) \in Q \} = Z \cup Z ^{\prime } =X$. It is then sufficient to show that $\{ a \in M | \,R^{-1} (a) \in Q \} =Z^{\prime }$, because $Z^{\prime }$ does not belong to Q. If it did, $Z^{\prime }$ would be by construction the smallest element of $Q^{\prime }$. Since Q is not principal, $Q^{\prime }$ cannot have a smallest element. To see this, let C be such a smallest element. Since Q is not principal, there is D in Q such that $C \cap D$ is a proper subset of C, but then, since $Q^{\prime }$ is assumed to be maximal, $C \cap D$, which belongs to Q, also belongs to $Q^{\prime }$, contradicting the fact that C is the smallest element of $Q^{\prime }$. Thus, it remains only to be shown that $\{a \in M | \,R^{-1} (a)\in Q\}=Z^{\prime }$. We reason by cases:

• If a is not in X, $R^{-1} (a)= \emptyset$, which is not in Q.

• If a is in Z, $R^{-1} (a)= (\bigcup _{a \in Y} \Delta _Y )\cup Z^{\prime }$. Since a is in Z, there is a B in $Q^{\prime }$ such that a is not in B. Moreover, $(\bigcup _{a \in Y} \Delta _Y) \cap B = \emptyset$, since $a \in Y$ implies that B is strictly included in Y, $Q^{\prime }$ being totally ordered by inclusion. As a consequence, $R^{-1} (a) \cap B=Z^{\prime }$. Since B is in Q and $Z^{\prime }$ is not, closure under intersection of Q implies that $R^{-1} (a)$ is itself not in Q.

• If a is in $Z^{\prime }$, $R^{-1} (a)=Z \cup Z^{\prime }=X$, which is in Q.

This proves that Q is not commutative. Hence, by contraposition, if Q is commutative, Q is principal. It remains to be shown that Q is closed under the interpretation of terms in ${\mathcal {M}}$. Let Q be generated by A, let $t(x_1,\ldots ,x_n)$ be a term, and let $a_1,\ldots ,a_n \in A$. We need to show that $||t(x_1,\ldots ,x_n)||^{\mathcal {M}}(a_1,\ldots ,a_n) \in A$. First, interpret P by A. Then ${\mathcal {M}}, Q\,\vDash\,\forall x Px$, and therefore ${\mathcal {M}},Q\,\vDash\,\forall x_1\ldots \forall x_n Pt(x_1,\ldots ,x_n)$ by hypothesis. By the satisfaction clause for $\forall$, it follows that

$$ \{\langle a_1,\ldots ,a_n \rangle \,| \,||t||^{\mathcal {M}}(a_1,\ldots ,a_n) \in A\} \supseteq A^n $$

as desired.

(c) implies (a). Let Q be a principal filter generated by a subset A of M. Let H be a Hilbert proof system for $\vDash _L$ as for example the one given by Cori and Lascar (2000), p. 194; predicate symbols and predicate variables being treated on a par. It suffices to establish that if $\varphi$ is deducible from a set $\Gamma$ of formulas without free individual variables in H, then ${\mathcal {M}}, Q\,\vDash\,\Gamma$ implies ${\mathcal {M}}, Q\,\vDash\,\varphi \,\sigma$ for any assignment $\sigma$ whose individual variables have values in A. This is shown by induction on the length of proofs in H. The two key steps are the soundness of universal instantiation, which, in H, is the axiom $\forall x\varphi \rightarrow \varphi [t/x]$ with t free for x in $\varphi$, and the soundness of universal generalization, which, in H, is inferring $\forall x \varphi$ from $\varphi$ (no restriction on x is needed since we consider only derivability from a set of sentences without free individual variables).

For universal instantiation, we need to show that ${\mathcal {M}}, Q\,\vDash\,\varphi [t/x]$ for any assignment $\sigma$ with values in A, for any term t free for x in $\varphi$. Assume ${\mathcal {M}},Q\,\vDash\,\forall x\varphi \,\sigma$. By the satisfaction clause for $\forall$ and the fact that Q is a filter generated by A, the set of objects $a \in M$ such that ${\mathcal {M}}, Q\,\vDash\,\varphi \,\sigma [x:=a]$ is a superset of A. Hence, for our term t with free variables $x_1,\ldots ,x_n$, ${\mathcal {M}},Q\,\vDash\,\varphi [t/x]\,\sigma$, because $\sigma (x_1),\ldots ,\sigma (x_n)$ are in A and A is closed under the interpretation of t.

For universal generalization, we assume that we have a proof of a formula $\forall x \varphi$ from a set of sentences $\Gamma$ in H ending with an application of universal generalization. By induction hypothesis, ${\mathcal {M}}, Q\,\vDash\,\Gamma$ implies ${\mathcal {M}}, Q\,\vDash\,\varphi \,\sigma$ for any assignment $\sigma$ with values in A. Assume ${\mathcal {M}},Q\,\vDash\,\Gamma$. Let $\sigma$ be an arbitrary assignment with values in A. By induction hypothesis, the set of objects $a \in M$ such that ${\mathcal {M}},Q\,\vDash\,\varphi \,\sigma [x:=a]$ is a superset of A. Therefore, since Q is interpreted by a filter generated from A, we have ${\mathcal {M}}, Q\,\vDash\,\forall x\varphi \,\sigma$, as required. $\square$

Next, we show

• (4) A principal filter Q on M is invariant under permutation if and only if $Q= \{ M \}$.

Proof

The direction from right to left is immediate. We prove the direction from left to right by contraposition. Assume that Q is a principal filter generated by a set A different from M. There are $a,b \in M$ such that $a \in A$ but $b \not \in A$. Consider the permutation $\pi$ which swaps a and b and is the identity everywhere else. a is not in $\pi (A)$, so A is not included in $\pi (A)$, so $\pi (A)\not \in Q$, contradicting the invariance of Q. $\square$

Finally, we give a proof of

• (5) If I is an interpretation consistent with an intensional logic, then I is normal on the connectives $\lnot ,\wedge ,\vee ,\rightarrow$.

Let W be a set of worlds, and I an interpretation (over W) consistent with an intensional logic $\vdash$. We must show that $I(\#)$ is normal for $\# \in \{\lnot ,\wedge ,\vee ,\rightarrow \}$. Recall that for all formulas $\varphi ,\psi ,\theta$,

• (6) $\varphi ,\psi \vdash \theta \,$ implies that for each assignment f, $\llbracket \varphi \rrbracket ^{I}_f \cap \llbracket \psi \rrbracket ^{I}_f \subseteq \llbracket \theta \rrbracket ^{I}_f$.

To begin, it is clear that $\wedge$ is normal:

• (7) For $X,Y \subseteq W$, we have $I(\wedge )(X,Y) = X\cap Y$.

This follows from the introduction and elimination rules for $\wedge$, in the form

• $p\wedge q\,\vDash _{PL}\, p$,   $\;p\wedge q\,\vDash _{PL}\,q$,   $p, q\,\vDash _{PL}\,p\wedge q$

Since $\vdash$ is an intensional logic, these rules hold for $\vdash$ too. Let f be such that $f(p)=X$ and $f(q)=Y$. Using (6), (7) follows.

Next, we observe that it suffices to show that negation must be interpreted normally by I.

• (8) If $I(\lnot )(X) = W-X$ for all $X\subseteq W$, then also $\vee$ and $\rightarrow$ are interpreted normally by I.

Consider $\vee$. From the fact that $p \vdash p\vee q$ and $q \vdash p\vee q$ we obtain from (6) (with a suitable f) that $X \cup Y \subseteq I(\vee )(X,Y)$. Also, since $p \vee q,\lnot p \vdash q$ we get, using our assumption,

$$ I(\vee )(X,Y) - X \,\subseteq \, Y $$

In other words, $I(\vee )(X,Y) \subseteq X \cup Y$, so $I(\vee )(X,Y) = X\cup Y$, as was to be proved. In a similar way, one shows that $I(\rightarrow )(X,Y) = (W-X)\cup Y$. (The assumption about negation is used to show $W-X \subseteq I(\rightarrow )(X,Y)$, which one gets from $\,\lnot p \vdash p\rightarrow q$.) This proves (8).

Concerning negation, it is easy to see that the following holds:

• (9) For all $X\subseteq W$, $\,X \cap I(\lnot )(X) = \emptyset$.

This follows from the fact that $p,\lnot p \vdash q$, letting $f(p) = X$ and $f(q)=\emptyset$. Thus, all that remains to prove is:

• (10) For all $X\subseteq W$, $\,X \cup I(\lnot )(X) = W$.

First, it follows from (9) that

• (11) $I(\lnot )(W) = \emptyset$

Also,

• (12) $I(\lnot )(\emptyset ) = W$

This is because $\vdash \lnot (p\wedge \lnot p)$ (so for all f, $\llbracket \lnot (p\wedge \lnot p) \rrbracket ^{I}_f = W$), with $f(p)=\emptyset$; recall that conjunction is interpreted as intersection.

Now suppose $\emptyset \subsetneq X \subsetneq W$ and, for contradiction, that $X \cup I(\lnot )(X) \ne W$. Take $b \in W - (X \cup I(\lnot )(X))$, and let $f(p)=X$ and $f(q)=\{b\}$.¹² Then we have

• (13) $\llbracket \lnot (p\wedge q) \rrbracket ^{I}_f = W$

[by (12), since $X \cap \{b\} = \emptyset$], and

• (14) $\llbracket \lnot p\wedge q \rrbracket ^{I}_f = \emptyset$

(since $I(\lnot )(X) \cap \{b\} = \emptyset$). Since $\,\lnot (p\wedge q) \vdash \lnot p\vee \lnot q$, it follows from (13) that

• (15) $\llbracket \lnot p\vee \lnot q \rrbracket ^{I}_f = W$

And since $\,\lnot (p\vee \lnot q) \vdash \lnot p\wedge q$, it follows from (14) that $\llbracket \lnot (p\vee \lnot q) \rrbracket ^{I}_f = \emptyset$, and hence by (12) that $\llbracket \lnot \lnot (p\vee \lnot q) \rrbracket ^{I}_f = W$. Thus, since $\,\lnot \lnot (p\vee \lnot q) \vdash p\vee \lnot q$, we have

• (16) $\llbracket p\vee \lnot q \rrbracket ^{I}_f = W$

But we also have

$$ p\vee \lnot q, \lnot p\vee \lnot q \vdash \lnot q $$

By (15) and (16), this entails that $\llbracket \lnot q \rrbracket ^{I}_f = I(\lnot )(\{b\}) = W$, contradicting the fact [from (9)] that $\{b\}\cap I(\lnot )(\{b\}) = \emptyset$. This proves (10), and thereby (5), as desired.$\square$