Consider the first-order logic sentence 𝜑 ≡ ∃𝑠∃𝑡∃𝑢∀𝑣∀𝑤∀𝑥∀𝑦 𝜓(𝑠,𝑡, 𝑢, 𝑣, 𝑤, 𝑥, 𝑦) where…

Question

Consider the first-order logic sentence

𝜑 ≡ ∃𝑠∃𝑡∃𝑢∀𝑣∀𝑤∀𝑥∀𝑦 𝜓(𝑠,𝑡, 𝑢, 𝑣, 𝑤, 𝑥, 𝑦)

where 𝜓(𝑠,𝑡, 𝑢, 𝑣, 𝑤, 𝑥, 𝑦) is a quantifier-free first-order logic formula using only predicate symbols, and possibly equality, but no function symbols. Suppose 𝜑 has a model with a universe containing 7 elements.

Which one of the following statements is necessarily true?

Accepted Answer

Correct answer: A — Key idea: use the three existential witnesses and the induced substructure to get a small model. Pick the three elements a, b, c in the given 7-element model that witness ∃s ∃t ∃u. Form the induced substructure whose universe is {a,b,c}. In a language without function symbols, this is a valid structure in the same signature. Any universally quantified ψ that held for all tuples from the 7-element universe still holds for all tuples from the smaller universe (the smaller domain is a subset), so the substructure satisfies ∀v ∀w ∀x ∀y ψ(a,b,c,v,w,x,y). Therefore φ is true in this substructure, giving a model of size at most 3. (If some witnesses coincide, the model could be size 1 or 2.)

Answer

A. There exists at least one model of 𝜑 with universe of size less than or equal to 3.

Answer

B. There exists no model of 𝜑 with universe of size less than or equal to 3.

Answer

C. There exists no model of 𝜑 with universe of size greater than 7.

Answer

D. Every model of 𝜑 has a universe of size equal to 7.

Consider the first-order logic sentence 𝜑 ≡ ∃𝑠∃𝑡∃𝑢∀𝑣∀𝑤∀𝑥∀𝑦 𝜓(𝑠,𝑡,…