Questions: Models and Interpretations in First-Order Logic

Question 1

The sentence ∃x ∀y (x ≤ y) is evaluated in two models: M1 has domain ℕ with standard ≤, and M2 has domain ℤ with standard ≤. What is true?

• A. The sentence is true in both models — 0 is the smallest element in both ℕ and ℤ
• B. The sentence is false in both models — no integer is smaller than all others
• C. The sentence is true in M1 but false in M2 — ℕ has a minimum (0), but ℤ has no smallest integer
• D. The sentence is false in M1 but true in M2 — integers allow for a universal lower bound that natural numbers don't

Answer: (C)

In M1 (domain ℕ), the sentence is true: the witness is 0, since 0 ≤ y for every natural number y. In M2 (domain ℤ), the sentence is false: for any integer x, x − 1 is also an integer with x − 1 < x, so no element satisfies ∀y (x ≤ y). This example demonstrates the key insight: the same sentence, with the same symbol ≤ interpreted identically (as the standard ordering), can have opposite truth values depending solely on the domain of quantification.

Question 2

You want to construct a model in which the sentence ∀x P(x) is false. Which approach is guaranteed to work?

• A. Choose a domain containing infinitely many objects — ∀x is harder to satisfy over infinite domains
• B. Interpret P as an empty relation — then no object satisfies P, making ∀x P(x) false
• C. Use the empty domain, so there are no objects to test the universal claim against
• D. Choose any domain where the interpretation of P has at least one object not in its extension

Answer: (D)

∀x P(x) is false if and only if at least one object in the domain fails to satisfy P. Option D correctly identifies this: any domain where some object d has P(d) = false makes the universal false. Option B works too (no objects satisfy P), but option D is the minimal sufficient condition and more revealing. Option C is wrong — the standard semantics of first-order logic requires non-empty domains, and in an empty domain ∀x P(x) would vacuously be true. Option A is a misconception — domain size doesn't directly determine truth of a universal.

Question 3

A formula in first-order logic has a definite truth value that does not depend on which model is used to interpret it.

• T. True
• F. False

Answer: False

This is the central misconception the model-theoretic framework is designed to correct. Truth in first-order logic is always relative to a model: the same formula can be true in one model and false in another. Only logical validities (formulas true in every model) and contradictions (false in every model) have model-independent truth values. Most interesting formulas are contingent — true in some models, false in others. This is why formal semantics requires explicitly specifying a model before asking whether a sentence is true.

Question 4

A valid model in standard first-order logic must have a non-empty domain — interpretations over the empty set are not permitted.

• T. True
• F. False

Answer: True

Standard first-order logic requires the domain to be non-empty (at least one object must exist). This is a foundational stipulation, not an arbitrary convention: many inference rules (like existential instantiation and universal instantiation) break down over empty domains. The non-emptiness requirement also ensures that ∃x (x = x) is logically valid — a sentence saying 'something exists' is true in every valid model. Some non-classical systems (free logic) relax this constraint, but classical first-order logic assumes non-empty domains throughout.

Question 5

What are the two distinct components of a model in first-order logic, and how can varying each independently change the truth of a sentence?

Model answer: A model has two components: (1) a domain — the set of objects that exist in the model, and (2) an interpretation function — which assigns specific objects, functions, or relations to each constant, function symbol, and predicate symbol in the language. Varying the domain while keeping interpretation fixed can change truth: 'there is a smallest element (∃x ∀y x ≤ y)' is true in ℕ but false in ℤ with the same ≤ interpretation. Varying the interpretation while keeping the domain fixed also changes truth: over domain ℕ, interpreting binary predicate R as '<' vs. 'divides' gives a different model in which different sentences hold.

The two-component structure is essential because it separates existence questions (what objects are there?) from meaning questions (what do the symbols refer to?). A sentence can fail to be true either because the domain lacks the needed objects (existential statements) or because the predicates don't have the right extension given the domain. This distinction underlies model theory, the study of which theories have which kinds of models — and it is the foundation for soundness and completeness results in logic.