New Foundations
概要
New Foundations（New Foundations）とは、Quine が提案した集合論で、外延性と、変数に型を割り当てて $x\in y$ では $y$ の型が $x$ の型より $1$ 大きくなるようにできる成層的な論理式についての内包の図式からなり、NF と略す。$x=x$ が成層的なのですべての集合からなる集合 $V$ が存在し、どの集合も補集合をもつが、$x\notin x$ は成層的でないので Russell の逆理は起こらない。Cantor の定理は一元集合の集合 $\iota[A]$ から冪集合への全射がないという形で成り立ち、写像 $x\mapsto\{x\}$ は $V$ 上では集合でない。NF は選択公理の否定を証明し（Specker）、原子を許す変種 NFU は無矛盾で選択公理と両立する。
New Foundations（NF）は、Quine が 1937 年に提案した集合論である（Hol98 Ch. 1, p. 11）。ZFC公理系と同じく所属関係 $\in$ だけを基本記号とし、対象はすべて集合だが、「条件を満たすもの全体は集合である」という内包の原理を、集合の大きさではなく論理式の形で制限する。許されるのは、変数に「型」を割り当てて $x\in y$ では $y$ の型が $x$ の型より $1$ 大きくなるようにできる成層的な論理式だけである（Kun80 Ch. I §12, p. 36）。
この制限のもとでは $x=x$ が使えるので、すべての集合からなる集合 $V$ が存在し、どの集合にも補集合がある。一方 $x\notin x$ は成層的でないので、Russell の逆理は起こらない。この記事では NF を定義し、基本の集合が存在することと、NF での Cantor の定理を証明する。後者から、$V$ の各元 $x$ に一元集合 $\{x\}$ を対応させる写像は集合でないことが分かる。最後に、選択公理の否定を導く Specker の定理、原子を許す変種 NFU、無矛盾性について述べる。
定義
$\in$ と $=$ だけを使う一階の論理式 $\varphi$ が成層的であるとは、$\varphi$ に現れる各変数（自由変数も束縛変数も）に自然数（型）を一つずつ割り当てて、次を満たすようにできることをいう（Hol98 Ch. 7, p. 44）。
(a) 同じ変数には、現れるどこでも同じ型を割り当てる。
(b) 原子式 $x=y$ では、$x$ と $y$ の型が等しい。
(c) 原子式 $x\in y$ では、$y$ の型が $x$ の型より $1$ 大きい。
束縛変数は名前を付け替えてよいので、別々の量化子が束縛する変数には別々の型を割り当ててよい。
NF は次の二つからなる（Kun80 Ch. I §12, p. 36、Hol98 Ch. 8, p. 47）。
(i) 外延性：$\forall a\,\forall b\,\bigl(\forall x\,(x\in a\leftrightarrow x\in b)\to a=b\bigr)$。
(ii) 成層的内包の図式：$\varphi(x,p_1,\dots,p_k)$ を成層的な論理式とし、$a$ は $\varphi$ に現れないとする。このとき
$$
\forall p_1\cdots\forall p_k\ \exists a\ \forall x\ \bigl(x\in a\leftrightarrow\varphi(x,p_1,\dots,p_k)\bigr).
$$
(ii) で得る $a$ は外延性により一意なので、$\{x\mid\varphi(x,\vec p)\}$ と書く。(ii) の式自身も、$a$ に $x$ の型より $1$ 大きい型を割り当てれば成層的である。
成層的であるかは、略記を元の論理式に戻して判定する。よく使う略記の型の関係は次のとおりで、どれも定義を書き下せば確かめられる。
| 略記 | 定義 | 型の条件 |
|---|---|---|
| $x\subseteq y$ | $\forall z\,(z\in x\to z\in y)$ | $x,y$ は同じ型 |
| $y=\{x\}$ | $\forall z\,(z\in y\leftrightarrow z=x)$ | $y$ は $x$ より $1$ 大きい |
| $z=\{x,y\}$ | $\forall w\,(w\in z\leftrightarrow w=x\lor w=y)$ | $x,y$ は同じ型、$z$ はそれより $1$ 大きい |
| $z=\langle x,y\rangle$ | $z=\{\{x\},\{x,y\}\}$（Kuratowski の順序対） | $x,y$ は同じ型、$z$ はそれより $2$ 大きい |
特に順序対 $\langle x,y\rangle$ の二つの成分は同じ型でなければならない。関数や関係は順序対の集合として定めるので、$f(x)=y$ と書くとき、$x$ と $y$ は同じ型で、$f$ はそれより $3$ 大きい。
例：成層的な論理式とそうでない論理式
- $x=x$ は成層的である（$x$ に型 $0$）。
- $x\notin a$ は成層的である（$x$ に $0$、$a$ に $1$）。
- $\exists y\,(y\in a\land x\in y)$ は成層的である（$x$ に $0$、$y$ に $1$、$a$ に $2$）。
- $x\notin x$ は成層的でない。$x\in x$ の両辺が同じ変数なので、(a) と (c) を同時に満たせない。
- $\exists y\,(z=\langle y,\{y\}\rangle)$ は成層的でない。順序対の二つの成分 $y$ と $\{y\}$ に同じ型が要るが、$\{y\}$ の型は $y$ の型より $1$ 大きい。
- により、NF は $\{x\mid x\notin x\}$ を集合として与えない。実際この集合が存在すると Russell の逆理で矛盾する（ZFC公理系の定理「すべての集合からなる集合はない」の証明と同じ議論）。(5) は、写像 $y\mapsto\{y\}$ をそのまま内包で作ることはできないことを示している。この写像が集合でないことは、下の cor-nf-singleton-map で証明する。
基本の集合
NF の中で、任意の集合 $a,b$ に対し次の集合が存在する。
(1) 普遍集合 $V=\{x\mid x=x\}$。特に $V\in V$。
(2) 空集合 $\emptyset=\{x\mid x\neq x\}$ と補集合 $a^{c}=\{x\mid x\notin a\}$。
(3) $a\cap b$、$a\cup b$、$\{a,b\}$、$\bigcup a$。
(4) 冪集合 $\mathcal P(a)=\{x\mid x\subseteq a\}$ と、一元集合の集合 $\iota[a]:=\{y\mid\exists x\,(x\in a\land y=\{x\})\}$。
(5) 直積 $a\times b=\{z\mid\exists x\,\exists y\,(x\in a\land y\in b\land z=\langle x,y\rangle)\}$。
どれも成層的内包 (ii) の例である。各論理式に型を割り当てて、成層的であることを示せばよい。以下、集合の元になる変数（$\{x\mid\cdots\}$ の $x$ や $y,z$）の型を $0$ から数える。
(1) $x=x$ は $x$ に $0$ で成層的。$V$ はすべての集合を元にもつので、$V$ 自身も元にもつ。
(2) $x\neq x$ は (1) と同じ。$x\notin a$ は $x$ に $0$、$a$ に $1$。
(3) $x\in a\land x\in b$、$x\in a\lor x\in b$、$x=a\lor x=b$ は、$x$ に $0$、前の二つでは $a,b$ に $1$、最後では $a,b$ に $0$。$\exists y\,(y\in a\land x\in y)$ は ex-nf-stratified の (3) である。
(4) $x\subseteq a$ は、略記 $\forall z\,(z\in x\to z\in a)$ の $z$ に $0$、$x,a$ に $1$。$\exists x\,(x\in a\land y=\{x\})$ は $x$ に $0$、$a$ と $y$ に $1$。
(5) $x,y$ に $0$、$a,b$ に $1$、$z$ に $2$ を割り当てると、$x\in a$、$y\in b$、$z=\langle x,y\rangle$ の型の条件がすべて満たされる。$\square$
- により、NF の集合は補集合をもち、$V$ の部分集合全体は $\cap$、$\cup$、補集合について Boole 代数をなす。ZFC ではどの集合も補集合をもたない（補集合と元の和は全体集合になるため）ので、ここが ZFC と最も違う点である。
一方、ZFC の分出図式は NF では一般に成り立たない。$a=V$ と論理式 $x\notin x$ に分出を当てると $\{x\mid x\notin x\}$ になるからである。
NF での Cantor の定理
ZFC の Cantorの定理 は「集合 $A$ から $\mathcal P(A)$ への全射はない」と述べる。NF では $V$ の部分集合はすべて $V$ の元なので $\mathcal P(V)=V$ であり、恒等写像が $V$ から $\mathcal P(V)$ への全射になる（恒等写像 $\{z\mid\exists x\,(z=\langle x,x\rangle)\}$ は成層的な内包で得られる）。したがってこの形の Cantor の定理は NF では成り立たない。成り立つのは、定義域を一元集合の集合 $\iota[A]$ に替えた形である。
$X$ から $Y$ への関数とは、$X\times Y$ の部分集合 $f$ で、各 $s\in X$ に対し $\langle s,t\rangle\in f$ となる $t$ がちょうど一つあるものをいい、その $t$ を $f(s)$ と書く。全射・単射は通常どおり定める。
NF の中で、任意の集合 $A$ について、$\iota[A]$ から $\mathcal P(A)$ への全射は存在しない（Hol98 §17.2, p. 130 の議論）。
$f$ を $\iota[A]$ から $\mathcal P(A)$ への関数とし、$f$ の値にならない $A$ の部分集合を作る。
$$
D:=\bigl\{x\ \big|\ x\in A\land\exists s\,\exists B\,\bigl(s=\{x\}\land\langle s,B\rangle\in f\land x\notin B\bigr)\bigr\}
$$
とおく。この論理式は成層的である：$x$ に $0$、$s$ と $B$ と $A$ に $1$ を割り当てると、$s=\{x\}$、$x\in A$、$x\notin B$ の条件が満たされ、順序対 $\langle s,B\rangle$ の型は $3$ になるので、$f$ に $4$ を割り当てればよい。よって成層的内包 (ii) により $D$ は集合で、$D\subseteq A$ すなわち $D\in\mathcal P(A)$ である。
$f$ が全射だと仮定すると、$f(s)=D$ となる $s\in\iota[A]$ があり、$s=\{d\}$ となる $d\in A$ がある。$f$ は関数なので、$\langle\{d\},B\rangle\in f$ となる $B$ は $D$ だけである。したがって $D$ の定義から
$$
d\in D\iff d\notin D
$$
となり、矛盾する。よって全射はない。$\square$
この証明は ZFC の Cantorの定理 の対角線論法と同じ形をしている。違いは、$f$ の引数を $x$ ではなく $\{x\}$ にした点だけである。$f(x)$ と書くと $x$ と $f(x)\subseteq A$ の型が合わず、$D$ の定義が成層的でなくなる。
NF の中で次が成り立つ。
(1) $\iota[V]$ から $V$ への全射は存在しない。特に $\iota[V]\neq V$ である。
(2) 包含写像は $\iota[V]$ から $V$ への単射だが、$\iota[V]$ と $V$ の間に全単射はない。
(3) すべての $x$ について $\langle x,\{x\}\rangle\in s$、かつ $s$ の元はすべてこの形であるような集合 $s$ は存在しない。すなわち、写像 $x\mapsto\{x\}$ は集合でない。
- NF の対象はすべて集合で、どの $x$ も $x\subseteq V$ を満たすので、$\mathcal P(V)=V$ である。thm-nf-cantor を $A=V$ に当てればよい。$\iota[V]=V$ なら恒等写像が全射になるので、$\iota[V]\neq V$ である。
- 包含写像 $\{z\mid\exists y\,(y\in\iota[V]\land z=\langle y,y\rangle)\}$ は成層的な内包で得られる単射である。全単射 $\iota[V]\to V$ があれば全射であり、(1) に反する。全単射 $V\to\iota[V]$ があれば、(3) の $r$ と同じ成層的な内包でその逆をとると全単射 $\iota[V]\to V$ になり、やはり (1) に反する。
- そのような $s$ があるとする。その逆 $r:=\{z\mid\exists x\,\exists y\,(\langle x,y\rangle\in s\land z=\langle y,x\rangle)\}$ は成層的な内包で得られる（$x,y$ に $0$、$z$ に $2$、$s$ に $3$）。$s$ の元 $\langle x,y\rangle$ では $y=\{x\}$ なので、$r$ は各 $\{x\}\in\iota[V]$ に $x$ を対応させる関数であり、$\iota[V]$ から $V$ への全射になる。これは (1) に反する。$\square$
ZFC では、任意の集合 $A$ 上で $x\mapsto\{x\}$ は置換図式により集合になり、$A$ と $\iota[A]$ の間の全単射を与える。NF ではこれが $A=V$ で崩れる。$A$ と $\iota[A]$ の間に全単射がある集合 $A$ を Cantor 的（Cantorian）といい、Cantor 的な $A$ では通常の形の Cantor の定理「$A$ から $\mathcal P(A)$ への全射はない」がそのまま成り立つ（Hol98 §17.5, p. 134）。
理由を開く
$h$ を $A$ から $\iota[A]$ への全単射とし、$g$ を $A$ から $\mathcal P(A)$ への全射とする。$h^{-1}$ を合成した $g\circ h^{-1}$ は $\iota[A]$ から $\mathcal P(A)$ への全射になり、thm-nf-cantor に反する。合成 $g\circ h^{-1}=\{z\mid\exists s\,\exists x\,\exists B\,(\langle x,s\rangle\in h\land\langle x,B\rangle\in g\land z=\langle s,B\rangle)\}$ は、$x,s,B$ に $0$、$z$ に $2$、$h,g$ に $3$ を割り当てれば成層的なので、集合として存在する。
Specker の定理
NF の大きな特徴は、選択公理と両立しないことである。
NF は選択公理の否定を証明する（Specker, 1953。Kun80 Ch. I §12, p. 36。この記事では証明しない）。
Hol98 §17.4（pp. 132–133）は、原子を許す体系に選択公理を加えたものの中で $\lvert\mathcal P(V)\rvert<\lvert V\rvert$ を示し、そこから原子が存在することを導いている。原子のない NF では $\mathcal P(V)=V$（cor-nf-singleton-map の証明）なので、同じ議論が選択公理と Axiom of Counting のもとで矛盾を導く。Hol98 の証明は、成層的でない条件についての自然数の帰納法を使うために追加の公理（Axiom of Counting）を使うが、外延性・成層的内包・選択公理だけによる、より込み入った証明もある（Hol98 p. 134）。
この議論の要は、NF では $\iota[A]$ と $A$ の大きさが一般に一致せず、thm-nf-cantor が「$\iota[A]$ は $\mathcal P(A)$ より真に小さい」という形でしか成り立たない点にある。
原子を許す変種 NFU
NFU は、外延性を集合に限って弱め、元をもたない対象（原子）を許した体系である。言語に「$x$ は集合である」という述語を加え、次を公理とする（Hol98 Ch. 2, p. 16 と Ch. 8, p. 47。原子を許す一般の形は Shu18 p. 8）。
- 集合の外延性：集合 $a,b$ が同じ元をもてば $a=b$。
- 原子の公理：集合でない対象は元をもたない。
- 成層的内包：成層的な $\varphi$ について、集合 $\{x\mid\varphi\}$ が存在する。
NFU では原子 $p$ も元をもたないので $p\subseteq a$ を満たしてしまう。そこで冪集合を $\mathcal P(a):=\{x\mid x\text{ は集合}\land x\subseteq a\}$ と定めると、prop-nf-basic-sets と thm-nf-cantor は同じ証明で成り立つ（使ったのは成層的内包と、$\{x\}$・順序対が定まることだけであり、「$x$ は集合」は型の条件に関わらない）。原子は $\mathcal P(V)$ に属さないので、原子があれば $\mathcal P(V)\subsetneq V$ である。
NFU は Jensen（1969）により無矛盾性が示され、無限公理とも選択公理とも両立する（Hol98 Ch. 1, pp. 11–12。この記事では証明しない）。選択公理を加えた NFU では原子が存在する（Hol98 §17.4）。
無矛盾性
NF の無矛盾性は長く未解決だった。Holmes と Wilshaw は、NF と等無矛盾な体系のモデルを ZFC の一部分の中で作ることで NF の無矛盾性を証明したと発表し、その構成が Lean で形式的に検証されたと述べている（HW25 §1.1, p. 3、§3, p. 24。この記事では証明しない）。
反例の表
| 外す条件 | 反例 | 成り立たなくなること |
|---|---|---|
| 内包の論理式が成層的であること | $x\notin x$ | 内包の図式の無矛盾性（Russell の逆理） |
| thm-nf-cantor の定義域が $\iota[A]$ であること（$A$ に替える） | $A=V$ と恒等写像 $V\to\mathcal P(V)=V$ | $A$ から $\mathcal P(A)$ への全射がないこと |
| 選択公理を加えないこと | NF＋選択公理 | 無矛盾性（thm-nf-specker） |
1 行目は ex-nf-stratified の (4)、2 行目は節「NF での Cantor の定理」の冒頭による。3 行目は、NF が選択公理の否定を証明するので、選択公理を加えると矛盾することを表す。
ZFC との比較
| 性質 | ZFC | NF |
|---|---|---|
| 普遍集合 $V$ | 存在しない | 存在する |
| 補集合 | どの集合にもない | すべての集合にある |
| 内包の制限 | 既存の集合の中から選ぶ（分出） | 成層的な論理式に限る |
| $x\mapsto\{x\}$ | 各集合上で集合（置換） | $V$ 上では集合でない |
| 選択公理 | 公理に含む | 否定が証明できる |
NF の「すべての群の集合」「すべての 3 元集合の集合」のような大きな集まりは集合として存在する。たとえば濃度を、互いに全単射がある集合の同値類 $\{b\mid b\text{ と }a\text{ の間に全単射がある}\}$ として定められる（この論理式は、全単射 $f$ に $a,b$ より $2$ 大きい型を割り当てれば成層的）。
注意
- 成層的であるかは論理式の形の性質であり、同値な論理式の中に成層的なものがあれば内包が使える。たとえば $\{x,\{y\}\}$ は成層的に定義できるが、$\{x,\{x\}\}$ の自然な定義は成層的でない（Hol98 §8.3, p. 54）。
- NF の公理は有限個の公理で置き換えられることが知られている（Hailperin。Hol98 Ch. 1, p. 12）。
関連項目
- 前提: ZFC公理系, Cantorの定理, 一階述語論理
- 比較: Zermelo集合論, Kripke–Platek集合論, 構成的集合論, NBG集合論
- 発展: 選択公理, 型理論
参考文献
Mathpediaは寄付と、参考文献の書籍リンク（Amazonアソシエイト）の紹介料で運営されています。 支援について ／ 寄付する
