A logician wants to decide algorithmically whether the first-order sentence 'every element has a square root' holds in all algebraically closed fields of characteristic 0. Which property of ACF makes such algorithmic decision possible?
AThe axiom of choice guarantees root existence in any algebraically closed field
BQuantifier elimination reduces every sentence to a quantifier-free statement, which is evaluable as true or false — giving a decision procedure
CGödel's completeness theorem implies every sentence is provable or refutable in ACF₀
DCategoricity in ℵ₁ means all models agree on truth values of all sentences
Quantifier elimination is the key: every sentence of ACF (a formula with no free variables) reduces to either ⊤ or ⊥, so there is an algorithm that decides any first-order claim. Option C is a confusion — Gödel's completeness theorem says provability and semantic truth coincide, but it does not give a decision procedure. Option D conflates categoricity (models being isomorphic) with completeness (sentences having fixed truth values); both follow from QE but for distinct reasons.
Question 2 Multiple Choice
A student argues: 'Since there are many algebraically closed fields of characteristic 0 — the complex numbers, their elementary extensions of larger cardinality, etc. — the theory ACF₀ cannot be complete: different models might disagree on some sentence.' What is wrong with this reasoning?
AACF₀ is not complete — the student is correct
BCompleteness requires that all models be isomorphic, which fails here, so the argument has a false premise
CCompleteness means every sentence has the same truth value across all models; QE guarantees this even when models are non-isomorphic
DAll algebraically closed fields of characteristic 0 are isomorphic regardless of cardinality, so the premise is false
The student confuses completeness with categoricity. Completeness means every sentence φ is either a theorem or its negation is — equivalently, all models agree on truth values. QE achieves this: every sentence reduces to ⊤ or ⊥ by quantifier-free reasoning, independent of which specific model you pick. Categoricity (models of the same cardinality being isomorphic) is a stronger structural property that also holds in uncountable cardinalities, but it is a separate consequence, not the definition of completeness.
Question 3 True / False
ACF is categorical in most infinite cardinalities: for each infinite cardinal κ and each characteristic, there is exactly one algebraically closed field of cardinality κ up to isomorphism.
TTrue
FFalse
Answer: False
ACF is categorical in every *uncountable* cardinality, but not in ℵ₀. In the countable case, algebraically closed fields of the same characteristic can differ in their transcendence degree over the prime field — e.g., the algebraic closure of ℚ has transcendence degree 0, while the algebraic closure of ℚ(t) has transcendence degree 1. These are non-isomorphic countable algebraically closed fields of characteristic 0. Morley's theorem ensures categoricity above ℵ₀.
Question 4 True / False
The key step in proving quantifier elimination for ACF — eliminating an existential quantifier ∃y from a formula involving polynomials in x and y — uses the fact that every polynomial of degree ≥ 1 over an algebraically closed field has a root.
TTrue
FFalse
Answer: True
Algebraic closure is exactly what makes the resultant argument work. The resultant of a system expresses 'these polynomials have a common root in y' in terms of their coefficients alone (polynomials in x). For this to correctly characterize satisfiability, you need the field to contain roots whenever the resultant condition is met — which algebraic closure guarantees. Over non-algebraically closed fields like ℝ, the same argument fails because the polynomial x² + 1 has no real root, and no quantifier elimination is possible for the full first-order theory.
Question 5 Short Answer
Why does quantifier elimination imply decidability for ACF, and why would QE alone not give decidability for a theory with infinitely many complete extensions?
Think about your answer, then reveal below.
Model answer: QE reduces every sentence (formula with no free variables) to a quantifier-free sentence. With no variables left, a quantifier-free sentence is just a Boolean combination of equalities between constants — computable as true or false. So every ACF sentence is decided: you run the QE algorithm, read off ⊤ or ⊥. If a theory had infinitely many complete extensions (different truth-value assignments to sentences), QE would still work within each extension, but you'd need to know which extension you're in before deciding. ACF is special because fixing the characteristic pins down a unique complete extension — so the decision procedure needs no further input.