3.2 Semantics, models, and interpretations

First-order logic helps us reason about objects and their relationships. In this section, we'll explore how models and interpretations give meaning to logical statements. We'll see how domains define what we're talking about and how interpretations assign specific meanings.

We'll also dive into semantics and satisfaction, which tell us when statements are true. We'll learn about validity and logical consequence, which help us determine when arguments are sound. These concepts are crucial for understanding how first-order logic works in practice.

Models and Interpretations

Defining the Domain and Interpretation

• Domain of discourse specifies the set of objects that are being reasoned about in a particular context
  • Can be any non-empty set (integers, real numbers, people, countries)
  • Provides a universe for the quantifiers $\forall$ (for all) and $\exists$ (there exists) to range over
• Interpretation function assigns meaning to the non-logical symbols in a first-order language
  • Maps constant symbols to elements of the domain
  • Maps function symbols to actual functions on the domain
  • Maps predicate symbols to relations on the domain

Models as Instantiations of a Theory

• Model is a structure that provides a concrete interpretation of a first-order theory
  • Consists of a domain of discourse together with an interpretation function
  • Essentially an instantiation or "possible world" in which the theory could be realized
• Truth valuation determined by a model assigns truth values (true or false) to each sentence in the language
  • Determined recursively based on the interpretation of the non-logical symbols and the meanings of the logical connectives and quantifiers
  • A sentence is true in a model if it holds under the interpretation provided by that model

Semantics and Satisfaction

Evaluating Truth in First-Order Logic

• Satisfaction is the key notion for defining truth in first-order logic
  • A formula $\phi(x_1, \ldots, x_n)$ is satisfied by a sequence of elements $a_1, \ldots, a_n$ from the domain if $\phi$ becomes true when each $x_i$ is interpreted as $a_i$
  • A sentence (formula with no free variables) is true in a model if it is satisfied by every sequence of elements
• "Tarski's truth definition" recursively defines truth based on satisfaction
  • Atomic formulas are true if the corresponding relation holds of the elements assigned to the terms
  • Compound formulas built using $\land$, $\lor$, $\rightarrow$, $\neg$ are evaluated based on truth tables
  • $\forall x \, \phi(x)$ is true if $\phi(a)$ is satisfied for every element $a$ in the domain
  • $\exists x \, \phi(x)$ is true if $\phi(a)$ is satisfied for at least one element $a$ in the domain

Validity and Logical Consequence

• Validity is a stronger notion than truth in a particular model
  • A sentence is valid if it is true in every model
  • Corresponds to the idea of a tautology or logically necessary truth
  • Valid sentences are true based solely on the meanings of the logical symbols, regardless of the interpretation of the non-logical symbols
• Logical consequence captures the idea of a sentence following from a set of premises
  • A sentence $\psi$ is a logical consequence of a set of sentences $\Phi$ if $\psi$ is true in every model in which all the sentences in $\Phi$ are true
  • Allows for sound reasoning and inference based on the meanings of the logical symbols and the structure of the argument