While propositional logic evaluates compound statements as monolithic atomic units, classical mathematics requires dissecting internal structure: quantifying over individuals, relating objects, and performing algebraic operations. First-Order Predicate Logic ($text{FOL}$) provides this expressive machinery. However, defining what it means for a quantified sentence like $forall x exists y (x < y)$ to be "true" was one of the deepest philosophical puzzles in history—solved definitively by Alfred Tarski in 1933 through inductive satisfaction in mathematical structures.
1. The First-Order Language Signature
A first-order language $mathcal{L}$ is defined by its signature $sigma = (mathcal{C}, mathcal{F}, mathcal{R}, text{ar})$, where:
- $mathcal{C}$ is a set of constant symbols (e.g., $0, 1$).
- $mathcal{F}$ is a set of function symbols (e.g., $+$, $times$, $circ$).
- $mathcal{R}$ is a set of relation or predicate symbols (e.g., $<$, $in$, $=$).
- $text{ar}: mathcal{F} cup mathcal{R} to mathbb{N}^+$ assigns an arity (number of arguments) to each function and relation symbol.
The syntax builds terms and formulas:
- Terms represent mathematical objects: variables $x_i$ and constants $c$ are terms. If $f in mathcal{F}$ has arity $n$ and $t_1, dots, t_n$ are terms, then $f(t_1, dots, t_n)$ is a term.
- Atomic Formulas assert elementary relations: $R(t_1, dots, t_n)$ where $R in mathcal{R}$, or equalities $t_1 = t_2$.
- Formulas combine atomic formulas via connectives $neg, land, lor, to$ and quantifiers $forall x$ (for all $x$) and $exists x$ (there exists $x$).
2. First-Order Structures (Models)
A formula in isolation has no truth-value; it is merely an uninterpreted string of symbols. Truth exists only relative to a structure $mathcal{M} = (M, I)$:
- Domain / Universe ($M$): A non-empty set of mathematical entities over which variables range.
- Interpretation Function ($I$):
- For each constant $c in mathcal{C}$, $c^mathcal{M} = I(c) in M$.
- For each function $f in mathcal{F}$ of arity $n$, $f^mathcal{M} = I(f): M^n to M$.
- For each relation $R in mathcal{R}$ of arity $n$, $R^mathcal{M} = I(R) subseteq M^n$.
For example, in the language of ordered rings $mathcal{L}_{text{ring}} = {0, 1, +, times, <}$, the field of real numbers $mathcal{R} = (mathbb{R}, 0, 1, +, times, <)$ and the ring of integers $mathcal{Z} = (mathbb{Z}, 0, 1, +, times, <)$ are two entirely distinct structures sharing the identical syntactic signature.
3. Tarski’s Truth Definition via Satisfaction
Why could Tarski not define $mathcal{M} vDash phi$ directly on formulas? Consider the formula $phi(x) equiv (x > 0)$. Is it true in the real numbers $mathbb{R}$? The question is meaningless without specifying what $x$ is. Therefore, truth must be defined via variable assignments:
A variable assignment is a mapping $sigma: text{Var} to M$. Every term $t$ evaluates to an element $t^mathcal{M}[sigma] in M$:
[
x^mathcal{M}[sigma] = sigma(x), quad c^mathcal{M}[sigma] = c^mathcal{M}, quad (f(t_1, dots, t_n))^mathcal{M}[sigma] = f^mathcal{M}(t_1^mathcal{M}[sigma], dots, t_n^mathcal{M}[sigma])
]
Tarski’s Inductive Definition of Satisfaction ($mathcal{M}, sigma vDash phi$)
- $mathcal{M}, sigma vDash t_1 = t_2 iff t_1^mathcal{M}[sigma] = t_2^mathcal{M}[sigma]$
- $mathcal{M}, sigma vDash R(t_1, dots, t_n) iff (t_1^mathcal{M}[sigma], dots, t_n^mathcal{M}[sigma]) in R^mathcal{M}$
- $mathcal{M}, sigma vDash neg phi iff mathcal{M}, sigma notvDash phi$
- $mathcal{M}, sigma vDash phi land psi iff mathcal{M}, sigma vDash phi text{ and } mathcal{M}, sigma vDash psi$
- Universal Quantifier:
[
mathcal{M}, sigma vDash forall x , phi iff forall m in M ; (mathcal{M}, sigma[x mapsto m] vDash phi)
]
where $sigma[x mapsto m]$ denotes the assignment identical to $sigma$ except that $x$ is mapped to domain element $m$.
A variable $x$ is free in $phi$ if it does not occur within the scope of $forall x$ or $exists x$. A formula with no free variables is a sentence. For a sentence $phi$, satisfaction is independent of the assignment $sigma$. We write simply $mathcal{M} vDash phi$ and say that $phi$ is true in $mathcal{M}$ (or $mathcal{M}$ is a model of $phi$).
4. Tarski’s Undefinability of Truth
Tarski discovered a monumental corollary: arithmetical truth cannot be defined within the arithmetic language itself. If a language $mathcal{L}$ containing arithmetic could express a predicate $text{True}(x)$ such that $mathcal{M} vDash text{True}(ulcorner phi urcorner) leftrightarrow phi$, one could apply diagonalization to construct a sentence $lambda leftrightarrow neg text{True}(ulcorner lambda urcorner)$ (the Liar Paradox), creating a formal contradiction.
Thus, truth in a structure $mathcal{M}$ can only ever be defined from an external metalanguage possessing strictly higher expressive power.
