Model-Theoretic Connections
First-order Languages and Structures
Adding relation symbols and quantifiers to the algebraic language buys enormous expressive power and costs the whole equational apparatus. Chapter V is the accounting of that trade.
- Specify a first-order language and distinguish it from an algebraic type.
- Define a structure and identify algebras as the relation-free case.
- Build terms and formulas and track free versus bound variables.
- Classify formulas as atomic, quantifier-free, universal, existential and Horn.
- Explain what expressive power is gained and what closure properties are lost.
- Recognise where equational methods stop applying.
01Languages
A first-order language L consists of operation symbols with arities, relation symbols with arities, and the logical apparatus: variables, equality, connectives and quantifiers.
| Ingredient | Expressive gain | Cost |
|---|---|---|
| Operation symbols | the algebraic content | none — this is the base case |
| Relation symbols | orderings, incidences, graphs | substructures behave differently |
| Connectives | implications between equations | H-closure lost; gives quasivarieties |
| Quantifiers | existence and universality claims | Birkhoff's theorem no longer applies |
The source's convention is to keep the model-theoretic notation aligned with Chang and Keisler, which is why F is used for both the type of an algebra and the operation symbols of a language, disambiguated by context.
02Structures
A structure for L is a non-empty set together with an interpretation of every symbol: an operation for each operation symbol, a relation for each relation symbol.
A substructure must be closed under the operations, and the relations are inherited by restriction. But a subset closed under the operations always gives a substructure, whereas whether the restricted relation is the 'right' one depends on the intended reading. Ordered structures are the standard trap: a substructure of a linear order is a linear order, but a substructure of a well-order need not be well-ordered, and well-ordering is not first-order expressible.
03Terms and formulas
Terms are built exactly as in the algebraic case, from variables and operation symbols. Formulas are built from atomic formulas by connectives and quantifiers.
- atomic formulas:
- p ≈ q for terms p, q
- r(p₁,…,pₘ) for an m-ary relation symbol r and terms pᵢ
- if φ and ψ are formulas, so are:
- ¬φ, (φ & ψ), (φ ∨ ψ), (φ → ψ), (φ ↔ ψ)
- if φ is a formula and x a variable, so are:
- ∀x φ and ∃x φ
- free variables: those not in the scope of a quantifier binding them
- a sentence is a formula with no free variables
The free/bound distinction is where most early errors occur. A formula with free variables is not true or false in a structure — it is satisfied or not by particular assignments to those variables. Only sentences have truth values.
04The formula hierarchy
Restricting the shape of formulas gives classes with distinctive preservation properties, and the preservation theorems later in this stream are organised by them.
| Class | Shape | Preserved by |
|---|---|---|
| Atomic | p ≈ q or r(p⃗) | homomorphisms, substructures, products |
| Quantifier-free | Boolean combinations of atomic | substructures, embeddings |
| Universal (∀) | ∀x⃗ ψ with ψ quantifier-free | substructures |
| Existential (∃) | ∃x⃗ ψ with ψ quantifier-free | extensions |
| Positive | no ¬ or → | surjective homomorphisms |
| Horn | conjunctions of clauses with ≤ 1 positive literal | direct products |
| Identity | ∀x⃗ (p ≈ q) | H, S and P — the equational case |
Identities are the intersection of several rows: universal, positive and Horn at once. That triple membership is exactly why they are preserved by all three class operators, and hence why Birkhoff's theorem holds for them and nothing weaker.
05What is gained
06What is lost
Equations are weak enough to have a structure theory; first-order sentences are strong enough to say what one wants and too strong for the structure theory to survive. Chapter V works in the gap, using first-order tools to prove equational results — principal congruence formulas and the finite basis theorems are exactly that.
Frequently asked
Is equality a relation symbol or a logical symbol?
A logical symbol, interpreted as genuine identity in every structure. Treating it as a relation symbol would allow structures where ≈ is some other congruence, which gives first-order logic without equality — a weaker system. The source, following Chang and Keisler, treats equality as logical.
Why must structures be non-empty?
Convention, chiefly to keep ∀x φ → ∃x φ valid. Empty structures can be accommodated in free logic at the cost of complicating the axioms. The algebraic convention of non-empty universes, adopted in Chapter II, matches the model-theoretic one here.
Can I still use free algebras in the first-order setting?
Only for the equational part. Free structures for a first-order theory generally do not exist, because the universal mapping property depends on the theory being closed under the constructions that build the free object. Where a first-order theory happens to be equational, the free algebra survives and is the same object.
- S. Burris and H. P. Sankappanavar, A Course in Universal Algebra, Millennium Edition (a corrected re-typesetting of Springer GTM 78, 1981).
- G. Grätzer, Universal Algebra, 2nd edition, Springer.
- R. McKenzie, G. McNulty and W. Taylor, Algebras, Lattices, Varieties, Volume I.
Original KEVOS® explanatory article. Written from the topic map of the cited works; no text is reproduced from them.