Questions: Elementary Substructures and Preservation of Formulas

Question 1

The integers ℤ are a substructure of the rationals ℚ under the ordering <. Is ℤ an elementary substructure of ℚ?

• A. Yes — ℤ and ℚ are both infinite ordered sets, so they satisfy the same sentences
• B. No — ℚ satisfies ∃y(1 < y < 2) with witness y = 3/2, but no such element exists in ℤ
• C. Yes — elementary equivalence between ℤ and ℚ implies ℤ is an elementary substructure
• D. No — elementary substructures must have the same cardinality as their ambient structure

Answer: (B)

The Tarski-Vaught test requires that every existential formula true in ℚ with parameters from ℤ already has a witness in ℤ. The formula ∃y(1 < y < 2) is true in ℚ (witnessed by 3/2), but no such element exists in ℤ — so the test fails. Note that option C is a common confusion: two structures can be elementarily equivalent (same closed sentences) without either being an elementary substructure of the other, since elementary substructure additionally requires formula agreement for all assignments of free variables from M's domain.

Question 2

The Tarski-Vaught test says M ≺ N if and only if, for every formula ∃y φ(ā, y) with ā from M that is true in N, there exists a witness in M. This condition is equivalent to requiring that M and N satisfy the same:

• A. Closed first-order sentences only
• B. First-order formulas under all variable assignments from M's domain, not just sentences
• C. Quantifier-free formulas with parameters from M
• D. Universal sentences — ∀x φ(x) formulas

Answer: (B)

Elementary substructure (M ≺ N) is strictly stronger than elementary equivalence (M ≡ N). Elementary equivalence means the same closed sentences hold; elementary substructure means that for every formula φ(x̄) — including formulas with free variables — and every tuple ā from M, φ(ā) holds in M iff it holds in N. The Tarski-Vaught test is equivalent to this because closing off existential witnesses in N within M is exactly what guarantees formula-agreement for all assignments.

Question 3

If M ≺ N (M is an elementary substructure of N), then M and N satisfy exactly the same first-order sentences.

• T. True
• F. False

Answer: True

Elementary substructure implies elementary equivalence. Since every sentence is a formula with no free variables, and M ≺ N requires truth-value agreement for all formulas under all assignments from M, it certainly requires agreement on all closed sentences. The converse fails: elementary equivalence does NOT imply elementary substructure, which requires the stronger condition of formula-agreement for all variable assignments.

Question 4

If M ≡ N (M and N are elementarily equivalent) and M is a substructure of N, then M is an elementary substructure of N.

• T. True
• F. False

Answer: False

This is a key misconception. Elementary equivalence (same closed sentences) plus substructure does NOT imply elementary substructure. Elementary substructure additionally requires that for every formula φ(x₁, …, xₙ) with free variables and every tuple ā from M, the formula holds of ā in M iff it holds of ā in N. A counterexample: the integers ℤ and rationals ℚ under ordering are elementarily equivalent (both are dense linear orders without endpoints... actually ℤ is not dense). Better: consider ℝ and a non-archimedean elementary extension — they are elementarily equivalent, but a substructure might fail the Tarski-Vaught test even when the theories agree.

Question 5

State the Tarski-Vaught test for elementary substructures and explain why it is equivalent to the definition M ≺ N.

Model answer: The Tarski-Vaught test: M ≺ N if and only if for every formula ∃y φ(ā, y) with parameters ā from M, whenever this formula is true in N, there exists b ∈ M with N ⊨ φ(ā, b). This is equivalent to M ≺ N because the only way a formula can be true in N but false in M is if some existential witness needed in N is missing from M. By closing M under Skolem witnesses — adding elements of N that witness existential formulas over current M-parameters — you build an elementary substructure. The test makes the inductive step precise: truth of quantified formulas propagates correctly between M and N exactly when existential witnesses in N can always be found in M.

The Tarski-Vaught test is the practical engine behind the downward Löwenheim-Skolem theorem. Given any infinite structure N and a subset X ⊆ N, you iteratively close X under witnesses: whenever ∃y φ(ā, y) is true in N with ā from the current set, add a witness. The closure is countable if X and the language are countable, and the resulting set is the domain of an elementary substructure M ≺ N. This shows that any infinite structure has an elementary submodel of any infinite cardinality ≥ the language's size.