Questions: First-Order Logic Semantics and Structures

Question 1

Consider a structure M with domain {a, b} where the predicate Happy holds only of element a. What is the truth value of ∀x Happy(x) in M?

• A. True, because Happy(a) holds
• B. False, because Happy does not hold of every domain element
• C. True, because a is the only named constant
• D. Undefined, because b has no truth value assigned

Answer: (B)

∀x Happy(x) requires Happy to hold of every element in the domain. Since Happy does not hold of b, the sentence is false in M. This illustrates a key point: universal quantifiers range over all domain elements, not just those for which the predicate happens to hold.

Question 2

The sentence ∃x P(x) has the same truth value in nearly every first-order structure with the same signature.

• T. True
• F. False

Answer: False

Truth in first-order logic is model-relative. ∃x P(x) is true in a structure where at least one domain element satisfies P, and false in a structure where no element does. The same formula can be true in one structure and false in another — this is the fundamental insight of model-theoretic semantics.

Question 3

What is the difference between a formula φ(x) being satisfied by an element a in structure M, and the sentence ∀x φ(x) being true in M?

Model answer: φ(x) is satisfied by a when the variable assignment mapping x to a makes φ true in M. The sentence ∀x φ(x) is true in M when every element in the domain satisfies φ — satisfaction of the universal sentence requires checking every possible assignment.

Satisfaction is element-relative; truth of a universal sentence requires that satisfaction hold across the entire domain. This distinction underlies the recursive definition of satisfaction and is why quantifiers are the semantically distinctive feature of first-order logic compared to propositional logic.