Questions: Domain and Structure in First-Order Logic

Question 1

The sentence 'every element has a predecessor' is false in ℕ (natural numbers) but true in ℤ (integers). What does this illustrate about first-order logic?

• A. The sentence is ambiguous — its meaning depends on how 'predecessor' is informally defined
• B. Truth in first-order logic is relative to a structure — the same sentence can be true in one structure and false in another
• C. ℕ and ℤ use different logical systems, so comparison between them is invalid
• D. Universal quantifier sentences are always harder to satisfy than existential ones

Answer: (B)

In ℕ, the element 0 has no predecessor (there is no natural number y with y + 1 = 0), so the sentence is false. In ℤ, every integer n has a predecessor n − 1, so the sentence is true. The sentence hasn't changed; only the structure (domain + interpretation of the function and predicate symbols) has changed. This is the defining feature of first-order model theory: truth is not absolute but always relative to a structure. A sentence defines a *class* of structures in which it is true, not a single truth value.

Question 2

What components are required to define a first-order structure M for a language with a binary predicate symbol P, a unary function symbol f, and a constant symbol c?

• A. A domain set |M|, a truth assignment for P, and numerical values for f and c
• B. A non-empty domain |M|, a set of pairs P^M ⊆ |M|², a function f^M : |M| → |M|, and an element c^M ∈ |M|
• C. A non-empty domain |M| and a single interpretation function mapping all symbols to domain elements
• D. A domain |M|, axioms governing P, and a recursive definition of f in terms of P

Answer: (B)

A structure must provide the domain and a concrete interpretation for every symbol. For binary predicate P: the interpretation P^M is a set of ordered pairs from the domain — the set of (a, b) pairs for which P holds. For unary function f: f^M is a total function from the domain to itself. For constant c: c^M is a specific element of the domain. Without all components, quantified statements like ∀x P(x, f(x)) have no meaning — you cannot evaluate whether P holds of x and its f-image without knowing what f and P denote.

Question 3

The same first-order sentence can be true in one structure and false in another structure for the same language.

• T. True
• F. False

Answer: True

This is the fundamental fact about first-order semantics. The sentence 'there exists an element with no additive inverse' is true in (ℕ, +) — the number 0 has no additive inverse in ℕ — but false in (ℤ, +) — every integer n has the inverse −n. The sentence is syntactically identical in both cases; the structure provides the interpretation of the domain and operation that determines truth. This is why logicians ask 'in which structures is this formula satisfied?' rather than 'is this formula true?'

Question 4

The domain of a first-order structure can be the empty set.

• T. True
• F. False

Answer: False

By definition, the domain of a first-order structure must be non-empty. This is a technical requirement with logical consequences: the universal quantifier ∀x φ(x) would be vacuously true over an empty domain (no elements to violate it), while the existential quantifier ∃x φ(x) would be vacuously false (no elements to witness it). These vacuous truth values create complications in standard first-order logic, so the convention requires at least one element in the domain. Some systems (free logic) relax this, but standard FOL maintains the non-emptiness requirement.

Question 5

Explain why a first-order sentence like '∀x ∃y (x < y)' has no absolute truth value and must always be evaluated relative to a structure.

Model answer: The sentence contains quantifiers ranging over a domain and a predicate symbol <, but neither the domain nor the meaning of < is specified by the sentence itself. A structure must provide: (1) the domain (the set of objects x and y range over), and (2) the interpretation of < (which pairs (a, b) satisfy 'a < b' in that structure). In (ℕ, <), the sentence is true — every natural number has a larger one. In the structure ({1, 2, 3}, <), it is false — 3 has no element greater than it. The sentence's truth depends entirely on the structure.

This is the key contrast with propositional logic, where atomic propositions are assigned truth values directly. In first-order logic, atomic formulas involve variables ranging over a domain and predicates denoting relations on that domain. Without fixing the domain and the predicate interpretations, the formula is an open semantic object — it defines a property of structures (those in which it is true), not a single truth value. Model theory exploits this: the set of all structures satisfying a collection of sentences defines a mathematical theory, and studying which structures satisfy it reveals the content of the axioms.