Tarski–Seidenbergの定理

量化記号消去 ⇒ 射影定理。$S\subset R^{n+1}$ を半代数的集合とすると、量化記号のない論理式 $\Phi(X_1,\dots,X_{n+1})$ で $S=\mathrm{Real}(\Phi)$ となるものがある。$\pi(S)=\mathrm{Real}\bigl((\exists X_{n+1})\Phi\bigr)$ であり、量化記号消去により、これは量化記号のない論理式の $\mathrm{Real}$、すなわち半代数的集合である。
射影定理 ⇒ 量化記号消去。論理式の構成についての帰納法で、$\mathrm{Real}(\Phi)$ が（$D$ の上で定義される）半代数的集合であることを示す。そうなれば、標準形により $\mathrm{Real}(\Phi)$ は量化記号のない論理式の $\mathrm{Real}$ なので、$\Phi$ はそれと同値である。原子論理式なら定義から半代数的である。$\wedge,\vee,\neg$ については、半代数的集合の族が共通部分・和・補集合で閉じていることによる。$(\exists X)\Phi$ については、変数の番号を付け替えて $X$ を最後の変数 $X_{k+1}$ とすれば、$\mathrm{Real}\bigl((\exists X)\Phi\bigr)=\pi\bigl(\mathrm{Real}(\Phi)\bigr)$ であり、帰納法の仮定と射影定理により半代数的である。$(\forall X)\Phi$ は $\neg(\exists X)\neg\Phi$ と同値なので、補集合と射影の場合に帰着する。$\square$

要点：$P$ を $(X-a)^m(X-b)^nQ$ と因数分解して $P'$ の余因子の端点での符号を比べ、多項式の中間値の定理を使う。2 と 3 は 1 から従う。

$h=b\bigl(X^e+\sum_{j< e}\beta_jX^j\bigr)$ とし、$M:=1+2\sum_{j< e}\lvert\beta_j\rvert$ とおく。$\lvert x\rvert>M$ なら $\lvert x\rvert>1$ なので $\bigl\lvert\sum_{j< e}\beta_jx^{j-e}\bigr\rvert\le\sum_j\lvert\beta_j\rvert/\lvert x\rvert< 1/2$ であり、$h(x)=bx^e\bigl(1+\sum_{j< e}\beta_jx^{j-e}\bigr)$ の符号は $bx^e$ の符号に等しい。$\square$

要点：$p$ についての帰納法。$P'$ の符号の列を固定した集合が開区間なら、その上で $P$ は狭義単調なので、$P$ の符号でさらに切っても空・1 点・開区間のどれかにしかならない。

符号の列が等しいとすると、$x,x'$ は同じ $\sigma$（$\sigma_0=0$）の $\mathrm{Real}(\sigma)$ に属する。lem-tarski-seidenberg-thom によりこれは 1 点か開区間であり、開区間なら $P$ がその上で恒等的に $0$ となって $P\ne0$ に反する。よって 1 点であり、$x=x'$ である。$\square$

$F^\flat$ の符号表の行を、$f_1,\dots,f_{s-1}$、$f_s'$、$g_1,\dots,g_s$ の順に並べておく。以下の段 0〜5 で、$F$ の符号表の各項目が $F^\flat$ の符号表だけから読み取れることを示す。各段で読み取る手順は $R$ にも $F$ にもよらないので、それを $\Gamma_s$ と定めればよい。$\deg f_s=d\ge1$ で $R$ の標数は $0$ なので $f_s'\ne0$ である。
段 0（零多項式）。$f_i=0$ であることと、$F^\flat$ の符号表の $f_i$ の行がすべて $0$ であることは同値である（零でない多項式は区間 $I_0$ に根をもたないので、そこで $0$ でない符号をとる）。
段 1（区切りの点）。$F^\flat$ の符号表の根 $y_1< \cdots< y_M$ のうち、零でないある $f_i$（$i< s$）または $f_s'$ の符号が $0$ になるものを $z_1< \cdots< z_L$ とする。これは零でない $f_1,\dots,f_{s-1}$ と $f_s'$ の根の全体であり（それらは $F^\flat$ の成分なので、根はすべて $y_j$ に現れる）、どの $y_j$ がそれに当たるかは表から読める。$z_0:=-\infty$、$z_{L+1}:=+\infty$、$J_l:=(z_l,z_{l+1})$ とおく。
段 2（区切りの点での $f_s$ の符号）。$z_l$ が $f_i$（$i< s$、$f_i\ne0$）の根なら、割り算 $f_s=q_if_i+g_i$ に代入して $f_s(z_l)=g_i(z_l)$ である。$z_l$ が $f_s'$ の根なら、同様に $f_s(z_l)=g_s(z_l)$ である。よって $\operatorname{sign}f_s(z_l)$ は $g_i$ または $g_s$ の行から読める。
段 3（区切りの間）。各 $J_l$ は $F^\flat$ の符号表の連続するいくつかの点と区間の和であり、少なくとも 1 つの区間を含む。$J_l$ には $f_s'$ と零でない $f_i$（$i< s$）の根がないので、それらの $J_l$ 上の符号は一定で、$J_l$ に含まれる区間の列から読める。特に $\tau_l:=\operatorname{sign}f_s'(J_l)\in\{1,-1\}$ が読め、lem-tarski-seidenberg-monotone により $f_s$ は $J_l$ の閉包の上で、$\tau_l=1$ なら狭義単調増加、$\tau_l=-1$ なら狭義単調減少である。
段 4（区切りの間の $f_s$ の根）。$J_l$ の左端での符号 $\varepsilon_l^-$ を、$l\ge1$ なら $\operatorname{sign}f_s(z_l)$（段 2）、$l=0$ なら $f_s$ の $-\infty$ での符号とし、右端での符号 $\varepsilon_l^+$ を同様に定める。$f_s$ の $\pm\infty$ での符号は、lem-tarski-seidenberg-infinity の後の注意により、$f_s'$ の行の最初の列の符号を反転したもの、最後の列の符号に等しいので、表から読める。このとき次が成り立つ。
(★) $f_s$ は $J_l$ に高々 1 つの根をもち、根をもつことは $\varepsilon_l^-\varepsilon_l^+=-1$ と同値である。
高々 1 つであることは狭義単調性による。$\varepsilon_l^-=-1$、$\varepsilon_l^+=1$ とする（逆の場合も同じ）。左端が有限なら、$f_s(z_l)< 0$ と連続性から、$z_l$ の十分近くの $u\in J_l$ で $f_s(u)< 0$ となる。左端が $-\infty$ なら、$f_s$ のどの根よりも小さい $u\in J_l$ で $f_s(u)< 0$ となる。同様に $u< v\in J_l$ で $f_s(v)>0$ となるものがとれ、中間値の定理により $(u,v)$ に根がある。逆に根 $r\in J_l$ があり、たとえば $\tau_l=1$ とすると、$J_l$ の閉包の上の狭義単調増加性から、左端が有限なら $f_s(z_l)< f_s(r)=0$、左端が $-\infty$ なら $r$ より小さいすべての点で $f_s< 0$ なので、$\varepsilon_l^-=-1$ である。同様に $\varepsilon_l^+=1$ で、積は $-1$ である。$\tau_l=-1$ でも同じである。
段 5（組み立て）。$F$ の成分の根は、零でない $f_i$（$i< s$）の根と $f_s$ の根である。前者は $z_l$ のうち段 1 でそれと分かるもの、後者は $z_l$ のうち段 2 で $\operatorname{sign}f_s(z_l)=0$ となるものと、段 4 で根をもつと分かった $J_l$ のただ 1 つの根 $r_l$ である。$r_l$ は $J_l$ の内部にあり、ほかの根はすべて $z$ の点か別の $J$ の中にあるので、$F$ の根の個数 $N$ と並び順が決まる。各根と各区間での符号は次のように読める。

• $f_i$（$i< s$）：$z_l$ での符号は表にある。$r_l$ での符号と、$J_l$ の部分区間での符号は、段 3 の $J_l$ 上の一定の符号である。
• $f_s$：$z_l$ での符号は段 2、$r_l$ では $0$ である。$J_l$ が根 $r_l$ をもつなら、$r_l$ の左で $-\tau_l$、右で $\tau_l$ である。根をもたないなら $J_l$ 上で一定の $0$ でない符号をとり、それは $\varepsilon_l^-\ne0$ なら $\varepsilon_l^-$（左端の近くの符号）、$\varepsilon_l^-=0$ なら $\tau_l$（$0$ から増加または減少する）である。
  $F$ の符号表の各区間は、いくつかの $J_l$ の部分区間と $z$ の点からなり、その上で各成分の符号は一定なので、上のどれか 1 つから読めばよい。以上で $\mathrm{SIGN}_R(F)$ のすべての項目が $\mathrm{SIGN}_R(F^\flat)$ から読み取れた。$\square$

まず、$R$ の順序は $R'$ の順序の制限である。実際、$c\in R$ が $R$ で正なら $c$ は $R$ の $0$ でない元の平方（実閉体 の系「順序の一意性」）なので、$R'$ でも正である。負の元についても同様である。
1 を、列の成分の次数の組 $(d,m)$ についての帰納法で示す。成分がすべて定数なら、どちらの符号表も $N=0$ で、定数の符号は $R$ と $R'$ で一致する。そうでなければ、次数最大の成分を最後に並べ替え（符号表の行も同じく並べ替わる）、thm-tarski-seidenberg-reduction の $F^\flat$ を作る。微分と割り算の余りは $R[X]$ の中で計算され、$R'[X]$ で計算しても同じ多項式になるので、$F^\flat$ は $R$ と $R'$ で共通であり、$(d,m)$ は真に小さい。帰納法の仮定と定理から
$$ \mathrm{SIGN}_R(F)=\Gamma_s\bigl(\mathrm{SIGN}_R(F^\flat)\bigr)=\Gamma_s\bigl(\mathrm{SIGN}_{R'}(F^\flat)\bigr)=\mathrm{SIGN}_{R'}(F) $$
である。2 は、符号表の直後の注意（$(\exists X)\Phi$ の真偽は $\Phi$ と符号表で決まる）と 1 から従う。$\square$

1. $f\colon A\to B$（$A\subset R^n$、$B\subset R^m$）を半代数的写像、$A'\subset A$ を半代数的集合とする。$f(A')$ は $\Gamma_f\cap(A'\times R^m)$（半代数的）を最後の $m$ 座標へ射影したものなので、thm-tarski-seidenberg-projection を繰り返し使えば半代数的である。$g\colon B\to C$（$C\subset R^p$）も半代数的なら、$\Gamma_{g\circ f}$ は $(\Gamma_f\times R^p)\cap(R^n\times\Gamma_g)$ から真ん中の $m$ 座標を消す射影の像なので、半代数的である。
2. $A=\mathrm{Real}(\Psi)$ となる量化記号のない論理式 $\Psi$ をとる。$R^n$ の直積位相では、点 $x$ の近傍の基本系として $\{y\mid\sum_i(x_i-y_i)^2< \varepsilon\}$（$\varepsilon>0$）をとれる（一辺 $2\delta$ の開箱は $\varepsilon=\delta^2$ の球を含み、$\varepsilon$ の球は $\delta^2=\varepsilon/n$ の開箱を含む。$\delta$ は実閉体の中にある）。よって
   $$ \overline A=\mathrm{Real}\Bigl((\forall E)\bigl(E>0\Rightarrow(\exists Y_1)\cdots(\exists Y_n)(\Psi(Y)\wedge E-\textstyle\sum_i(X_i-Y_i)^2>0)\bigr)\Bigr) $$
   であり（$\Phi\Rightarrow\Psi$ は $\neg\Phi\vee\Psi$ の略記）、thm-tarski-seidenberg-qe により半代数的である。内部は補集合の閉包の補集合である。$\square$