B.1 Inner Diamond

Let us start with the Inner Diamond lemma (Lemma B.1), which will help us capture natural reasoning about conditional logical possibility in a more intuitive manner. Specifically, while the Importing (Axiom 8.6) and Logical Closure (Axiom 8.7) axioms capture the intuition that we can deploy our normal tools of reasoning to infer what further facts must be true in some particular logically possible context, using them directly would force us to carry unwieldy long conjunctions of all facts we’ve derived are logically possible through our proofs. The Inner Diamond lemma justifies our use of more natural mathematical reasoning.

The intuition behind the Inner Diamond lemma is that reasoning like the following is valid:

We note that this lemma supports the following kind of reasoning (as illustrated in the above example).

We derive some sentence of the form ${◊}_{ℒ}\Theta$ from the assumptions ${\Gamma }_1$ . For instance, in the example above $\Theta$ would be the claim that “every cat slept on a distinct blanket” and $ℒ$ would just be the predicate cat. We then wish to reason about the “world” whose possibility is guaranteed by the fact that ${◊}_{ℒ}\Theta$ , e.g., the possible world which holds fixed (the structure of) the application of cat and at which every cat slept on a distinct blanket. In that world $\Theta$ (every cat slept on a distinct blanket) is true as is, intuitively, every fact content-restricted to $\text{cat}$ true in the actual world. For instance, in the example above the fact that there are at least three cats is also true in that world (we refer to the act of taking a sentence content-restricted to $ℒ$ and concluding it holds at the world whose logical possibility is asserted by ${◊}_{ℒ}\Theta$ as importing). We then use proof rules to derive some desired conclusion $\Phi$ from $\Theta$ and the set of “imported” sentences ${\Gamma }_2$ . For instance, in the above example, $\Phi$ is the sentence asserting there are at least three blankets. Intuitively, $\Phi$ must also be true in the logically possible world under consideration and thus ${◊}_{ℒ}\Phi$ must be actually true. In the example above, ${\Gamma }_2$ would just contain the sentence asserting that there are at least three cats. Since $\Theta ,{\mathrm{\Gamma }}_2⊢\mathrm{\Phi }$ and all sentences in ${\Gamma }_2$ are content-restricted to $\text{cat}$ this intuition is born out rigorously since the above lemma establishes that ${\Gamma }_1,{\Gamma }_2⊢{◊}_{ℒ}\Phi$ .

B.2 Natural Deduction with Inner Diamond Arguments

Since the process of entering ${◊}_{ℒ}$ contexts, i.e., using Inner Diamond (Lemma B.1) to reason about what else must be true in a particular logically possible scenario, is unfamiliar and can be a bit tricky, I will informally introduce a natural deduction system for the notion of proof defined in Chapter 8 together with some notational conventions which make it easier to keep track of arguments like the one above (especially in contexts where one must make multiple Inner Diamond arguments within one another).

This system is loosely based around that used by Reference GarsonGoldfarb (2003) and I follow his system in citing the line numbers justifying each inference rule to the left of the name of the inference rule, while indicating the assumptions a line depends on by placing those line numbers in brackets (line numbers not in brackets are the lines cited as immediate justification for the current inference). So, for example, we write down $\Phi 5,6X\left[2,4,5\right]$ on line $7$ of a proof when rule $X$ allows us to conclude $\Phi$ from lines $5,6$ and the cumulative set of assumptions from which we’ve established $\Phi$ are the sentences on lines $2,4$ and $5$ . Note that this system satisfies the principle that if $\psi$ appears on some line of the proof and $\Gamma$ is the set of sentences appearing on the lines listed in brackets next to $\psi$ then $\Gamma ⊢\psi$ .

However, my system differs from Goldfarb’s in two primary ways. First, I will allow any purely first-order deduction to be compressed into a single FOL rule. However, I will still sometimes explicitly make use of $\to I$ to infer $\varphi \to \psi$ in cases where $\psi$ can only be inferred from $\varphi$ via modal reasoning. I will also use Ass. to indicate that a new assumption is being made.

Second, all modal axioms and axiom schema proposed in Chapter 8 are taken to be logical truths. So, any instance of these axiom schemata can be written down with no associated citations or assumptions. And, to save time, any instance of an axiom schema with the form $\varphi \to \psi$ may instead be regarded as an inference rule allowing us to infer $\psi$ from $\varphi$ (citing the line containing $\varphi$ as a justification). For example, this is an acceptable deduction of ${◊}_P\left[\left(\exists x\right)P\left(x\right)\right] \to P\left(x\right)$ :

This is also an acceptable deduction of the same fact:

Third, and most distinctively, I will introduce a special context called a $◊$ context (nestable to arbitrary depth) corresponding to reasoning via Inner Diamond (Proposition B.1), i.e., reasoning about what else must be true within some scenario which is known to be (conditionally) logically possible. I will graphically indicate what sentences are being asserted or assumed within this context by indentation and a sideways T labeled with a $◇$ to indicate this context.

So, for example, we can represent the following extremely short Inner Diamond argument:

with a proof that looks like this:

The vertical line going from 2–3 above indicates those lines occur inside a special context. I call this a $◊$ context to indicate that these lines contain reasoning about what must be true within a logically possible scenario in which $\left(\exists x\right)(cat\left(x\right) \wedge hunter\left(x\right))$ , while all the structural facts about, how cathood applies, are preserved.

What are the rules for writing things down in this context? Recall that the Inner Diamond (Proposition B.1) lemma says that if we have one conditional possibility claim ${◊}_{ℒ}(\Theta )$ , and some facts ${\Gamma }_2$ which are content-restricted to the relations being held fixed, then if we can show that any such possible scenario where $\Theta$ must also be one where $\Phi$ (by showing $\Theta ,{\Gamma }_2⊢\Phi$ ), we can infer the corresponding conditional logical possibility clam for $\Phi$ .

The key idea will be to use indentation and the Fitch-style sidewise T to graphically distinguish a main line of argument which goes from ${\Gamma }_2$ (where the sentences ${\Gamma }_2$ are content-restricted to $ℒ$ ) and ${◊}_{ℒ}\Theta$ and then ${◊}_{ℒ}\Phi$ , from a supporting subproof which shows that ${\Gamma }_2,\Theta ⊢\Phi$ and thereby justifies the latter inference.

In the latter subproof (which I indent and mark off as a separate context) we are, in essence, attempting to milk new consequences from our knowledge that ${◊}_{ℒ}(\Theta )$ , by thinking about what else must be true in a possible ( ${◊}_{ℒ}$ ) situation where $\Theta$ . Thus, I will call beginning such a subproof “entering the ${◊}_{ℒ}$ context” (associated with some claim ${◊}_{ℒ}(\Theta )$ that was established on a previous line), and thereby beginning an Inner Diamond (Lemma B.1) argument.

One will only be permitted to import those claims ${\Gamma }_2$ from the main line of argument (thereby assuming they continue to hold in the current context) which are content-restricted to the relevant list of relation $ℒ$ . And we will only be allowed to close the Inner Diamond context, i.e., dropping back one level of indentation and writing down ${◊}_{ℒ}(\Phi )$ , if we have proved that $\Phi$ holds inside the Inner Diamond context, by showing that it follows from the initial assumption that $\Theta$ and some facts ${\Gamma }_2$ which we were allowed to import because they were content-restricted to $ℒ$ .

Reasoning inside a $◊$ context proceeds just as it does normally, with the exception that each line in the context must either be our initial assumption that $\Theta$ (where ${◊}_{ℒ}\Theta$ is the sentence that opened the diamond context), an instance of “importing” (where the sentence must be imported from the parent context) or be deducible from previous lines within this exact $◇$ context.

While the operation of In $◊$ I is rather straightforward, I’ll call attention to one detail. Note that besides line $2$ we wrote $\left[2^{*}\right]$ rather than $\left[1\right]$ as one might expect. We do this to maintain the property that if $\mathrm{\Psi }$ is written on a line it is deducible from the lines written in brackets next to it.Footnote ²

One can leave the ${◊}_{ℒ}$ context above by going from knowledge that $\varphi$ holds within this context to the conclusion that ${◊}_{ℒ}\varphi$ holds outside it. We indicate this inference pattern via the rule In $◇$ E. This is the only way to introduce a sentence into the current context based on activity in a child context.Footnote ³

B.3 Example of Inner ◊ with Importing

We can also capture the reasoning in the slightly more complicated argument below, where we use knowledge of suitably content-restricted claims about the actual world to draw consequences from a modal claim.Footnote ⁴

It’s logically possible, given what cats there are, that each slept on a distinct blanket. There are at least three cats. Therefore, it’s logically possible, given what cats there are that there are at least three blankets:

B.4 Box Inference Rules

Although the $\square$ is not an official item in our symbolism, but merely an abbreviation for $\neg ◊\neg$ , it is often helpful to reason in terms of it. Earlier we proved a couple of rules regarding $\square$ inferences and here we present several more.

First, I present an introduction rule for $\square$ .

Proof. Suppose for contradiction that $\Gamma ,\Theta$ are as above, but the lemma fails, i.e., ${◊}_{ℒ}\neg \Theta$ . By Inner Diamond (Lemma B.1) with ${\Theta }_1={◊}_{ℒ}\neg \Theta$ and ${\Theta }_2=\Theta$ , we can infer ${◊}_{ℒ}\perp$ as $\Theta ,\neg \Theta ⊢\Theta \wedge \neg \Theta$ . Hence, by $◇$ Elimination (Axiom 8.2) we can export the contradiction. Hence, ${\square }_{ℒ}\Theta$ as desired. ■ Now I give the corresponding elimination rule.

Note that I prove a stronger version of this result in Section H of the online appendix that allows arbitrary substitution of relations when eliminating the box and, for ease of reading, I will also refer to that result as $\square$ Elimination.

Proof. Assume the claim fails. We can derive contradiction immediately by applying $◊$ Introduction (Axiom 8.1) to $\neg \Theta$ to derive ${◊}_{ℒ}\neg \Theta$ , which is $\neg {\square }_{ℒ}\Theta$ . We can write this in terms of the natural deduction system presented above as follows:

■

To give a more visceral sense of how proofs using this logical system work, see Section B.6 where I prove two lemmas which mirror results in set theory (which can be found in elementary texts like Reference JechJech (1978)).

B.5 ◊ Reducing and □ Expansion

Using first-order logic and the basic principles in Chapter 8 we can prove various useful lemmas.

The Reducing lemma (Lemma B.4) (together with $\to$ E) vindicates intuitive reasoning along the following lines. Suppose it’s logically possible, given the facts about friendship and enmity in the actual world, that something has a frenemy (i.e., there are items $x$ and $y$ such that $x$ is the friend of $y$ and $x$ is the enemy of $y$ ). Then it’s logically possible given (just) the facts about friendship in the actual world that something has a frenemy.

We note that this immediately entails a corresponding expansion property for sentences under the $\square$ .

B.6 Lemmas about Well-Orderings

To give a more visceral sense of how proofs using my logical system work, I’ll now prove two lemmas which mirror results in set theory (which can be found in elementary texts like Reference JechJech (1978)). In each case, I will make an argument verbally, and then follow it up with an argument using the formal notation (making explicit when we enter and leave Inner Diamond contexts).

Elsewhere I will present proofs in a more informal style. However, I hope the completely explicit proofs in this section will help the reader understand how these informal proofs can be expanded into a formal argument.

B.6.1 Reconstructing Well-Orderings: Part I

Jech’s version of the first lemma I am going to prove says the following:

“If $\left(W,<\right)$ is a well-ordered set and $f:W \to W$ is an increasing function, then $x<f\left(x\right)$ for each $\in W$ .” (Reference JechJech 1978)

We can write a version of Jech’s Lemma follows (see Section E of the online appendix for the definition of a well-order):

Lemma B.6 If $f$ is an embedding of the well-order $W,<$ into itself then $(\forall x,y:W\left(x\right) \wedge W\left(y\right))(x<f\left(x\right))$ .

We define embedding as follows:

Definition B.1 (Definition of Embedding). A two-place relation $f$ is an embedding of $W,<$ into $W^{\prime },{<}^{\text{'}}$ iff:

• $f$ is a function (remember we define what it takes for a relation to qualify as a function in Section A.1)

• $\left(\forall x\right)[W\left(x\right) \to \left(\exists y\right)(W^{\prime }\left(y\right)\wedge f\left(x\right)]$ i.e., $f$ maps all of $W$ into $W^{\prime }$

• $\left(\forall x\right)\left(\forall y\right)\left(\forall x^{\prime }\right)\left(\forall y^{\prime }\right)\left[x<y\leftrightarrow f\left(x\right)<f\left(y\right)\right]$ , i.e., $f$ respects $<$ .

Remember that we’ve defined function so that the function $f\left(x\right)$ is a convenient way of talking about the relation $f\left(x,y\right)$ satisfying $f\left(x,y\right)\wedge f\left(x^{\prime },y\right) \to x=x^{\prime }$ .

As usual, I will sometimes abbreviate the claim that $x<y\vee x=y$ as $x \le y$ .

Proof. To prove this, we will use essentially the same reasoning which Jech uses to prove his set theoretic version of this claim.

Assume that $f$ is an embedding of $\left(W,<\right)$ into itself, as per the statement of the lemma. And suppose, for contradiction, the lemma fails. As in Jech’s proof, our aim will be to use the properties of well-orderings to derive the existence of a $<$ least counterexample, i.e., an $x$ in $W$ such that $\neg x<f\left(x\right) \wedge \left(\forall y:y<x\right)(y<f\left(y\right))$ and derive contradiction from this.

Applying Simple Comprehension (Axiom 8.4) to $\neg x<f\left(x\right)$ tells us it would logical possible – while holding fixed the facts about how $W,<,f$ apply in the situation we are currently considering – for the predicate $G$ apply to just such counterexamples. That is:

${◊}_{W,<,f}(\forall x)(G\left(x\right)\leftrightarrow \neg x<f\left(x\right))$

Now we can enter this ${◊}_{W,<,f}$ context, i.e., begin an Inner Diamond (Lemma B.1) argument, where we reason about what else must be true in a possible scenario where (the facts about $W,<,f$ in our original scenario are held fixed but) we also have:

$\left(\forall x\right)(G\left(x\right)\leftrightarrow \neg x<f\left(x\right))$

Now the premises of the lemma (that $f$ is an embedding of $\left(W,<\right)$ into itself and $\left(W,<\right)$ a well-order) and the assumption that the conclusion of the lemma fails are all implicitly context restricted to $W,<,f$ (seen by appropriately restricting all the quantifiers). So, all of these statements must all remain true in this new context and can by imported into this context.

Thus, we can infer that $G$ is non-empty, from the assumption that the lemma fails, i.e., $(\exists x\mid W\left(x\right))(\neg x<f\left(x\right)$ , together with the fact that $\left(\forall x\right)(G\left(x\right)\leftrightarrow \neg x<f\left(x\right))$ .

We know that $W,<$ is a well-ordering, and the least element condition from the definition of well-ordering (Definition E.2 in the online appendix) says the following:

${\square }_{W,<}\left[(\exists x\mid W\left(x\right))G\left(x\right) \to (\exists y\mid W\left(y\right)\wedge G\left(y\right))(\forall z\mid W\left(z\right)\wedge G\left(z\right))\left(y\le z\right))\right]$

So, by $\square$ Elimination (Lemma B.3) we can infer the existence of a least counterexample $y$ , i.e.,

$(\exists y\mid W\left(y\right)\wedge G\left(y\right))(\forall z\mid W\left(z\right)\wedge G\left(z\right)))\left(y\le z\right))$

Now let $z=f\left(y\right)<y$ . By our assumption that $f$ is an embedding (and thus must respect $<$ ) it follows from $z<y$ that $f\left(z\right)<f\left(y\right)=z$ . So, by the equation specifying the extension of G above we can infer that $G\left(z\right)$ . Thus, $z$ is an satisfies $G\left(z\right)$ and is less than $y$ . Contradiction $\perp$ .

Exiting the above $◊$ context (i.e., completing our Inner Diamond argument), we get ${◊}_{W,<,f}\perp$ . And from this $\perp$ follows by $◊$ Elimination (Axiom 8.2) (remembering that $\perp$ is content-restricted to the empty list). Hence, the desired conclusion follows by contradiction. ■

Intuitively speaking, the argument above shows that the if there were a counterexample to the lemma then it would be logically possible (indeed logically possible, while holding fixed the $W,<,f$ facts!) for the canonical contradiction $\perp$ to be true. But it’s not logically possible for $\perp$ to be true. So, there is no counterexample to the lemma.

Representing this proof in terms of our natural deduction system:

B.6.2 Reconstructing Well-Orderings: Part 2

Reference HorstenJech (1978) writes, “No well-ordered set is isomorphic

to an initial segment

of itself.” We can state the claim to be proved using the definition of isomorphism (Definition 7.4) from Chapter 7.

Lemma B.7 If $\left(W,<\right)$ is a well-ordering and there is some $x$ in $W$ such that $W^{\prime }$ applies to just those $z<x$ in $W$ then $\neg {◊}_{W,W^{\prime },<}〈W,>〉\underset{f}{\cong }〈W\text{'},>〉$ .

Proof. Let $W,W^{\prime },<$ be as in the lemma and suppose for contradiction that ${◊}_{W,W^{\prime },<}〈W,>〉{\cong }_f〈W\text{'},>〉$ . Using Inner Diamond (Lemma B.1) we can enter this $◊$ context. We can import the fact $W,<$ is a well-order (because it is content-restricted to $W,W^{\prime }$ and $<$ ). By first-order logic and unpacking definitions we can infer from the fact that $f$ isomorphically maps $〈W,>〉$ to $〈W^{\prime },>〉$ that $f$ is an embedding of $W,<$ into $W^{\prime },<$ . And, by the assumptions about $W^{\prime }$ above, this implies that $f$ is an embedding of $W,<$ into $,<$ .

Now, to get contradiction, note that by Lemma B.6 (all instances of which are provable from empty premises, hence provable in any $◊$ context) $f$ does not map any object satisfying $W$ strictly $<$ -below itself. However, we know there is an object $x$ satisfying $W$ which is $>$ all objects satisfying $W^{\prime }$ and that $〈W,>〉{\cong }_f〈W^{\prime },>〉$ . It follows by first-order logic that $f$ maps this $x$ to some $y<x$ . Thus, we have derived contradiction/the false ( $\perp$ ) from premises which would have to obtain in this (supposedly) logically possible scenario.

As before, we can conclude this inner ${◊}_{W,W^{\prime },<}$ argument and returning to our original context with the conclusion that ${◊}_{W,W^{\prime },<}\perp$ . And from this $\perp$ follows by $◇$ Elimination (Axiom 8.2).

This completes our proof by contradiction that there can be no $f$ isomorphically mapping $\left(W,>\right)$ to a proper initial segment of itself. ■

We can use the natural deduction system to expose the modal reasoning within this argument, as follows:

B.7 Pasting and Collapsing

Finally, I will conclude this chapter with two lemmas involving more complex modal reasoning using multiple $◊$ contests. The first lemma tells us when two logically possible facts can be inferred to be jointly possible.

One cannot generally infer from ${◊}_{ℒ}\Phi$ and ${◊}_{ℒ}$ to ${◊}_{ℒ}(\Phi \wedge \Psi )$ . Consider the case where $\Phi$ says there are exactly eight million things and $\Psi$ says there are exactly nine million things. However, the Pasting lemma (Lemma B.8) says that one can make this inference in the special situation when the sentences $\Phi$ and $\Psi$ are content-restricted so that they can only make claims about the objects satisfying some disjoint lists of relations $ℐ$ and $𝒥$ (and how these relate the actual $ℒ$ -structure, which both ${◊}_{ℒ}\Phi$ and ${◊}_{ℒ}\mathit{\text{Ψ}}$ preserve).

Intuitively speaking, the facts about content-restriction above ensure that attempting to make the sentences inside both possibility claims true at the same time cannot impose conflicting demands. For the only relations whose extensions are relevant to the truth of both sentences are the relations on the list $ℒ$ . And our assumptions say that it’s possible to make each interior sentence true while fixing the actual application of these relations.

Proof. Let $\Phi$ be content-restricted to $ℒ,ℐ$ and $\Psi$ to $ℒ,𝒥$ , as per the antecedent:

Informally, this deduction corresponds to the following reasoning. Assume that ${◊}_{ℒ}\Phi$ and ${◊}_{ℒ}\Psi .$ We can prove our claim by making two nested Inner Diamond (Lemma B.1) arguments.

First enter the ( ${◊}_{ℒ}$ ) context associated with ${◊}_{ℒ}\Phi$ . That is, consider what else must be true in any such possible ( ${◊}_{ℒ}$ ) situation where $\Phi$ . In this situation ${◊}_{ℒ}\Psi$ must remain true, for it is content-restricted to $ℒ$ , and we are considering a scenario which preserves the $ℒ$ facts. By $◇$ Ignoring (Axiom 8.3) it follows that ${◊}_{ℒ,ℐ}\Psi$ .

Now enter this second, interior, ${◊}_{ℒ,ℐ}$ context. That is, consider what must be true in a further possible scenario where $\Psi$ is true while all facts about how relations $ℒ,ℐ$ applied in the scenario we previously considered are preserved. Here we clearly have $\Psi$ . But we can import the fact that $\Phi$ from the previous context, because it is content-restricted to $ℒ,ℐ$ . So we can deduce $\Phi \wedge \Psi$ .

Now, leaving this inner ${◊}_{ℒ,ℐ}$ context, we can conclude that ${◊}_{ℒ,ℐ}(\Phi \wedge \Psi )$ . And we can infer that that ${◊}_{ℒ}(\Phi \wedge \Psi )$ by $◊$ Ignoring (Axiom 8.3) (because $ℒ$ is clearly a sublist of $ℒ,ℐ$ ).

So, leaving the larger ${◊}_{ℒ}$ context we can conclude that ${◊}_{ℒ}({◊}_{ℒ}\left(\Phi \wedge \Psi \right))$ holds in the situation we were originally considering.

Finally, because ${◊}_{ℒ}(\Phi \wedge \Psi )$ is content-restricted to $ℒ$ , we can use $◇$ E to draw the desired conclusion ${◊}_{ℒ}(\Phi \wedge \Psi )$ . ■

The other lemma concerns when we can collapse multiple logical possibility operators into a single operator.

Proof. To prove the left to right direction, suppose that ${◊}_{ℒ}{◊}_{ℒ\text{'}}\Phi$ . Enter the ${◊}_{ℒ}$ context. In this context we have ${◊}_{ℒ\text{'}}\Phi$ . Since ${ℒ}^{\prime }\supset ℒ$ , by Reducing (Lemma B.4) we can infer ${◊}_{ℒ}\Phi$ . Exiting the ${◊}_{ℒ}$ context, we have ${◊}_{ℒ}\left({◊}_{ℒ}\Phi \right)$ in our original contest. So, we can apply $◇$ Elimination (Axiom 8.2) to infer ${◊}_{ℒ}\Phi$ .

To prove the other direction, suppose that ${◊}_{ℒ}\Phi$ . Entering this diamond context, we have $\Phi$ and can infer that ${◊}_{ℒ\text{'}}\Phi$ by $◇$ Introduction (Axiom 8.1). So, completing our Inner Diamond argument gives us ${◊}_{ℒ}{◊}_{ℒ\text{'}}\Phi$ .

We also observe that there is a corresponding $\square$ version of the above lemma.

Proof. Note that this is equivalent to proving

$\neg {\square }_{ℒ}\Phi \leftrightarrow \neg {\square }_{ℒ}{\square }_{{ℒ}^{\prime }}\Phi$

which is just

${◊}_{ℒ}\neg \Phi \leftrightarrow {◊}_{ℒ}{◊}_{ℒ\text{'}}\neg \Phi$

This is true by Diamond Collapsing (Lemma B.9). ■