# Notes - Logic and Proof MT24, Algebraically closed fields

> Source: https://ollybritton.com/notes/uni/part-b/mt24/logic-and-proof/notes/algebraically-closed-fields/ · Updated: 2025-06-11 · Tags: uni, notes

- [Course - Logic and Proof MT24](https://ollybritton.com/notes/uni/part-b/mt24/logic-and-proof/)

### Flashcards
Consider a field described by a $\sigma$-structure $\mathcal F = (F, +^\mathcal F, \cdot^\mathcal F, 0^\mathcal F, 1^\mathcal F)$ and the field axioms. @Describe the notational convenience used for the terms and the atomic formulas.::

Consider terms as polynomials with non-negative integer coefficients, i.e. $(x + (y + 1)) + x$ can be written as $2x + y + 1$.

Consider atomic formulas as $p(\pmb x) = 0$ where $p$ is a polynomial with integer coefficients.

#### Pseudo-division
@State a result which lets you almost do division with remainder in a polynomial ring with coefficients in an integral domain (as opposed to a field).::

Suppose:

- $R$ is an integral domain
- $f, g \in   R[x]$
- $\deg(f) \le \deg(g)$
- $c$ is the leading coefficient of $f$
- $d = \deg(g) - \deg(f) + 1$

Then there exists unique $q, r \in R[x]$ such that
$$
c^d g = qf + r
$$
and
$$
\deg(r) < \deg(f)
$$

#### Quantifier elimination
When performing quantifier elimination for algebraically closed fields, the simplest "base case" is a formula like this:
$$
\exists a (f(a) = 0 \land g(a) \ne 0)
$$
@State a proposition which helps you eliminate the quantifier in this case.::

Suppose:

- $F$ is an algebraically closed field
- $f, g \in F[y]$ are non-constant polynomials
- $r \in F[y]$ is the remainder from dividing $g^{\deg(f)}$ by $f$ in $F[y]$.

Then there exists $a \in F$ with $f(a) = 0$ and $g(a) \ne 0$ if and only if $r$ is not identically zero.

When performing quantifier elimination for algebraically closed fields, the simplest "base case" is a formula like this:
$$
\exists a (f(a) = 0 \land g(a) \ne 0)
$$
@Prove that if:

- $F$ is an algebraically closed field
- $f, g \in F[y]$ are non-constant polynomials
- $r \in F[y]$ is the remainder from (pseudo) dividing $g^{\deg(f)}$ by $f$ in $F[y]$.

Then there exists $a \in F$ with $f(a) = 0$ and $g(a) \ne 0$ if and only if $r$ is not identically zero.::

Since $\mathcal F$ is algebraically closed, $f$ splits into linear factors
$$
f = c(y - \alpha_1)^{v_1} \cdots (y - \alpha_s)^{v_s}
$$
where $c \in F$ and $\alpha_1, \ldots, \alpha_s$ are distinct roots of $f$, with $\alpha_i$ having multiplicity $v_i$. Then
$$
\begin{aligned}
&\exists a (f(a) = 0 \land g(a) \ne 0) \\
\iff& \exists 1 \le i \le s : g(\alpha_i) \ne 0 \\
\iff& \exists 1 \le i \le s : (y - \alpha_i) \not\mid g \\
\iff& \exists 1 \le i \le s : (y - \alpha_i)^{v_i} \not\mid g^{\deg(f)} \\
\iff& f \not\mid g^{\deg f} \\
\iff& r \ne 0
\end{aligned}
$$

@Prove that given $f, g \in \mathbb Z[x, y]$ and a formula $\exists y (f(\pmb x, y) = 0 \land g(\pmb x, y) \ne 0)$ over an algebraically closed field, there is an equivalent quantifier-free formula.::

**General idea**: Induct on the degree of $y$ in $f$. If $f$ doesn't mention $y$, then the only thing we need to check is that $g$ is non-zero. If $f$ does mention $y$, split up the highest-degree term from $f$. By induction we have a quantifier elimination procedure for the lower-degree terms, so we just need to check whether we can make the highest-order term zero and $g(\pmb x, y)$ non-zero simultaneously. If we were in a field, this could be done by checking remainders, but since we are only in a ring we use pseudo-division instead.

---

Consider the polynomial ring
$$
R := \mathbb Z[x]
$$
Treat $f, g$ as univariate polynomials in $R[y]$ and write $\deg(f)$ and $\deg(g)$ for the respective degrees of $f$ and $g$ in variable $y$.

Induct on $\deg(f)$.

**Base case**: $\deg (f) = 0$

Then $f$ does not mention $y$. Write
$$
g(\pmb x, y) = \sum^d_{i = 0} c_i(\pmb x) y^i
$$
where $c_0, \ldots, c_d \in R$.

Since every algebraically closed field $F$ is infinite, for every non-zero polynomial $h \in F[y]$, there exists $a \in F$ with $h(a) \ne 0$. Then:
$$
\begin{aligned}
\pmb T_\mathrm{ACF} &\models \exists y (f(\pmb x) = 0 \land g(\pmb x, y) \ne 0) \\
&\leftrightarrow (f(\pmb x) = 0 \land \bigvee^d_{i = 0} c_i(\pmb x) \ne 0)
\end{aligned}
$$
and so the quantifier has been eliminated. Here we've used the fact that $g$ can be made non-zero unless all the coefficients are identically zero.

**Inductive step**: $\deg (f) > 0$.

Write $f(\pmb x, y) = f_0(\pmb x) y^d  + f_1(\pmb x, y)$ where $\deg (f_1) \le d-1$.

Recall pseudo-division (∆pseudo-division). Let $r(\pmb x, y) = \sum^{d-1}_{i = 0} b_i(\pmb x) y^i$ be the pseudo-remainder of $g^d$ divided by $f$ in $R[y]$ (note that $\deg(g^d) \ge \deg(f)$, so pseudo division is allowed).

Note that for any valuation $\pmb v$ in $F$ of variables $\pmb x$, $r(\pmb v, y)$ is identically zero iff the remainder when dividing $g^d(\pmb v, y)$ by $f(\pmb v, y)$ is zero.

Then by ∆acf-root-nonvanishing-criterion we have
$$
\begin{aligned}
& \pmb T_\mathrm{ACF} \\
\models& \text{ } \exists y (f(\pmb x, y) = 0 \land g(\pmb x, y) \ne 0) \\ \leftrightarrow& \text{ } [f_0(\pmb x) = 0 \land \exists y(f_1(\pmb x, y) = 0 \land g(\pmb x, y) \ne 0)] \lor [f_0(\pmb x) \ne 0 \land \bigwedge^{d-1}_{i = 0} b_i \ne 0]
\end{aligned}
$$

(Why is it necessary to split into the two cases $f_0(\pmb x) = 0$ and $f_0(\pmb x) \ne 0$? Although $\deg f(\pmb x, y) > 0$ implies that $f_0(\pmb x)$ is not identically zero, whether this formula is true or not depends on the free variables of the formula: it could be the case that a particular assignment to the free variables makes $f_0(\pmb x)$ vanish, and this is the case that we have to handle separately).

We have a result (∆acf-quantifier-elimination-step-proof) that says: given $f, g \in \mathbb Z[x, y]$ and a formula $\exists y (f(\pmb x, y) = 0 \land g(\pmb x, y) \ne 0)$ over an algebraically closed field, there is an equivalent quantifier-free formula.

This result is only about a conjunction of two polynomials. In an arbitrary formula in the theory of algebraically closed fields we need to perform quantifier elimination on formulas
$$
\exists y:  \bigwedge^m_{i = 1} f_i(\pmb x, y) = 0 \land  \bigwedge^m_{i = 1} g_i(\pmb x, y) \ne 0
$$

@Prove that the above result implies that the theory of algebraically closed fields actually has quantifier elimination.::

**Overall idea**: We can turn conjunctions of $g_i(\pmb x, y) \ne 0$ into just one polynomial by taking their product, but still have to deal with conjunctions of $f_i(\pmb x, y) = 0$ in full. Induct on the sum of degrees of $f_i$, and order the polynomials in increasing order of degree $f_1, f_2, \ldots$. Then (splitting up by whether the coefficient of $y^d$ is zero), the pseudo dividing $f_2$ by $f_1$ gives a relationship which can be used to write an equivalent formula with the terms having smaller degree.

---

Note that
$$
\exists y:\bigwedge^m_{i = 1} g_i(\pmb x, y) \ne 0 \equiv \exists y: \prod^m_{i = 1}g_i(\pmb x, y)  \ne 0
$$
Hence it suffices to eliminate the quantifier $\exists y$ from formulas in the form
$$
\exists y \left(
\bigwedge^m_{i = 1} f_i(\pmb x, y) = 0 \land g(\pmb x, y) \ne 0
\right)
$$
Consider $f$ and $g$ as elements of the univariate polynomial ring $R[y]$ where $R := \mathbb Z[x]$. Let $\deg f$ denote the degree of $f$ in the variable $y$.

Induct on $\sum^m_{i = 1} \deg(f_i)$.

**Base case**: $m = 1$

This case is handled by the above proposition.

**Inductive step**: $m > 1$.

Suppose $0 < \deg (f_1) \le \cdots \le \deg (f_m)$. Write
$$
f_1(\pmb x, y) = a_d(\pmb x) y^d + \cdots + a_1 (\pmb x) y + a_0 (\pmb x)
$$
and
$$
h(\pmb x, y) := a_{d-1}(\pmb x) y^{d-1} + \cdots + a_1(\pmb x)y + a_0(\pmb x)
$$
obtained by dropping the leading term of $f_1$.

Pseudo dividing $f_2$ by $f_1$ in $R[y]$ gives $(a_d(\pmb x))^e f_2(\pmb x, y) = q f_1(\pmb x, y) + r(\pmb x, y)$ where $e = \deg (f_2) - \deg (f_1) + 1$ and $\deg (r) < \deg (f_1)$. But then
$$
\exists y \left(
\bigwedge^m_{i = 1} f_i(\pmb x, y) = 0 \land g(\pmb x, y) \ne 0
\right)
$$
is equivalent to the formula
$$
\left[
a_d(\pmb x) = 0 \land \exists y \left( h(\pmb x, y) = 0 \land \bigwedge^m_{i = 2} f_i(\pmb x, y) = 0 \land g(\pmb x, y) \ne 0 \right)
\right] \lor \left[
a_d(\pmb x) \ne 0 \land \exists y \left(f_1(\pmb x, y) = 0 \land r(\pmb x, y) = 0 \land \bigwedge^m_{i = 3} f_i(\pmb x, y) = 0 \land g(\pmb x, y) \ne 0\right)
\right]
$$

- Case 1 says that if $a_d(\pmb x) = 0$, then we can instead apply quantifier elimination to $h(\pmb x, y)$ rather than the full $f_1(\pmb x, y)$.
- Case 2 says that if $a_d(\pmb x) \ne 0$, since $a_d^e f_2 = q f_1 + r$, once $f_1 = 0$ we have $f_2 = 0$ iff $r = 0$, so we can swap $f_2$ for the lower-degree $r$.

(Why is it necessary to split into the two cases $a_d(\pmb x) = 0$ and $a_d(\pmb x) \ne 0$? Although $\deg f_1(\pmb x, y) > 1$ implies that $a_d(\pmb x)$ is not identically zero, whether this formula is true or not depends on the free variables of the formula: it could be the case that a particular assignment to the free variables makes $a_d(\pmb x)$ vanish, and this is the case that we have to handle separately).

Since the above formula is a boolean combination of formulas that either don't mention $y$ or have the same form as the original but with a smaller induction parameter, by the inductive hypothesis, the result follows.

#### Examples
Compute the pseudo-remainder when
$$
g(x, y) = x^2 y^3 - y
$$
is divided by $f(x, y) := x^3 y - 2$ where $f, g$ are considered as polynomials in $y$ with coefficients in $\mathbb Z[x]$.::

- Multiply $g$ by the leading coefficient of $f$ to the power of $\deg(g) - \deg(f) + 1$
- In this case, the leading coefficient is $x^3$ and the power is $3$
- Dividing $x^9 g$ by $f$ in $R[y]$ gives quotient $x^8 y^2 + 2x^5 y + 4x^2 - x^6$ with remainder $8x^2 - 2x^6$

@sheets~ @example~

Given that when
$$
g(x, y) = x^2 y^3 - y
$$
is pseudo-divided by
$$
f(x, y) = x^3 y - 2
$$
where $f, g$ are considered as polynomials in $y$ with coefficients in $\mathbb Z[x]$, we have quotient
$$
x^8 y^2 + 2x^5 y + 4x^2 - x^6
$$
and remainder
$$
8x^2 - 2x^6
$$
Find a quantifier-free formula equivalent to
$$
\exists y (x^3 y - 2 = 0 \land x^2 y^3 - y \ne 0)
$$
over every algebraically closed field.::

We can satisfy $f = 0 \land g \ne 0$ iff the pseudo remainder when $g$ is divided by $f$ is non-zero. Hence we have
$$
8x^2 - 2x^6 \ne 0
$$
or, equivalently,
$$
x \ne 0 \land 4 - x^4 \ne 0
$$

@sheets~ @example~

---
Olly Britton — https://ollybritton.com. Machine-readable index: https://ollybritton.com/llms.txt