Consistent Sets of Formulas
Consistent Sets of Formulas
Definition
We say that a set Γ of propositional formulas is consistent if there is no formula ϕ such that both Γ |- ϕ and Γ |- ¬ϕ.
If Γ is not consistent, we say it is inconsistent.
Theorem
A set Γ of formulas is consistent if and only if there is some formula ϕ such that Γ 0 ϕ.
Proof: We show that Γ is inconsistent iff Γ |- ϕ for all formulas ϕ. If Γ |- ϕ for all formulas ϕ, then in particular Γ |- P1 and Γ |- ¬P1, so Γ is inconsistent.
Now suppose that Γ is inconsistent. Let ψ be such that Γ |- ψ and Γ |- ¬ψ. Let ϕ be an arbitrary formula. In an early example, we have seen that {P, ¬P} |- Q. Replacing P with ψ and Q with ϕ in that derivation, we obtain a derivation {ψ, ¬ψ} |- ϕ. Thus, Γ |- ϕ.
Example
Γ = {¬(P → ¬P), (P → Q), (Q → ¬P)} is inconsistent.
Proof: We have Γ |- (P → ¬P) via the following derivation.
(1) (P → Q) (premiss)
(2) (Q → ¬P) (premiss)
(3) (P → ¬P) (HS on (1) and (2))
Also Γ |- ¬(P → ¬P) since ¬(P → ¬P) ∈ Γ . Thus Γ is inconsistent.
How do we find an example of a consistent set of formulas?
Satisfiable Sets of Formulas are Consistent
Theorem
Let Γ be a satisfiable set of propositional formulas. Then Γ is consistent.
Proof: Let Γ be a satisfiable set of formulas. Assume for a contradiction that Γ is inconsistent. So let ϕ be such that Γ |- ϕ and Γ |- ¬ϕ. By the Soundness Theorem, Γ |= ϕ and Γ |= ¬ϕ. Since Γ is satisfiable, there exists a truth assignment e such that e(γ) = T for all γ ∈ Γ. Then since Γ |= ϕ, e(ϕ) = T. But since Γ |= ¬ϕ, e(¬ϕ) = T so e(ϕ) = F, a contradiction. Hence, Γ is consistent.
We will see that the converse of this theorem is also true. That is, the consistent sets of formulas are exactly the satisfiable sets of formulas.
Question
Which of the following sets of formulas are consistent?
1. {P, ¬Q, R}
2. {¬P, ¬(Q → Q)}
3. {(P → Q), (P → ¬Q), P}
4. {(P → Q), (¬P → Q)}
Maximal Consistent Sets
Consistent Sets of Formulas
Theorem
Let Γ be a set of formulas, and let ϕ be a formula.
(1) If Γ is consistent and Γ |- ϕ, then Γ ∪ {ϕ} is consistent.
(2) If Γ 0 ϕ, then Γ ∪ {¬ϕ} is consistent.
Proof of (1): Suppose that Γ is consistent and Γ |- ϕ. Assume for a contradiction that Γ ∪ {ϕ} is inconsistent. Let ψ be arbitrary.
Since Γ ∪ {ϕ} is inconsistent, Γ ∪ {ϕ} |- ψ.
So by the Deduction Theorem, Γ |- (ϕ → ψ).
But since Γ |- ϕ, Γ |- ψ by MP.
As ψ was arbitrary, this shows that Γ is inconsistent, a contradiction.
Proof of (2): Suppose Γ 0 ϕ. Assume for a contradiction that Γ ∪ {¬ϕ} is inconsistent.
In particular, Γ ∪ {¬ϕ} |- ϕ.
By the Deduction Theorem, Γ |- (¬ϕ → ϕ).
We’ve also seen that |- ((¬ϕ → ϕ) → ϕ).
So by MP, Γ |- ϕ, a contradiction.
Maximal Consistent Sets of Formulas
Definition
Let Γ be a set of formulas. We say Γ is a maximal consistent set of formulas if Γ is consistent and if for every formula ϕ, either ϕ ∈ Γ or ¬ϕ ∈ Γ.
That is, a maximal consistent set of formulas is a largest possible set of consistent formulas in the sense that there is no formula not already in the set that could be added and maintain consistency.
Theorem
Let Γ be a consistent set of formulas. Then there exists a maximal consistent set of formulas Θ such that Γ ⊆ Θ.
Proof: To begin, note that we can generate a list ϕ1, ϕ2, ϕ3, ϕ4, . . . of all propositional formulas. (To see this, convince yourself that for each n, you can list all formulas of length at most n on the variables P1, . . . , Pn, so doing this in turn for each n generates such a list.)
Theorem
Let Γ be a consistent set of formulas. Then there exists a maximal consistent set of formulas Θ such that Γ ⊆ Θ.
Proof (continued): We now define, for each n, a set of formulas Θn as follows.
Let Θ0 = Γ
Let We claim that Θ is the desired set.
Certainly Γ = Θ0 ⊆ Θ.
If ϕ is a formula, ϕ = ϕn for some n, so either ϕ ∈ Θn ⊆ Θ (if Θn−1 |- ϕ), or ¬ϕ ∈ Θn ⊆ Θ (if Θn−1 0 ϕ). So it remains to check that Θ is consistent. We first show by induction on n that each Θn is consistent.
Indeed Θ0 = Γ, so it is consistent. Assume Θn−1 is consistent. If Θn−1 |- ϕn, then by (1) of the previous theorem, Θn−1 ∪ {ϕn} is consistent. But in this case Θn = Θn−1 ∪ {ϕn}, so it is consistent.
Theorem
Let Γ be a consistent set of formulas. Then there exists a maximal consistent set of formulas Θ such that Γ ⊆ Θ.
Proof (continued): If Θn−1 0 ϕn, then by (2) of the previous theorem, Θn−1 ∪ {¬ϕn} is consistent. We also have Θn = Θn−1 ∪ {¬ϕn}, so Θn is consistent. Thus, , where each Θn is consistent.
Note also that Θ0 ⊆ Θ1 ⊆ Θ2 ⊆ · · ·
Assume for a contradiction that Θ is inconsistent. So there is a formula ϕ such that Θ |- ϕ and Θ |- ¬ϕ. Let ψ1, . . . , ψk and γ1, . . . , γl be derivations of ϕ and ¬ϕ, respectively, from Θ. There are finitely many premisses among ψ1, . . . , ψk and γ1, . . . , γl
. So there exists some n such that all the premisses among ψ1, . . . , ψk and γ1, . . . , γl belong to Θn. But then Θn ` ϕ and Θn |- ¬ϕ, contradicting the consistency of Θn. Thus, Θ is consistent.