Questions: Extension Lemmas and Back-and-Forth Methods

Question 1

In the back-and-forth construction between structures 𝔄 and 𝔅, what is the specific role of the 'back' step, and what goes wrong if only 'forth' steps are performed?

• A. The back step extends the map to cover new elements of 𝔄; without it, the construction only embeds 𝔅 into 𝔄 rather than 𝔄 into 𝔅
• B. The back step ensures every element of 𝔅 eventually receives a preimage in 𝔄; without it, the result is only an elementary embedding of 𝔄 into 𝔅 — injective but not surjective, so not an isomorphism
• C. The back step corrects errors in the forth step by re-mapping elements that were matched incorrectly
• D. The back step is a redundancy built into the method; omitting it produces the same isomorphism more efficiently

Answer: (B)

The forth steps extend the partial map by matching elements of 𝔄 to elements of 𝔅, ensuring every element of 𝔄 eventually maps somewhere — this gives injectivity. But without back steps, elements of 𝔅 may have no preimage: the map covers all of 𝔄 but may miss parts of 𝔅. Back steps alternate the direction of extension, matching elements of 𝔅 to elements of 𝔄, guaranteeing surjectivity. An injective-but-not-surjective elementary map is an embedding, not an isomorphism. The name 'back-and-forth' directly names this bidirectional alternation that purchases both injectivity and surjectivity.

Question 2

The back-and-forth method proves that any two countable dense linear orders without endpoints are isomorphic. At each step, when extending the partial map to include a new rational number, which property of ℚ is essential for guaranteeing a matching element always exists?

• A. ℚ is Archimedean — every rational number has a rational upper bound
• B. ℚ is dense — between any two rationals there is another rational, so any finite ordering constraint can be satisfied
• C. ℚ is Cauchy-complete — every Cauchy sequence of rationals converges in ℚ
• D. ℚ is well-ordered — every nonempty subset of ℚ has a least element

Answer: (B)

At each step of the construction, we need to insert a new element that fits correctly between the already-matched elements — it must be greater than some and less than others according to the partial isomorphism. Density guarantees this: between any two rationals (or below all of them, or above all of them, since ℚ has no endpoints) there is always another rational. This is precisely the extension lemma at work in this specific structure. Completeness (option C) is a different and stronger property — in fact, ℝ is complete but ℚ is not. The categoricity of the dense linear order without endpoints depends on density and the absence of endpoints, not on completeness.

Question 3

In the back-and-forth construction, the back step ensures that every element of the target structure 𝔅 eventually acquires a preimage in 𝔄 under the constructed map, guaranteeing the final bijection is surjective.

• T. True
• F. False

Answer: True

This is the definitional purpose of back steps. At each back step, we choose an element of 𝔅 not yet in the image of the current partial map and use the extension lemma to find a matching element in 𝔄 — adding it to the domain of the partial map. Since the construction is countably infinite and both structures are countable, every element of 𝔅 is addressed in a back step at some finite stage. Combined with the forth steps ensuring every element of 𝔄 is in the domain, the limit map is a bijection that is elementary in both directions — a full isomorphism.

Question 4

The back-and-forth method can construct an isomorphism between any two elementarily equivalent structures, regardless of their cardinality.

• T. True
• F. False

Answer: False

The back-and-forth method as usually presented requires both structures to be countable: the construction proceeds through countably many stages, each adding one element, and this enumeration exhausts both structures only when they are countable. For uncountable structures, the method as stated fails — you cannot cover an uncountable structure in countably many steps. The method extends to uncountable structures under additional conditions: if both structures are κ-saturated (for an appropriate cardinal κ), transfinite back-and-forth arguments work. But elementary equivalence alone is insufficient — elementarily equivalent structures need not be isomorphic even in the countable case if they lack homogeneity.

Question 5

What role does the extension lemma play in the back-and-forth method, and what property of the target structure does it rely on to guarantee each step succeeds?

Model answer: The extension lemma is the engine that makes each individual step of the construction possible. At each forth step, we have a partial elementary map defined on a finite subset of 𝔄, and we need to extend it to include one new element a ∈ 𝔄. This requires finding an element b ∈ 𝔅 that realizes the same complete type over the current image as a realizes over the current domain — i.e., b satisfies all the same first-order formulas with parameters from the image that a satisfies with parameters from the domain. The extension lemma guarantees such a b exists when 𝔅 is sufficiently homogeneous or saturated: every type realized in 𝔄 over a finite set can also be realized in 𝔅 over the corresponding image. Without this property, some step might fail — there might be no suitable matching element — and the construction would halt before covering all of 𝔄 or 𝔅.

The connection to Ehrenfeucht-Fraïssé games is direct: each back-and-forth step corresponds to one round of the EF game, and the extension lemma corresponds to the winning strategy for the Duplicator player. The back-and-forth method is the algebraic version of the game — it constructs the isomorphism explicitly rather than proving existence by winning the game abstractly.