Connections with Model Theory
First-Order Structures and Interpretation
Structures as the semantic counterpart of languages: sets carrying interpretations of every function, constant and relation symbol.
Learning objectives
- Define a structure for a given language
- Distinguish structures from algebras
- Define substructure and the reduct/expansion operations
Structures
For a language L, a structure A consists of a non-empty universe A, an operation fA: An → A for each n-ary function symbol, an element cA ∈ A for each constant symbol, and a relation rA ⊆ An for each n-ary relation symbol.
A structure whose language has no relation symbols is exactly an algebra. So Chapter V's structures generalise Chapters I–IV's algebras by permitting relations.
| Structure | Relations |
|---|---|
| Ordered set | The order relation ≤ |
| Graph | The adjacency relation |
| Ordered field | ≤, alongside the field operations |
| Model of set theory | The membership relation ∈ |
| Ordered group | ≤, alongside the group operations |
Substructures
A subset B ⊆ A closed under all operations and containing all constants, with relations restricted: rB = rA ∩ Bn.
Relations restrict rather than being freely chosen. This is what makes substructure the right notion — the same tuples are related in B as were related in A.
A substructure agrees with the ambient structure on atomic formulas only. Agreement on all formulas is the much stronger notion of elementary substructure, treated two pages on.
Reducts and expansions
Given a structure for a language L and a sublanguage L′, the L′-reduct forgets the interpretations of symbols not in L′.
The reverse: adding interpretations for new symbols on the same universe.
Naming every element of A with a new constant is the standard device underlying the compactness proofs, the Tarski–Vaught test, and the connection between polynomials and terms. It is the model-theoretic counterpart of the polynomial/term distinction from Chapter II.
Homomorphisms of structures
A homomorphism between structures must preserve operations and relations: ⟨a1,…⟩ ∈ rA implies ⟨α(a1),…⟩ ∈ rB.
| Map | Condition on relations |
|---|---|
| Homomorphism | Preserves — one direction only |
| Strong homomorphism | Preserves and reflects |
| Embedding | Injective, preserves and reflects |
| Isomorphism | Bijective embedding |
| Elementary embedding | Preserves all first-order formulas |
For algebras, a bijective homomorphism is automatically an isomorphism. For structures this fails: a bijective homomorphism may relate strictly fewer tuples in the source than in the target. Reflection must be required separately.
Frequently asked questions
Is the empty structure allowed?
Not in this development — universes are non-empty, following the convention for algebras. Some logic texts allow empty structures at the cost of complicating the quantifier rules.
Does every structure have substructures?
It has itself. Whether it has proper ones depends on the language: if constants generate the whole universe, the only substructure is the structure itself.
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 218-221.
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.