Formal logic distinguishes between semantic consequence and syntactic derivability. Semantic consequence, written Γ ⊨ φ, means that every model satisfying the premises Γ also satisfies φ. Syntactic derivability, written Γ ⊢ φ, means that φ can be obtained from Γ through the inference rules of a formal proof system. A proof system is sound if every formula it derives is semantically entailed by its premises. It is complete if every semantic consequence can be formally derived within the system. In a sound and complete system, derivability and semantic consequence coincide. These properties are important when evaluating the reliability and expressive power of formal logical systems. Completeness of first-order logic should not be confused with Gödel's incompleteness theorems concerning sufficiently expressive, consistent, effectively axiomatized formal theories of arithmetic.
Soundness and Completeness: Basic Ideas
Soundness and completeness describe important relationships between formal proof systems and semantic truth: sound systems derive only valid conclusions, while complete systems can derive every conclusion that is semantically valid.
Soundness: if Γ ⊢ φ, then Γ ⊨ φ
Completeness: if Γ ⊨ φ, then Γ ⊢ φ
For a sound and complete system: Γ ⊢ φ if and only if Γ ⊨ φ
Explanation
Variables
Γ: a set of premises
φ: a logical formula
⊢: formal derivability
⊨: semantic consequence
Proof system: a formal collection of axioms and inference rules
Example or application
In a sound propositional proof system, if a formula is derived from a set of premises using permitted rules, that formula must be true in every interpretation satisfying those premises.
Definition
Soundness is the property that formal derivations preserve semantic validity, while completeness is the property that every semantically valid consequence is formally derivable in the proof system.
Purpose
To explain how formal proof rules relate to the meanings and truth conditions of logical statements.
Importance
Soundness ensures that a proof system does not establish semantically invalid conclusions, while completeness explains whether the system can derive all consequences recognized by its semantics.
Learning Objectives
Define soundness and completeness.
Distinguish formal derivability from semantic consequence.
Explain the soundness condition.
Explain the completeness condition.
Recognize why first-order logic completeness differs from Gödel's incompleteness theorems.
Key Concepts
Soundness
Completeness
Formal derivability
Semantic consequence
Proof system
Axioms
Inference rules
Working Principle
A proof system is evaluated by comparing what its rules can derive with what its semantics regards as valid. Soundness prevents incorrect derivations, while completeness ensures that valid semantic consequences are not missing from the formal system.
Process
Define the formal language and its semantics.
Specify the axioms and inference rules.
Determine which conclusions are formally derivable.
Check whether every derivation preserves semantic consequence.
Check whether every semantic consequence has a formal derivation.
Applications
Designing theorem-proving systems
Formal verification
Mathematical foundations
Programming language logic
Automated reasoning
Studying the limits of formal systems
Worked Example
Suppose a proof system derives q from the premises p and p → q. The semantic rule of modus ponens guarantees that every interpretation satisfying both premises also satisfies q. This illustrates soundness for that inference step. Completeness is a broader property: it asks whether every semantically valid consequence in the chosen logic can be derived using the system's rules.
Common Misconceptions
Soundness and completeness are not synonyms.
A sound system does not necessarily derive every semantically valid consequence unless it is also complete.
Completeness of classical first-order logic does not contradict Gödel's incompleteness theorems.
The meaning of soundness and completeness depends on the formal system and its semantics.
Practice Questions
Define soundness in formal logic.
What does completeness mean for a proof system?
Explain the difference between Γ ⊢ φ and Γ ⊨ φ.
Why is soundness important in automated theorem proving?
Why should first-order logic completeness not be confused with Gödel's incompleteness theorems?
Key Takeaway
Soundness guarantees that formal proofs preserve semantic truth, while completeness guarantees that all semantic consequences can be formally derived.
Prerequisites
Logical Validity and Logical Truth
Logical Consequence
Valid and Invalid Arguments
Mathematical Arguments
Reference
A Mathematical Introduction to Logic — Herbert B. Enderton
Mathematical Logic — Joseph R. Shoenfield
Gödel's Proof — Ernest Nagel and James R. Newman
Related Topics
Logical Consequence
Valid and Invalid Arguments
Logic and Mathematical Proof
Historical Development of Mathematical Logic
Sources and verification
Sources are shown as provided in the project data. Not every source has yet been independently verified. Please report errors or missing citations.
- Source verification pending; check an authoritative textbook, university, standards body, or peer-reviewed source.
Suggest a correction or source · More in Mathematical Logic & Set Theory