4.2 Consistency and completeness of theories

Consistency and completeness are crucial concepts in model theory, shaping our understanding of formal systems. These properties determine whether theories have models and if they can prove all true statements, respectively. They're fundamental to exploring the relationship between syntax and semantics in logical systems.

The Löwenheim-Skolem theorem and compactness theorem are key results in this area. They reveal surprising facts about model existence and size, influencing how we approach consistency proofs and model construction. Understanding these concepts is essential for grasping the power and limitations of formal systems in mathematics and logic.

Consistency and Completeness in Model Theory

Defining Consistency and Completeness

Top images from around the web for Defining Consistency and Completeness

• 

  Homogenizable structures and model completeness | SpringerLink View original

  Is this image relevant?

• 

  Homogenizable structures and model completeness | SpringerLink View original

  Is this image relevant?

1 of 1

Top images from around the web for Defining Consistency and Completeness

• 

  Homogenizable structures and model completeness | SpringerLink View original

  Is this image relevant?

• 

  Homogenizable structures and model completeness | SpringerLink View original

  Is this image relevant?

1 of 1

• Consistency in model theory denotes a theory with at least one model satisfying all its axioms
• Completeness encompasses two distinct concepts
  • Semantic completeness occurs when every sentence or its negation proves provable in the theory's language
  • Syntactic completeness arises when every sentence true in all models proves provable within the theory
• Inconsistent theories prove both a statement and its negation, leading to contradictions
• Consistent and complete theories determine unique structures up to isomorphism
• Löwenheim-Skolem theorem demonstrates consistent theories in countable languages always have countable models
• Compactness theorem states a set of sentences has a model if and only if every finite subset has a model

Key Theorems and Relationships

• Löwenheim-Skolem theorem highlights interplay between syntax and semantics in model theory
  • Example: Theory of dense linear orders has both countable and uncountable models
• Compactness theorem proves fundamental in establishing consistency of infinite theories
  • Application: Proving existence of non-standard models of arithmetic
• Relationship between consistency and completeness shapes model-theoretic investigations
  • Example: Peano Arithmetic consistent but incomplete due to Gödel's Incompleteness Theorem

Model Construction for Consistency

Construction Techniques

• Consistency proofs often involve constructing explicit models satisfying all theory axioms
• Method of diagrams builds larger models using elementary diagram of a structure
  • Example: Constructing algebraically closed fields from given fields
• Henkin's method adapts completeness proofs to demonstrate consistency through term model construction
• Relative consistency proofs show consistency of one theory by assuming consistency of another, often simpler theory
  • Example: Consistency of non-Euclidean geometries relative to Euclidean geometry

Advanced Methods

• Forcing in set theory provides sophisticated method for consistency proofs, particularly independence results
  • Application: Proving independence of Continuum Hypothesis from ZFC
• Model-theoretic techniques like ultraproducts and reduced products construct models and prove consistency
  • Example: Using ultraproducts to construct non-standard models of arithmetic
• Compactness theorem proves consistency for theories with infinite models by showing every finite subset of axioms has a model
  • Application: Proving existence of infinitely large cardinal numbers in set theory

Completeness Through Provability

Fundamental Concepts

• Completeness theorem for first-order logic equates logical validity with provability in formal systems
• Completeness proofs typically show that non-provable formulas have models where they are false
• Henkin construction extends consistent sentence sets to maximally consistent sets systematically
  • Example: Constructing models for consistent sets of sentences in propositional logic
• Henkin theories contain witnesses for all existential statements, crucial in completeness proofs
  • Application: Proving completeness of first-order logic

Techniques and Limitations

• Lindenbaum lemma extends any consistent sentence set to a maximally consistent set
  • Used in completeness proofs for various logical systems (modal logic, intuitionistic logic)
• Relationship between semantic consequence and syntactic derivability forms core of completeness proofs
  • Example: Proving soundness and completeness of natural deduction systems
• Completeness may not hold for logics beyond first-order, such as second-order or infinitary logics
  • Limitation: Second-order logic lacks a complete proof system

Gödel's Incompleteness and Model Theory

First and Second Incompleteness Theorems

• First Incompleteness Theorem states consistent formal systems with elementary arithmetic have unprovable statements
  • Example: Gödel sentence in Peano Arithmetic, true but unprovable within the system
• Second Incompleteness Theorem shows such formal systems cannot prove their own consistency
  • Implication: No consistent axiomatization of arithmetic can prove its own consistency
• These theorems reveal inherent limitations of axiomatic method in mathematics and logic
  • Impact: Shifted focus from finding complete axiomatizations to studying models and independence results

Model-Theoretic Implications

• Incompleteness theorems lead to existence of non-standard models in arithmetic and set theory
  • Example: Non-standard models of Peano Arithmetic with elements greater than all standard natural numbers
• ω-consistency, introduced by Gödel, proves crucial in understanding formal system limitations
  • Application: Strengthening results in proof theory and model theory
• Incompleteness theorems highlight distinction between truth and provability in formal systems
  • Consequence: Emergence of new areas in logic, such as proof theory and computability theory