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.

Advertisement