Semantics of Predicate Logic

In the previous posts, we’ve discussed the syntax of predicate logic, outlining how terms, predicates, and formulas are formed. Now, we’ll explore semantics, explaining how meaning is formally assigned to these formulas.

Structures and Interpretations

The meaning of formulas in predicate logic is given by structures (or interpretations). Intuitively, a structure assigns concrete meanings to symbols, transforming abstract formulas into meaningful statements about specific objects.

Formal Definition of a Structure

Formally, a structure \(\mathcal{M}\) consists of:

• A non-empty set \(D\), the domain of discourse.
• An interpretation for each constant symbol, associating it with an element of \(D\).
• An interpretation for each function symbol \(f\) of arity \(n\), assigning a function: \(f^{\mathcal{M}}: D^n \rightarrow D\)
• An interpretation for each predicate symbol \(P\) of arity \(n\), assigning a subset of \(D^n\) indicating exactly when \(P\) holds true.

Formally, we represent a structure as: \(\mathcal{M} = (D, I)\)

where \(I\) gives the interpretations of all symbols.

Examples of Mathematical Structures

Example 1: Structure of integers with standard arithmetic

• Domain \(D = \mathbb{Z}\).
• Constants: integers like \(0, 1\).
• Functions: Arithmetic operations (addition \(+\), multiplication \(\times\)).
• Predicate “<” interpreted as: \(\{(x,y) \in \mathbb{Z}^2 \mid x < y \text{ as integers}\}\). Intuitively, the set defined by “<” includes all pairs of integers where the first integer is strictly less than the second.

Truth in a Model

Given a structure \(\mathcal{M}\), truth for formulas is defined recursively:

Atomic Formulas

An atomic formula \(P(t_1, \dots, t_n)\) is true in \(\mathcal{M}\) precisely when the tuple \((t_1^{\mathcal{M}}, \dots, t_n^{\mathcal{M}})\) lies in the subset defined by \(P\).

This aligns intuitively with our everyday notion of truth: “Even(2)” is true because 2 indeed satisfies our usual definition of evenness.

Extending Truth Definitions to Quantified Statements

For quantified formulas, truth is defined as follows:

• Universal Quantification (\(\forall x \varphi\)): True if, when we substitute any element from the domain for \(x\), the formula \(\varphi\) remains true.
  • Formally, \(\mathcal{M} \models \forall x \varphi\) means for every \(a \in D\), the formula \(\varphi[a/x]\) (formula \(\varphi\) with \(x\) replaced by \(a\)) is true in \(\mathcal{M}\).
• Existential quantification (\(\exists x \varphi\)) is true if there exists at least one element in the domain for which \(\varphi\) becomes true when \(x\) is interpreted as this element.
  • Formally, \(\mathcal{M} \models \exists x \varphi\) means there is at least one \(a \in D\) such that \(\varphi[a/x]\) is true in \(\mathcal{M}\).

In these definitions, \(\mathcal{M} \models \varphi\) means “formula \(\varphi\) is true in the structure \(\mathcal{M}\).”

Models and Logical Validity

• Model: A structure \(\mathcal{M}\) is a model for formula \(\varphi\) (written \(\mathcal{M} \models \varphi\)) if \(\varphi\) is true in \(\mathcal{M}\).
• Satisfiability: A formula is satisfiable if it has at least one model.
• Logical Validity: A formula is logically valid if it is true in every possible structure. We write this as: \(\models \varphi\)

Intuitively, a logically valid formula represents a statement that holds universally, regardless of how its symbols are interpreted.

Exercises

1. Describe explicitly a structure that makes the formula \(\exists x (x^2 = 4) \) true.
2. Consider the structure \(\mathcal{M}\) with domain \(\mathbb{N}\) and predicate \(Divides(x,y)\) meaning “\(x\) divides \(y\)”. Determine the truth value of:
   \(\forall x \exists y \; Divides(x,y)\)
3. Give an example of a logically valid formula and one that is satisfiable but not logically valid. Clearly explain why each has the given property.

This foundational understanding of semantics will enable us to move forward into exploring proof techniques and deeper logical analysis in predicate logic.