11.3 Complete theories and their properties

Complete theories are the backbone of model theory, defining systems where every statement is either provable or disprovable. They're crucial for understanding formal systems' limits and capabilities, connecting to broader concepts like categoricity and decidability.

Diving into complete theories reveals their rich properties, from homogeneity to saturation. This exploration leads us to stability theory, a powerful tool for classifying theories based on their models' behavior, with far-reaching applications in mathematics and logic.

Completeness of Theories

Defining Completeness

Top images from around the web for Defining Completeness

• 

  Gödel's completeness theorem - Wikipedia View original

  Is this image relevant?

• 

  Gödel's completeness theorem - Wikipedia View original

  Is this image relevant?

1 of 1

Top images from around the web for Defining Completeness

• 

  Gödel's completeness theorem - Wikipedia View original

  Is this image relevant?

• 

  Gödel's completeness theorem - Wikipedia View original

  Is this image relevant?

1 of 1

• Completeness in model theory describes a theory where every sentence or its negation proves from the axioms
• Complete theory means all sentences or their negations logically follow from the theory's axioms
• Theory of dense linear orders without endpoints exemplifies a complete theory
• Theory of algebraically closed fields of a given characteristic provides another example of completeness
• Incomplete theories contain sentences neither provable nor disprovable (theory of groups)
• Gödel's incompleteness theorems show consistent formal systems with arithmetic remain incomplete
• Completeness allows full characterization of a theory's models

Completeness vs Completeness Theorem

• Completeness of a theory differs from the completeness theorem in first-order logic
• Completeness theorem states a sentence proves if and only if true in all models
• Theory completeness focuses on provability within the specific theory
• Completeness theorem applies to the logical system as a whole
• Understanding the distinction clarifies the scope of completeness in different contexts

Completeness vs Decidability

Proving Equivalence

• Theory decides a sentence if it proves either the sentence or its negation
• "If" direction proof assumes theory T decides every sentence
• For any sentence φ in T's language, either T ⊢ φ or T ⊢ ¬φ, satisfying completeness definition
• "Only if" direction proof assumes T completes
• For any sentence φ, completeness implies T ⊢ φ or T ⊢ ¬φ, thus deciding every sentence
• Equivalence highlights completeness as theory's ability to prove or disprove all statements
• Proof relies on excluded middle principle in classical logic

Implications and Limitations

• Characterization of completeness crucial for understanding formal systems' limitations
• Gödel's incompleteness theorems demonstrate these limitations in arithmetic systems
• Decidability relates to algorithmic procedures for determining truth values
• Completeness does not guarantee decidability (some complete theories remain undecidable)
• Understanding the relationship between completeness and decidability informs theoretical computer science

Completeness and Categoricity

Defining Categoricity

• Categoricity describes a theory where all models of a given cardinality are isomorphic
• ℵ₀-categorical theory combines completeness and categoricity in some infinite cardinality
• Löwenheim-Skolem theorem implies complete theories with infinite models cannot be categorical in all infinite cardinalities
• Theory of dense linear orders without endpoints exemplifies both completeness and ℵ₀-categoricity
• Ryll-Nardzewski theorem characterizes ℵ₀-categorical theories using n-types over the empty set

Relationships and Applications

• Completeness does not imply categoricity (some complete theories have non-isomorphic models)
• Categoricity does not imply completeness (some categorical theories remain incomplete)
• Combination of completeness and categoricity provides powerful model-theoretic analysis tools
• Study of completeness-categoricity relationship advances stability theory
• Applications extend to classification theory in model theory
• Understanding these connections deepens insight into model-theoretic structures

Properties of Complete Theories

Homogeneity and Saturation

• Models of complete theories exhibit homogeneity and saturation
• Homogeneity allows extension of partial isomorphisms between finitely generated substructures to automorphisms
• Saturation means a model realizes all types over subsets with cardinality less than the model
• Monster model serves as a universal domain for studying complete theories
• Monster model exhibits high saturation and homogeneity
• Complete theories with model companion property have existentially closed models
• Omitting Types Theorem describes existence of certain models in complete theories
• Prime Model Theorem characterizes properties of specific models in complete theories

Stability Theory and Classifications

• Study of model properties in complete theories leads to stability theory development
• Stability theory classifies theories based on model behavior regarding saturation
• Classification extends to other model-theoretic properties (number of models, forking independence)
• Understanding stability aids in analyzing structure and behavior of models
• Applications of stability theory extend to algebraic geometry and number theory
• Classification results provide insights into model-theoretic complexity of theories