12.3 Set theory in logic and model theory

Set theory plays a crucial role in logic and model theory. It provides the foundation for understanding mathematical structures and relationships, allowing us to analyze complex systems using formal languages and reasoning techniques.

In this section, we'll explore first-order logic, predicate calculus, and the concept of models. We'll also dive into theories and their properties, uncovering how set theory helps us make sense of abstract mathematical ideas.

First-Order Logic and Predicate Calculus

Foundations of First-Order Logic

Top images from around the web for Foundations of First-Order Logic

• 

  File:Argument terminology used in logic (en).svg - Wikipedia View original

  Is this image relevant?

• 

  N元关系的表示模型 View original

  Is this image relevant?

• 

  File:Argument terminology used in logic (en).svg - Wikipedia View original

  Is this image relevant?

• 

  N元关系的表示模型 View original

  Is this image relevant?

1 of 2

Top images from around the web for Foundations of First-Order Logic

• 

  File:Argument terminology used in logic (en).svg - Wikipedia View original

  Is this image relevant?

• 

  N元关系的表示模型 View original

  Is this image relevant?

• 

  File:Argument terminology used in logic (en).svg - Wikipedia View original

  Is this image relevant?

• 

  N元关系的表示模型 View original

  Is this image relevant?

1 of 2

• First-order logic extends propositional logic by introducing quantifiers and predicates
• Predicates are functions that map elements of a domain to truth values (true or false)
• Quantifiers, such as the universal quantifier $\forall$ (for all) and the existential quantifier $\exists$ (there exists), allow reasoning about entire sets of elements
• First-order logic enables the expression of more complex statements and relationships compared to propositional logic

Predicate Calculus and Its Properties

• Predicate calculus is a formal system for reasoning with first-order logic
• Completeness of a logical system means that every valid formula can be derived from the axioms and inference rules of the system
• Consistency of a logical system means that no contradiction can be derived from the axioms and inference rules
• Gödel's completeness theorem states that first-order predicate calculus is complete, meaning that every logically valid formula can be proved using the rules of the calculus
• Gödel's completeness theorem establishes a strong connection between syntax (provability) and semantics (logical validity) in first-order logic

Models and Theories

Models and Their Properties

• A model is a mathematical structure that satisfies a set of sentences in a formal language (such as first-order logic)
• Models provide a way to interpret and give meaning to the symbols and formulas in a logical system
• The Löwenheim-Skolem theorem states that if a first-order theory has an infinite model, then it has models of every infinite cardinality
• The Löwenheim-Skolem theorem implies that first-order logic cannot characterize a unique infinite structure (such as the natural numbers) up to isomorphism

Theories and Compactness

• A theory is a set of sentences in a formal language that is closed under logical consequence
• A theory is consistent if no contradiction can be derived from its sentences
• A theory is complete if, for every sentence in the language, either the sentence or its negation is provable from the theory
• The compactness theorem states that a set of first-order sentences has a model if and only if every finite subset of the sentences has a model
• The compactness theorem has important consequences, such as the existence of non-standard models of arithmetic and the possibility of constructing models with certain properties by using infinite sets of sentences