数理解析研究所講究録 1217 巻 2001 年 98-120

98

2 階算術における実数と複素数
東北大学大学院理学研究科数学専攻
坂本伸幸 (SAKAMOTO, Nobuyuki)
田中一之 (TANAKA, Kazuyuki)
概要
本論文は,における実数, 複素数の取り扱い, 特に, シンプソン・田中・山崎のメタ定理 [6] に関連する話題を中心としたものである. この定理は,実閉体 (代数閉体) の理論の定理がにおける実数 (複素数) に関して或り立つことを主張するものである. 第 1 節では 2 階算術, 逆数学の基礎の概説をおこなう. 第 2 節では,において実数の集まりが実閉体になるという定理を紹介する. 実は, この定理の強化版がまだ未解決であるのだが, 解決の足がかりとして, 条件を弱めることによって強化版の部分的解決を試みる. また,
この定理とも密接に関係する, 代数学の強基本定理をで証明する. これは, 定数でない複素係数多項式の重複を込めた根全体の存在を主張する定理である. 第 3 節では, より強い集合存在公理を必要とする実数の性質を見る. また, 上の未解決問題がより強い集合存在公理を仮定すれば証明可能であることを見る.
$\mathrm{R}\mathrm{C}\mathrm{A}_{0}$$\mathrm{R}\mathrm{C}\mathrm{A}_{0}$$\mathrm{R}\mathrm{C}\mathrm{A}_{0}$$\mathrm{R}\mathrm{C}\mathrm{A}_{0}$12 階算術と実数
2 階算術とは, 自然数と自然数からなる集合を対象とした理論である.

この理論

がほぼ数学全般の土台になりうることはかなり昔から知られてぃる. 例えぼ, 有理数の可算列を考えることによって実数を取り扱うことができ, 実数の可算列を考えることによって実数から実数への連続関数を扱える.
この理論を用いて, 個々の数学の定理の証明に必要な公理は何がを調べようとい

うのが「逆数学」である. より詳しく言えば, 逆数学とは,$\mathrm{R}\mathrm{C}\mathrm{A}_{0}$という体系をもとにして, ある数学の定理の証明に必要十分な集合存在公理を求めようというプログラムである.

本節では, 実数の議論に必要な 2 階算術の基礎知識について説明する.

99

1.1

2 階算術

まず, 2 階算術の説明を簡単に行う. 2 階算術の詳細につぃては [5] を参照.
定義 LL1$(\mathcal{L}_{2})$.

階算術の言語$2$

は, 数変数 $x,$ $y,$ $z,$$\mathcal{L}_{2}$$\ldots$と集合変数 $X,$$\mathrm{Y},$$Z,$ $\ldots$を持つ 2 領域言語である. 数項は数変数と定数記号 0, 1 から加法, 乗法にょって得られるものとし, 原子論理式は数項 $s,$ , 集合変数 $X$ によって $s=t,$ $s<t,$ $s\in X$ と$t$表されるものとする. 論理式は原子論理式から命題結合記号$\forall,$$\exists$$\neg,$$\wedge,$$\vee,$\rightarrowと量化記号を用いて構或される.

定義 LL2 (論理式の階層). 量化記号のない論理式 (quantffler free formula,formula) とは, 量化記号$(\forall, \exists)$

含まれる量化記号がすべて$\forall x$形である論理式のこととする.
$\Sigma_{n+1}^{0}$

論理式とは, ある$n0$を含まない論理式のこととする.

くち $\exists x<t$ ( $x$ は数変数,$\Sigma_{0}^{0}$

論理式

$t$

論理式とは,

は $x$ を含まない数項) の論理式のことを 00 論理式,$\varphi(x)$$\Sigma_{0}^{0}$.

$\mathrm{q}.\mathrm{f}$$\Delta_{0}^{0}$

論理式とも呼ぶ.

があって,$\exists x\varphi(x)$と書けるものとする. ただし,
い.

以下同様.

$\varphi(x)$はパラメータ (論理式とは, ある$\Pi_{n+1}^{0}$$\Sigma_{n}^{0}$

論理式

$x$

以外の自由変数) を含んでょ$\varphi(x)$があって,$\forall x\varphi(x)$と書けるものとする.

式のこととする.

$\Sigma_{0}^{1}$

は, ある垣 論理式$n1$$\Sigma_{0}^{1}$

論理式とは, ある自然数

論理式のことを 01 論理式,$\varphi(X)$$n$$\Delta_{0}^{1}$に対して$\Sigma_{n}^{0}$

論理式となる論理

論理式とも呼ぶ.

$\Sigma_{n+1}^{1}$

論理式と

があって,
$\exists X\varphi(X)$と書けるものとする.

$\Pi_{n+1}^{1}$

論理式とは, ある$\Sigma_{n}^{1}$

論理式$\varphi(X)$があって,$\forall X\varphi(X)$と書けるものとする. $i=0,1,j=0,1,$
合をそれぞれ$\Sigma_{j}^{i},$$\Pi_{j}^{i}$で表す. 関係が論理式でも記述できる 1 ことを言う.
1

正確には, 考える体系に依存している$\ldots$$\Delta_{j}^{i}$に対し,$\Sigma_{j}^{i}$

論理式,$\Pi_{j}^{i}$であるとは, この関係が論理式全体の集$\Sigma j$

論理式でも$\Pi \mathrm{j}$.

$\tilde{\pi}\# 1.1.3(\Sigma_{0}^{0}(\Gamma))$)$\Gamma k-\ovalbox{\tt\small REJECT} \mathrm{g}\ovalbox{\tt\small REJECT}.\sigma$$\ovalbox{\tt\small REJECT}_{\mathrm{D}}^{\mathrm{A}}kT$.

100$\Gamma\}_{-}’$

有限量化記号によって結合してできる論理式全体を論理式を$\Sigma_{0}^{0}(\Gamma)$ET$6^{-}\ovalbox{\tt\small REJECT} \mathrm{E}\mathrm{R}^{\backslash }k*_{\tilde{\mathrm{P}}^{\mathrm{B}}}\mathrm{a}\mathrm{f}\mathrm{f}\mathrm{i}_{\mathrm{D}\overline{\overline{\mathrm{Q}}}}^{\mathrm{A}-}-\mathrm{E}\dot{\mathrm{p}}$$\Sigma_{0}^{0}(\Gamma)$

で表す.

$\Sigma_{0}^{0}(\Gamma)$

,

に属する

論理式と呼ぶ.

定義 LL4 (帰納法と有界内包公理).

$\Gamma$

を論理式の集合とする. 次の 4 つの公理図

式を定義する.

:$[\varphi(0)\wedge\forall x(\varphi(x)arrow\varphi(x+1))]arrow\forall x\varphi(x)$$\Gamma$

内包公理):$\exists X\forall i(i\in Xrightarrow\psi(i))$$\Gamma$

内包公理):$\forall n\exists X\forall i(i\in Xrightarrow(i<n\wedge\psi(i)))$

最小値原理):$\exists x\varphi(x)arrow\exists x[\varphi(x)\wedge\forall y<x\neg\varphi(y)]$r-CA($\Gamma$-BCA(有界$\Gamma$

ここに,

-LNP(

$\varphi,$$\Gamma$$\psi\in\Gamma$

定義 LL5で,$(\mathrm{R}\mathrm{C}\mathrm{A}_{0})$

(

帰納法)

$\Gamma- 1\mathrm{N}\mathrm{D}$.

$\Gamma$は $X$ を自由変数として含まない.

$\psi$$\mathrm{R}\mathrm{C}\mathrm{A}_{0}$は言語$\mathcal{L}_{2}$する離散順序半環の公理 (ここに,を持つ体系で, 公理として $(\omega, +, \cdot, 0,1, <)$ &こ関は自然数全体の集合を表す) とと$\Delta_{1}^{0}$

2 個の自然数のペアを 1 個の自然数によってコード化できる.

ペ$\omega$$\Sigma_{1}^{0_{-}}1\mathrm{N}\mathrm{D}$

内包公理$\forall n(\varphi(n)rightarrow\psi(n))arrow\exists X\forall n(n\in Xrightarrow\varphi(n))$($\varphi$は$\Sigma_{1}^{0}$$\mathrm{R}\mathrm{C}\mathrm{A}_{0}$論理式,$\psi$

において,

ア $i,j$ のコードを$s_{0},$$s_{1},$$\ldots,$$s_{n}$

は 01 論理式で $X$ が自由に現れない) を持つ体系とする.

$\langle i,j\rangle$とする. また, 自然数の有限列もコード化できる. 有限列のコードを$\langle s_{0}, s_{1}, \ldots, s_{n}\rangle$

で表す. 有限列のコード全体を Seq で表し,

特に 0, 1 だけからなる有限列のコード全体をドを同一視する.

$s^{\wedge}t$$\mathrm{S}\mathrm{e}\mathrm{q}_{2}$で表す. 以降, 有限列とそのコーで有限列 $s,t$ の結合を表し, (s): で有限列$s$の $i+1$ 番目の要素を表す. すなわち,$s=\langle s_{0}, s_{1}, \ldots, s_{n}\rangle$であるとき,
し,$s[i]$ でどの関係は$\langle$$(s):=s_{i}$ である$(s)_{0},$ $(s)_{1},$$\Sigma_{0}^{0}$$\ldots,$. また,$1\mathrm{h}(s)$で有限列$(s):-1)$ を表すことにする.

$s$の長さを表し,$1\mathrm{h}(s)=n,$$i\leq 1\mathrm{h}(s)$に対. $=n,$ $s^{\wedge}t=u$ な$(s)_{1}$論理式で表現できる. また, 自然数の有限列のコード化は$\forall i\leq n(S:\leq s_{1}’.)\Rightarrow\langle s_{0}, s_{1}, \ldots, s_{n}\rangle\leq\langle s_{0}’, s_{1}’, \ldots, s_{n}’\rangle$

101を成り立たせているとしてよい.

集合 $f$ が$\mathrm{Y}$から $Z$ への関数であるとは,

は

$f$

の元

$\mathrm{Y}$$y$と $Z$ の元

のペア.

$z$

$\langle y, z\rangle$

た

ちからなり,$\forall y\in \mathrm{Y}\exists z\in Z(\langle y, z\rangle\in f)$$\forall x\forall y\forall y’(\langle x, y\rangle\in f\wedge\langle x, y’\rangle\in farrow y=y’)$を満たすことをいう. 関数については, 関数合或が自然にでき, ゼロ関数$\lambda x.\mathrm{O}$, 後継者関数 $\lambda x.x+1$ , 射影関数 $\lambda x_{0}x_{1}\ldots x_{i}.x_{j}(0\leq j\leq i)$ が存在すること, 関数のクラスが原始再帰法, 最小化演算について閉じていることをで証明できるこ$\mathrm{R}\mathrm{C}\mathrm{A}_{0}$とが知られている. 詳しくは [5] を参照のこと.
以下では, 論理式の集合であることを, 単に「$\varphi,$$\psi$

が$\Sigma_{k}^{0}$ならば,$\varphi$

は$\Gamma$$\Gamma$

に対し ,「論理式$\varphi$がある論理式と$\psi\in\Gamma$$\mathrm{R}\mathrm{C}\mathrm{A}_{0}$で同値」

である」 と略記する.
.

$\varphi\wedge\psi,$ $\varphi\vee\psi,$$\exists x<u\varphi$

も$\Sigma_{k}^{0}$であることはよく知られている.

さらに, 次のこともいえる.

定理 1.1.6.

$k$を自然数とし,$\varphi\in\Pi_{k}^{0}$とする.

$\mathrm{R}\mathrm{C}\mathrm{A}_{0}+\Sigma_{k+1}^{0}$-IND において$\forall x<v\exists y\varphi(x, y)arrow\exists u\forall x<v\exists y<u\varphi(x, y)$

が示せ,
証明

$k$

$\Sigma_{k+1}^{0}$

論理式と ($\mathrm{R}\mathrm{C}\mathrm{A}_{0}+\Sigma_{k+1^{-}}^{0}1\mathrm{N}\mathrm{D}$で) 同値になる.

に関する帰納法で証明する.

$k=0$ の場合を示す.

$a<v$ とおく. これは

により

はある

$\forall x<v\exists y\varphi(x, y)$$\forall v\psi(v)$. 特に$\forall x<v\exists y\varphi(x, y)$$\forall x<a\exists y\varphi(x, y)$$\Sigma_{1}^{0}$を仮定する. $\psi(v)\equiv\exists s\forall x<v\exists y<s\varphi(x, y)\vee$

論理式で, $\psi(0)$ と $\psi(v)arrow\psi(v+1)$ がいえるから,$\psi(a)$, すなわち $\exists s\forall x<a\exists y<s\varphi(x, y)$は明らかだから,$\forall x<v\exists y\varphi(x, y)$は$\Sigma_{1}^{0}$.

$\Sigma_{1}^{0}$-IND$\exists u\forall x<v\exists y<u\varphi(x, y)arrow$

論理式 $\exists u\forall x<v\exists y<u\varphi(x, y)$と同値である.
$k>0$ とする.. 前と同じように,$s\varphi(x, y)\vee a<v$法の仮定によりとおく. ここに,$\psi$はある$\Sigma_{k+1}^{0}$$\forall x<a\exists y\varphi(x, y)$を仮定し ,$\psi(v)\equiv\exists s\forall x<v\exists y$$\exists y<s\varphi(x, y)rightarrow\neg(\forall y<s\neg\varphi(x, y))$くだから, f 量納

論理式と同値. 以降は $k=0$ の場合と同様である.

口

帰納法, 有界内包公理, 最小値原理については次のことが知られている.
定理 LL7 (帰納法, 有界内包公理, 最小値原理の同値性). 任意の!こおいて$\Sigma_{k^{-}}^{0}1\mathrm{N}\mathrm{D},$$\Sigma_{0}^{0}(\Sigma_{k}^{0})- \mathrm{I}\mathrm{N}\mathrm{D},$$\Sigma_{k}^{0}$-LNP,$\Sigma_{0}^{0}(\Sigma_{k}^{0})$-LNP,$\Sigma_{k}^{0}$

-BCA,

$k$

$\Sigma_{0}^{0}(\Sigma_{k}^{0})$に対して,$\mathrm{R}\mathrm{C}\mathrm{A}_{0}$-BCA は同値で

102
ここで, 逆数学プログラムで用いられる体系のうち, 本論文に関係するものを紹介する.
定義 L1.8$(\mathrm{W}\mathrm{K}\mathrm{L}_{0}, \mathrm{A}\mathrm{C}\mathrm{A}_{0})$.

に “任意の無限 2 分木$\mathrm{R}\mathrm{C}\mathrm{A}_{0}$ことを表す公理図式を加えた体系を

た体系を

1.2
$\mathrm{R}\mathrm{C}\mathrm{A}_{0}$$\mathrm{A}\mathrm{C}\mathrm{A}_{0}$$\mathrm{W}\mathrm{K}\mathrm{L}_{0}$とする.

$(\subseteq \mathrm{S}\mathrm{e}\mathrm{q}_{2})$$\mathrm{R}\mathrm{C}\mathrm{A}_{0}$は無限道をもつ”に公理図式$\Sigma_{0^{-}}^{1}\mathrm{C}\mathrm{A}$

を加え

とする.

2 階算術における数の取り扱い
における自然数全体の集合, すなわち $x\in Xrightarrow x=x$ なる集合 $X$ を$\mathrm{N}$で表す. 整数, 有理数は自然数で容易に表現できる. 整数は自然数のペアを適当な同値関係で類別したものの代表元全体, 有理数は整数のペアを適当な同値関係で類別したものの代表元全体とすればよい. 整数全体, 有理数全体の集合をそれぞれ乙$\mathbb{Q}$で表す. しかし, 実数, 複素数の取り扱いは簡単ではない.

定義 L2.1 (実数, 複素数).

$\mathrm{R}\mathrm{C}\mathrm{A}_{0}$において, 実数は , 有理数の無限列$\langle q_{k} :k\in \mathrm{N}\rangle$

で,$\forall k\forall i(|q_{k}-q_{k+:}|\leq 2^{-k})$を満たすものとする. 二つの実数$x=\langle q_{k} :k\in \mathrm{N}\rangle,$ $y=\langle q_{k}’ :k\in \mathrm{N}\rangle$の和, 積や$x$のマイナス元が$x+y=\langle q_{k+1}+q_{k+1}’ :k\in \mathrm{N}\rangle$$xy=\langle q_{k+m}+q_{k+m}’$$-x=\langle-q_{k} :: k\in p り

k\in \mathrm{N}\rangle$(ここに, $m$ は $\max(|q_{0}|,$ $|q_{0}’|)+1\leq 2^{m-1}$ となる最小の自然数) で定められる. 一般に, 多変数多項式 , 実数
$t$

$x$

$x_{0},$ $x_{1},$$\ldots,$$x_{n}$

に対し, 実数 $t(x_{0}, x_{1}, \ldots, x_{n})$ の各或分が: たちの或分から和, 積をもちいて得られる. また, 二つの実数$y(x/y)=x(y\neq 0)$ ,$x/0=.0$を成り立たせる $x/y$ が存在することがわかる (命題 1.2.4 参照).
二つの実数

$x=\langle q_{k} :k\in \mathrm{N}\rangle,$$y=\langle q_{k}’$:$k\in \mathrm{N}$に対し ,$x\leq y\equiv\forall k(q_{k}\leq q_{k}’+2^{-k+1})$$x,$ $y$

に対し,

103
と定め,

$x<y\equiv\neg(y\leq x),$ $x=y\equiv(x\leq y\wedge y\leq x)$と定める.

複素数は , 2 個の実数のペア $(x, y)$ とし, 複素数 $c=(x, y),$ $d=(x’, y’)$ に対し加法, マイナス元, 乗法, 除法を$c+d=(x+x’, y+y’)$$-d=(-x’, -y’)$$c\cdot d=(xx’-yy’, xy’+x’y)$$c/d=( \frac{xx’+yy’}{x^{2}+y^{2}}, \frac{x’y-xy’}{x^{2}+y^{2}})$と定める.

$(x, y)$ は $x+y\sqrt{-1}$ を意図している.

定義 L22(無限実数列, 無限複素数列). 集合 $X$ が与えられたとき, 各$i\in \mathrm{N}$に対し,$(X)_{\dot{*}}=\{y|\langle i, y\rangle\in X\}$とおく (この集合は$\Sigma_{0^{-}}^{0}\mathrm{C}\mathrm{A}$により存在).

し $(E)_{i}$ が実数であることとする.

に対し
さ

$l$

$(E)_{i}$

$E$

$E$

が長さ

$l$

の有限実数列であるとは, 任意の $i<l$が実数であることとする. 無限実数列全体を (非公式に)の有限実数列全体を (非公式に)$\mathbb{R}^{l}$

を (非公式に)$\mathbb{C}^{l}$$\mathrm{R}^{\mathrm{N}}$と表し, 長と表す. 有限複素数列, 無限複素数列も同様に定め , 無限複素数列全体を (非公式に)$\mathrm{R}\mathrm{C}\mathrm{A}_{0}$が無限実数列であるとは, 任意の \sim こ対$\mathbb{C}^{\mathrm{N}}$と表し , 長さ の有限複素数列全体
$l$

と表す.

における実数, 複素数について , 次のような性質が成り立っ.

命題 L23.

$\mathrm{R}\mathrm{C}\mathrm{A}_{0}$で以下のことが証明できる.

$n\in \mathrm{N}$とする. 長さ$n$以上の任意の有限実数 (複素数) 列 $E$ に対し,
$i\in Xrightarrow(i<n\wedge(E)_{i}=0)$なる集合 $X$ が存在する.
証明 関係 $(E)_{i}=0$ が

命題 L2.4.

$\mathrm{R}\mathrm{C}\mathrm{A}_{0}$$\Pi_{1}^{0}$だから,-BCA より直ちにわかる.

で以下のことが証明できる.

数 (複素数) 列 $E$ に対し, 長さるものが存在する.

$\Pi_{1}^{0}$$n$$n\in \mathrm{N}$口とする. 長さの有限実数 (複素数) 列 $F$ で,$n$以上の有限実$(F):–1/(E)_{i}$ な

104
証明 まず実数の場合を示す. 前命題より,$i\in Xrightarrow(i<n\wedge(E):=0)$がとれる. 最小化演算を用いて, 長さ $n$ の自然数の有限$\mathrm{F}^{1}\mathrm{J}$

$s$

で,

$i\not\in X$

なる集合 $X$のとき,$(s)_{i}$は$|((E)_{i})_{m}|>2^{-m+1}$をみたす最小の $m$ であるようなものがとれる. このとき, 実数の定義から, 任意の$j\in \mathrm{N}$に対し$|((E):)_{(s):+j}|\geq 2^{-(s)_{i}+1}-2^{-(s)_{i}}=2^{-(s):}$が成立する.

$F$を次のように定める.

$i\in X$ ならぼ $((F):)_{k}=0$ とし,$i\not\in X$

ならば $((F):)_{k}=1/((E):)_{k+2(s)_{t}}$ とする. 前者の場合 $(F):=0$ で, 後者の場合, 任意の$j\in \mathrm{N}$に対し,$|((F):)_{k}-((F):)_{k+j}|$$=$$| \frac{1}{((E)1)_{k+2(s)}}.‘-\frac{1}{((E)1)_{k+j+2(s)_{l}}}.|$$=$$.. \frac{|((E)_{1})_{k+2(t)}.-((E)_{\dot{\iota}})_{k+j+2(\epsilon)_{l}}|}{((E)_{1})_{k+2(\iota).((E)_{})_{k+j+2(s)_{i}}}}.$.
$2^{-k-2(\epsilon):}$$\leq$$\overline{2^{-}(S)\cdot 2^{-(s)}}$$=2^{-k}$

だから (F): は実数. これが $(F):=1^{\cdot}/(E)$ : を満たすことも$\langle$$((E):)_{k}$:$k\in \mathrm{p}\text{り}=\langle((E):)_{k+2(s)}::k\in \mathrm{N}\rangle$(両辺は実数として等しい) からわかる. 複素数の場合は $1/(x+y\sqrt{-1})=(x-$$y\sqrt{-1})/(x^{2}+y^{2})$から示せる.

$\square$実数, 複素数の計算と充足論理式

2$\mathrm{R}\mathrm{C}\mathrm{A}_{0}$で実数, 複素数の計算を行おうとすると大変面倒な議論が必要となる.

この手間を軽減できるメタ定理が [6] で証明された. この結果は , 実閉体のすべての定理は$\mathrm{R}$において成り立つということを主張するものである. この定理を結果のみ紹介する. また, この結果をより強いものに置き換えることができるか考察する. そして, この定理の証明に必要となる代数学の基本定理の証明を見る.

105
実数, 複素数の計算と充足論理式

2.1

定義 2.1.1(ACF(0), RCOF). 言語
系 A 日よ言語が$\mathcal{L}_{\mathrm{A}\mathrm{F}}$$x\cdot 0=0$

は体の言語 $(\langle+, -, \cdot, /, 0,1, =\rangle)$ とする. 体

で, 以下の公理を持つものとする.

,$x\cdot 1=x$,$x\cdot y=y\cdot x$$x/0=0$ ,$1\neq 0$,$x+(-x)=0$$x+(y+z)=(x+y)+z$ ,$x+y=y+x$ ,$x+0=x$ ,$\mathcal{L}_{\mathrm{A}\mathrm{F}}$,$x\cdot(y\cdot z)=(x\cdot y)\cdot z$$x\neq 0arrow x\cdot(y/x)=y$$x\cdot(y+z)=(x\cdot y)+(x\cdot z)$

ACF(0) は A 日こ以下の公理を加えたものとする.

0$(n\geq 2)$$\forall x_{0}\forall x_{1}\cdots\forall x\exists y(x_{n}\neq 0arrow x_{0}+x_{1}y+\cdots+x_{n}y^{n}=0)$$(n\geq 1)$

これは標数 0 の代数的閉体の公理を表している.
語 Lo 一よ$-\overline{=\mathrm{D}}$$\mathrm{A}\mathrm{F}$$\mathcal{L}_{\mathrm{A}\mathrm{F}}$に $<$ を加えたものとする.

体系 RCOF は言語が$\mathcal{L}_{\mathrm{A}\mathrm{F}}$で, 公理はに

くは線形順序,$0<1$$(x>0\wedge y>0)arrow(x+y>0\wedge xy>0)$と$\forall x_{0}\forall x_{1}\cdots\forall x_{n}\forall y\forall z($$(y<z\wedge x_{0}+x_{1}y+\cdots+x_{n}y^{n}<0<x_{0}+x_{1}z+\cdots+x_{n}z^{n})$$\Rightarrow\exists u(y<u<z\wedge x_{0}+x_{1}u+\cdots+x_{n}u^{n}=0))$$(n>0)$を加えたものとする. これは実閉順序体の公理を表している.
以下,$\mathrm{R}\mathrm{C}\mathrm{A}_{0}$で ACF(0), RCOF が形式化されているとし(項, 論理式, 証明が自然

数 (こコード化されている) , その際の ACF(0), RCOF の変数は
る.

また,

$t’$

を

$t$

の部分項とするとき,

$t’$

のコードは

$t$

$v_{0},$$v_{1},$$\ldots$であるとすのコードより小さいとしてお

106

-.

$\mathrm{g}\triangleright\#_{\vee}’,$$\mathrm{A}\mathrm{C}\mathrm{F}(0)$, RCOF)$\sigma$$\mathrm{f}\mathrm{f}\mathrm{i}\#_{\backslash }\sigma)^{-}\ovalbox{\tt\small REJECT}\not\in*\cdot k’\epsilon\sigma 2\mathrm{R}\mathrm{C}\mathrm{A}_{0}\iota_{\vee}^{\sim}k^{\backslash }l1o\supset-$.

一視する. そして, 任意の無限複素数列 $E$ , 複素数 $A$ に対し,

複素数を

$A$

$E_{A}^{1}$}$\backslash \cdot*\mathrm{g}\mu_{1\backslash \backslash }.\iota=\Pi\overline{\mathfrak{o}}$で $E$ の$i$番目のに置き換えて得られる複素数列を表すとする. 無限実数列 $E$ と実数$A$に対しても同様の定義をする.
定義 21.2( 解釈列). 無限複素数列 $E$ , 自然数 #こ対し , 有限複素数列
$l$

$l$

$V_{E}=\langle$$V_{E}(s):s<l,$ $s$ は ACF(0) の項のコード$\rangle$

が環境 $E$ における 解釈列であるとは,$l$$V_{E}(0)=0$,$V_{E}(1)=1$$V_{E}(v:)=(E)$$V_{E}(t_{1}+t_{2})=V_{E}(t_{1})+V_{E}(t_{2})$$V_{E}(t_{1}t_{2})=V_{E}(t_{1})V_{E}(t_{2})$

,

:

,

$V_{E}(-t)=-V_{E}(t)$$V_{E}(t_{1}/t_{2})=V_{E}(t_{1})/V_{E}(t_{2})$が成り立つことをいう. 有限実数列に対する 解釈列も同様に定義する.
$l$

以下の定理は, 実数, 複素数に関する基本的な演算が$\mathrm{R}\mathrm{C}\mathrm{A}_{0}$でできることを主張する.

定理 2.13.
$l$$\mathrm{R}\mathrm{C}\mathrm{A}_{0}$で以下の主張がいえる. 任意の無限複素数列 $E$ , 自然数 に対し,
$l$

解釈列が存在する. しかも,

ける

$l$

解釈列で,

小さく,

$s$

$V_{E}’$$l$

解釈列は次の意味で一意である.

, が環境 $E’$ におけるに現れる自由変数を$v:_{0},$ $v:_{1},$$(E):_{0}=(E’)_{\dot{\iota}_{0}},$$l’$$V_{E}$

が環境 $E$ にお解釈列であり, 項 のコードカ. とするとき,$\ldots,$

$s$

$s$

$l$

と

$l’$

より

$v_{1j}$$(E)_{i_{1}}=(E’)_{i_{1}},$$\ldots,$$(E)|.j=(E’)_{\dot{l}_{j}}$が成り立つならば,$V_{E}(s)=V_{E}’,(s)$実数に関しても同様の主張が成り立つ.
さらに, 次の充足論理式に関する結果がある.

.
口

107
定理 2.1.4(充足論理式).

の$\mathrm{R}\mathrm{C}\mathrm{A}_{0}$$\Delta_{2}^{0}$

論理式$\mathrm{S}\mathrm{A}\mathrm{T}_{\mathbb{C}}(x, E),$$\mathrm{S}\mathrm{A}\mathrm{T}_{\mathrm{R}}(x, E)$

で, 以下の 3

つの主張を満たすものが存在する.

1) タルスキの充足条件. すなわち,

SAT 献 tl)に対し, $V_{E}(t_{1})=V_{E}(t_{2})$$\Leftrightarrow$ある 解釈列$\Leftrightarrow$

任意の 解釈列$\Leftrightarrow$ある$\Leftrightarrow$

任意の 解釈列$\forall i\leq n\mathrm{S}\mathrm{A}\mathrm{T}_{\mathrm{R}}(\varphi:, E)$$\Leftrightarrow$$\mathrm{S}\mathrm{A}\mathrm{T}_{\mathbb{C}}(\varphi_{0}\wedge\varphi_{1}\wedge\cdots\wedge\varphi_{n}, E)$$\exists i\leq n\mathrm{S}\mathrm{A}\mathrm{T}_{\mathrm{R}}(\varphi:, E)$$\Leftrightarrow$$\mathrm{S}\mathrm{A}\mathrm{T}_{\mathbb{R}}(\varphi_{0}\vee\varphi_{1}\vee\cdots\vee\varphi_{n}, E)$$\Leftrightarrow$$\mathrm{S}\mathrm{A}\mathrm{T}_{\mathrm{R}}(\neg\varphi, E)$$\Leftrightarrow$$\mathrm{S}\mathrm{A}\mathrm{T}_{\mathrm{R}}(\forall v:\varphi, E)$$\Leftrightarrow$$\mathrm{S}\mathrm{A}\mathrm{T}_{\mathrm{R}}(\exists v:\varphi, E)$$=t_{2},$ $E$$\mathrm{S}\mathrm{A}\mathrm{T}_{\mathrm{R}}(t_{1}<t_{2}, E)$$\neg \mathrm{S}\mathrm{A}\mathrm{T}_{\mathrm{R}}(\varphi, E)$$\forall A.\in \mathbb{R}(\mathrm{S}\mathrm{A}\mathrm{T}_{\mathrm{R}}(\varphi, E_{A}^{1}.

))$$\exists A\in \mathbb{R}(\mathrm{S}\mathrm{A}\mathrm{T}_{\mathrm{R}}(\varphi, E_{A}^{\dot{\iota}}))$$l$$V_{E}$

$l$

$l$

解釈列

$V_{E}$$V_{E}$$l$に対し , $V_{E}(t_{1})=V_{E}(t_{2})$に対し, $V_{E}(t_{1})<V_{E}(t_{2})$$V_{E}$

に対し , $V_{E}(t_{1})<V_{E}(t_{2})$.

2) 実閉体で成り立つことは任意の実数に対して成り立っ. すなわち,$(\mathrm{R}\mathrm{C}\mathrm{O}\mathrm{F}\vdash\varphi)\Leftrightarrow\forall E\in \mathbb{R}^{\mathrm{N}}\mathrm{S}\mathrm{A}\mathrm{T}_{\mathrm{R}}(\varphi, E)$3) 任意の $E,$と$E’\in \mathbb{R}^{\mathrm{N}}$$\varphi$について, 各

に対し

$i$

:が

.

$\mathrm{r}v$$\varphi$に自由に現れるならば(E)i=(E’)i」 となるならば$\mathrm{S}\mathrm{A}\mathrm{T}_{\mathrm{R}}(\varphi, E)\Leftrightarrow \mathrm{S}\mathrm{A}\mathrm{T}_{\mathrm{R}}(\varphi, E’)$となる.
$\mathrm{S}\mathrm{A}\mathrm{T}_{\mathbb{C}}$も “ タルスキの充足条件” を満たし,$(\mathrm{A}\mathrm{C}\mathrm{F}(0)\vdash.\varphi)\Leftrightarrow\forall E\in \mathbb{C}^{\mathrm{N}}\mathrm{S}\mathrm{A}\mathrm{T}_{\mathbb{C}}(\varphi, E)$が成立する. そして, 任意の $E,$

$E’\in \mathbb{C}^{\mathrm{N}}$と$\varphi$について, 各 H こ対し:が$\mathrm{r}v$$\varphi$に自由に現れるならぼ (E)i=(E’)i」 となるならぼ$\mathrm{S}\mathrm{A}\mathrm{T}_{\mathbb{C}}(\varphi, E)\Leftrightarrow \mathrm{S}\mathrm{A}\mathrm{T}_{\mathbb{C}}(\varphi, E’)$

となる.

口

注意 2.15(算術に対する充足論理式).

足条件” を満たす論理式
る([2, Ch .

$\mathrm{I}\mathrm{V}],$$[1$$\mathrm{S}\mathrm{A}\mathrm{T}_{\mathrm{N}}$が$\Sigma_{0}^{1}$$\langle \mathrm{N}, +, \cdot, 0,1, =, <\rangle$

ではとれないが, Ch C.l] 等を参照).

$\Delta_{1}^{1}$

に関する “ タルスキの充でとれることが知られてぃ

108
未解決問題 SSC

2.2

実は, 次の問題がまだ未解決である.

予想 22.1. 前に定めた$\mathrm{R}\mathrm{C}\mathrm{A}_{0}$の論理式$\mathrm{S}\mathrm{A}\mathrm{T}_{\mathrm{R}}$は次のことも満たす.

$\forall n[\mathrm{S}\mathrm{A}\mathrm{T}_{\mathrm{R}}(\exists v_{::_{\hslash-1}}\exists v\cdots\exists v\varphi 01’ E)\Rightarrow\exists A\in \mathbb{R}^{n}(\mathrm{S}\mathrm{A}\mathrm{T}_{\mathrm{R}}(\varphi, E_{(A)_{0},(A)_{1},\ldots,(A)_{n-1}}^{1}.0^{11\prime},\cdot\ldots,i_{n-1}))]$

ただし,$E_{(A)_{0},(A)_{1},\ldots,(A)_{n-1}}^{|0,|1^{1_{\hslash-1}}}..’\ldots,\cdot$

は, 各

$k$

に対し, $E$ の$i_{k}$

番日を $(A)$ : で置き換えたものを表す.
ただし, この予想の \Rightarrow を \Leftarrow に置き換えたものが成り立つことは [6] の証明を見ることにより容易にわかる. この問題を本論文では SSC (Strong Satisfaction Condition)と呼ぶことにする. この問題の複素数版もまた未解決である. この予想が解決されれぼ,$\mathrm{R}\mathrm{C}\mathrm{A}_{0}$における実数に関する多くの問題の取り扱いが容易になることが期待される.

しかし, 論理式の形を制限すればこの問題は解決できる. 以下でそのことを見よう.

命題 2.2.2. 量化記号と演算記号., / を持たない論理式
たない$\mathrm{A}\mathrm{F}$の項の列$t_{1}(\tilde{w}),$ $t_{2}(\tilde{w}),$$\iota_{k}(\tilde{w})$$\ldots,$$\varphi(v,\tilde{w})$に対し, 変数$v$

を持が原始再帰的にとれ,$\mathrm{R}\mathrm{C}\mathrm{O}\mathrm{F}\vdash[\exists v\varphi(v,\tilde{w})rightarrow\varphi(t_{1}(\tilde{w}), \varpi)\vee\varphi(t_{2}(\tilde{w}),\tilde{w})\vee\cdots\vee\varphi(t_{k}(\tilde{w}),\tilde{w})]$となる.

証明 与えられた$\ldots\wedge\alpha_{\overline{l}_{i}}$$\varphi$

に対し , 原子論理式を$\wedge$でつないだ形の論理式$\varphi:\equiv\alpha_{1}^{\dot{l}}\wedge\alpha_{2}^{i}\wedge$たちが存在し,$\varphi(v,\varpi)rightarrow\varphi_{1}(v,\tilde{w})\vee\varphi_{2}(v,\tilde{w})\vee\cdots\vee\varphi_{l}(v,\tilde{w})$とできる. 各$\varphi$: に対し,$\exists v\varphi:(v,\tilde{w})rightarrow\varphi:(t_{1}^{\dot{l}}(\tilde{w}),\tilde{w})\vee\varphi:(t_{2}^{1}.(\tilde{w}),\tilde{w})\vee\cdots\vee\varphi:(t_{k}^{1}.(:\tilde{w}),\tilde{w})$

109
なる項の列

$t_{\overline{1}}(\tilde{w}),$$t_{\overline{2}}(\tilde{w}),$$\ldots,$$\exists v\varphi(v,\tilde{w})$$t_{k}^{i}(:\tilde{w})$が得られていれぼ,$rightarrow$$\exists v\varphi_{1}(v,\tilde{w})\vee\exists v\varphi_{2}(v,\tilde{w})\vee\cdots\vee\exists v\varphi l(v,\tilde{w})$$rightarrow$$\varphi_{1}(t_{1}^{1}(\tilde{w}),\tilde{w})\vee\varphi_{1}(t_{2}^{1}(\vec{w}),\tilde{w})\vee\cdots\vee\varphi_{1}(t_{k_{1}}^{1}(\vec{w}),\vec{w})$$\varphi_{2}(t_{1}^{2}(\tilde{w}),\tilde{w})\vee\varphi_{2}(t_{2}^{2}(\tilde{w}),\tilde{w})\vee\cdots\vee\varphi_{2}(t_{k_{2}}^{2}(\tilde{w}),\tilde{w})$$\vee$$\vee$$arrow$$\cdot$..

$\varphi\iota(t_{1}^{l}(\tilde{w}),\vec{w})\vee\varphi\iota(t_{2}^{l}(\tilde{w}),\vec{w})\vee\cdots\vee\varphi_{l}(t_{k_{l}}^{l}(\tilde{w}),\tilde{w})$$\varphi(t_{1}^{1}(\tilde{w}),\vec{w})\vee\varphi(t_{2}^{1}(\tilde{w}),\tilde{w})\vee\cdots\vee\varphi(t_{k_{1}}^{1}(\vec{w}),\vec{w})$$\varphi(t_{1}^{2}(\tilde{w}),\vec{w})\vee\varphi(t_{2}^{2}(\vec{w}),\vec{w})\vee\cdots\vee\varphi(t_{k_{2}}^{2}(\tilde{w}),\tilde{w})$..
$\vee$.

$\varphi(t_{1}^{l}(\tilde{w}),\vec{w})\vee\varphi(t_{2}^{l}(\vec{w}),\vec{w})\vee\cdots\vee\varphi(t_{k_{\mathrm{t}}}^{l}(\tilde{w}),\vec{w})$とできる. したがって, はじめから$\varphi$

は原子論理式を$\wedge$でつないだ形$\alpha_{1}\wedge\alpha_{2}\wedge\cdots\wedge\alpha_{k}$であるとしてよい.

項$t$と正の自然数 $m$ に対し , $mt$ で項」することにより, 各$\alpha_{i}$$t$を $m$ 回足しあわせたものを表すとすれぼ,「移は $mv<t,$ $mv=t,$ $mv>t(m\in \mathrm{N},$$\mathrm{t}$は変数号., / を含まない項) のいずれかの形であるとしてよい. また, ある$\alpha_{j}$

$v$

と演算記

が変数 : を含まなければ$\exists v(\alpha_{1}\wedge\alpha_{2}\wedge\cdots\wedge\alpha_{k})rightarrow\alpha_{j}\wedge\exists v(\alpha_{1}\wedge\alpha_{2}\wedge\cdots\wedge\alpha_{j-1}\wedge\alpha_{j+1}\wedge\cdots\wedge\alpha_{k})$である.

$\varphi’\equiv\alpha_{1}\wedge\alpha_{2}\wedge\cdots\wedge\alpha_{j-1}\wedge\alpha_{j+1}\wedge\cdots\wedge\alpha_{k}$に対し,$\exists v\varphi’(v,\tilde{w})rightarrow\varphi’(t_{1}’(\tilde{w}),\vec{w})\vee\varphi’(t_{2}’(\vec{w}),\tilde{w})\vee\cdots\vee\varphi’(t_{k’}’(\tilde{w}),\tilde{w})$なる項の列$t_{1}’(.\vec{w}),$$\exists v\varphi_{i}(v,\vec{w})$$t_{2}’(\tilde{w}),$$\ldots,$$t_{k’}’(\vec{w})$が得られているとすれば,$rightarrow$$\alpha_{j}(\tilde{w})\wedge\exists v\varphi’(v,\vec{w})$$rightarrow$$\alpha_{j}(\tilde{w})\wedge(\varphi’(t_{1}’(\tilde{w}),\tilde{w})\vee\varphi’(t_{2}’(\tilde{w}.),\vec{w})\vee\cdots\vee\varphi’(t_{k’}’(\tilde{w}),\tilde{w}))$$rightarrow$$(\alpha_{j}(\vec{w})\wedge\varphi’(t_{1}’(\vec{w}),\vec{w}))\vee(\alpha_{j}(\tilde{w})\wedge\varphi’(t_{2}’(\tilde{w}),\tilde{w}))$$\vee\cdots\vee(\alpha_{j}(\vec{w})\wedge\varphi’(t_{k’}’(\tilde{w}),\tilde{w}))$$rightarrow$$\varphi(t_{1}’(\tilde{w}),\tilde{w})\vee\varphi(t_{2}’(\tilde{w}),\tilde{w})$$\vee\cdots\vee\varphi(t_{k}’(:\tilde{w}),\tilde{w})$

$v$

110
となる. だから, はじめから各は変数$\alpha_{j}$$v$を含むとしてよい. 以上により,は$\varphi$$m_{1}v<r_{1}\wedge\cdots\wedge m_{k_{0}}v<r_{k_{0}}$$\wedge m_{1}’v=r_{1}’\wedge\cdots\wedge m_{k_{1}}’ v=r_{k_{1}}’$’$\wedge m_{1}’’v>r_{1}’’\wedge\cdots\wedge m_{k_{2}}’’v>r_{k_{2}}’$(ただし,$mj,$ $m_{j}’,$ $m_{j}’’$ は正の自然数の形であるとしてよい.
$0,$$k_{1}\geq 1$$k0>0,$ $k_{2}>0$ ならば,りも,

$r_{j}’’$

は変数

$v$

と演算記号., / を含まない項)

ならば, $k=1,$ $t_{1}=r_{1}’/m_{1}’$ ととればよい.

ということは,$\exists v\varphi(v)$$r:/m$$k_{1}=$: たちのうち最小のもの$r$よ, たちのうち最大のもの $r”$ のほうが小さいということと同値, これは$r_{1’}’’.,/m_{-\prime}’’$$r”<(r+r’’)/2<r$ と同値だから,
い.

$r_{j},$ $r_{j}’,$$=k_{1}=0,$ $k_{2}>0$$k_{0}$.

対しては常に様に,$\varphi(v)$ならぼ,$\{k_{n}\}$, たちのうち最大のもの $r”$ より大きな$r_{1’}’’.,/m_{1’}’’.$

が成立するから,$k_{2}=k_{1}=0,$ $k_{0}>0$

として $(r:/m:+r_{1’}’’.,/m_{1’}’’.,)/2$ たちをとれぼよならば,$\{k_{n}\}$$\{k_{n}\}$

として

$v$

に

たちをとればよい. 同$r_{1}’.1,/m_{1}’.t_{t}’+1$

として $r:/m_{i}-1$ たちをとればよい.

口

RCOF の論理式 に演算記号・が現れず, 演算 / の分母が常に $1+\cdots+1$ の形なら$\varphi$ぼ, 各原子論理式の辺々に適当な自然数をかけることによって$\varphi$は演算記号., / をもたない論理式と同値であることがわかる. このことと前の命題から次を得る.
命題 2.2.3. 1.
たちを持たない

量化記号と演算記号., / を持たない論理式$\mathrm{A}\mathrm{F}$の項の列の列$\mathrm{t}_{1}(\tilde{w}),$$\mathrm{t}_{2}(\tilde{w}),$$\mathrm{t}_{k}(\tilde{w})$$\ldots,$$\varphi(\tilde{v},\tilde{w})$に対し, 変数$\tilde{v}$で,$\mathrm{R}\mathrm{C}\mathrm{O}\mathrm{F}\vdash[\exists\tilde{v}\varphi(\vec{v},\tilde{w})rightarrow\varphi(\mathrm{t}_{1}(\tilde{w}),\tilde{w})\vee\varphi(\mathrm{t}_{2}(\tilde{w}),\tilde{w})\vee\cdots\vee\varphi(\mathrm{t}_{k}(\tilde{w}),\tilde{w})]$

なるものが原始再帰的にとれる.

2. 演算記号., / を持たない論理式
理式で,$\psi$$\psi$

に対し , 量化記号と演算記号., / を持たない論と RCO 日こおいて同値なものがある.

この命題から, SSC の部分的解決である次の定理を得る.
定理 2.2.4. 演算記号., / を持たない論理式$\varphi$に対し,$\forall n[\mathrm{S}\mathrm{A}\mathrm{T}_{\mathrm{R}}(\exists v:_{0}\exists v:_{1}\cdots\exists v_{i_{n-1}}\varphi, E)\Rightarrow\exists A\in \mathbb{R}^{n}(\mathrm{S}\mathrm{A}\mathrm{T}_{\mathrm{R}}(\varphi, E_{(A)_{0},(A)_{1},\ldots,(A)_{n-1}}^{1}.0,|.1,\ldots,_{n-1}))]$

が成り立つ.

$\text{口}$111
証明 前の命題の 2 により,り, 変数

$v_{i_{0}},$$v_{i_{1}},$$\ldots,$

RCOF

$v$

:

$\varphi$は量化記号をもたないとしてよい. 前の命題の 1 によたちを持たない$\mathrm{A}\mathrm{F}$の項の列の列$\mathrm{t}_{1},$$\mathrm{t}_{k}$$\mathrm{t}_{2},$$\ldots,$で,$\vdash 1\exists v_{1}.\exists v:\cdots\exists v:_{\hslash-1}01\varphi(v_{0}, v:_{1}, \ldots , v:_{\hslash-1},\tilde{w})$$rightarrow\varphi(\mathrm{t}_{1}(\vec{w}),\tilde{w})\vee\varphi(\mathrm{t}_{2}(\tilde{w}),\tilde{w})\vee\cdots\vee\varphi(\mathrm{t}_{k}(\tilde{w}),\tilde{w})]$

なるものが原始再帰的にとれる. SAT 献\exists v* 0\exists v:1. .
$\cdot$が成り立つならば,$\exists v:_{\hslash-1}\varphi(v_{1}.

v_{i_{1}}0,, \ldots, v:_{\hslash-1},\tilde{w}),$$\mathrm{S}\mathrm{A}\mathrm{T}_{\mathrm{R}}(\varphi(\mathrm{t}_{1}(\tilde{w}),\tilde{w})\vee\varphi(\mathrm{t}_{2}(\tilde{w}),\vec{w})\vee\cdots\vee\varphi(\mathrm{t}_{k}(\vec{w}),\vec{w}),$がって, ある $i\leq k$ に対し要の有限実数列が $E,$$\mathrm{t}$$\mathrm{S}\mathrm{A}\mathrm{T}_{\mathrm{R}}(\varphi(\mathrm{t}_{i}(\vec{w}),\tilde{w}),$

$E)$

$E)$

$n$

. した

. このとき, 定理 2.1.4 により, 所: から得られる.

この証明において,「この議論を

$E)$

口

回繰り返して...」 などという強い帰納法を暗に用いるような議論を用いていないことに注意. 未解決問題 SSC の難しさは, 実数係数多項式 の根たちをとり, それらを含む項を係数にもつ多項式の根たちをとり, 再$p$

びそれらを含む項を係数にもつ多項式の根たちをとり. . . という操作を任意有限回繰り返すことで, それを$\mathrm{R}\mathrm{C}\mathrm{A}_{0}$で行う方法はまだ発見されていない. 予想 2.2.1 を [6]と同じ方法で証明しようとすると, このような操作が本質的に必要になるのである.
なお, 命題 222, 命題 223, 定理 2.2.4 の証明の複素数 (ACF(0)) 版も同様に (しかもより簡単に) 証明できる.

2.3

代数学の基本定理

ここでは, 代数学の基本定理がて,$\mathrm{R}\mathrm{C}\mathrm{A}_{0}$$\mathrm{R}\mathrm{C}\mathrm{A}_{0}$で証明できることを見る. 既に, [8] においで複素係数多項式の根の一つがとれることは示されているが, 今回はより強い主張である, 複素係数多項式の (重複を込めた) 根全体の存在が$\mathrm{R}\mathrm{C}\mathrm{A}_{0}$で証明できることを見る.
定義 23.1.

$\mathrm{R}\mathrm{C}\mathrm{A}_{0}$で次の定義をする. 有理複素数とは, 実部, 虚部が共に有理数であるような複素数とする. これは有理数のペアでコード化される. 有理複素数全体の集合を$\mathrm{E}$で表す.

$\mathrm{E}$係数多項式全体の集合を$\mathrm{E}[Z]$あるような 1 次以上の E 係数多項式全体の集合をで表す. 特に, 最高次の係数が 1 で$\mathrm{E}[Z]^{\star}$で表す.

$\mathrm{E}[Z]$の元は有理複素数有限列でコード化される. そして, $a_{0}+a_{1}Z+\cdots+a_{N-1}Z^{N-1}+a_{N}Z^{N}=P\in \mathrm{E}[Z]$に対し, ノルムを $||P||= \max\{|a_{0}|, \ldots, |a_{N}|\}$ と定める.

次の定理の証明は [8] または [3] を参照のこと.

112
定理 2.3.2.

$\mathrm{R}\mathrm{C}\mathrm{A}_{0}$で,$|P(\psi(P, n))|<2^{-n}$を成り立たせる関数$P\in \mathrm{E}[Z]^{\star},$$\psi$:$\mathrm{E}[Z]^{\star}\cross \mathrm{N}arrow \mathrm{E}$$N=\deg P$ とする.

が存在する.

このとき,

口が $|z|\geq 1+N||P||$ を満たしてい$z\in \mathrm{E}$れば,$|P(z)|\geq|z|^{N}-N||P|||z|^{N-1}=|z|^{N-1}(|z|-N||P||)>1$となる. すなわち, 上の定理で得られる関数$\psi$

は $|\psi(P, n)|<1+N||P||$ を成り立たせている.

これを用いて,$\varphi(P, n)(P\in \mathrm{E}[Z]^{\star}, n\in \mathrm{N})$を,$\varphi(Z-z_{0},n)=\langle z_{0}\rangle$$N=\deg P>1$ のとき,

(ここに,の次数に関して再帰的に$P$,$\varphi(P, n)=\langle\psi(P, t)\rangle^{\wedge}\varphi(P’, n)$$P’(Z)$ は $P(Z)$ を $(Z-\psi(P, t))$ で割った商,$t=2^{N}\cdot n+2$ で,すなわち,$P(Z)=P(\psi(P, t))+(Z-\psi(P, t))P’(Z))$ と定める.

命題 2.3.3.

$\mathrm{R}\mathrm{C}\mathrm{A}_{0}$で, 以下が示せる. 任意の$P\in \mathrm{E}[Z]^{\star},$$2^{-2^{\mathrm{d}\cdot e^{\mathrm{p}}}\cdot(\epsilon+1)-1}arrow\exists l<\deg P(|z-(\varphi(P, m))\downarrow|<2^{-s})$

証明 $N=\deg P$ に関する

ならば,$\Pi_{1}^{0_{-}}\mathrm{I}\mathrm{N}\mathrm{D}$.

より成立. $N>1$ の場合は,$<$

く$|z-\psi(P, t)|\leq 2^{-2^{N}\cdot s-1}<2^{-s}$$2^{-2^{N}\cdot(s+1)-1}+2^{-t}$$2^{-2^{N}\cdot s}$.

または $|P’(z)|\leq 2^{-2^{N}\cdot\epsilon-1}\leq 2^{-2^{(N-1)}}.(s+1)-1$. 後者の場合, 帰納法の仮定によりある夏
ら’
.

$N$

に対し,

$!^{z-}.(\varphi(P’, m))_{l}|<2^{-s}$$|z-(\varphi(P, m))_{l+1}|<2^{-s}$$P\in \mathrm{E}[Z]^{\star}$の命題は ,$t=$$P(Z)=P(\psi(P, t))+(Z-\psi(P, t))P’(Z)$ として,$|(z-\psi(P, t))P’(z)|\leq|P(z)|+|P(\psi(P, t))|$

従って,に対し , $|P(z)|<$で証明する. $N=1$ のときは $|P(z)|<2^{-2^{N}\cdot(s+1)-1}$$|(\varphi(P, m))_{0}-z|<2^{-2^{N}\cdot(s+1)-1}<2^{-s}$$2^{N}\cdot s+2,$$z\in \mathrm{E}$に対し ,$\tilde{P}^{m}$$\tilde{P}^{n}=(Z-(\psi(P, n))_{0})\cdots(Z-(\psi(P, n))_{\deg P-1})$

が $P$ の$\mathrm{E}$だか口と定める. 次で一次式に分解できる多項式による近似であることを表し

113
命題 234.

で, 以下が示せる. 任意の$\deg P=N,$$m\in \mathrm{N}$に対し,$||P- \tilde{P}^{m}||<2^{-2^{N}\cdot m+N-1}\cdot(1+\max\{|(\varphi(P, m))_{0}|, \ldots, |(\varphi(P, m))_{N-1}|\})^{N-1}$

. 特

に,

$||P-\tilde{P}^{m}||<2^{-2^{N}\cdot m+N-1}\cdot(2+N||P||)^{N-1}$$\mathrm{R}\mathrm{C}\mathrm{A}_{0}$$P\in \mathrm{E}[Z]^{\star},$.

証明 $N=\deg P$ に関する帰納法で示す. $N=1$ の場合は $P=\tilde{P}^{m}$ だから自明.

$N>1$ の場合,

$t=2^{N}\cdot m+2,$ $P(Z)=P(\psi(P, t))+(Z-\psi(P, t))P’(Z)$ として,$P(Z)-\overline{P}^{m}(Z)$$=$$P(\psi(P, t))+(Z-\psi(P, t))P’(Z)-\tilde{P}^{m}(Z)$$=$$P(\psi(P, t))+(Z-\psi(P, t))(P’(Z)-\overline{P^{\prime^{m}}}(Z))$

だから,$||P(Z)-\tilde{P}^{m}(Z)||$$\leq$$(1+| \psi(P, t)|)(1+\max\{|(\varphi(P, m))_{0}|, \ldots, |(\varphi(P, m))_{N-1}|\})^{N-2}2^{-2^{N-1}\cdot m+N-2}$$+2^{-t}$$\leq$$(1+ \max\{|(\varphi(P, m))_{0}|, \ldots, |(\varphi(P, m))_{N-1}|\})^{N-1}2^{-2^{N-1}\cdot m+N-1}$.
口

次の命題は [4] による. これは, 多項式の係数を変化させるとき, 多項式の根–$\text{全体}$の変動は連続であることを表している.
命題 235.
$w_{0},$$\ldots,$$\mathrm{R}\mathrm{C}\mathrm{A}_{0}$$w_{N-1}\in \mathrm{E},$で, 以下を満たす関数$\nu$: Q,0 N$\cross$$\cross$

N\rightarrow N がとれる.

$z_{0},$$\ldots,$ $z_{N-1}$,$P(Z)=(Z-z_{0})\cdots(Z-z_{N-1}),$ $Q(Z)=(Z-w_{0})\cdots(Z-w_{N-1})$に対して, $||P||<R,$ $||Q||<R,$ $||P-Q||<2^{-\nu(R,N,m)}$ となる
ある 0, 1, . . . , $N-1$ 上の置換$\sigma$で,$R\in \mathbb{Q}_{>0}$が存在すれば,$|z_{0}-w_{\sigma(0)}|<2^{-m},$ $\ldots,$ $|z_{N-1}-w_{\sigma(N-1)}|<2^{-m}$を満たすものがある.
証明 $H(R, N)$ を,意の$2^{H(R,N)}\geq(1+NR)^{N}$ なる単調増加関数とし,$S\in \mathrm{E}[Z],\cdot z,$ $z’\in \mathrm{E}$に対し ,$M(R, N)$ を, 任$||S||<2^{H(R,N)}\wedge|z|<2^{H(R,N)}\wedge|z’|<2^{H(R,N)}arrow$$|S(z)-S(z’)|\leq 2^{M(R,N)}|z-z’|$ を成り立たせる単調増加関数とする.

$\nu(R, 0, m)=m+H(R, 1)$$\nu(R, N+1, m)=(N+1)(3\nu(R, N, m)+2M(R, N)+(N+2)H(R, N+1)+8)$ととればよい. これが所要の条件を満たすことを示すために, 次のより強い主張を$\Sigma_{1}^{0_{-}}1\mathrm{N}\mathrm{D}$

で示す.

114
$P(Z)=(Z-z_{0})\cdots(Z-z_{N-1}),$ $Q(Z)=(Z-w_{0})\cdots(Z-w_{N-1})$ が任意の$|z|<2^{H(R,N)}$ なる $z\in \mathrm{E}$ に対し,$|P(z)-Q(z)|<(N+1)2^{NH(R,N)-\nu(R,N,m)}$を成り立たせるならば, ある 0, 1, . . . , $N-1$ 上の置換 で,$\sigma$$2^{-m},$$\ldots,$$|z_{0}-w_{\sigma(0)}|<$$|z_{N-1}-w,(N-1)|<2^{-m}$ を満たすものがある.

$N=1$ のとき, これが成り立つことは明らか. $N>1$ のとき, $P,$$|z|<2^{H(R,N)}$ なる $z\in \mathrm{E}$ に対し,

$Q$

が任意の

$|P(z)-Q(z)|<(N+1)2^{NH(R,N)-\prime(R,Vm)}$ を成り立たせるならば, $|Q(z_{0})|=|P(z_{0})-Q(z_{0})|<(N+1)2^{NH(R,N)-\nu(R,N,m)}$$2^{NH(R,N)-\nu(R,N,m)+N}$. よって, ある に対し,$|w:-z_{0}|$$i$$\leq$$2^{(NH(R,N)-\nu(R,N,m))/N+1}$$=$$2^{H(R,N)-(3\nu(R,N-1),m)+2M(R,N-1)+(N+1)H(R,N)+8)}$$=$$2^{-3\nu(R,N-1,m)-2M(R,N-1)-NH(R,N)-8}$く$2^{-m}$.

$i=n$ として一般性を失わない.

おく.

く$P^{\star}(Z)=P(Z)/(Z-z_{0}),$ $Q^{\star}(Z)=Q(Z)/(Z-w_{0})$ と

任意の国’ $2^{H(R,N-1)}<2^{H(R,N)},$ $|z-z_{0}|>2^{-\nu(R,N-1,m)-M(R,N)-3},$ $|z-w_{0}|>$$2^{-\nu(R,N-1,m)-M(R,N)-3}$ なる $z\in \mathrm{E}$ に対し ,$|P^{\star}(z)-Q^{\star}(z)|$$=$$| \frac{P(z)(z-z_{0})+P(z)(z_{0}-w_{0})-Q(z)(z-z_{0})}{(z-z_{0})(z-w_{0})}|$$=$$\frac{|P(z)-Q(z)|}{|z-w_{0}|}+\frac{|P(z)||z_{0}-w_{0}|}{|z-z_{0}||z-w_{0}|}$$\leq$$|P(z)-Q(z)|2^{\nu(R,N-1,m)+M(R,N)+3}$$+|P(z)|2^{-3\nu(R,N-1,m)-2M(R,N-1)-NH(R,N)-8}\cdot(2^{\nu(R,N-1,m)+M(R,N)+3})^{2}$$<$$(N+1)2^{NH(R,N)-\nu(R,N,m)+\nu(R,N-1,m)+M(R,N)+3}$$+(N+1)2^{NH(R,N)-3\nu(R,N-1,m)-2M(R,N-1)-NH(R,N)-8+2\nu(R,N-1,m)+2M(R,N)+6}$$<$$(N+1)2^{-\nu(R,N-1,m)-2}+(N+1)2^{-\nu(R,N-1,m)-2}$$<$$(N+1)2^{-\nu(R,N-1,m)-1}$が成り立つ.
$z\in \mathrm{E}$$w\in \mathrm{E}$が $|w|<2^{H(R,N-1)}$ を成り立たせているとする. このとき,

で, $|w-z|<2^{-M(R,N)-\nu(R,N-1,m)-2}$ と $|z|$ ’ $2^{H(R,N-1)}<2^{H(R,N)},$ $|z-z_{0}|>$115$2^{-\nu(R,N-1,m)-M(R,N)-3}$,

レー $w_{0}|>2^{-\nu(R,N-1,m)-M(R,N)-3}$ を満たすものがとれ,$|P^{\star}(w)-Q^{\star}(w)|$く$|P^{\star}(w)-P^{\star}(z)|+|P^{\star}(z)-Q^{\star}(z)|+|Q^{\star}(z)-Q^{\star}(w)|$く$2^{M(R,N-1)+1}|z-w|+(N+1)2^{-N\nu(R,N-1,m)-1}$く$2^{-\nu(R,N-1,m)-2+1}+(N+1)2^{-\nu(R,N-1,m)-1}$

く$(N+1)2^{-\nu(R,N-1,m)}$$.\leq$$N2^{(N-1)H(R,N-1)-\nu(R,N-1,m)}$となる. よって, 帰納法の仮定により, 1, 2, . . . , $N-1$ 上の置換$2^{-m},$$|z_{N-1}-w_{\tau(N-1)}|<2^{-m}$$\ldots,$$\tau$

で,$|z_{1}-w_{\tau(1)}|<$

なるものがある. そこで, $\sigma(0)=0,$ $\sigma(i)=\tau(i)(i>$0) とすれぼよい.

$\text{口}$定理 236(代数学の基本定理).

$\mathrm{R}\mathrm{C}\mathrm{A}_{0}$で以下が示せる. 任意の$A_{0},$$\ldots,$$A_{N-1}\in \mathbb{C}$に対し,$A_{0}+A_{1}Z+\cdots+A_{N-1}Z^{N-1}+Z^{N}=(Z-B_{0})\cdots(Z-B_{N-1})$なる複素数列$B_{0},$

正明 各を,$A_{i}$$\ldots,$$\mathrm{E}$$B_{N-1}$

がとれる.

の元の列

のとみる. このとき,$a_{i,0},$$\ldots$

で,$\forall j\forall k|a:,j-ai,j+k|<2^{-j}$$P_{j}=a_{0,j}+a_{1,j}Z+\cdots+a_{N-1,j}Z^{N-1}+Z^{N}$の $j,$ $k$ (こ対し $||P_{j}-P_{j+k}||<$ $2^{-j}$.
$||P_{j}||<R$$a_{\dot{l},1},$とすれば, 任意

. また, $R=||P_{0}||+1$ とすれば, 任意の. 従って,$||\tilde{P}_{j}^{j}-\overline{P_{j+k}}^{j+k}||$$\leq$$||\overline{P_{j}}^{j}-P_{j}||+||P_{j}-P_{j+k}||+||P_{j+k}-\overline{P_{j+k}}^{j+k}||$$<$$2^{-2^{N}\cdot j+N-1}\cdot(2+N||P_{j}||)$$+2^{-j}+2^{-2^{N}\cdot(j+k)+N-1}\cdot(2+N||P_{j+k}||)$

そこで,

を満たすも

$\mathrm{E}$$<$$2^{-2^{N}\cdot j+N}\cdot(2+NR)+2^{-j}$ .

$<$$2^{-2^{N}\cdot j+N+1}\cdot(2+NR)$の元の有限列の列$\langle\langle b_{0,j}, \ldots, b_{N-1,j}\rangle :.

j\in \mathrm{N}\rangle$を,$b_{i,j}=(\varphi(P_{\nu(R,N,j)}, \nu(R, N,j)))_{i}$

$j$

に対し

116
ととり, 各 $j>0$ で$b_{0,\ovalbox{\tt\small REJECT}},$$\ldots,$$1|+\cdots+|b_{N-\mathit{1},\ovalbox{\tt\small REJECT}}-b_{N-1,\mathrm{j}-1}|$$|b_{0,\ovalbox{\tt\small REJECT}}-b_{0,\ovalbox{\tt\small REJECT}}$を並べ替えれぼ. 列$b_{N-,,j}$$B_{i}\ovalbox{\tt\small REJECT}\langle b_{i,0}b_{i,\mathit{1}}\rangle’\ldots)$

が最$/\sim\dashv$

こなるようには所要の条件を満たす複素数を定める.

帰納法, 内包公理と実数

3

今までは

$\mathrm{R}\mathrm{C}\mathrm{A}_{0}$で示すことができる実数に関する性質を見てきたが, ここではより強い公理を必要とする実数の性質を見る. また,$\mathrm{R}\mathrm{C}\mathrm{A}_{0}$により強い公理を加えることによる問題 SSC の部分的解決をみる.

帰納法, 内包公理と実数

3.1$x\in \mathrm{R}$が有理数であるという主張は$\exists q\in \mathbb{Q}(x=q)$と$\Sigma_{2}^{0}$

論理式で記述できる. この事実の発展として, 次のこともわかる.

定理 3.LL

1.

$\Sigma_{2^{-}}^{0}\mathrm{B}\mathrm{C}\mathrm{A}$2.

$\Sigma_{2}^{0}$$\mathrm{R}\mathrm{C}\mathrm{A}_{0}$で, 以 T の主張が同値なことが示せる.

.

-BCA を以下の形に制限したもの :$\forall Nn(\varphi(l, n)rightarrow\psi(l, n))arrow\forall m\exists X(i\in Xrightarrow(i<m\wedge\exists x\forall y>x\varphi(i, y))$ここに,$\varphi\in\Sigma_{1}^{0},$3. 任意の$l\in \mathrm{N}$$\psi\in\Pi_{1}^{0}$で, これらは $X$ を自由変数として含まない.

について, 長さ$l$の任意の実数列 $A$ に対し, 有限集合 $B$ で$i\in Brightarrow$( $i<l\wedge$ (A):が有理数)なるものが存在する.
証明$\mathit{2}arrow \mathit{1}$$\mathit{1}arrow \mathit{3}$.

は (A): が有理数であるという主張が$\varphi(x, y, i)\in\Sigma_{0}^{0}$とする.

$f,$ $g:\mathrm{N}\cross \mathrm{N}arrow \mathrm{N}$$\Sigma_{2}^{0}$であることから直ちにわかる.

を次のように定める.

$f(0, i)=g(0, i)=0$$\varphi(f(n, i),g(n, i),$ $i)\Rightarrow[f(n+1,i)=f(n, i),g(n+1, i)=g(n, i)+1]$$\neg\varphi(f(n, i),g(n, i),$ $i)\Rightarrow[f(n+1,i)=f(n, i)+1, g(n+1, i)=0]$

117
このとき, 関係 $g(y, i)\neq 0$ が$\Delta_{1}^{0}$だがら,$\exists x\forall y\varphi(x, y, i)rightarrow\exists x\forall y>x(g(y, i)\neq 0)$を示せば十分である.

まず \rightarrow を示す.

とする.

$\exists x\forall y\varphi(x, y, i)$$\Pi_{1}^{0}$-LNP によりなる$\forall y\varphi(x, y, i)$

$x$

のうち

最小のものがとれる. すなわち,$\forall z<x\exists y\neg\varphi(z, y, i)\wedge\forall y\varphi(x, y, i)$

このとき, 任意の $j<x+1$ に対し, $f(l, i)=j\wedge g(l, i)=0$ なる$\Sigma_{1}^{0_{-}}1\mathrm{N}\mathrm{D}$$l$がとれることがによりいえる. 特に $j=x$ として $f(l, i)=x\wedge g(l, i)=0$ なる$\forall l’>l(g(l’, i)\neq 0)$

$l$

をとれば

.

逆を示す. $\exists x\forall y>x(g(y, i)\neq 0)$ とすれば,$\Sigma_{1}^{0_{-}}\mathrm{I}\mathrm{N}\mathrm{D}$(の対偶) により $\forall y(g(y, i)\neq 0)$

または $\exists x(g(x, i)=0\wedge\forall y>x(g(y, i)\neq 0))$ が成り立つ. $g(0, i)=0$ だから前者の場

合は起こりえない. 後者を成り立たせるの$z\in \mathrm{N}$$x$をとる. このとき,$\Sigma_{1^{-}}^{0}1\mathrm{N}\mathrm{D}$により, 任意に対し$f(x+z, i)=f(x, i)\wedge g(x+z, i)=z\wedge\varphi(f(x+z, i),g(x+z, i),$ $i)$がいえる. $x’=f(x, i)$ とすれぼ,$\mathit{3}arrow \mathit{2}$.

$\varphi\in\Sigma_{1}^{0},$$\psi\in\Pi_{1}^{0}$$\forall z\varphi(x’, z, i)$.

が $\forall l\forall n(\varphi(l, n)rightarrow\psi(l, n))$ を満たすとする.

により $(x, i)\in Xrightarrow\varphi(x, i)$ なる $X$ がとれる. 有理数の 2 重列$\langle q_{i,j} :$\Delta_{1}^{0}$

内包公理

i,j\in \mathrm{N}\rangle$を$q_{i,0}=0$$q_{i,j+1}=\{$

で定める.
$\varphi(j, i)$$A_{i}.=\langle q_{i,j} :j\in \mathrm{N}\rangle$$q:,j$$(j, i)\in X$ のとき$q_{i,j}+2^{-j^{2}-1}$$(j, i)\not\in X$

は実数になる.

$A_{:}$のときは 2 進小数表示で,$2^{-j^{2}-1}$の位が,のとき, そしてそのときに限り 0 になり, その他の位は常に 0 になる実数を表す. このとき,$A_{i}\in \mathbb{Q}rightarrow\exists x\forall y>x\varphi(y, i)$が成り立つことを示せぼ十分である.
\leftarrow は明らかなので逆を示す.
$n\in \mathrm{N}$-{0}&こ対し$nA_{i}\not\in \mathbb{Z}$\rightarrowの対偶を示す.

をいう.

$\forall x\exists y>x\neg\varphi(y, i)$$2^{k}\leq n<2^{k+1}$

なる$k\in \mathrm{N}$とする. 任意のをとる. このとき,

118$2^{k+1}Aj$の小数部分 $B$ は仮定

より 0 でなく,$\forall x\exists y>x\neg\varphi(y, i)$未満である. すなわち $0<B<2^{-2k}\leq 1/n$ . よって$\langle q:,j\rangle$$2^{k+1}nA_{i}\not\in \mathbb{Z}$の定義により. ゆえに$2^{-2k}$$nA_{i}\not\in \mathbb{Z}$.

口

無限個の実数に対する条件判定, 計算を行おうとするとより強い公理が必要になる.
定理 3.12.

1.

$\mathrm{R}\mathrm{C}\mathrm{A}_{0}$で, 以下の主張が同値なことが示せる.

$\mathrm{A}\mathrm{C}\mathrm{A}_{0}$.
3. 任意の無限実数列$\mathit{2}$$\Sigma_{1}^{0_{-}}\mathrm{C}\mathrm{A}$$A$に対し, 集合 $B$ で$i\in Brightarrow((A):=0)$なるものが存在する.

4. 任意の無限実数列$A$に対し, 集合 $B$ で

i\in B\leftrightarrow ((A):は有理数)なるものが存在する.

5. 任意の$E\in \mathbb{R}^{\mathrm{N}}$

定義 2.12 の6. 任意の$V_{E}$

に対し, 無限実数列$V_{E}=\langle$ $V_{E}(s)$:$s$は RCOF の項のコード$\rangle$

で,に関する条件を満たすものが存在する.

$E\in \mathbb{R}^{\mathrm{N}}$に対し, 集合 $B$ で,$i\in Brightarrow \mathrm{S}\mathrm{A}\mathrm{T}_{\mathrm{R}}(i, E)$なるものが存在する.

証明$\mathit{1}rightarrow \mathit{2}$$\mathit{1}arrow\theta$

はは [5] 参照.

$\mathrm{S}\mathrm{A}\mathrm{T}_{\mathrm{R}}$が$\Delta_{2}^{0}$なることからわかる.

$\mathit{1}arrow \mathit{5}$も$V_{E}(t)=A\mathrm{B}^{\mathrm{f}}\Delta_{2}^{0}$

であること

’

からわかる.
$\mathit{5}arrow \mathit{3}$い.

.

$\mathit{3}arrow \mathit{2}$$\mathit{6}arrow \mathit{3}$は自明であろう.

$V_{E}(v_{i}/v:)=\langle q_{0}^{i}, q_{1}^{\dot{\iota}}, \ldots\rangle$.

$\varphi\in\Sigma_{0}^{0}$

に対し,

$f$

:

として,

$\mathrm{N}arrow \mathrm{N}$$X$

を $i\in Xrightarrow q_{2}^{i}<1/2$ ととれぼよを $f(i,j)=[\varphi(i, n)$ なる最小の $n<j$ , た

だしこのような $n<j$ が存在しないときは刃と定める. そして, 有理数の 2 重列$\langle q:,j:i,j\in \mathrm{N}\rangle$

で,を$q:,j=2^{-f\mathrm{t}i_{\dot{\beta})}}$$(A)_{i}\neq 0rightarrow\exists j\varphi(i,j)$$x\in Xrightarrow x\not\in \mathrm{Y}$で定める.

$((A):)_{j}=q:,j$を満たす. よって,ととれぼ $x\in Xrightarrow\exists j\varphi(i,j)$$\mathrm{Y}$

.

を

とすれば,

$y\in \mathrm{Y}rightarrow(A)_{y}$$A$は実数の無限列$=0$ ととり,

$X$

を

119

$\mathit{1}arrow \mathit{4}$は (A): が有理数であるという主張が$\Sigma_{2}^{0}$であることからわかる.

$\mathit{4}arrow \mathit{2}$定理 3. 垣の証明と同様にしてわかる.
ここで,$\mathrm{R}\mathrm{C}\mathrm{A}_{0}$は口により強い公理を加えることによる SSC の部分的解決を試みよう.

定義 3.13(有界従属選択公理).

$\Gamma$

を論理式の集合とする. 公理図式 -BDC を$\Gamma$$\forall n\forall X\exists \mathrm{Y}\varphi(n, X, \mathrm{Y})arrow\forall l\exists Z\forall n<l\varphi(n, (Z)_{n},$で定める. ここに,$\varphi\in\Gamma$

で,

$Z$

この公理図式は次の公理図式$(Z)_{n+1})$

を自由変数として含まないものとする.

$\Gamma- \mathrm{B}\mathrm{D}\mathrm{C}’$$\forall n\forall X\exists \mathrm{Y}\varphi(n, X, \mathrm{Y})arrow\forall l\forall Z\exists W[(W)_{0}=Z\wedge\forall n<l\varphi(n, (W)_{n}, (W)_{n+1})]$と$\mathrm{R}\mathrm{C}\mathrm{A}_{0}$上同値であること, 並びに, 任意のが導出できること,$\mathrm{W}\mathrm{K}\mathrm{L}_{0}+\Sigma_{2}^{0_{-}}1\mathrm{N}\mathrm{D}$から$\Sigma_{2}^{0}$

$k$

に対し,

$\mathrm{R}\mathrm{C}\mathrm{A}_{0}+\Sigma_{k}^{0}$-BDC から$\mathrm{S}\mathrm{A}\mathrm{T}_{\mathrm{R}}$.

-BDC が導出できることが知られている([7] 参照).
定理 3.1.4. 論理式$\Sigma_{k}^{0_{-}}1\mathrm{N}\mathrm{D}$は次を満たすことが$\mathrm{R}\mathrm{C}\mathrm{A}_{0}+\Sigma_{2}^{0}$-BDC で示せる$\forall n[\mathrm{S}\mathrm{A}\mathrm{T}_{\mathrm{R}}(\exists v_{i+n-1}\exists v_{i+n-2}\cdots\exists v_{i}\varphi, E)\Rightarrow\exists A\in \mathbb{R}^{n}(\mathrm{S}\mathrm{A}\mathrm{T}_{\mathrm{R}}(\varphi, E_{A}^{\dot{l}}))]$

ここに,$E_{A}^{i}=E_{(A4)_{0},(A)_{1},\ldots,(A)_{n-1}}^{i,\dot{\iota}+1,\ldots,i+n-1}$である. これから,$\forall n[\mathrm{S}\mathrm{A}\mathrm{T}_{\mathbb{R}}(\exists v_{i_{0}}\exists v_{i_{1}}\cdots\exists v_{\dot{\iota}_{n-1}}\varphi, E)\Rightarrow\exists A\in \mathbb{R}^{n}(\mathrm{S}\mathrm{A}\mathrm{T}_{\mathrm{R}}(\varphi, E_{(A)_{0},(A)_{1},\ldots,(A)_{n-1}}^{\dot{l}_{0},\dot{l}1}’\ldots,)i_{n-1})]$

もいえる.

証明

$\varphi(m, \gamma, i, F, F’)$$(F’)_{j})$かつとき, 各 $m,$を“$\mathrm{S}\mathrm{A}\mathrm{T}_{\mathrm{R}}(\exists v_{i+m}\exists v:+m-1\ldots\exists v_{i}\gamma, F)$$\mathrm{S}\mathrm{A}\mathrm{T}_{\mathrm{R}}(\exists v_{i+m-1}\exists v_{i+m-2}\cdots\exists v_{i}\gamma, F’)]$$i,$$\gamma,$

$F$

に対し,

”

ならぼ酌 $\neq i+m((F)_{j}=$を主張する$\mathrm{S}\mathrm{A}\mathrm{T}_{\mathbb{R}}(\exists v:+m\exists v_{i+m-1}\cdots\exists v_{\dot{l}}\gamma, F)$$\Sigma_{2}^{0}$

論理式とする.

このならば定理 2.1.4 により$\mathrm{S}\mathrm{A}\mathrm{T}_{\mathbb{R}}(\exists v_{i+m-1}\exists v_{i+m-2}\cdots\exists v_{i}\gamma, F_{B}^{i+m})$なる実数 $B$ がとれる. $F’=F_{B}^{i+m}$ とすれば $\forall j\neq i+m((F)_{j}=(F’)_{j})$ かつ$\exists v_{i+m-2}\cdots\exists v_{i}\gamma,$

$F’)$

. よって

$\forall m\forall F\exists F’\varphi(m, \gamma, i, F, F’)$$E\wedge\forall m<n\varphi(m, \gamma, i, (W)_{m}, (W)_{m+1})$ととれば,$\Sigma_{2^{-}}^{0}1\mathrm{N}\mathrm{D}$により, 任意のなる $W$ がとれる.

$l\in \mathrm{N}$. ゆえに,$A\in \mathbb{R}^{l}$$\Gamma$$\mathrm{S}\mathrm{A}\mathrm{T}_{\mathrm{R}}(\exists v_{i+m-1}$-BDC’ より $(W)_{0}=$を $(A)_{j}=((W)_{n})_{i+n-j}$に対して$l<n+1arrow \mathrm{S}\mathrm{A}\mathrm{T}_{\mathrm{R}}(\exists v_{i+n-l-1}\exists v_{i+n-l-2}\cdots\exists v_{i}\gamma, E_{\langle(A)_{0},(A)_{1},\ldots,(A)_{l-1}\rangle}^{i})$120がいえる. 特に $l=n$ として$\mathrm{S}\mathrm{A}\mathrm{T}_{\mathrm{R}}(\gamma, E_{A}^{\dot{\iota}})$

を得る.

口

この定理の複素数版も同様に示せる.

参考文献[1] J. Barwise (ed). Handbook of Mathematical Logic. Studies in Logic and theFoundations of Mathematics. North-Holland, 1977.

[2] P. G. Odifreddi. Classical Recursion Theory. Studies in Logic and the Founda-

tions of Mathematics. North-Holland, 1989.
[3]$\mathrm{P}.\mathrm{C}$. Rosenbloom. An elementary constructive proof of the fundamental theoremof algebra. American Mathematics Monthly, Vol. 52, pp. 562-570, 1945.
[4] Wim B. G. Ruitenburg. Constructing roots of polynomials over the complex

numbers. In Computational Aspects of Lie Group Representations and Related
Topics, No. 84 in CWI Tract, 1991.
[5] S. G. Simpson. Subsystems of Second Order Arithmetic. Perspectives in Mathe-

matical Logic. Springer-Verlag, 1999.
[6] K. Tanaka and T. Yamazaki. Manipulating the reals in$\mathrm{R}\mathrm{C}\mathrm{A}_{0}$. Preprint.

[7] 田中一之, 山崎武. 2 階算術と有界選択公理. 2 階算術の諸体系の研究, 数理解析
研究所講究録, No. 1096. 京都大学数理解析研究所, 1999.

[8] 齋藤晃. 2 階算術における関数解析の基礎. 修士論文. 東北大学, 1996.