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) [...]

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 [...]

Standard Axiom Schemata for Propositional Logic

Standard Axiom Schemata for Propositional Logic (II): φ ⇒ (ψ ⇒ φ) (ID): (φ ⇒ (ψ ⇒ χ)) ⇒ ((φ ⇒ ψ) ⇒ (φ ⇒ χ)) (CR): (¬φ ⇒ ψ) ⇒ ((¬φ ⇒ ¬ψ) ⇒ φ) (EQ): (φ ⇔ ψ) ⇒ (φ ⇒ ψ) (φ ⇔ ψ) ⇒ (ψ ⇒ φ) (φ ⇒ ψ) ⇒ [...]