公理系(axiom system)とは、ある種類の数学的対象について出発点として認める性質を一階述語論理の文で書き並べた集合のことで、そのモデルの全体と、そこから論理的に出てくる文の全体(理論)を定める。同じ理論を与える公理系は同値であるといい、どの公理もほかの公理から出てこないとき独立であるという。公理の独立性は、その公理だけが偽になる構造を 1 つ作れば示せ、可算な公理系はいつも同値で独立な公理系に取り替えられる。コンパクト性定理により、無限で独立な公理系の理論は有限個の文では公理化できない。
前提知識: 一階述語論理, コンパクト性定理(一階論理)
公理系(axiom system)とは、ある種類の数学的対象について、出発点として認める性質を一階述語論理の文で書き並べたものである。群の公理、順序の公理、Peano算術 や ZFC公理系 の公理がその例である。公理系 $\Sigma$ を決めると、$\Sigma$ のすべての文を満たす構造の全体($\Sigma$ のモデルの全体)と、$\Sigma$ から論理的に出てくる文の全体($\Sigma$ の理論)が決まる。公理系について問うことは、おもにこの 2 つについての問いである。数学ではより広く、ある種類の構造を定める公理の一覧(位相空間の公理、マトロイドの公理、ホモロジー論の Eilenberg–Steenrod の公理など)も公理系とよぶ。そうした一覧は集合や写像についての条件として書かれ、一階の文の集合になるとは限らない(二階の帰納法の公理を含む Peano の公理系など)。この記事では、一階述語論理の文の集合として書かれた公理系を扱う。
この記事では、公理系、公理系が理論を公理化すること、2 つの公理系の同値、公理の独立性を定める。独立性はモデルを 1 つ作れば示せることを確かめ、群の公理と同値関係の公理が独立であることを有限のモデルで示す。次に、有限の公理系からは同値で独立な部分集合がとれること、可算な公理系はいつも同値で独立な公理系に取り替えられることを証明する。最後に、コンパクト性定理から、理論が有限個の文で公理化できるなら公理系のうちの有限個で足りることを導き、無限の独立な公理系の理論は有限公理化できないことを示す。
一階言語 $L$ を固定する。$L$ の文(自由変数をもたない論理式)と $L$ 構造については 一階述語論理 の定義に従う。$L$ 構造 $M$ で文 $\varphi$ が真であることを $M\models\varphi$ と書く。
この定め方は OLT26 Definition 17.1(閉包と公理化、p. 240)、Definition 17.2(集合のモデル、p. 242)と同じである。健全性定理 と Gödelの完全性定理 により、$\Sigma\models\varphi$ は $\Sigma$ から $\varphi$ が導出できること $\Sigma\vdash\varphi$ と同値である。したがって理論 $\operatorname{Cn}(\Sigma)$ は、$\Sigma$ を公理として加えた 形式体系 の定理のうち文であるものの全体と一致する。さらに $\Sigma$ は文の集合なので、自由変数をもつ論理式が $\Sigma$ から導出できることは、その全称閉包が導出できることと同値である(一階論理の証明体系 の定理「汎化定理」と同記事の公理図式 (A4))。よって、$L$ が可算で公理系が決定可能なとき(加えたものが 形式体系 の例「論理と理論の形式体系」の 2 の形式体系になるとき)、2 つの公理系が下の def-ax-equiv-indep の意味で同値であることは、それぞれを公理として加えた形式体系が 形式体系 の定義「同値・拡大・無矛盾」の意味で同値であることと同じである。以下では意味の側の $\models$ で述べ、導出は使わない。
$\Sigma$ がモデルをもつことは $\Sigma$ が 無矛盾性 の意味で無矛盾であることと同値である(同記事の定理「無矛盾性とモデルの存在」)。モデルをもたない $\Sigma$ ではどの文も帰結になる。
独立でない公理は、ほかの公理から出てくるので除いても理論は変わらない。独立な公理系とは、どの公理も欠かせない公理系のことである。
$\Sigma,\Sigma'$ を公理系、$\sigma\in\Sigma$ とする。
2 は、公理の独立性を示す標準の方法を与える。$\sigma$ だけが偽で残りの公理がすべて真になる構造を 1 つ作ればよい。OLT26 §17.1 の 5(p. 241)が、平行線公準がほかの幾何の公理から独立であることの示し方として挙げているのもこの方法である(平行線公準、Hilbertの公理系)。逆に、独立でないことを示すには、残りの公理からの帰結であることを示す。
公理系は、対象を外から直接指さす代わりに、満たすべき性質の一覧で対象の範囲を囲う道具である。一覧が短いほど確かめることが少なく、囲われる範囲は広い。公理を 1 つ足すと、モデルの全体は狭くなり、理論は大きくなる。同じ範囲を囲う一覧は何通りもあり、それらが同値な公理系である。独立性は、一覧に余分な項目がないことを表す。
独立性を確かめるには、問題の公理だけが成り立たない「ほとんどモデル」を見つける。後で見る群の公理の例では、3 つの公理それぞれについて、それだけが成り立たない小さな有限構造がある。一方、ある理論が有限個の公理では囲えないことは、1 つの構造では示せない。そこで使うのがコンパクト性定理である。
2 項関係記号 $R$ だけの言語で、次の 3 つの文を考える。
$$
\rho:\ \forall x\,R(x,x),\qquad \sigma:\ \forall x\,\forall y\,(R(x,y)\to R(y,x)),\qquad \tau:\ \forall x\,\forall y\,\forall z\,\bigl((R(x,y)\land R(y,z))\to R(x,z)\bigr)
$$
$\{\rho,\sigma,\tau\}$ のモデルは、$R$ の解釈が 同値関係 である構造にほかならない。この公理系は独立である。prop-ax-basic の 2 により、それぞれについて 1 つだけが偽になる構造を示せばよい。
定数記号 $1$ と 2 項演算の記号 $\cdot$ の言語で、群の理論は次の 3 つの文で公理化される(OLT26 Example 17.5、p. 243)。
$$
G_1:\ \forall x\,(x\cdot1=x),\qquad G_2:\ \forall x\,\forall y\,\forall z\,\bigl(x\cdot(y\cdot z)=(x\cdot y)\cdot z\bigr),\qquad G_3:\ \forall x\,\exists y\,(x\cdot y=1)
$$
右単位元と右逆元だけを要求する形だが、群 の命題「片側公理による群の特徴づけ」の左右を入れ替えた形により、モデルはちょうど群である。この 3 つは独立である。
$n\ge1$ について、「少なくとも $n$ 個の元がある」という等号だけの言語の文を
$$
\lambda_n:\ \exists x_1\cdots\exists x_n\bigwedge_{1\le i< j\le n}x_i\ne x_j
$$
とおく($\lambda_1$ は $\exists x_1\,(x_1=x_1)$ と読む)。$M\models\lambda_n$ は $M$ の元が $n$ 個以上あることを意味する。また $\mu_n:=\lnot(\lambda_n\land\lnot\lambda_{n+1})$ は「元がちょうど $n$ 個ではない」という文である。
$\Lambda:=\{\lambda_n\mid n\ge1\}$ のモデルは無限集合(を領域とする構造)の全体である。$m\le n$ なら $\lambda_n\models\lambda_m$ なので、$\Lambda$ は独立でない。たとえば $\Lambda\setminus\{\lambda_2\}$ は $\lambda_3$ を含むので $\lambda_2$ を帰結にもつ。
一方 $N:=\{\mu_n\mid n\ge1\}$ は $\Lambda$ と同値で、独立である。構造の領域は空でないので、$\operatorname{Mod}(N)$ は「どの $n$ についても元がちょうど $n$ 個ではない」構造、すなわち無限構造の全体であり、prop-ax-basic の 1 により同値である。$\mu_n$ を除いた残りは、ちょうど $n$ 個の元をもつ構造で真であり、この構造で $\mu_n$ は偽なので、$\mu_n$ は独立である。
公理系から余分な公理を取り除いて独立にできるかどうかは、公理系が有限か無限かで事情が変わる。
有限公理系 $\Sigma$ は、$\Sigma$ と同値で独立な部分集合をもつ。
$\Sigma$ が独立なら $\Sigma$ 自身をとればよい。独立でなければ、独立でない元 $\sigma$ を 1 つ選んで除く。prop-ax-basic の 3 により $\Sigma\setminus\{\sigma\}$ は $\Sigma$ と同値である。これを繰り返すと、元の個数が 1 つずつ減るので、有限回で独立な部分集合に達する(空集合は独立である)。同値は推移的なので、それは $\Sigma$ と同値である。$\square$
ex-ax-infinite の $\Lambda$ が示すように、無限の公理系では、同値で独立な部分集合がとれるとは限らない(後の反例の表を見よ)。それでも、公理を取り替えてよければ、可算な公理系については次が成り立つ。
可算な公理系 $\Sigma$ に対し、$\Sigma$ と同値で独立な公理系 $P$ が存在する。
$\Sigma$ が有限なら prop-ax-finite-indep による。$\Sigma$ が可算無限のとき、$\Sigma=\{\tau_0,\tau_1,\tau_2,\dots\}$ と並べる。
1 段目:前の公理から出るものを除く。 $\{\tau_0,\dots,\tau_{n-1}\}\models\tau_n$ となる $\tau_n$ を除き($n=0$ では $\tau_0$ がどの構造でも真のとき除く)、残りを順に $\sigma_0,\sigma_1,\dots$ とする。除いた $\tau_n$ はそれより前の $\tau$ の帰結であり、帰納法により前の $\sigma$ たちの帰結でもあるので、$\{\sigma_k\}$ は $\Sigma$ と同値である(prop-ax-basic の 1 の (c))。各 $\sigma_n$ について
$$
\{\sigma_0,\dots,\sigma_{n-1}\}\not\models\sigma_n\qquad(\ast)
$$
が成り立つ。残りが有限個なら、prop-ax-finite-indep によって終わる(残りがなければ空集合をとる)。以下、残りが無限個あるとする。
2 段目:含意に書き換える。 $\rho_0:=\sigma_0$、$n\ge1$ について
$$
\rho_n:=(\sigma_0\land\cdots\land\sigma_{n-1})\to\sigma_n
$$
とおき、$P:=\{\rho_n\mid n\ge0\}$ とする。
同値であること。 $\{\sigma_k\}$ のモデルでは各 $\rho_n$ の後件が真なので $\rho_n$ も真である。逆に $M\models P$ とする。$M\models\sigma_0$ であり、$M\models\sigma_0,\dots,\sigma_{n-1}$ なら $\rho_n$ の前件が真なので $M\models\sigma_n$ である。帰納法により $M\models\sigma_n$ がすべての $n$ で成り立つ。モデルの全体が等しいので同値である。
独立であること。 $n$ を固定する。$(\ast)$ により、$\sigma_0,\dots,\sigma_{n-1}$ が真で $\sigma_n$ が偽の構造 $M$ がある($n=0$ なら $\sigma_0$ が偽の構造)。$M$ で $\rho_n$ は前件が真で後件が偽なので偽である。$m< n$ なら $\sigma_m$ が真なので $\rho_m$ は真である。$m>n$ なら $\rho_m$ の前件は偽の $\sigma_n$ を含むので $\rho_m$ は真である。よって $M$ は $(P\setminus\{\rho_n\})\cup\{\lnot\rho_n\}$ のモデルであり、prop-ax-basic の 2 により $\rho_n$ は独立である。$\square$
$\Lambda$ にこの手順を当てると、$\lambda_1$ はどの構造でも真なので除かれ、$\sigma_k=\lambda_{k+2}$ となる。$n\ge1$ の $\rho_n$ は「元が $n+1$ 個以上なら $n+2$ 個以上」、すなわち $\mu_{n+1}$ と同じ構造で真になる文であり、$\rho_0=\lambda_2$ も $\mu_1$ と同じ構造で真になる。文ごとに置き換えれば、ex-ax-infinite の $N$ が得られる。
理論が有限個の文で公理化できるかどうかは、公理系を 1 つ眺めるだけでは分からない。次の命題は、問題を与えられた公理系の有限部分集合の問題に帰着させる。
公理系 $\Sigma$ の理論 $\operatorname{Cn}(\Sigma)$ が有限公理化可能なら、$\Sigma$ の有限部分集合 $\Sigma_0$ で $\Sigma$ と同値なものがある。
有限公理系 $\{\varphi_1,\dots,\varphi_k\}$ が $\operatorname{Cn}(\Sigma)$ を公理化するとし、$\varphi:=\varphi_1\land\cdots\land\varphi_k$ とおく($k=0$ なら $\varphi$ を $\forall x\,(x=x)$ とする)。$\varphi\in\operatorname{Cn}(\Sigma)$ なので $\Sigma\models\varphi$ である。コンパクト性定理(一階論理) の系「帰結の有限性」により、有限部分集合 $\Sigma_0\subset\Sigma$ で $\Sigma_0\models\varphi$ となるものがある。すると
$$
\operatorname{Cn}(\Sigma)=\operatorname{Cn}(\{\varphi_1,\dots,\varphi_k\})\subset\operatorname{Cn}(\Sigma_0)\subset\operatorname{Cn}(\Sigma)
$$
である。最初の包含は、$\Sigma_0$ のモデルで $\varphi$ が真なので各 $\varphi_i$ も真であることによる。最後の包含は $\Sigma_0\subset\Sigma$ による。よって $\Sigma_0$ は $\Sigma$ と同値である。$\square$
$\Sigma$ が無限で独立な公理系なら、$\operatorname{Cn}(\Sigma)$ は有限公理化可能でない。
有限公理化可能だとすると、prop-ax-finite-subset により $\Sigma$ と同値な有限部分集合 $\Sigma_0$ がある。$\Sigma$ は無限なので $\sigma\in\Sigma\setminus\Sigma_0$ がとれる。$\Sigma_0\subset\Sigma\setminus\{\sigma\}$ で $\Sigma_0\models\sigma$ なので $\Sigma\setminus\{\sigma\}\models\sigma$ となり、$\sigma$ の独立性に反する。$\square$
公理系についての代表的な問いは、モデルの全体と理論の言葉で次のように言える。$\Sigma$ が矛盾しないことはモデルをもつことである(無矛盾性)。どの文 $\varphi$ についても $\varphi$ か $\lnot\varphi$ が帰結になることが、理論が 完全な理論 であることである。ある濃度のモデルが同型を除いて 1 つしかないことが 範疇性 である。ある文が公理系から独立であるとは、その文もその否定も帰結にならないことであり、ZFC公理系 に対する 連続体仮説 がその例である(ZFC が無矛盾であるという仮定のもとで)。
| 外す仮定・手順 | 反例 | 成り立たなくなる結論 |
|---|---|---|
| prop-ax-finite-indep の「有限」 | $\Lambda=\{\lambda_n\mid n\ge1\}$ | 同値で独立な部分集合がある |
| prop-ax-finite-subset の「理論が有限公理化可能」 | $\Lambda$ | 同値な有限部分集合がある |
| cor-ax-infinite-indep の「独立」 | 群の公理に $\forall x\,((x\cdot1)\cdot1=x)$、$\forall x\,(((x\cdot1)\cdot1)\cdot1=x)$、… を加えた無限の公理系 | 理論は有限公理化可能でない |
| prf-ax-indep-exists の 1 段目(前の公理から出るものを除く手順) | $\tau_0=\lambda_3$、$\tau_1=\lambda_2$、$\tau_k=\lambda_{k+2}$($k\ge2$)と並べ、1 段目を飛ばして 2 段目を当てる | 得られた $P$ は独立である |
| def-ax-equiv-indep の 2 で「残りの公理全体」を見ること | $\{A,B,A\leftrightarrow B\}$、$A=\exists x\,P(x)$、$B=\exists x\,Q(x)$ | どの元もほかの 1 つの元から出なければ独立である |
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する