11 Metatheory

Proof. We look at each direction in turn.

($\Rightarrow$) If $\mathrm{\Gamma }{⊢}_{\mathrm{\Sigma }}\phi$, then $\mathrm{\Gamma },\mathrm{\neg }\phi {⊢}_{\mathrm{\Sigma }}\phi$. Since ${⊢}_{\mathrm{\Sigma }}(\mathit{\alpha }\wedge \mathrm{\neg }\phi )\to \mathrm{\neg }\phi$, we have ${⊢}_{\mathrm{\Sigma }}(\mathit{\alpha }\wedge \mathrm{\neg }\phi )\to \mathrm{\perp }$. So, $\mathrm{\Gamma },\mathrm{\neg }\phi$ is $\mathrm{\Sigma }$-inconsistent.

($\Leftarrow$) If $\mathrm{\Gamma },\{\mathrm{\neg }\phi \}$ $\mathrm{\Sigma }$-inconsistent, for some conjunction $\mathit{\alpha }$ of members of $\mathrm{\Gamma }$, we have ${⊢}_{\mathrm{\Sigma }}\mathit{\alpha }\wedge \mathrm{\neg }\phi \to \mathrm{\perp }$. Since ${⊢}_{\mathrm{\Sigma }}\mathrm{\neg }\mathrm{\perp }$, we have that ${⊢}_{\mathrm{\Sigma }}\mathit{\alpha }\to \phi$ and $\mathrm{\Gamma }{⊢}_{\mathrm{\Sigma }}\phi$.

Proof. We look at each claim in turn.

1. There are two directions.

   ($\Rightarrow$) If $\mathrm{\Gamma }{⊢}_{\mathrm{\Sigma }}\phi$, then $\mathrm{\Gamma },\mathrm{\neg }\phi$ is $\mathrm{\Sigma }$-inconsistent. On the other hand, if $\phi \notin \mathrm{\Gamma }$, then, by definition of maximal $\mathrm{\Sigma }$-consistency, $\mathrm{\Gamma },\phi$ would be $\mathrm{\Sigma }$-inconsistent making $\mathrm{\Gamma }$ $\mathrm{\Sigma }$-inconsistent. So, $\phi \in \mathrm{\Gamma }$.

   ($\Leftarrow$) If $\phi \in \mathrm{\Gamma }$, then $\mathrm{\Gamma }{⊢}_{\mathrm{\Sigma }}\phi$ since ${⊢}_{\mathrm{\Sigma }}\phi \to \phi$.

2. We look at each direction in turn.

   ($\Rightarrow$) If $\mathrm{\neg }\phi \in \mathrm{\Gamma }$, then $\mathrm{\Gamma }{⊢}_{\mathrm{\Sigma }}\mathrm{\neg }\phi$. So, if $\mathrm{\Gamma }$ is $\mathrm{\Sigma }$-consistent, then $\phi \notin \mathrm{\Gamma }$.

   ($\iff$) If $\phi \notin \mathrm{\Gamma }$, then $\mathrm{\Gamma },\phi$ is $\mathrm{\Sigma }$-inconsistent. So, $\mathrm{\Gamma },\mathrm{\neg }\mathrm{\neg }\phi$ is $\mathrm{\Sigma }$-inconsistent, and by Proposition 5.1 $\mathrm{\Gamma }{⊢}_{\mathrm{\Sigma }}\mathrm{\neg }\phi$.

3. The proof of part 3 is analogous.

Proof. ($\Rightarrow$) Suppose $\{◊\phi :\phi \in \mathrm{\Delta }\}\subseteq \mathrm{\Gamma }$. Suppose now that $◻\phi \in \mathrm{\Gamma }$. For a reductio, suppose $\phi \notin \mathrm{\Delta }$. In that case, $\mathrm{\neg }\phi \in \mathrm{\Delta }$, which means, by assumption, that $◊\mathrm{\neg }\phi \in \mathrm{\Gamma }$. Since $◊$ is $\mathrm{\neg }◻\mathrm{\neg }$, we have that $\mathrm{\neg }◻\mathrm{\neg }\mathrm{\neg }\phi \in \mathrm{\Gamma }$. Since ${⊢}_{\mathrm{\Sigma }}\mathrm{\neg }◻\mathrm{\neg }\mathrm{\neg }\phi \leftrightarrow \mathrm{\neg }◻\phi$, we have $\mathrm{\neg }◻\phi \in \mathrm{\Gamma }$ and $◻\phi \notin \mathrm{\Gamma }$, which completes the reductio.

($\Leftarrow$) Suppose $\{\phi :◻\phi \in \mathrm{\Gamma }\}\subseteq \mathrm{\Delta }$. We argue for the contrapositive: if $◊\phi \notin \mathrm{\Gamma }$, then $\phi \notin \mathrm{\Delta }$. Suppose that $◊\phi \notin \mathrm{\Gamma }$. Since $◊$ is $\mathrm{\neg }◻\mathrm{\neg }$, we have that $\mathrm{\neg }◻\mathrm{\neg }\phi \notin \mathrm{\Gamma }$. By maximal $\mathrm{\Sigma }$-consistency of $\mathrm{\Gamma }$, $◻\mathrm{\neg }\phi \in \mathrm{\Gamma }$, which, by assumption, requires $\mathrm{\neg }\phi \in \mathrm{\Delta }$. It follows that $\phi \notin \mathrm{\Delta }$.

Proof. We distinguish two directions:

($\Rightarrow$) Consider the set of modal formulas $$\{\phi \}\cup \{\psi :◻\psi \in \mathrm{\Gamma }\}$$ Notice that if $\mathrm{\Delta }$ is a maximal $\mathrm{\Sigma }$-consistent, which includes that union as a subset, then $\mathrm{\Gamma }R\mathrm{\Delta }$, and we would be done.

We now argue that the set given above is $\mathrm{\Sigma }$-consistent.

Suppose not. Then there is a conjunction ${\psi }_1\wedge \cdots \wedge {\psi }_n$ of modal formulas with $◻{\psi }_1,\dots ,◻{\psi }_n\in \mathrm{\Gamma }$ such that $${⊢}_{\mathrm{\Sigma }}\phi \wedge ({\psi }_1\wedge \cdots \wedge {\psi }_n)\to \mathrm{\perp }$$ Thus: $${⊢}_{\mathrm{\Sigma }}({\psi }_1\wedge \cdots \wedge {\psi }_n)\to \mathrm{\neg }\phi$$ Since $\mathrm{\Sigma }$ is a normal modal system, we have: $${⊢}_{\mathrm{\Sigma }}◻{\psi }_1\wedge \cdots \wedge ◻{\psi }_n\to ◻\mathrm{\neg }\phi$$ Since $\mathrm{\Gamma }$ is maximal $\mathrm{\Sigma }$-consistent, it contains every theorem of $\mathrm{\Sigma }$. Therefore: $$(◻{\psi }_1\wedge \cdots \wedge ◻{\psi }_n)\to ◻\mathrm{\neg }\phi \in \mathrm{\Gamma }$$ Because $◻{\psi }_1\dots ◻{\psi }_n\in \mathrm{\Gamma }$, by lemma 5.1, we infer: $$(◻{\psi }_1\wedge \cdots \wedge ◻{\psi }_n)\in \mathrm{\Gamma }$$ $$◻\mathrm{\neg }\phi \in \mathrm{\Gamma }$$ But since $◊$ abbreviates $\mathrm{\neg }◻\mathrm{\neg }$, $◻\mathrm{\neg }\phi$ is equivalent to $\mathrm{\neg }◊\phi$, and given the $\mathrm{\Sigma }$-consistency of $\mathrm{\Gamma }$, we have thereby contradicted the assumption that $$◊\phi \in \mathrm{\Gamma }.$$ We conclude that the set $$\{\phi \}\cup \{\psi :◻\psi \in \mathrm{\Gamma }\}$$ is $\mathrm{\Sigma }$-consistent and can be extended to a maximal $\mathrm{\Sigma }$-consistent set $\mathrm{\Delta }$. It follows that $\mathrm{\Gamma }R\mathrm{\Delta }$ and $\phi \in \mathrm{\Delta }$.

($\Leftarrow$) This direction is trivial once we unpack the definition of $\mathrm{\Gamma }R\mathrm{\Delta }$.

Proof. We argue by contraposition. Suppose a modal formula $\phi$ is not a theorem of $K$. Then its negation $\mathrm{\neg }\phi$ will be $K$-consistent. That means that we may use Lindenbaum’s lemma to extend $\{\mathrm{\neg }\phi \}$ to a maximal $K$-consistent set $\mathrm{\Gamma }$. Now, note that $\mathrm{\Gamma }$ is one of the worlds of the canonical model for $K$, $(W_K,R_K,V_K)$, and, by the Truth Lemma, we know that $\mathrm{\neg }\phi$ will be true at $\mathrm{\Gamma }$ in the canonical model for $K$. Therefore, $\phi$ fails at a world in the canonical model for $K$. We conclude that $\phi$ is not valid in every frame.

Proof. We know that if $\phi$ is not a theorem of $KT$, then $\phi$ is not valid in the canonical frame for $KT$.

We proceed to verify that the canonical frame for $KT$ is reflexive:

• for all $\mathrm{\Gamma }\in W_{KT}$, $\mathrm{\Gamma }{R}_{KT}\mathrm{\Gamma }$.

Given how we defined $R_{KT}$, this is tantamount to the claim:

• if $\phi \in \mathrm{\Gamma }$, then $◊\phi \in \mathrm{\Gamma }$.

But since ${⊢}_{KT}\phi \to ◊\phi$, it follows that $\phi \to ◊\phi \in \mathrm{\Gamma }$ and since $\mathrm{\Gamma }$ is closed under $KT$-derivability, if $\mathrm{\Gamma }⊢◊\phi$, then $◊\phi \in \mathrm{\Gamma }$. So, if $\phi \in \mathrm{\Gamma }$, then $\mathrm{\Gamma }⊢◊\phi$ and $◊\phi \in \mathrm{\Gamma }$.

Proof. We unpack the argument for each axiom.

• $D$ / $R_{\mathrm{\Sigma }}$ is serial on $W_{\mathrm{\Sigma }}$

  Suppose $\mathrm{\Sigma }$ proves every substitution instance of the formula $◻p\to ◊p$. We proceed to verify that the canonical frame for $\mathrm{\Sigma }$ is serial:

  • for all $\mathrm{\Gamma }\in W_{\mathrm{\Sigma }}$ there is some $\mathrm{\Delta }\in W_{\mathrm{\Sigma }}$ such that $\mathrm{\Gamma }{R}_{\mathrm{\Sigma }}\mathrm{\Delta }$.

  This is tantamount to the claim:

  • $\{\phi :◻\phi \in \mathrm{\Gamma }\}\subseteq \mathrm{\Delta }$ for some $\mathrm{\Delta }\in W_{\mathrm{\Sigma }}$.

  It will suffice to prove that $\{\phi :◻\phi \in \mathrm{\Gamma }\}$ is $\mathrm{\Sigma }$-consistent.

  Suppose not. Then there is a conjunction ${\phi }_1\wedge \cdots \wedge {\phi }_n$ of modal formulas with $◻{\phi }_1,\dots ,◻{\phi }_n\in \mathrm{\Gamma }$ such that $${⊢}_{\mathrm{\Sigma }}({\phi }_1\wedge \cdots \wedge \cdots \wedge {\phi }_n)\to \mathrm{\perp }$$ Since $\mathrm{\Sigma }$ is a normal modal system, we have: $${⊢}_{\mathrm{\Sigma }}◻({\phi }_1\wedge \cdots \wedge ◻{\phi }_n)\to ◻\mathrm{\perp }$$ Since $\mathrm{\Gamma }$ is maximal $\mathrm{\Sigma }$-consistent, it contains every theorem of $\mathrm{\Sigma }$. Therefore: $$(◻{\phi }_1\wedge \cdots \wedge ◻{\phi }_n)\to ◻\mathrm{\perp }\in \mathrm{\Gamma }$$ Because $◻{\phi }_1\dots ◻{\phi }_n\in \mathrm{\Gamma }$, by lemma 5.1, we infer: $$(◻{\phi }_1\wedge \cdots \wedge ◻{\phi }_n)\in \mathrm{\Gamma }$$ $$◻\mathrm{\perp }\in \mathrm{\Gamma }$$ But since ${⊢}_{\mathrm{\Sigma }}◻\mathrm{\perp }\to \diamond \mathrm{\perp }$, $$◊\mathrm{\perp }\in \mathrm{\Gamma }.$$ Unfortunately, since ${⊢}_{\mathrm{\Sigma }}◻\mathrm{\neg }\mathrm{\perp }$, $$\mathrm{\neg }◊\mathrm{\perp }\in \mathrm{\Gamma },$$ which would make $\mathrm{\Gamma }$ $\mathrm{\Sigma }$-inconsistent. We conclude that the original set is $\mathrm{\Sigma }$-consistent and can be extended to a maximal $\mathrm{\Sigma }$-consistent set.

• $B$ / $R_{\mathrm{\Sigma }}$ is symmetric on $W_{\mathrm{\Sigma }}$

  Suppose $\mathrm{\Sigma }$ proves every substitution instance of the formula $p\to ◻◊p$. We proceed to verify that the canonical frame for $\mathrm{\Sigma }$ is symmetric:

  • for all $\mathrm{\Gamma },\mathrm{\Delta }\in W_{\mathrm{\Sigma }}$, if $\mathrm{\Gamma }{R}_{\mathrm{\Sigma }}\mathrm{\Delta }$, then $\mathrm{\Delta }{R}_{\mathrm{\Sigma }}\mathrm{\Gamma }$.

  This is tantamount to the claim:

  • if $\{\phi :◻\phi \in \mathrm{\Gamma }\}\subseteq \mathrm{\Delta }$, then $\{◊\phi :\phi \in \mathrm{\Gamma }\}\subseteq \mathrm{\Delta }$.

  To prove that conditional, assume the antecedent for arbitrary $\mathrm{\Gamma },\mathrm{\Delta }$: $\{\phi :◻\phi \in \mathrm{\Gamma }\}\subseteq \mathrm{\Delta }$. We want to establish the consequent: if $\phi \in \mathrm{\Gamma }$, then $◊\phi \in \mathrm{\Delta }$. Let $\phi \in \mathrm{\Gamma }$. Since $\mathrm{\Gamma }{⊢}_{\mathrm{\Sigma }}\phi \to ◻◊\phi$, we find that $◻◊\phi \in \mathrm{\Gamma }$. So, since $\mathrm{\Gamma }{R}_{\mathrm{\Sigma }}\mathrm{\Delta }$, it follows that $◊\phi \in \mathrm{\Delta }$ as desired.

• $4$ / $R_{\mathrm{\Sigma }}$ is transitive on $W_{\mathrm{\Sigma }}$

  Suppose $\mathrm{\Sigma }$ proves every substitution instance of the formula $◻p\to ◻◻p$. We proceed to verify that the canonical frame for $\mathrm{\Sigma }$ is euclidean:

  • for all $\mathrm{\Gamma },\mathrm{\Delta },\mathrm{\Theta }\in W_{\mathrm{\Sigma }}$, $\mathrm{\Gamma }{R}_{\mathrm{\Sigma }}\mathrm{\Delta }$ and $\mathrm{\Delta }{R}_{\mathrm{\Sigma }}\mathrm{\Theta }$, then $\mathrm{\Gamma }{R}_{\mathrm{\Sigma }}\mathrm{\Theta }$.

  This is tantamount to the claim:

  • if $\{\phi :◻\phi \in \mathrm{\Gamma }\}\subseteq \mathrm{\Delta }$ and $\{\phi :◻\phi \in \mathrm{\Delta }\}\subseteq \mathrm{\Theta }$, then $\{\phi :◻\phi \in \mathrm{\Gamma }\}\subseteq \mathrm{\Delta }$.

  To prove that conditional, assume the antecedent for arbitrary $\mathrm{\Gamma },\mathrm{\Delta },\mathrm{\Theta }$: $\{\phi :◻\phi \in \mathrm{\Gamma }\}\subseteq \mathrm{\Delta }$ and $\{\phi :◻\phi \in \mathrm{\Delta }\}\subseteq \mathrm{\Theta }$. We want to establish the consequent: if $◻\phi \in \mathrm{\Gamma }$, then $\phi \in \mathrm{\Theta }$.

  If $◻\phi \in \mathrm{\Gamma }$, then since ${⊢}_{\mathrm{\Sigma }}◻\phi \to ◻◻\phi$ and $◻\phi \to ◻◻\phi \in \mathrm{\Gamma }$, it follows that $◻◻\phi \in \mathrm{\Gamma }$. Since $\mathrm{\Gamma }{R}_{\mathrm{\Sigma }}\mathrm{\Delta }$, it follows that $◻\phi \in \mathrm{\Delta }$, and since $\mathrm{\Delta }{R}_{\mathrm{\Sigma }}\mathrm{\Theta }$, we conclude that $\phi \in \mathrm{\Theta }$ as desired.

• $5$ / $R_{\mathrm{\Sigma }}$ is euclidean on $W_{\mathrm{\Sigma }}$

  Suppose $\mathrm{\Sigma }$ proves every substitution instance of the formula $◊p\to ◻◊p$. We proceed to verify that the canonical frame for $\mathrm{\Sigma }$ is euclidean:

  • for all $\mathrm{\Gamma },\mathrm{\Delta },\mathrm{\Theta }\in W_{\mathrm{\Sigma }}$, $\mathrm{\Gamma }{R}_{\mathrm{\Sigma }}\mathrm{\Delta }$ and $\mathrm{\Gamma }{R}_{\mathrm{\Sigma }}\mathrm{\Theta }$, then $\mathrm{\Delta }{R}_{\mathrm{\Sigma }}\mathrm{\Theta }$.

  This is tantamount to the claim:

  • if $\{\phi :◻\phi \in \mathrm{\Gamma }\}\subseteq \mathrm{\Delta }$ and $\{◊\phi :\phi \in \mathrm{\Theta }\}\subseteq \mathrm{\Gamma }$, then $\{◊\phi :\phi \in \mathrm{\Theta }\}\subseteq \mathrm{\Delta }$.

  To prove that conditional, assume the antecedent for arbitrary $\mathrm{\Gamma },\mathrm{\Delta },\mathrm{\Theta }$: $\{\phi :◻\phi \in \mathrm{\Gamma }\}\subseteq \mathrm{\Delta }$ and $\{◊\phi :\phi \in \mathrm{\Theta }\}\subseteq \mathrm{\Gamma }$. We want to establish the consequent: if $\phi \in \mathrm{\Theta }$, then $◊\phi \in \mathrm{\Delta }$. Let $\phi \in \mathrm{\Theta }$. Since $\mathrm{\Gamma }{R}_{\mathrm{\Sigma }}\mathrm{\Theta }$, $◊\phi \in \mathrm{\Gamma }$. Since $\mathrm{\Gamma }{⊢}_{\mathrm{\Sigma }}◊\phi \to ◻◊\phi$, we find that $◻◊\phi \in \mathrm{\Gamma }$. So, since $\mathrm{\Gamma }{R}_{\mathrm{\Sigma }}\mathrm{\Delta }$, it follows that $◊\phi \in \mathrm{\Delta }$ as desired.