Session 1 - Solutions to Exercises

Exercise 1

Exercise: Prove that classical semantic consequence $⊢$ is reflexive, transitive, and monotonic.

Solution: Let $\Gamma ,\Delta \subseteq \mathcal{L}$ be arbitrary sets of sentences, and let $w$ represent an arbitrary possible world.

• $⊢$ is Reflexive: Let $\gamma$ be an arbitrary sentence in $\Gamma$. Consider any world $w$ such that $w\models \Gamma$ (meaning $w$ satisfies every sentence in $\Gamma$). Since $\gamma \in \Gamma$, it trivially follows that $w\models \gamma$. Because $w$ was an arbitrary world satisfying the premises, we conclude $\Gamma ⊢\gamma$.
• $⊢$ is Transitive: Assume $\Gamma ⊢\delta$ for all $\delta \in \Delta$, and assume $\Delta ⊢\varphi$. Consider an arbitrary world $w$ such that $w\models \Gamma$. By our first assumption, $w\models \delta$ for every $\delta \in \Delta$. This is logically equivalent to saying $w\models \Delta$. Because $w\models \Delta$, our second assumption ($\Delta ⊢\varphi$) guarantees that $w\models \varphi$. Since $w$ was an arbitrary world satisfying $\Gamma$, we conclude $\Gamma ⊢\varphi$.
• $⊢$ is Monotonic: Assume $\Gamma \subseteq \Delta$ and $\Gamma ⊢\varphi$. Consider an arbitrary world $w$ such that $w\models \Delta$. Because $\Gamma \subseteq \Delta$, any world that satisfies all of $\Delta$ must also satisfy all of $\Gamma$; therefore, $w\models \Gamma$. Since $\Gamma ⊢\varphi$, it follows that $w\models \varphi$. Since $w$ was an arbitrary world satisfying $\Delta$, we conclude $\Delta ⊢\varphi$.

Exercise 2

Exercise: Prove that the classical consequence operator $Cn$ satisfies reflexivity, transitivity, monotonicity, and idempotence.

Solution: Reflexivity, transitivity, and monotonicity for $Cn$ follow directly from the corresponding properties of the semantic consequence relation $⊢$ proved in Exercise 1, simply by translating them through the definition $Cn(\Gamma ):=\{\varphi \in \mathcal{L}:\Gamma ⊢\varphi \}$. We will explicitly prove the fourth property: Idempotence.

To prove set equality, we must prove mutual inclusion.

$(\subseteq )$ Prove $Cn(\Gamma )\subseteq Cn(Cn(\Gamma ))$: This direction follows immediately from the reflexivity of $Cn$. Reflexivity states that for any set $X$, $X\subseteq Cn(X)$. By substituting $Cn(\Gamma )$ for $X$, we immediately get $Cn(\Gamma )\subseteq Cn(Cn(\Gamma ))$.

$(\supseteq )$ Prove $Cn(Cn(\Gamma ))\subseteq Cn(\Gamma )$: Let $\varphi$ be an arbitrary sentence such that $\varphi \in Cn(Cn(\Gamma ))$. By the definition of the consequence operator, this means $Cn(\Gamma )⊢\varphi$. Furthermore, by definition, for every sentence $\psi \in Cn(\Gamma )$, it is true that $\Gamma ⊢\psi$. We can now apply the transitivity of $⊢$: since $\Gamma ⊢\psi$ for all premises $\psi \in Cn(\Gamma )$, and $Cn(\Gamma )⊢\varphi$, it follows that $\Gamma ⊢\varphi$. Therefore, $\varphi \in Cn(\Gamma )$. Since $\varphi$ was arbitrary, $Cn(Cn(\Gamma ))\subseteq Cn(\Gamma )$.

Mutual inclusion establishes the identity $Cn(\Gamma )=Cn(Cn(\Gamma ))$. eproof

Exercise 3

Exercise: The properties of consequence relations $▹$ and consequence operators $C$ are not all logically independent. Explore their logical interactions by proving the following claims:

1. Reflexivity + Transitivity $⟹$ Monotonicity: Prove that if a consequence relation $▹$ (or operator $C$) is reflexive and transitive, it must necessarily be monotonic.
2. Monotonicity + Idempotence $⟹$ Transitivity: For a consequence operator $C$, prove that if $C$ is monotonic and idempotent, then $C$ is transitive.
3. Reflexivity + Transitivity $⟹$ Idempotence: For a consequence operator $C$, prove that if $C$ is reflexive and transitive, then $C$ is idempotent.
4. Reflexivity + Monotonicity $\cancel{⟹}$ Transitivity: Provide a counterexample (e.g., a restricted consequence operator on $\mathcal{L}$) that is reflexive and monotonic, but fails to be transitive.

(N.b., 4 implies that Reflexivity + Monotonicity $\cancel{⟹}$ Idempotence.)

Solution:

1. Reflexivity + Transitivity $⟹$ Monotonicity. Suppose $▹$ is reflexive and transitive, and suppose $\Gamma \subseteq \Delta$ and $\Gamma ▹\varphi$. By reflexivity, $\Delta ▹\delta$ for all $\delta \in \Delta$. Thus, in particular, $\Delta ▹\gamma$ for all $\gamma \in \Gamma$, since $\Gamma \subseteq \Delta$. Since $\Gamma ▹\varphi$, the transitivity of $▹$ yields $\Delta ▹\varphi$. Thus, $▹$ is monotonic.

The proof is analogous for any consequence operator $C$. Suppose $\Gamma \subseteq \Delta$. By reflexivity, $\Delta \subseteq C(\Delta )$, and hence $\Gamma \subseteq C(\Delta )$. By the transitivity of $C$, since $\Gamma \subseteq C(\Delta )$, it follows that $C(\Gamma )\subseteq C(\Delta )$. Therefore, $C$ is monotonic.

2. Monotonicity + Idempotence $⟹$ Transitivity. Suppose $C$ is monotonic and idempotent. Suppose also that $\Gamma \subseteq C(\Delta )$. By the monotonicity of $C$, $C(\Gamma )\subseteq C(C(\Delta ))$. By idempotence, $C(C(\Delta ))=C(\Delta )$, which yields $C(\Gamma )\subseteq C(\Delta )$. Therefore, $C$ is transitive.

3. Reflexivity + Transitivity $⟹$ Idempotence. Suppose $C$ is reflexive and transitive. By reflexivity, $C(\Gamma )\subseteq C(C(\Gamma ))$. We now need to prove that $C(C(\Gamma ))\subseteq C(\Gamma )$. By reflexivity, $C(\Gamma )\subseteq C(\Gamma )$ holds trivially. By transitivity, if $C(\Gamma )\subseteq C(\Gamma )$, then $C(C(\Gamma ))\subseteq C(\Gamma )$. Therefore, $C(\Gamma )=C(C(\Gamma ))$.

Reflexivity + Monotonicity $⟹$ (Transitivity $⟺$ Idempotence)

As a result of (2) and (3), it follows immediately that, given $C$ is reflexive and monotonic, $C$ is idempotent iff $C$ is transtive

4. Reflexivity + Monotonicity $\cancel{⟹}$ Transitivity. Let $\mathcal{L}$ be a standard propositional language. Define a consequence operator $C$ that takes a set of sentences $\Gamma$ and adds the negation of each sentence in $\Gamma$:

$C(\Gamma )=\Gamma \cup \{\neg \varphi :\varphi \in \Gamma \}$

Reflexivity holds trivially since $\Gamma \subseteq C(\Gamma )$. Monotonicity holds because if $\Gamma \subseteq \Delta$, then $\{\neg \varphi :\varphi \in \Gamma \}\subseteq \{\neg \varphi :\varphi \in \Delta \}$, which ensures $C(\Gamma )\subseteq C(\Delta )$.

However, $C$ fails Transitivity. Let $\Gamma =\{p\}$. Then $C(\Gamma )=\{p,\neg p\}$. If we apply the operator a second time, we obtain $C(C(\Gamma ))=\{p,\neg p,\neg \neg p\}$. Since $\neg \neg p\notin C(\Gamma )$, we have $C(C(\Gamma ))⊈C(\Gamma )$. Thus, $C$ is not idempotent. Given that Reflexivity + Transitivity $⟹$ Idempotence (as proven in step 3), the failure of idempotence logically guarantees the failure of transitivity. To verify this directly against the definition of transitivity: let $X=\{p,\neg p\}$ and $Y=\{p\}$. We have $X\subseteq C(Y)$, but $C(X)⊈C(Y)$.

Reflexivity + Monotonicity $\cancel{⟹}$ Idempotence

This is directly shown in the example above, but it also follows from (3).

Exercise 4

Exercise:

1. Reflexivity + Cut + Idempotence $\cancel{⟹}$ Monotonicity: Provide a counterexample demonstrating that a consequence relation $▹$ (or operator $C$) can be reflexive, cumulatively transitive, and idempotent, yet fail to be monotonic.
2. Reflexivity + Monotonicity $⟹$ (Transitivity $⟺$ Cut): Prove this logical equivalence.
3. Reflexivity + Monotonicity $⟹$ (Idempotence $⟺$ Cut): Prove this logical equivalence.

Solution:

1. Reflexivity + Cut + Idempotence $\cancel{⟹}$ Monotonicity: Let $\mathcal{L}$ be a standard propositional language. Define a consequence operator $C$ such that:

• If $\Gamma$ is consistent, $C(\Gamma )=Cn(\Gamma )$ (where $Cn$ is classical consequence).
• If $\Gamma$ is inconsistent, $C(\Gamma )=\Gamma$.

Reflexivity: $C$ is reflexive because $Cn$ is reflexive (so $\Gamma \subseteq Cn(\Gamma )$) and trivially $\Gamma \subseteq \Gamma$.

Idempotence: If $\Gamma$ is consistent, $Cn(\Gamma )$ is consistent, so $C(C(\Gamma ))=C(Cn(\Gamma ))=Cn(Cn(\Gamma ))=Cn(\Gamma )=C(\Gamma )$. If $\Gamma$ is inconsistent, $C(C(\Gamma ))=C(\Gamma )=\Gamma$. Thus, $C$ is idempotent.

Cut: Suppose $\Gamma \subseteq \Delta \subseteq C(\Gamma )$. If $\Gamma$ is consistent, then $C(\Gamma )=Cn(\Gamma )$. Since $\Delta \subseteq Cn(\Gamma )$, $\Delta$ must also be consistent. Therefore, $C(\Delta )=Cn(\Delta )$. Since $Cn$ satisfies Cut, $Cn(\Delta )\subseteq Cn(\Gamma )$, meaning $C(\Delta )\subseteq C(\Gamma )$. If $\Gamma$ is inconsistent, $C(\Gamma )=\Gamma$. The assumption $\Gamma \subseteq \Delta \subseteq \Gamma$ implies $\Gamma =\Delta$. Thus $C(\Delta )=C(\Gamma )$, which satisfies $C(\Delta )\subseteq C(\Gamma )$.

Failure of Monotonicity: Let $\Gamma =\{p\}$ and $\Delta =\{p,\neg p\}$. $\Gamma$ is consistent, so $C(\Gamma )=Cn(\{p\})$, which contains $p\vee q$. $\Delta$ is inconsistent, so $C(\Delta )=\Delta =\{p,\neg p\}$. We have $\Gamma \subseteq \Delta$, but $p\vee q\in C(\Gamma )$ and $p\vee q\notin C(\Delta )$. Thus, $C(\Gamma )⊈C(\Delta )$, meaning $C$ is not monotonic.

2. Reflexivity + Monotonicity $⟹$ (Transitivity $⟺$ Cut). Suppose that $C$ satisfies reflexivity and monotonicity.

(2.a) Suppose that $C$ satisfies Cut, and also that $\Delta \subseteq C(\Gamma )$. We need to prove that $C(\Delta )\subseteq C(\Gamma )$. By reflexivity, $\Gamma \subseteq C(\Gamma )$. Since we assumed $\Delta \subseteq C(\Gamma )$, it follows that their union is also a subset of $C(\Gamma )$, yielding $\Gamma \subseteq \Gamma \cup \Delta \subseteq C(\Gamma )$. By Cut, this implies $C(\Gamma \cup \Delta )\subseteq C(\Gamma )$. Since $\Delta \subseteq \Gamma \cup \Delta$, monotonicity guarantees that $C(\Delta )\subseteq C(\Gamma \cup \Delta )$. By transitivity of the subset relation, $C(\Delta )\subseteq C(\Gamma )$. Thus, $C$ is transitive.

(2.b) Suppose that $C$ satisfies transitivity, and also that $\Gamma \subseteq \Delta \subseteq C(\Gamma )$. We need to prove that $C(\Delta )\subseteq C(\Gamma )$. From our assumption, we have $\Delta \subseteq C(\Gamma )$. By the definition of transitivity, if $\Delta \subseteq C(\Gamma )$, then $C(\Delta )\subseteq C(\Gamma )$. Thus, $C$ satisfies Cut.

3. Reflexivity + Monotonicity $⟹$ (Idempotence $⟺$ Cut). Suppose that $C$ satisfies reflexivity and monotonicity.

(3.a) Suppose $C$ is idempotent, and let $\Gamma \subseteq \Delta \subseteq C(\Gamma )$. We must prove $C(\Delta )\subseteq C(\Gamma )$. From the assumption, $\Delta \subseteq C(\Gamma )$. By monotonicity, $C(\Delta )\subseteq C(C(\Gamma ))$. By idempotence, $C(C(\Gamma ))=C(\Gamma )$. Substituting this equality yields $C(\Delta )\subseteq C(\Gamma )$. Thus, $C$ satisfies Cut.

(3.b) Suppose $C$ satisfies Cut. We must prove $C(C(\Gamma ))=C(\Gamma )$. By reflexivity, $C(\Gamma )\subseteq C(C(\Gamma ))$. It remains to prove that $C(C(\Gamma ))\subseteq C(\Gamma )$. By reflexivity, we know $\Gamma \subseteq C(\Gamma )$. Let $\Delta =C(\Gamma )$. We therefore have $\Gamma \subseteq \Delta \subseteq C(\Gamma )$. Applying Cut yields $C(\Delta )\subseteq C(\Gamma )$. Substituting $C(\Gamma )$ back for $\Delta$, we obtain $C(C(\Gamma ))\subseteq C(\Gamma )$. Having established mutual inclusion, $C(C(\Gamma ))=C(\Gamma )$. Thus, $C$ is idempotent.

Exercise 5