Notes - Logic and Proof MT24, Algebraically closed fields

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.

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)\]

Suppose:

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

Then there exists $a \in F$ with $f(a) \ne 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 \mathbb Z$ 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}\]

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 on-zero polynomial $h \in F[y]$, there exists $a \in F$ with $h(a) \ne 0$. Then:

\[\pmb T_\text{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)\]

and so the quantifier has been eliminated.

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$. 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 the result that says

Suppose:

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

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

we have

\[\begin{aligned} & \pmb T_\text{ACF} \\ \models& \exists y (f(\pmb x, y) = 0 \land g(\pmb x, y) \ne 0) \\ \leftrightarrow& [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}\]

Note that

\[\exists y:\bigwedge^m_{i = 1} g_i(\pmb x, y) \ne 0 \equiv \exists y: \prod^m_{i = 1}g(\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 $m \ge 2$ and $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) + 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^e f _ 2 = q f _ 1 + r$ 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(r(\pmb x, y) = 0 \land \bigwedge^m_{i = 2} f_i(\pmb x, y) = 0 \land g(\pmb x, y) \ne 0\right) \right]\]

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.