Deduction Theorem Counterexample Relational Logic

Counterexample:

Γ = {}

φ = p(x)

ψ = ∀x p(x)

Now, applying Deduction Theorem, from prop. logic, substituting above Γ |= (φ ⇒ ψ) iff Γ ∪ {φ} |= ψ yields:

({} |= (p(x) ⇒ ∀x p(x)) ⇔ ({p(x)} |= ∀x p(x))

The LHS of this equivalence is the logical entailment {} |= (p(x) ⇒ ∀x p(x). For this entailment to be true we need the logical sentence p(x) ⇒ ∀x p(x) to be valid in relational logic, but we have shown that p(x) ⇒ ∀x p(x) is contingent. Therefore the entailment is false.

On RHS, we have the entailment {p(x)} |= ∀x p(x). Consider the following short proof:

1    p(x)           Premise
2   ∀x p(x)      UG

Thus {p(x)} |- ∀x p(x) and, by soundness, {p(x)} |= ∀x p(x). So the right-hand entailment is true.

Since assuming the Deduction Theorem for prop. Logic holds for relational logic leads to the contradictory equivalence F ⇔ T, our assumption must be false; i.e. DT does not hold.

Prop. Logic Metatheorems

Deduction Theorem:
Δ |- (φ ⇒ ψ) if and only if
Δ∪{φ} |- ψ.

Substitution Theorem:
Δ |- (φ ⇔ ψ) and Δ |- χ, then it
is the case that Δ |- χφ←ψ.

ChainingTheorem:
If Δ|-(φ⇒ψ)andΔ|-(ψ⇒χ), then Δ |- (φ ⇒ χ).

Prop Logic Wrap-up Notes

There is a close connection between provability and logical entailment. In fact, they are equivalent. A set of sentences Δ logically entails a sentence φ if and only if φ is provable from Δ.

Soundness Theorem: If φ is provable from Δ, then Δ logically entails φ.

Completeness Theorem: If Δ logically entails φ, then φ is provable from Δ.

The concept of provability is important because it suggests how we can automate the determination of logical entailment. Starting from a set of premises Δ, we enumerate conclusions from this set. If a sentence φ appears, then it is provable from Δ and is, therefore, a logical consequence. If the negation of φ appears, then ¬φ is a logical consequence of Δ and φ is not logically entailed (unless Δ is inconsistent). Note that it is possible that neither φ nor ¬φ will appear.

Standard Axiom Schemata for Propositional Logic

Standard Axiom Schemata for Propositional Logic

(II): φ ⇒ (ψ ⇒ φ)

(ID): (φ ⇒ (ψ ⇒ χ)) ⇒ ((φ ⇒ ψ) ⇒ (φ ⇒ χ))

(CR): (¬φ ⇒ ψ) ⇒ ((¬φ ⇒ ¬ψ) ⇒ φ)

(EQ):

(φ ⇔ ψ) ⇒ (φ ⇒ ψ)

(φ ⇔ ψ) ⇒ (ψ ⇒ φ)

(φ ⇒ ψ) ⇒ ((ψ ⇒ φ) ⇒ (φ ⇔ ψ))

(OQ):

(φ ⇐ ψ) ⇔ (ψ ⇒ φ)

(φ ∨ ψ) ⇔ (¬φ ⇒ ψ)

(φ ∧ ψ) ⇔ ¬(¬φ ∨ ¬ψ)

(II), (ID), and (CR) form the Mendelson Axiom Schemata for Propositional Logic