Connections with Model Theory
Satisfaction and the Tarski Truth Definition
The recursive definition of truth in a structure, and the reason a recursion over formulas requires assignments rather than sentences alone.
Learning objectives
- State the satisfaction relation by recursion
- Explain why assignments are needed
- Compute satisfaction in concrete examples
Assignments
A function from the variables into the universe of a structure. Given an assignment, every term denotes an element and every formula receives a truth value.
Satisfaction is written A ⊧ Φ[a] — the structure A satisfies Φ under the assignment a.
A sentence has no free variables, so its truth is assignment-independent. But the recursion defining truth passes through subformulas that do have free variables — ∀x Φ is defined in terms of Φ, which has x free. So the recursion must be carried out for formulas with assignments even if only sentences are ultimately of interest. This is Tarski's insight.
The recursion
| Formula | <strong>A</strong> ⊧ Φ[<em>a</em>] holds when |
|---|---|
| t1 ≈ t2 | t1 and t2 denote the same element under a |
| r(t1,…) | the denoted tuple lies in rA |
| ¬Φ | A ⊧ Φ[a] fails |
| Φ ∧ Ψ | both hold |
| Φ ∨ Ψ | at least one holds |
| Φ → Ψ | Φ fails or Ψ holds |
| ∀x Φ | Φ holds under every assignment differing from a at most at x |
| ∃x Φ | Φ holds under some such assignment |
Tarski's criterion is that the definition should yield, for each sentence, exactly the expected biconditional — that “snow is white” is true if and only if snow is white. The recursion above satisfies this, and it is what makes model theory possible as mathematics rather than philosophy.
Worked satisfaction
In the integers under addition
- ∀x∃y (x + y ≈ 0) — true; every integer has an additive inverse.
- ∃x∀y (x + y ≈ y) — true, witnessed by 0.
- ∀x∃y (y + y ≈ x) — false; odd integers are not doubles.
The second example is true; reversing the quantifiers to ∀y∃x gives a different and weaker statement that is also true, but the two are not equivalent in general. Reading quantifier prefixes carefully is the single most common source of error.
Two turnstiles
- <strong>A</strong> ⊧ Φ
- the structure satisfies the sentence
- Σ ⊧ Φ
- every model of Σ satisfies Φ — semantic consequence
- Σ ⊢ Φ
- Φ is derivable from Σ — syntactic consequence
Gödel's completeness theorem asserts that the last two coincide for first-order logic, exactly as Birkhoff's completeness theorem does for equational logic. The source does not prove Gödel's theorem but uses its consequences freely.
For identities, A ⊧ p ≈ q in the Chapter II sense agrees with the Chapter V sense applied to the universally quantified sentence. The notation is reused deliberately.
Frequently asked questions
Why is the definition called a truth definition rather than a truth theory?
Because it defines truth for a fixed structure in a metalanguage, rather than analysing truth in general. Tarski showed a language cannot define its own truth predicate, which is why the metalanguage is essential.
Does satisfaction depend on the whole assignment?
Only on the values assigned to the free variables of the formula. This is a lemma proved by induction, and it is what makes sentences assignment-independent.
Source. S. Burris and H. P. Sankappanavar, A Course in Universal Algebra, The Millennium Edition — a corrected re-typesetting of Springer-Verlag Graduate Texts in Mathematics 78 (1981). Section V.1, book pages 221-226.
This page is an original exposition prepared for the KEVOS® knowledge library. It restates and reorganises mathematical results; it is not a reproduction of the source text.