3.3 Truth and satisfaction in structures

Truth and satisfaction in structures are fundamental concepts in first-order logic. They provide a framework for evaluating the meaning of logical formulas within specific mathematical contexts, bridging the gap between abstract syntax and concrete interpretations.

Understanding these concepts is crucial for grasping how logical statements relate to mathematical objects. They form the basis for model theory and enable us to reason about the validity and consistency of logical systems in various domains.

Structures in First-Order Logic

Components of a Structure

Top images from around the web for Components of a Structure

• 

  Domain and Range · Algebra and Trigonometry View original

  Is this image relevant?

• 

  Logical symbols | JD2718 View original

  Is this image relevant?

• 

  Domain model - Wikipedia View original

  Is this image relevant?

• 

  Domain and Range · Algebra and Trigonometry View original

  Is this image relevant?

• 

  Logical symbols | JD2718 View original

  Is this image relevant?

1 of 3

Top images from around the web for Components of a Structure

• 

  Domain and Range · Algebra and Trigonometry View original

  Is this image relevant?

• 

  Logical symbols | JD2718 View original

  Is this image relevant?

• 

  Domain model - Wikipedia View original

  Is this image relevant?

• 

  Domain and Range · Algebra and Trigonometry View original

  Is this image relevant?

• 

  Logical symbols | JD2718 View original

  Is this image relevant?

1 of 3

• Structure in first-order logic encompasses non-empty set (domain or universe) and interpretations for constant, function, and predicate symbols
• Domain represents set of objects variables in language can range over (integers, real numbers, people)
• Constant symbols interpreted as specific elements in domain (0, π, John)
• Function symbols interpreted as functions from domain to itself (addition, multiplication)
• Predicate symbols interpreted as relations on domain (less than, equality)
• Interpretation function assigns meanings to each symbol relative to structure's domain
• Structure provides mathematical model for interpreting symbols and formulas of first-order language

Significance of Structures

• Structures bridge abstract syntax of logic with concrete mathematical objects
• Enable formal reasoning about mathematical and real-world concepts
• Allow evaluation of truth and satisfaction of formulas within specific contexts
• Provide framework for studying model theory and mathematical logic
• Facilitate comparison between different interpretations of same logical language
• Form basis for semantics of first-order logic, connecting syntax to meaning

Truth and Satisfaction of Formulas

Truth in Structures

• Truth defined for sentences (formulas with no free variables)
• Determined by interpretation of symbols and structure's domain
• Sentences either true or false in given structure
• Truth value independent of variable assignments
• Evaluated recursively based on logical connectives and quantifiers
• Atomic sentences true if interpreted relation holds for interpreted terms
• Complex sentences evaluated using truth tables for logical connectives

Satisfaction Relation

• Satisfaction extends truth to formulas with free variables
• Relation between formula, structure, and variable assignment
• Formula satisfied if variable assignment makes it true in structure
• Defined recursively based on logical connectives and quantifiers
• For atomic formulas, determined by interpretation of predicate symbols and term values
• Complex formulas evaluated using satisfaction of subformulas
• Sentence true in structure if satisfied by every variable assignment

Truth Value of Formulas with Free Variables

Variable Assignments and Truth Evaluation

• Formulas with free variables lack definite truth value without variable assignment
• Variable assignment maps free variables to elements in structure's domain
• Truth value determined by evaluating formula under specific assignment
• Quantified formulas evaluated considering all possible assignments to quantified variables
• Truth value may change depending on chosen variable assignment
• Formula valid in structure if satisfied by every possible variable assignment
• Satisfaction set represents all variable assignments satisfying formula in structure

Examples of Truth Evaluation

• Formula: $x < y$ in structure of natural numbers
  • True for assignment $(x=2, y=5)$
  • False for assignment $(x=7, y=3)$
• Formula: $P(x) \lor Q(y)$ in structure with domain $\{a,b\}$ and $P=\{a\}, Q=\{b\}$
  • True for assignments $(x=a, y=b)$, $(x=a, y=a)$, $(x=b, y=b)$
  • False for assignment $(x=b, y=a)$

Formula Satisfaction with Variable Assignments

Evaluating Satisfaction

• Variable assignments function from set of variables to structure's domain
• Atomic formulas evaluated by interpreting terms and checking resulting tuple in predicate interpretation
• Complex formulas evaluated recursively based on logical connectives and quantifiers
• Existential quantifiers satisfied if at least one assignment to quantified variable satisfies subformula
• Universal quantifiers satisfied if all possible assignments to quantified variable satisfy subformula
• Multiple free variables require considering all combinations of assignments
• Techniques like truth tables and semantic tableaux used for systematic evaluation in finite structures

Examples of Satisfaction Evaluation

• Formula: $\forall x (P(x) \rightarrow Q(x))$ in structure with domain $\{1,2,3\}$, $P=\{1,2\}$, $Q=\{2,3\}$
  • Satisfied because for all x, if $P(x)$ is true, then $Q(x)$ is true
• Formula: $\exists x (R(x,y))$ in structure with domain $\{a,b,c\}$ and $R=\{(a,b),(b,a),(c,c)\}$
  • Satisfied for assignments $(y=a)$, $(y=b)$, $(y=c)$
  • For each y, there exists an x such that $(x,y)$ is in R