✦ScienexySCIENCE KNOWLEDGE LIBRARY
reference · SCI-MAT-012-020

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

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.

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