properties of consistency


Fix a (classical) propositional logicPlanetmathPlanetmath L. Recall that a set Δ of wff’s is said to be L-consistent, or consistent for short, if Δ⊬. In other words, can not be derived from axioms of L and elements of Δ via finite applications of modus ponensMathworldPlanetmath. There are other equivalentMathworldPlanetmathPlanetmathPlanetmathPlanetmathPlanetmath formulations of consistency:

  1. 1.

    Δ is consistent

  2. 2.

    Ded(Δ):={AΔA} is not the set of all wff’s

  3. 3.

    there is a formulaMathworldPlanetmathPlanetmath A such that Δ⊬A.

  4. 4.

    there are no formulas A such that ΔA and Δ¬A.

Proof.

We shall prove 1.2.3.4.1.

  1. 1.2.

    Since {AΔA}.

  2. 2.3.

    Any formula not in {AΔA} will do.

  3. 3.4.

    If ΔA and Δ¬A, then A,A,,B,B is a deductionMathworldPlanetmathPlanetmath of B from A and ¬A, but this means that ΔB for any wff B.

  4. 4.1.

    Since Δ¬, Δ⊬ as a result.

Below are some properties of consistency:

  1. 1.

    Δ{A} is consistent iff Δ⊬¬A.

  2. 2.

    Δ{¬A} is not consistent iff ΔA.

  3. 3.

    Any subset of a consistent set is consistent.

  4. 4.

    If Δ is consistent, so is Ded(Δ).

  5. 5.

    If Δ is consistent, then at least one of Δ{A} or Δ{¬A} is consistent for any wff A.

  6. 6.

    If there is a truth-valuation v such that v(A)=1 for all AΔ, then Δ is consistent.

  7. 7.

    If ⊬A, and Δ contains the schema based on A, then Δ is not consistent.

Remark. The converseMathworldPlanetmath of 6 is also true; it is essentially the compactness theorem for propositional logic (see here (http://planetmath.org/CompactnessTheoremForClassicalPropositionalLogic)).

Proof.

The first two are contrapositive of one another via the theorem A¬¬A, so we will just prove one of them.

  1. 2.

    Δ,¬A iff Δ¬¬A by the deduction theoremMathworldPlanetmath iff ΔA by the substitution theorem.

  2. 3.

    If Γ is not consistent, Γ. If ΓΔ, then Δ as well, so Δ is not consistent.

  3. 4.

    Since Δ is consistent, Ded(Δ). Now, if Ded(Δ), but by the remark below, Ded(Δ), a contradictionMathworldPlanetmathPlanetmath.

  4. 5.

    Suppose Δ is consistent and A any wff. If neither Δ{A} and Δ{¬A} are consistent, then Δ,A and Δ,¬A, or Δ¬A and Δ¬¬A, or Δ¬A and ΔA by the substitution theorem on A¬¬A, but this means Δ is not consistent, a contradiction.

  5. 6.

    If v(A)=1 for all AΔ, v(B)=1 for all B such that ΔB. Since v()=0, Δ is consistent.

  6. 7.

    Suppose v(A) for some valuation v. Let p1,,pm be the propositional variables in A such that v(pi)=0 and q1,,qn be the variables in A such that v(qj)=1. Let A be the instance of the schema A where each pi is replaced by and each qj replaced by (which is ¬). Then AΔ. Furthermore, v(A)=v(A)=0. Now, for any valuation u, since u()=0 and u()=1, we get u(A)=v(A)=0. In other words, u(¬A)=1 for all valuations u, so ¬A is valid, and hence a theorem of L by the completeness theorem. But this means that A, which implies that Δ.

Remark. The set Ded(Δ) is called the deductive closure of Δ. It is so called because it is deductively closed: ADed(Δ) iff Ded(Δ)A.

Proof.

If ADed(Δ), then ΔA, so certainly Ded(Δ)A, as Ded(Δ) is a supersetMathworldPlanetmath of Δ.

Before proving the converse, note first that if ΔB and ΔBA, ΔA by modus ponens. This implies that Ded(Δ) is closed underPlanetmathPlanetmath modus ponens: if B and BA are both in Ded(Δ), so is A.

Now, suppose Ded(Δ)A. We induct on the length of the deduction sequence of A. If n=1, then ADed(Δ) and we are done. Now, suppose the length of is n+1. If A is either a theorem or in Ded(Δ), we are done. Now, suppose A is the result of applying modus ponens to two earlier members, say Ai and Aj. Since A1,,Ai is a deduction of Ai from Ded(Δ), and it has length in, by the inductionMathworldPlanetmath step, AiDed(Δ). Similarly, AjDed(Δ). But this means that ADed(Δ) by the last paragraph. ∎

Title properties of consistency
Canonical name PropertiesOfConsistency
Date of creation 2013-03-22 19:35:07
Last modified on 2013-03-22 19:35:07
Owner CWoo (3771)
Last modified by CWoo (3771)
Numerical id 18
Author CWoo (3771)
Entry type Feature
Classification msc 03B45
Classification msc 03B10
Classification msc 03B05
Classification msc 03B99
Related topic FirstOrderTheories
Defines deductive closure
\@unrecurse