1.3 Syntax and semantics of first-order languages

First-order languages are the building blocks of model theory. They use symbols and rules to create precise mathematical statements, allowing us to express complex ideas in a structured way. It's like learning a new language, but for math!

Understanding the syntax and semantics of these languages is crucial. Syntax tells us how to form valid expressions, while semantics gives them meaning. Together, they let us create and interpret logical arguments, bridging the gap between abstract symbols and real-world concepts.

Syntax of First-Order Languages

Vocabulary and Formation Rules

Top images from around the web for Vocabulary and Formation Rules

• 

  Digital Circuits/Logic Operations - Wikibooks, open books for an open world View original

  Is this image relevant?

• 

  Introduction to Language | Boundless Psychology View original

  Is this image relevant?

• 

  Logical reasoning - Wikipedia View original

  Is this image relevant?

• 

  Digital Circuits/Logic Operations - Wikibooks, open books for an open world View original

  Is this image relevant?

• 

  Introduction to Language | Boundless Psychology View original

  Is this image relevant?

1 of 3

Top images from around the web for Vocabulary and Formation Rules

• 

  Digital Circuits/Logic Operations - Wikibooks, open books for an open world View original

  Is this image relevant?

• 

  Introduction to Language | Boundless Psychology View original

  Is this image relevant?

• 

  Logical reasoning - Wikipedia View original

  Is this image relevant?

• 

  Digital Circuits/Logic Operations - Wikibooks, open books for an open world View original

  Is this image relevant?

• 

  Introduction to Language | Boundless Psychology View original

  Is this image relevant?

1 of 3

• First-order languages built from vocabulary (logical symbols, non-logical symbols, variables) and formation rules for well-formed formulas
• Logical symbols include connectives (∧, ∨, →, ↔, ¬), quantifiers (∀, ∃), equality (=), and parentheses
• Non-logical symbols comprise constant symbols, function symbols, and predicate symbols, each with specified arity
• Formation rules dictate how to combine symbols to create valid expressions
  • Ensure proper use of parentheses for grouping
  • Specify correct application of connectives and quantifiers

Construction of Terms and Formulas

• Terms constructed recursively from variables, constant symbols, and function symbols applied to terms
  • Example: $f(x, g(y))$ where $f$ and $g$ are function symbols, $x$ and $y$ are variables
• Atomic formulas formed by applying predicate symbols to terms or using equality symbol between terms
  • Example: $P(x, c)$ where $P$ is a predicate symbol, $x$ is a variable, and $c$ is a constant symbol
• Complex formulas created by combining atomic formulas with logical connectives and quantifiers
  • Example: $∀x(P(x) → ∃y(Q(x, y)))$ where $P$ and $Q$ are predicate symbols
• Syntactic rules allow precise formulation of mathematical statements and logical arguments
  • Example: Expressing "For all real numbers, if x is positive, then there exists a y such that y^2 = x" as $∀x(x > 0 → ∃y(y^2 = x))$

Semantics of First-Order Languages

Structures and Interpretations

• Semantics provide meaning to syntactic elements by interpreting them in mathematical structures
• Structure for first-order language consists of non-empty domain (universe) and interpretations for non-logical symbols
  • Example: For arithmetic, domain could be set of integers, with interpretations for addition, multiplication, etc.
• Interpretation function assigns:
  • Elements of domain to constant symbols
  • Functions on domain to function symbols
  • Relations on domain to predicate symbols
• Variable assignments map variables to elements of domain
  • Allow evaluation of formulas with free variables

Models and Truth

• Satisfaction defines when formula is true in structure under given variable assignment
• Sentence (formula with no free variables) true in structure if satisfied by all variable assignments
• Model of set of sentences represents structure where all sentences in set are true
  • Example: Standard model of arithmetic satisfies Peano axioms
• Semantic entailment relation (⊨) captures notion of logical consequence between sentences or sets of sentences
  • Example: If $Φ ⊨ ψ$, then ψ is true in all models of Φ

Syntax vs Semantics

Correspondence and Principles

• Syntax provides formal rules for constructing expressions, semantics assigns meaning to these expressions
• Precise correspondence between syntactic operations and semantic interpretations in structures
  • Example: Syntactic conjunction (∧) corresponds to semantic intersection of truth conditions
• Principle of compositionality states meaning of complex formula determined by meanings of constituent parts and combination method
  • Example: Truth value of $P ∧ Q$ determined by truth values of $P$ and $Q$

Theoretical Connections

• Syntactic substitution of terms for variables corresponds semantically to changing variable assignments
• Soundness of inference rules justified by semantic preservation of truth
• Completeness theorem establishes fundamental connection between syntactic provability and semantic validity
  • If a formula is semantically valid, it is syntactically provable
• Löwenheim-Skolem theorems reveal limitations in expressive power of first-order languages
  • Show syntactic properties cannot always distinguish between structures of different cardinalities

Analyzing First-Order Formulas

Evaluation Techniques

• Determine well-formedness of expressions by applying syntactic rules recursively
  • Example: $∀x(P(x) ∧ Q(x))$ is well-formed, but $(∀x)P(x))$ is not
• Identify free and bound variables in formulas
  • Example: In $∀x(P(x) → Q(y))$, $x$ is bound and $y$ is free
• Evaluate truth value of formulas in given structures by recursively applying satisfaction relation
  • Example: Evaluate $∀x∃y(x < y)$ in structure of natural numbers with usual ordering
• Use semantic tableaux or truth trees to systematically analyze satisfiability of formulas and validity of arguments
  • Construct tree by breaking down formula into subformulas

Advanced Analysis Techniques

• Apply compactness theorem to reason about existence of models for infinite sets of sentences
  • If every finite subset of a set of sentences has a model, the entire set has a model
• Utilize Löwenheim-Skolem theorems to construct models of different cardinalities for consistent theories
  • Example: Constructing countable model for theory with uncountable model
• Employ techniques to simplify and standardize first-order formulas:
  • Prenex normal form moves all quantifiers to front of formula
  • Skolemization eliminates existential quantifiers by introducing new function symbols