Questions: Embeddings and Preservation of Formulas

Question 1

The sentence 'every element has a multiplicative inverse' (∀x ∃y xy = 1) holds in ℝ (the reals). Does it hold in ℤ (the integers), which is a substructure of ℝ?

• A. Yes — universal sentences are always preserved downward into substructures
• B. No — this sentence is not purely universal (it contains an embedded existential), so preservation under substructures is not guaranteed
• C. Yes — existential sentences are preserved upward, so any substructure inheriting ℝ will satisfy them
• D. No — ℤ is not a legitimate substructure of ℝ because multiplication behaves differently

Answer: (B)

The sentence ∀x ∃y xy = 1 is universally-existentially quantified (∀∃), not purely universal. The preservation theorem guarantees that *purely universal* sentences (∀x φ(x) with quantifier-free φ) are preserved downward into substructures — but this guarantee does not extend to mixed quantifier sentences. And indeed it fails here: in ℤ, the integer 2 has no multiplicative inverse (1/2 ∉ ℤ). The witness y = 1/x exists in ℝ but was removed when we restricted to ℤ.

Question 2

Structure M satisfies the existential sentence ∃x R(x,x), and M embeds injectively into structure N. Which conclusion is guaranteed by the preservation theorem?

• A. N also satisfies ∃x R(x,x) — the witness from M is still present in the image of M in N
• B. Every substructure of M also satisfies ∃x R(x,x)
• C. M and N satisfy exactly the same sentences
• D. M is isomorphic to N

Answer: (A)

Existential sentences are preserved under embeddings (extensions). If ∃x R(x,x) holds in M — say element a witnesses R(a,a) — then after embedding f: M → N, the element f(a) still exists in N and R(f(a),f(a)) holds (because embeddings preserve atomic formulas). So N inherits the existential witness. Option B is wrong: existential sentences go *upward* under extensions, not downward; a substructure of M might lack the witness. Option C is much stronger than what the preservation theorem guarantees.

Question 3

If a purely universal sentence holds in a substructure M of N, then it is expected to also hold in the larger structure N.

• T. True
• F. False

Answer: False

False — the direction is reversed. Universal sentences are preserved *downward*: if ∀x φ(x) holds in N, then it holds in every substructure M of N (because M has fewer elements and each one is already in N where φ holds). But the reverse is not guaranteed. A purely universal sentence might hold in M simply because M lacks the counterexample elements — those elements might exist in N. For example, 'every element squared is non-negative' holds in ℝ (as a substructure of ℂ), but ℂ contains elements like i where i² = −1 < 0, violating it.

Question 4

Positive formulas — built from atomic formulas using conjunction, disjunction, and quantifiers, but without any negation — are preserved under homomorphisms, even non-injective ones.

• T. True
• F. False

Answer: True

True. This is the most general of the three preservation results. A homomorphism f: M → N preserves the truth of atomic formulas (by definition). Since positive formulas are built only from operations that respect this — ∧ (and), ∨ (or), ∃ (existential), ∀ (universal) without negation — their truth is inherited by the homomorphic image. Negation would break this: if ¬R(a) holds in M but f is not injective, R(f(a)) might hold in N. The absence of negation is exactly what makes positive formulas preserved under the weakest morphism type.

Question 5

Explain the key directional asymmetry between universal and existential sentences in the preservation theorem, and why the asymmetry goes in opposite directions.

Model answer: Universal sentences are preserved *downward* into substructures: if ∀x φ(x) holds in N, it holds in every substructure M — M has fewer elements, so nothing new can violate the universal claim. Existential sentences are preserved *upward* under extensions: if ∃x φ(x) holds in M, any N that extends M retains the witness. But a substructure might have lost the existential witness, and a superstructure might introduce new elements that violate the universal claim. The asymmetry reflects what gets added versus removed when moving between structures.

Intuition: a universal claim is a constraint — 'nothing violates φ.' Removing elements (going to a substructure) cannot create a violation, but adding elements can. An existential claim is an existence assertion — 'something satisfies φ.' Adding elements cannot destroy a witness, but removing them can. This neat duality is why the preservation theorem is stated in terms of direction: ∀-sentences go down (to substructures), ∃-sentences go up (to extensions), and ∀∃-sentences (like most interesting mathematical statements) are preserved in neither direction unconditionally.