The sentence ∀x∀y (x < y → ∃z (x < z ∧ z < y)) — 'between any two elements there is a third' — is true in (ℚ, <) but false in (ℤ, <). What does this demonstrate?
AThe sentence is logically invalid, since it fails in at least one structure
BThe sentence is logically valid, since it succeeds in at least one structure
CThe truth value of a first-order sentence is relative to the structure, not an intrinsic property of the formula alone
DQuantifiers behave differently over rational numbers than over integers, making universal quantification unreliable
A sentence's truth is not absolute in first-order logic — it holds or fails relative to a specific structure's domain and interpretation. The sentence is true in (ℚ, <) because the rationals are dense (there is always a rational between any two rationals). It is false in (ℤ, <) because there is nothing between 3 and 4 in the integers. The same formula, different structure, different truth value. This is the foundational concept of model theory: M ⊨ φ is a relation, not a property of φ alone.
Question 2 Multiple Choice
To evaluate whether M ⊨ ∃x P(x), which of the following must be true?
AP(x) must hold for every element a in the domain |M|
BThere must exist at least one element a ∈ |M| such that M ⊨ P(x)[x↦a]
CThe variable x must already be assigned a value in the variable assignment s
DP must be interpreted as a total function in the structure M
The existential quantifier ∃x φ is satisfied in M iff there is *some* element a in the domain |M| for which φ is satisfied when x is assigned to a. You only need one witness — if any single element makes the formula true, ∃x φ is satisfied. Option A describes universal quantification (∀). Option C is wrong because the quantifier itself binds x; no prior assignment is needed.
Question 3 True / False
For a sentence φ (a formula with no free variables), the truth value M ⊨ φ does not depend on the variable assignment s.
TTrue
FFalse
Answer: True
Variable assignments matter only for free variables — the open slots in a formula that must be assigned concrete domain elements before the formula has a truth value. A sentence has no free variables by definition; all variables are bound by quantifiers, which range over the domain themselves. So whether M ⊨ φ holds is determined entirely by the structure M and not by any particular assignment s. This is why sentences can be said to be simply 'true or false in M' without specifying s.
Question 4 True / False
A formula that is satisfiable (true in some structure) is also valid (true in most structures).
TTrue
FFalse
Answer: False
Satisfiability and validity are distinct logical properties. A satisfiable formula is one that is true in *at least one* structure. A valid formula is true in *every* structure (a tautology). Most interesting formulas are satisfiable but not valid — the example ∀x∀y (x < y → ∃z (x < z ∧ z < y)) is true in (ℚ, <) but false in (ℤ, <), so it is satisfiable but not valid. Only logical tautologies like ∀x (P(x) → P(x)) are valid.
Question 5 Short Answer
Explain why evaluating a first-order sentence requires specifying a structure M, rather than simply determining whether the sentence is 'true' on its own.
Think about your answer, then reveal below.
Model answer: First-order sentences contain predicate symbols, function symbols, and constants that have no meaning by themselves — they are just syntactic labels. A structure M assigns each symbol a concrete interpretation: predicates become sets of tuples, functions become actual functions, constants become domain elements. Without a structure, 'x < y' has no truth value because < has no meaning, and the domain for quantifiers to range over is undefined. Satisfaction M ⊨ φ is inherently a relation between a formula and a structure because the formula's truth depends entirely on what the symbols are interpreted to mean in a specific mathematical universe.
This is what distinguishes first-order logic from propositional logic, where truth values are directly assigned. In first-order logic, meaning is supplied by structures, making satisfaction a two-place relation. Model theory studies exactly this relationship — which formulas are true in which structures — and it underlies all of modern mathematics' foundations.