## Ivano Ciardelli, Jeroen Groenendijk, and Floris Roelofsen

Print publication date: 2018

Print ISBN-13: 9780198814788

Published to Oxford Scholarship Online: December 2018

DOI: 10.1093/oso/9780198814788.001.0001

Show Summary Details
Page of

PRINTED FROM OXFORD SCHOLARSHIP ONLINE (oxford.universitypressscholarship.com). (c) Copyright Oxford University Press, 2021. All Rights Reserved. An individual user may print out a PDF of a single chapter of a monograph in OSO for personal use. date: 21 June 2021

# Basic operations on propositions

Chapter:
(p.43) 3 Basic operations on propositions
Source:
Inquisitive Semantics
Publisher:
Oxford University Press
DOI:10.1093/oso/9780198814788.003.0003

# Abstract and Keywords

Chapter 3 considers what the basic operations are that can be performed on propositions in inquisitive semantics. In the classical setting, where propositions are simple sets of worlds, one can form the intersection or the union of two propositions, or the complement of a single proposition. These operations play a central role in logic and in semantic analyses of natural languages: conjunction and disjunction are standardly taken to express intersection and union, respectively, while negation is standardly taken to express complementation. It is shown that these operations have natural counterparts in the inquisitive setting, even though propositions are no longer simple sets of worlds.

Now that we have introduced a new notion of propositions, it is natural to consider what the basic operations are that could be performed on such propositions. In the classical setting, where propositions are simple sets of worlds, we can form the intersection or the union of two propositions, or the complement of a single proposition. These operations play a central role in logic and in semantic analyses of natural languages: conjunction and disjunction are standardly taken to express intersection and union, respectively, while negation is standardly taken to express complementation. Do these operations have natural counterparts in the inquisitive setting, where propositions are no longer simple sets of worlds?

We will address this question in Section 3.1, adopting an algebraic perspective. We will find that the basic algebraic operations on classical propositions can indeed be applied to inquisitive propositions as well. This result facilitates a very natural way of dealing with connectives and quantifiers. In particular, in Chapter 4 it will allow us to define an inquisitive semantics for the language of first-order logic which is, from an algebraic perspective, the exact counterpart of classical first-order logic in the inquisitive setting. In Chapter 5 we will suggest that the algebraic operations are also crucial for the semantic analysis of connectives in natural languages. In particular, they will yield a uniform account of conjunction, disjunction, and conditionalization of statements and questions, as illustrated by examples (1)–(3) below, repeated from Section 1.1.3.

(1)

(2)

(p.44)

(3)

Returning now to the roadmap for the present chapter, after having discussed the basic algebraic operations on inquisitive propositions in Section 3.1, we will consider two other natural operations in Section 3.2, namely ones that trivialize the informative or the inquisitive content, respectively, of any given proposition. For reasons that will become clear below, we refer to such operators as projection operators. One projection operator turns any proposition into a corresponding non-inquisitive proposition, while the other turns any proposition into a corresponding non-informative proposition. Clearly, these operations do not have a counterpart in the classical setting, where propositions capture only informative content to begin with; but in the inquisitive setting they naturally arise, and we will suggest that they also have an important role to play in the semantic analysis of natural languages. More specifically, in Chapter 6 we will use these projection operators to capture the semantic contribution of declarative and interrogative complementizers.

# 3.1 Algebraic operations

In this section we will identify the basic algebraic operations that can be applied to inquisitive propositions. To illustrate our approach, we will first briefly review the algebraic perspective on classical logic.

## 3.1.1 The algebraic perspective on classical logic

In the classical setting a proposition P is simply a set of possible worlds. Let us denote the set of all classical propositions as $Pcl$. The proposition expressed by a sentence can be thought of as carving out a certain region in the logical space—the set of all possible worlds—and in asserting a sentence, a speaker is taken to provide the information that the actual world is located within this region. One proposition P entails another proposition Q, PQ, just in case $P⊆Q$, which means that P carves out a smaller region in the logical space than Q does, thereby encoding more information as to what the actual world is like. Entailment forms a partial order on the set of all classical propositions, i.e., it is a reflexive, transitive, and anti-symmetric relation. In Figure 3.1 we have depicted the set of all classical propositions, assuming that the logical space (p.45) consists of two worlds (the diagram on the left) or of three worlds (the diagram on the right). In each case, the arrows indicate entailment.

Figure 3.1 The set of all propositions in classical semantics if the logical space consists of two possible worlds (on the left) or three possible worlds (on the right). Arrows indicate entailment.

Now, given a partially ordered set, we can ask what natural operations can be defined on it—that is, what algebraic structure it has. The set of classical propositions ordered by entailment, $〈Pcl,⊧〉$, forms a so-called Heyting algebra, which comes with four basic operations: meet, join, relative pseudo-complementation and absolute pseudo-complementation.1

To illustrate these operations, we will make use of the diagrams in Figure 3.2. The grid in each diagram represents a space of propositions ordered by entailment: each node in the grid is a proposition, and one proposition entails another just in case there is a path from the first to the second along the grid such that each step of the path goes up. For instance, in Figure 3.2(a) P entails Q, because there is a path going up from P to Q, but P does not entail R because any path from P to R must contain at least one step that goes down. (p.46)

Figure 3.2 Visualization of basic algebraic operations.

The meet of P and Q is the greatest lower bound of P and Q with respect to entailment, i.e., the weakest proposition that entails both P and Q. As indicated in Figure 3.2(b), this greatest lower bound amounts to the intersection of the two propositions: $P∩Q$. More generally, the meet of a (possibly infinite) set of propositions Σ‎ amounts to the intersection of all the propositions in that set:

$Display mathematics$

If Σ‎ is empty, then $⋂Σ$ is the proposition consisting of all possible worlds, $W$. This is the weakest of all propositions, since it is entailed by all other propositions. It is denoted as ⊤. On the other hand, if Σ‎ is the set of all propositions, then $⋂Σ$ is the empty proposition, . This is the strongest of all propositions, since it entails all other propositions. It is denoted as ⊥.

The join of two propositions P and Q is the least upper bound of P and Q with respect to entailment, i.e., the strongest proposition that is entailed by both P and Q. As indicated in Figure 3.2(b), this least upper bound amounts to the union of the two propositions: $P∪Q$. More generally, the join of a (possibly infinite) set of propositions Σ‎ amounts to the union of all the propositions in that set:

$Display mathematics$

If Σ‎ is empty, then $⋃Σ$ is the empty proposition, ⊥. On the other hand, if if Σ‎ is the set of all propositions, then $⋃Σ$ is the proposition consisting of all possible worlds, ⊤.

The existence of meets and joins for arbitrary sets of propositions implies that $〈Pcl,⊧〉$ forms a complete lattice, bounded by ⊥ and ⊤ as its strongest and weakest elements, respectively.

Now let us turn to relative and absolute pseudo-complementation. The pseudo-complement of a proposition P relative to another (p.47) proposition Q, which we will denote as $P⇒Q$, can be thought of intuitively as the difference between P and Q: it is the weakest proposition R such that P and R together contain at least as much information as Q. More formally, it is the weakest proposition R such that $P∩R⊧Q$. To illustrate this notion, consider the propositions P and Q in Figure 3.2(c). How do we find the pseudo-complement of P relative to Q? The first step is to determine the set of all propositions R which are such that $P∩R⊧Q$. This is the shaded area in Figure 3.2(c). Indeed, if we take the meet of P with any proposition in this area, we obtain a proposition that entails Q. The second step is to select the weakest element of this set, i.e., that proposition which is entailed by all other propositions in the set. In our diagrams, one proposition entails another if there is a path going up from the first to the second. This means that the weakest element of a set of propositions is the topmost one. Thus, the topmost element of the shaded area in Figure 3.2(c) is the pseudo-complement of P relative to Q, which is denoted as $P⇒Q$.

It can be shown that $P⇒Q$ always consists of all possible worlds which, if contained in P, are also contained in Q:

$Display mathematics$

Absolute pseudo-complementation is a limit case of its relative counterpart. The absolute pseudo-complement of a proposition P, which we will denote as P*, is the weakest proposition R such that P and R are incompatible, in the sense that P and R together yield a contradiction. More formally, P* is the weakest proposition R such that $P∩R=⊥$. This means that P* amounts to $P⇒⊥$, the pseudo complement of P relative to ⊥. Within the space of classical propositions, the pseudo-complement of P is simply the set-theoretic complement of P:

$Display mathematics$

In a Heyting algebra it always holds, by definition of P*, that $P∩P*=⊥$. In the specific case of $〈Pcl,⊧〉$, we also always have that $P∪P*=⊤$. This means that in this particular setting, P* is in fact the Boolean complement of P, and that $〈Pcl,⊧〉$ forms a Boolean algebra, a special kind of Heyting algebra.

Thus, classical propositions are amenable to certain basic algebraic operations. Classical first-order logic is obtained by associating these operations with the connectives and the quantifiers. Indeed, the usual definition of truth can be reformulated as a recursive definition of the (p.48) set |φ‎| of worlds in which φ‎ is true (given a domain D of individuals). The inductive clauses then run as follows:

• φ‎| = |φ‎|*

• $|φ∧ψ|=|φ|∩|ψ|$

• $|φ∨ψ|=|φ|∪|ψ|$

• $|φ→ψ|=|φ|⇒|ψ|$

• $|∀x.φ(x)|=⋂d∈D|φ(d)|$

• $|∃x.φ(x)|=⋃d∈D|φ(d)|$

Negation expresses absolute pseudo-complementation; conjunction and disjunction express binary meet and join, respectively; implication expresses relative pseudo-complementation; and quantified formulas, ∀x.φ‎ and ∃x.φ‎, express the infinitary meet and join, respectively, of {|φ‎(d)|∣dD}.

Notice that everything started with a notion of propositions and a natural entailment order on these propositions. The entailment order induces certain basic operations on propositions, and classical first-order logic is obtained by associating these basic semantic operations with the connectives and quantifiers.

## 3.1.2 Algebraic operations on inquisitive propositions

Recall that in inquisitive semantics propositions are not sets of worlds, but rather sets of information states, non-empty and downward closed. In this setting, one proposition P entails another proposition Q just in case P is at least as informative and at least as inquisitive as Q. We have seen that this condition is satisfied just in case $P⊆Q$. So technically entailment still amounts to inclusion, just like in classical logic, though now it encompasses both informative and inquisitive strength. In Figure 3.3 we have depicted the set of all propositions in a logical space consisting of two possible worlds, and in Figure 3.4 we have done the same for a logical space consisting of three possible worlds. As before, arrows indicate entailment.

Figure 3.3 The set of all inquisitive semantics propositions if the logical space consists of two possible worlds. Arrows indicate entailment.

Figure 3.4 The set of all inquisitive semantics propositions if the logical space consists of three possible worlds. Arrows indicate entailment.

Now let us consider the algebraic structure of the space of all inquisitive propositions ordered by entailment, $〈P,⊧〉$, in order to determine which operations could be associated with the connectives and the quantifiers in an inquisitive semantics for the language of first-order logic. What kind of algebraic operations can be performed on inquisitive propositions? Does every set of propositions still have a unique greatest (p.49) lower bound (meet) and a unique least upper bound ( join) with regard to entailment? Does every proposition still have a pseudo-complement relative to any other proposition?

It turns out that these questions can be answered in the positive: $〈P,⊧〉$ forms a complete Heyting algebra, just like $〈Pcl,⊧〉$. First, any set of propositions $Σ⊆P$ still has a meet and a join, which can moreover still be characterized in terms of intersection and union.

Fact 3.1 (Meet)

Any set of propositions $Σ⊆P$ has a meet, which amounts to:

$Display mathematics$

Fact 3.2 (Join)

Any set of propositions $Σ⊆P$ has a join, which amounts to:

$Display mathematics$

if Σ‎≠, and to {} otherwise.

The existence of meets and joins for arbitrary sets of propositions implies that $〈P,⊆〉$ forms a complete lattice. This lattice has a unique strongest element, ⊥:={}, and a unique weakest element, $⊤:=℘(W)$.

Furthermore, just as in the classical setting, for every two propositions P and Q, there is a unique weakest proposition R such that $P∩R$ (p.50) (p.51) entails Q. Recall that this proposition, the pseudo-complement of P relative to Q, can be thought of intuitively as the difference between P and Q.

Fact 3.3 (Relative pseudo-complement)

For any $P,Q∈P$, the pseudo-complement of P relative to Q amounts to:

$Display mathematics$

The existence of relative pseudo-complements implies that $〈P,⊆〉$ forms a Heyting algebra. Finally, recall that the absolute pseudo-complement of a proposition P, denoted P*, is defined as the pseudo-complement of P relative to ⊥. We saw that in the classical setting, P* amounts to the set of worlds that are not in P. In the inquisitive setting, P* amounts to the set of states that are incompatible with any state in P.

Fact 3.4 (Absolute pseudo-complement)

For any proposition $P∈P$:

$Display mathematics$

A state s is incompatible with all states in P just in case it is incompatible with the union $⋃P$ of all these states, which amounts to info(P). In turn, s is incompatible with info(P) just in case $s⊆info(P)¯$. This leads to the following alternative characterization of P*.

Fact 3.5 (Absolute pseudo-complements, alternative characterization)

For any proposition $P∈P$:

$Display mathematics$

This characterization shows in particular that the absolute pseudo-complement of any given proposition P always contains a single alternative, $info(P)¯$, and is therefore never inquisitive.

The algebraic operations that we have identified are exactly the ones that are present in the classical setting. One notable difference, however, is that the absolute pseudo-complement of an inquisitive proposition is not always its Boolean complement. In fact, most inquisitive propositions do not have a Boolean complement at all. To see this, suppose that P and Q are Boolean complements. This means that:

1. (i) $P∩Q=⊥$

2. (ii) $P∪Q=⊤$

(p.52) Since $⊤=℘(W)$, condition (ii) can only be fulfilled if either P or Q contains $W$. Suppose $W∈P$. Then, since P is downward closed, $P=℘(W)=⊤$. But then, in order to satisfy condition (i), we must have that Q = {} = ⊥. So the only two elements of our algebra that have a Boolean complement are ⊤ and ⊥. Hence, the space $〈P,⊧〉$ of inquisitive propositions does not form a Boolean algebra, unlike the space $〈Pcl,⊧〉$ of classical propositions.

This difference has repercussions for the behavior of the logical system that we will specify, in particular for negation (for instance, the law of double negation will no longer hold). However, the similarity between $〈P,⊧〉$ and $〈Pcl,⊧〉$ that we identified, i.e., the fact that both form a Heyting algebra, is much more important for our current purposes. In particular, the existence of meets, joins, and relative and absolute pseudo-complements in $〈P,⊧〉$ will allow us to specify an inquisitive semantics for the language of first-order logic which is, from an algebraic perspective, the exact counterpart of classical first-order logic in the inquisitive setting. We will turn to this in Chapter 4. Before that, however, we will consider two additional operations that are particularly natural to perform on propositions in inquisitive semantics.

# 3.2 Projection operators

We noted in Section 2.4.2 that propositions in inquisitive semantics can be seen as inhabiting a two dimensional space, with non-inquisitive propositions living on one axis and non-informative propositions on the other. Given this picture, it is natural to consider whether it is possible to define general projection operators on this space, i.e., operators that map any given proposition to a corresponding proposition on one of the axes, trivializing either its informative or its inquisitive content. We will refer to such operators as info-cancelling and issue-cancelling projection operators.

Let us first consider more precisely what would be required for an operator π‎ to qualify as an issue-cancelling projection operator. Such an operator should project a proposition onto the axis inhabited by non-inquisitive propositions. This means that, when applied to a proposition P, π‎ should (i) trivialize the inquisitive content of P, i.e., turn P into a non-inquisitive proposition, and (ii) preserve the informative content (p.53) of P, i.e., yield a proposition that has the same informative content as P. This leads us to the following requirements.

Definition 3.6 (Requirements on issue-cancelling projection operators)

An operator π‎ qualifies as an issue-cancelling projection operator just in case for any $P∈P$:

• π‎P is non-inquisitive

• info(π‎P) = info(P)

Now, in Section 2.4.2 we saw that if P is non-inquisitive, then we always have that P = (info(P)). This means that in order to satisfy the above requirements, π‎P must amount to (info(P)) for any proposition P. Thus, the semantic behavior of π‎ is uniquely determined by the given requirements.

Fact 3.7 (Unique characterization)

An operator π‎ qualifies as an issue-cancelling projection operator just in case for any $P∈P$:

• π‎P = (info(P))

Now let us consider which requirements π‎ should fulfill in order to qualify as an info-cancelling projection operator. Such an operator should project a proposition onto the axis inhabited by non-informative propositions. For this, we should require that π‎ trivializes the informative content of the proposition to which it applies, i.e., π‎P should always be non-informative. But, given this basic requirement, we cannot further demand that π‎ always preserve the inquisitive content of P. For, if P and π‎P do not have the same informative content, then their inquisitive content will differ as well.

Fortunately, there is a natural way to overcome this obstacle. Namely, what we can require is that π‎ preserve the decision set of P, i.e., the set of states that either settle the issue embodied by P, or contradict the informative content of P and thereby establish that it is impossible to settle the issue altogether.

Definition 3.8 (Contradicting and deciding on a proposition)

Let s be an information state and P a proposition. Then we say that:

• s contradicts P just in case $s∩info(P)=∅$;

• s decides on P just in case s either supports or contradicts P.

(p.54)

Definition 3.9 (Decision set)

The decision set D(P) of a proposition P is the set of states that decide on P.

The decision set of a proposition can be characterized explicitly as follows.

Fact 3.10 (Decision set explicated)

For any proposition P:

• $D(P)=P∪P*$

Now, what we require of an info-cancelling projection operator π‎ is that, besides trivializing the informative content of the proposition it applies to, it preserves the proposition’s decision set. This is a requirement that can in principle be met, since P and π‎P can very well have the same decision set even if they differ in informative content.

Definition 3.11 (Requirements on info-cancelling projection operators)

An operator π‎ qualifies as an info-cancelling projection operator just in case for any $P∈P$:

• π‎P is non-informative;

• D(π‎P) = D(P).

Now suppose that π‎ fulfils these requirements. Then for any P, π‎P is non-informative, which means that $info(πP)=W$. But then $(πP)*=℘(info(P)¯)=℘(W¯)=℘(∅)={∅}$, and therefore $D(πP)=(πP)∪(πP)*=πP$. But since π‎ should preserve the decision set of P, we also have that $D(πP)=D(P)=P∪P*$. Putting these facts together, we obtain that $πP=P∪P*$. Thus, the requirements we placed on π‎ again uniquely determine its behavior.

Fact 3.12 (Unique characterization)

An operator π‎ qualifies as an info-cancelling projection operator just in case for any $P∈P$:

• $πP=P∪P*$

Thus, by spelling out the natural requirements on issue-cancelling and info-cancelling projection operators we have arrived at a unique characterization of these operators, which we will denote as ! and ?, respectively. (p.55)

Definition 3.13 (Projection operators)

For any proposition P:

• !P:= (info(P))

• $?P:=P∪P*$

As depicted in Figure 3.5, the projection operators ! and ? turn any proposition P into an non-inquisitive proposition !P which has the same informative content as P, and a non-informative proposition ?P which has the same decision set as P. P itself can always be reconstructed as the meet of these two ‘pure components’.

Figure 3.5 Projection operators.

Fact 3.14 (Division)

For any proposition P:

• $P=!P∩?P$

Finally, let us consider how ? and ! are related to the algebraic operations identified in Section 3.1. Notice that ?P is already explicitly characterized in terms of the algebraic operations: it amounts to the join of P and its absolute pseudo-complement P*. It turns out that !P can also be characterized in terms of pseudo-complementation. Namely, for any proposition P, !P amounts to P**, i.e., to the proposition that results from two successive applications of the absolute pseudo-complementation operator to P.

Fact 3.15 (Projection operators and algebraic operators)

For any proposition P:

• !P = P**

• $?P=P∪P*$

(p.56) This concludes our discussion of the basic semantic operations that can be performed on propositions in inquisitive semantics. We end this chapter with a brief remark on the linguistic relevance of these operations, which will be further substantiated in later chapters.

# 3.3 Linguistic relevance

Since the algebraic operations on propositions that are associated with the connectives and quantifiers in classical logic are so fundamental, it is to be expected that natural languages will generally have ways to express them as well; just like one would expect, for instance, that basic arithmetic operations like addition and substraction are generally expressible in natural languages. This makes the algebraic operations discussed here of special interest from a linguistic point of view.

Similar considerations apply to the projection operators. Again, since these semantic operators are so fundamental, it is to be expected that they too are expressible in many natural languages. More specifically, it seems plausible to hypothesize that they are expressed in English and many other languages by declarative and interrogative clause type markers. For instance, on a first approximation, we may hypothesize that declarative clause type marking in English invokes the issue-cancelling projection operator ‘!’, and interrogative clause type marking the info-cancelling projection operator ‘?’. A more detailed account of clause type marking in English in terms of the projection operators will be presented in Chapter 6.

# 3.4 Exercises

## Exercise 3.1 Working through some examples

Consider the four propositions depicted in Figure 2.4.

1. 1. Determine the absolute pseudo-complement of each of these propositions.

2. 2. Determine the meet and the join of every pair among these propositions.

3. 3. Determine the outcome of applying the projection operators to each of these propositions.

## (p.57) Exercise 3.2 Meets and joins

Prove Facts 3.1 and 3.2. That is, show that every set of propositions in inquisitive semantics has a meet and a join with respect to entailment.

## Exercise 3.3 Relative pseudo-complementation

Prove Fact 3.3. That is, show that in inquisitive semantics every proposition P has a pseudo-complement relative to any other proposition Q, which amounts to $P⇒Q={s∣for everyt⊆s,ift∈Pthent∈Q}$.

## Exercise 3.4 Projection operators

Suppose we apply both projection operators to a given sentence, one after the other. Does it matter in which order we do this? That is, does the following hold for every proposition P:

$Display mathematics$

## Exercise 3.5 Projection operators

Show that the projection operators are idempotent, meaning that for every proposition P we have !!P = !P and ??P = ?P.

## Exercise 3.6 Division

Prove Fact 3.14. I.e., show that for every proposition P we have $P=!P∩?P$. (p.58)

## Notes:

(1) In fact, as we will discuss, the space of classical propositions ordered by entailment is a special kind of Heyting algebra, namely a Boolean algebra. For us, however, the more general fact that it forms a Heyting algebra will be crucial, because we will find that in inquisitive semantics the space of propositions no longer forms a Boolean algebra, but does still form a Heyting algebra. This will allow us to construe the basic logical operators in inquisitive semantics as the exact counterparts of those in classical logic.