A logician describes the integers ℤ with two different signatures: σ₁ = {+, 0, 1} and σ₂ = {+, ·, 0, 1}. Which statement about these two presentations is correct?
ABoth presentations are equivalent — ℤ is the same object, so both signatures express the same properties
Bσ₂ is strictly more expressive — properties involving multiplication (like divisibility) can be expressed in σ₂ but not directly in σ₁
CThe choice of signature is a notational convenience with no effect on what can be proven
Dσ₁ is more fundamental because addition is the basic operation of ℤ
Signature determines what properties can be expressed in formulas. In σ₁ = {+, 0, 1}, multiplication is not part of the vocabulary, so properties essentially involving multiplication — like 'x divides y' or 'x is a perfect square' — cannot be expressed directly. Adding · to get σ₂ opens up an entire class of new expressible properties. The underlying mathematical object is the same ℤ, but two structures for different signatures speak different formal languages. Changing the vocabulary changes what can be said, what theories can be formulated, and what structures can be distinguished.
Question 2 Multiple Choice
A student says: 'I've written down signature σ = {e, ·, inv} with a constant, a binary function, and a unary function. This signature defines the theory of groups.' What is the error?
AGroup signatures cannot include a constant — identity must be a relation
BA signature specifies only the vocabulary — symbol names and arities. It defines no theory; axioms (associativity, identity, inverses) are separate statements in that vocabulary
CThe signature is correct and fully defines the theory of groups
DSignatures cannot mix constants, function symbols, and relation symbols
This is the core distinction: signature ≠ theory. A signature is purely syntactic: it lists symbol names and arities (e is a constant, · is binary, inv is unary) with no constraints on interpretation. Any set with any function interpreting · and any function interpreting inv is a σ-structure, even if it fails associativity or lacks inverses. The theory of groups requires additional axioms: associativity (∀xyz, x·(y·z)=(x·y)·z), identity (∀x, x·e=x=e·x), inverses (∀x, x·inv(x)=e). The signature σ is the vocabulary for groups; the axioms are what restrict σ-structures to groups specifically.
Question 3 True / False
Two structures that interpret different signatures cannot be directly compared for properties like isomorphism, because they speak different formal languages.
TTrue
FFalse
Answer: True
Isomorphism (and other structural comparisons like embedding or elementary equivalence) are defined between structures for the *same* signature. A σ₁-structure M and a σ₂-structure N interpret different symbols, so there is no natural way to compare them unless one signature extends the other. For instance, asking whether a group (interpreted in {·, e, inv}) is isomorphic to an ordered set (interpreted in {<}) is not a well-formed model-theoretic question. Comparing requires a shared vocabulary, which is why expansions and reducts — moving between related signatures — are important operations.
Question 4 True / False
The same set can serve as the universe for multiple distinct structures, all for the same signature, by interpreting the signature's symbols differently.
TTrue
FFalse
Answer: True
A structure for signature σ = {·, e} consists of a universe (a set) plus an interpretation: · gets assigned some binary function on the set, e gets assigned some element. The set ℤ can be a σ-structure with · as multiplication and e as 1 (giving a monoid), or with · as addition and e as 0 (giving a different monoid), or with · as the 'always return the left argument' function — all different σ-structures on the same universe. The structure is the combination of universe plus interpretation, not the universe alone.
Question 5 Short Answer
What does it mean to 'expand' a structure to a larger signature, and why is this operation useful in model theory?
Think about your answer, then reveal below.
Model answer: To expand a σ-structure M to a σ'-structure M' (where σ' adds new symbols to σ) means interpreting the new symbols in the same universe M already has. The existing interpretations of σ symbols are unchanged; the new σ'-symbols are given fresh interpretations. The operation is useful because it lets model theorists add 'named constants' or auxiliary functions to a structure to make certain elements or properties explicitly accessible — for example, adding constants for each element of M (the diagram construction) to study what sentences M satisfies, then taking the σ-reduct afterward to strip away the auxiliary machinery.
Expansion and reduct are the two basic signature operations. An expansion adds new vocabulary without changing the underlying universe or the interpretations of existing symbols. The reduct is the inverse: given a σ'-structure, forget the interpretations of symbols not in σ to get a σ-structure. These operations are used throughout model theory — for example, in the compactness theorem applications where you expand the language to include constant witnesses, prove something about the expanded structure, and then reduce back. Controlling which vocabulary is present at each step is essential to the method.