無矛盾性順序に関する注意
数理論理学に於いてGödelの第二不完全性定理が成り立つような理論 (以下ではこのような理論をGödel的と言う) $S,U$に対して相対的無矛盾性 (relativised consistency) というのが考えられることが多い。理論$T$に於いて理論$U$が理論$S$に対して相対的無矛盾であるというのは「$T$で$S$が無矛盾であると仮定したとき$U$の無矛盾性が証明できる」ということである。すなわち$$T\vdash\mathsf{Con}(S)\to\mathsf{Con}(U)$$が成立することである。例えばGödelは構成可能宇宙の理論を用いて、$\mathsf{PA}$に於いて$\mathsf{ZFC}+\mathsf{GCH}$が理論$\mathsf{ZF}$に対して相対的無矛盾であることを示している。さて相対的無矛盾性によって理論間に順序構造を入れることができ、それは以下のように定義される。
Gödel的理論$S,T,U$に対して二項関係$U\leq^T_\mathsf{Con} S$を$$T\vdash\mathsf{Con}(S)\to\mathsf{Con}(U)$$と定める。
任意のGödel的理論$T$に対して$\leq^T_\mathsf{Con}$は前順序になる。すなわち以下が成り立つ。
- 任意のGödel的理論$S$に対して$S\leq^T_\mathsf{Con} S$である。
- 任意のGödel的理論$S,U,V$に対して、$S\leq^T_\mathsf{Con} U$かつ$U\leq^T_\mathsf{Con} V$ならば$S\leq^T_\mathsf{Con} V$である。
明らか。
ではベースとなる理論を動かす、すなわちGödel的理論$S,U$に対して「$S$に於いて$S$が無矛盾であると仮定したとき$U$の無矛盾性が証明できる」というのを考えるとどうなるだろうか。
Gödel的理論$T,S$に対して$S\leq_\mathsf{Con} T$を$$T\vdash\mathsf{Con}(T)\to\mathsf{Con}(S)$$
と定める。
$\leq_\mathsf{Con} $は前順序にすらならない。
特に$T\leq_\mathsf{Con} S\leq_\mathsf{Con} U$であって$T\leq_\mathsf{Con} U$とならないようなGödel的理論$T,S,U$が存在する。
第二不完全性定理が証明できるようなGödel的理論$T$に対し
- $T_0:=T+\mathsf{Con}(T)+\mathsf{Con}(T+\mathsf{Con}(T))$
- $T_1:=T+\lnot\mathsf{Con}(T)$
- $T_2:=T+\mathsf{Con}(T)$
とする。まず自明に$T_1\vdash\mathsf{Con}(T_1)\to\mathsf{Con}(T)$であり、対偶を取れば$T_1\vdash\lnot\mathsf{Con}(T)\to\lnot\mathsf{Con}(T_1)$であり、よって$T_1\vdash\lnot\mathsf{Con}(T_1)$である。
このことから任意のGödel的理論$S$に対して$T_1\vdash\mathsf{Con}(T_1)\to\mathsf{Con}(S)$、つまり$S\leq_\mathsf{Con}T_1$であり、特に$T_0\leq_\mathsf{Con} T_1$である。
$T$は第二不完全性定理を示すことができるから$T\vdash\mathsf{Con}(T)\to\lnot\mathsf{Pr}_T(\mathsf{Con}(T))$であり、よって$T\vdash\mathsf{Con}(T)\to\mathsf{Con}(T_1)$。また明らかに$T\vdash\mathsf{Con}(T_2)\to\mathsf{Con}(T)$であるから$T_2\vdash\mathsf{Con}(T_2)\to\mathsf{Con}(T_1)$、よって$T_1\leq_\mathsf{Con}T_2$である。
$T_2+\mathsf{Con}(T_2)$に対して第二不完全性定理を適用すると$T_2+\mathsf{Con}(T_2)\nvdash\mathsf{Con}(T_0)$であり、よって$T_2\nvdash\mathsf{Con}(T_2)\to\mathsf{Con}(T_0)$、よって$T_0\leq_\mathsf{Con}T_2$は成り立たない。