Questions: Applications to Ordered and Algebraically Closed Fields

Question 1

In the theory ACF (algebraically closed fields), quantifier elimination means that every first-order definable subset of ℂⁿ is:

• A. A finite set or the complement of a finite set
• B. A Boolean combination of algebraic varieties (a constructible set)
• C. An open set in the Zariski topology
• D. Impossible to describe without invoking existential quantifiers

Answer: (B)

Quantifier elimination means every formula is equivalent to a quantifier-free one. In ACF the atomic formulas are polynomial equations, so quantifier-free formulas define Boolean combinations of zero sets of polynomials — precisely constructible sets. Option A describes merely algebraically closed fields being strongly minimal (every definable set is finite or cofinite in one variable); that is a consequence, not the full geometric picture. Option C is too weak: Zariski-open sets are definable, but so are their complements and intersections.

Question 2

The Tarski-Seidenberg theorem implies that if S ⊆ ℝⁿ is a semialgebraic set and π: ℝⁿ → ℝᵐ is a polynomial map, then π(S) is:

• A. An algebraic variety (zero set of polynomials)
• B. Semialgebraic — a finite Boolean combination of polynomial equations and inequalities
• C. Semialgebraic only when π is linear
• D. Not necessarily definable in any first-order language

Answer: (B)

This closure-under-projection property is exactly what quantifier elimination gives: the image of a semialgebraic set under any polynomial map is again semialgebraic. Logically, projecting is existential quantification — 'y = π(x) for some x ∈ S' — and quantifier elimination eliminates that quantifier to leave a quantifier-free (semialgebraic) description. Classical geometry had to prove this directly (Seidenberg's theorem); model theory gives it for free. Option A is too strong: images of semialgebraic sets need not be varieties.

Question 3

The first-order theory of ℝ (RCF) is decidable, while the first-order theory of ℤ is undecidable. This contrast is best explained by:

• T. True
• F. False

Answer: True

Exactly right. RCF admits quantifier elimination and is complete, so every sentence is provably true or provably false — an algorithm checks which. The theory of ℤ encodes enough arithmetic (multiplication and addition over all integers) to represent Gödel's undecidability argument. The key is that ℝ, as a real closed field, lacks the combinatorial complexity of integer arithmetic — there is no way to define 'x is an integer' in the first-order language of ordered fields over ℝ.

Question 4

Since ℤ is a substructure of ℝ and RCF is decidable, the first-order theory of ℤ is also decidable.

• T. True
• F. False

Answer: False

Decidability does not pass down to substructures. A sentence true in ℝ may be false in ℤ — the structures satisfy different theories. RCF's decidability comes from quantifier elimination working over the reals; the integer substructure lacks the field-completeness properties that make this possible. Indeed, the theory of ℤ is undecidable by Gödel's incompleteness theorems, even though ℤ ⊂ ℝ.

Question 5

Explain in your own words what quantifier elimination means for a theory T, and why it is connected to decidability.

Model answer: Quantifier elimination for T means that every first-order formula is provably equivalent (within T) to a formula with no quantifiers — one built only from atomic sentences and Boolean connectives. This matters for decidability because: (1) if T is complete (every sentence is settled by T) and (2) T has quantifier elimination, then to decide any sentence you can reduce it to a quantifier-free sentence whose truth value can be checked mechanically. For ACF and RCF, the quantifier-free formulas involve only polynomial equations and inequalities, which can be evaluated algorithmically.

The key steps are: completeness ensures there is a definite answer to every sentence, and quantifier elimination ensures you can compute that answer by simplifying to a decidable subclass. Without completeness, you might eliminate quantifiers but still face undecidable quantifier-free fragments. Without quantifier elimination, even a complete theory might require searching an infinite proof tree. Together they give decidability.