Questions: Existential Closure Under Homomorphisms

Question 1

A student argues: 'Since f: M → N is a homomorphism and M ⊨ ∀x R(x), we can conclude N ⊨ ∀x R(x).' What is wrong with this reasoning?

• A. Nothing — homomorphisms preserve all first-order formulas, including universal ones
• B. The student is correct only if f is surjective
• C. N may contain elements with no preimage under f; these elements need not satisfy R, destroying the universal claim
• D. Universal formulas are never preserved because homomorphisms are not embeddings

Answer: (C)

Homomorphisms only guarantee that atomic (and existential) facts about *images* of M-elements hold in N. If N has elements outside the image of f, those elements are unconstrained — they might not satisfy R. A surjective homomorphism maps every N-element from some M-element, which helps somewhat, but even then negated atomics can fail. Only embeddings (injective homomorphisms that also reflect atomic truth) give the control needed for universal preservation.

Question 2

Suppose M ⊨ ∃x φ(x, a) where φ is quantifier-free, and f: M → N is a homomorphism. Why does N ⊨ ∃x φ(x, f(a)) follow?

• A. Because f is injective, so the witness cannot be collapsed away
• B. Because φ involves only existential quantifiers, and homomorphisms preserve the entire existential theory
• C. The witness b ∈ M satisfies M ⊨ φ(b, a); since φ is quantifier-free, f preserves each atomic subformula involving b and a, so N ⊨ φ(f(b), f(a)); and f(b) exists in N, witnessing the existential
• D. Because homomorphisms are bijections, every element of M has a unique image that preserves all properties

Answer: (C)

The key is that φ is quantifier-free: it is a Boolean combination of atomic formulas. Homomorphisms preserve atomic truth (if M ⊨ R(b, a) then N ⊨ R(f(b), f(a))). Boolean combinations of preserved atomics remain preserved. So φ(b, a) holding in M implies φ(f(b), f(a)) holds in N. The image f(b) then serves as the witness for the existential in N. No injectivity is required — we just need f(b) to exist, which it does.

Question 3

If f: M → N is a homomorphism and M ⊨ ∃x∃y(R(x, a) ∧ ¬R(y, a)), then N ⊨ ∃x∃y(R(x, f(a)) ∧ ¬R(y, f(a))).

• T. True
• F. False

Answer: False

Homomorphisms preserve positive existential formulas — those built from atomic formulas using ∧, ∨, and ∃ — but NOT negated atomics. The formula here contains ¬R(y, a), a negated atomic. A homomorphism can collapse elements or make new atomic facts true: if f(y) = f(x) in N and R(f(x), f(a)) holds, then ¬R(f(y), f(a)) fails. Homomorphisms only push witnesses of *positive* existential claims forward; negation is not preserved.

Question 4

The diagram technique in model theory works because the existence of a homomorphism from the diagram of M into N corresponds precisely to N satisfying the existential consequences of M's theory.

• T. True
• F. False

Answer: True

This is exactly what existential closure under homomorphisms establishes. The diagram of M records all atomic facts about M's elements (expressed as sentences using new constants). A model of those sentences gives you a structure in which those atomic facts hold, and hence a homomorphism from M into that structure. Existential closure then guarantees that everything M existentially asserts — every ∃-formula true in M — is also true in N via the images of the witnesses. This is the foundational justification for diagram-based model constructions.

Question 5

Explain in your own words why the image of a witness under a homomorphism is a valid witness for the same existential formula in the target structure.

Model answer: An existential formula ∃x φ(x, a) is witnessed in M by some element b with M ⊨ φ(b, a). Since φ is quantifier-free, it is built from atomic subformulas by Boolean connectives without negation of non-atomic parts. Homomorphisms preserve atomic truth: every positive atomic fact about b and a that holds in M also holds about f(b) and f(a) in N. So N ⊨ φ(f(b), f(a)), and since f(b) exists in N, it witnesses ∃x φ(x, f(a)) there.

The critical insight is that existential witnesses are concrete elements, and their images are still present in N. The quantifier-free matrix φ only makes positive atomic claims about those witnesses — and homomorphisms, by definition, preserve positive atomic claims. Universal formulas fail because they make claims about *all* elements of N, including those with no preimage in M, which the homomorphism says nothing about.