集合の圏の初等理論
概要
集合の圏の初等理論（Elementary Theory of the Category of Sets、ETCS）とは、所属関係ではなく集合と写像を基本にとり、集合の圏が満たす性質を圏の一階の公理として述べた Lawvere の集合論である。今日の形では、自然数対象をもち、すべてのエピ射が切断をもち（選択公理）、終対象 $1$ が射を区別する（well-pointed）、退化していないトポスの理論として述べられる。その中では写像が元 $1\to A$ での値で決まり、真理値はちょうど 2 つになる。ZFC の集合の圏はそのモデルであり、ETCS は有界 Zermelo 集合論と等無矛盾である。
ZFC公理系では、すべての対象が集合であり、基本の関係は所属 $x\in y$ である。写像は順序対の集合として、自然数は $\emptyset,\{\emptyset\},\{\emptyset,\{\emptyset\}\},\dots$ として組み立てられる。これに対し Lawvere は、集合と写像を基本にとり、集合と写像のなす圏が満たす性質を、圏の言葉の一階の公理として書き下した（Law05 pp. 7–8）。これが 集合の圏の初等理論（Elementary Theory of the Category of Sets、ETCS）である。ETCS では、集合 $A$ の元とは 1 点集合 $1$ からの写像 $1\to A$ のことであり、元は、属する集合と写像による関係のほかに性質をもたない（Law05 pp. 2–3 の McLarty による解説）。
今日の言葉では、ETCS は、自然数対象をもち選択公理を満たす well-pointed なトポスの理論である（Shu18 §4, p. 16、MM92 第 VI 章の冒頭, p. 268）。この記事では、この形で ETCS を定義し、ETCS の中では元が射を決めること（単射・全射・同型の判定）、真理値がちょうど 2 つであること、Cantor の定理を証明する。さらに、ZFC の集合と写像の圏が ETCS の公理を満たすことを証明し、逆向きの比較（有界 Zermelo 集合論との等無矛盾性）を引用して述べる。
定義
射の合成は $g\circ f$（先に $f$）と書く。終対象を $1$、始対象を $0$ と書き、対象 $A$ から $1$ への唯一の射を $!_A$ と書く。
終対象 $1$ をもつ圏で、射 $x\colon1\to A$ を対象 $A$ の 元（大域元）という。射 $f\colon A\to B$ と $A$ の元 $x$ に対し、$B$ の元 $f\circ x$ を $f(x)$ とも書く。
圏 $\mathcal S$ が次の 4 条件を満たすとき、$\mathcal S$ を ETCS のモデル という。
- （トポス）$\mathcal S$ は有限極限と有限余極限をもち、Cartesian 閉であり（Cartesian閉圏）、部分対象分類子 $\mathrm{true}\colon1\to\Omega$ をもつ。
- （無限）$\mathcal S$ は自然数対象 $(N,0,s)$ をもつ。
- （well-pointed）次の (a)(b) が成り立つ。
- (a) $1$ が生成する：射 $f,g\colon A\to B$ について、$A$ のすべての元 $x$ で $f\circ x=g\circ x$ ならば $f=g$ である。
- (b) 退化していない：射 $1\to0$ は存在しない。
- （選択）すべてのエピ射 $p\colon X\to I$ は切断をもつ。すなわち $p\circ s=\operatorname{id}_I$ となる射 $s\colon I\to X$ がある。
条件 1〜4 は、対象・射・合成についての一階の文として書ける。これらを公理とする（古典論理の）一階の理論を 集合の圏の初等理論（ETCS）という。
条件 1 は $\mathcal S$ が初等トポス（トポス の定義「初等トポス」）であることにあたる。トポスでは有限余極限の存在は残りの条件から従う（MM92 第 IV 章の冒頭, p. 161）が、ここでは公理に含めておく。
Lawvere の元の論文は、圏の公理に加えて次の 8 つを置く（Law05 pp. 8–19。そこでは合成を $fg$＝「$f$ のあとに $g$」と書く）。
8 つの公理を開く
- 有限の極限と余極限（終対象・始対象・積・和・等化子・余等化子）が存在する。
- 指数 $B^A$ が存在する。
- 自然数の対象（Dedekind–Peirce 対象）$N$ が存在する。
- $1$ が生成する。
- 選択公理：$f$ の始域が元をもてば、$f\circ g\circ f=f$ となる $g$ がある。
- 始対象でない対象は元をもつ。
- 和の元はどちらかの入射の元から来る。
- 2 つ以上の元をもつ対象がある。
部分対象分類子は公理に含まれていない。Lawvere 自身の注釈によれば、この論文では選択公理などからトポスの性質（特性関数による部分対象の表現）が導かれている（Law05 p. 5）。Shu18 p. 16 は、Lawvere の ETCS を「自然数対象をもち古典論理と選択公理を満たす well-pointed なトポスの理論」として扱っている。
直感
ETCS の集合には「中身」がない。集合 $A$ について語れるのは、$A$ に出入りする写像だけである。それでも条件 3(a) により、写像は元での値で決まり、ふだんの集合の議論がそのまま書ける。積・指数・部分対象分類子は、直積集合・写像の集合・冪集合を普遍性で特徴づけたものであり、ZFC のように特定の集合として作ったものではない。そのため ETCS の定理はどれも同型で不変であり、たとえば「$3\in5$ か」のような、自然数の作り方に依存する問いは立てられない（Law05 p. 7、pp. 2–3 の McLarty による解説）。
| ZFC の言葉 | ETCS の言葉 |
|---|---|
| 集合 $A$、元 $a\in A$ | 対象 $A$、元 $a\colon1\to A$ |
| 写像 $f\colon A\to B$（順序対の集合） | 射 $f\colon A\to B$（基本の概念） |
| 部分集合 $S\subset A$ | 部分対象 $S\rightarrowtail A$、または射 $A\to\Omega$ |
| 直積 $A\times B$、写像の集合 $B^A$ | 積 $A\times B$、指数 $B^A$ |
| 冪集合 $\mathcal P(A)$ | 指数 $\Omega^A$ |
| 自然数 $\omega$ | 自然数対象 $(N,0,s)$ |
| 選択公理 | エピ射が切断をもつ |
| $x\in y\in z$ | 意味をもたない |
元が射を決める
ETCS では、射の性質が元での振る舞いで判定できる。射 $f\colon A\to B$ が元について 単射 であるとは、$A$ の元 $x,x'$ について $f(x)=f(x')$ なら $x=x'$ となることをいい、全射 であるとは、$B$ の任意の元 $y$ に対し $f(x)=y$ となる $A$ の元 $x$ があることをいう。
1：モノ射なら、元 $x,x'\colon1\to A$ について $f\circ x=f\circ x'$ から $x=x'$ が従う。逆に $f$ が元について単射で、射 $g,h\colon T\to A$ が $f\circ g=f\circ h$ を満たすとする。$T$ の任意の元 $t$ について $f(g\circ t)=f(h\circ t)$ なので $g\circ t=h\circ t$ であり、条件 3(a) により $g=h$ である。
2：$f$ が元について全射で、射 $g,h\colon B\to C$ が $g\circ f=h\circ f$ を満たすとする。$B$ の元 $y$ に対し $f\circ x=y$ となる元 $x$ をとると、$g\circ y=g\circ f\circ x=h\circ f\circ x=h\circ y$ である。条件 3(a) により $g=h$ なので、$f$ はエピ射である。逆に $f$ がエピ射なら、条件 4 により $f\circ s=\operatorname{id}_B$ となる $s$ があり、$B$ の元 $y$ について $x:=s\circ y$ が $f\circ x=y$ を満たす。
3：同型なら逆射により元について単射かつ全射である。逆に $f$ が元について単射かつ全射なら、1・2 により $f$ はモノ射かつエピ射である。条件 4 により $f\circ s=\operatorname{id}_B$ となる $s$ がある。すると $f\circ(s\circ f)=f=f\circ\operatorname{id}_A$ で、$f$ はモノ射なので $s\circ f=\operatorname{id}_A$ である。よって $s$ は $f$ の逆射である。$\square$
条件 4 を仮定しなくても、古典論理のもとで条件 1・3 を満たす圏では、正則エピ射であることと元について全射であることが同値になり、3 も成り立つ（Shu18 Corollary 4.5, p. 15 と Lemma 4.7 (i)(ii), p. 15。この記事では証明しない）。上の証明は選択公理を使って短くしたものである。
真理値はちょうど 2 つ
トポスの真理値は $\Omega$ の元であり、一般には 2 つとは限らない（部分対象分類子 の定理「前層圏の分類子」）。ETCS では 2 つに限られる。$0$ は厳密な始対象である（始対象 の命題「デカルト閉な圏の始対象は厳密」）ので、$0\to A$ はモノ射であり（同じ記事の系「厳密な始対象からの射はモノ射」）、$A$ の部分対象 $0\rightarrowtail A$ を定める。$\mathrm{false}\colon1\to\Omega$ を $0\rightarrowtail1$ の特性射と定める。
$\mathcal S$ が条件 1 と 3 を満たす圏とする。
- 元をもたない対象は始対象である。
- $1$ の部分対象は、$0\rightarrowtail1$ と $\operatorname{id}_1$ のどちらかと同じ部分対象である。
- $\Omega$ の元はちょうど $\mathrm{true}$ と $\mathrm{false}$ の 2 つで、$\mathrm{true}\ne\mathrm{false}$ である。
1：$A$ が元をもたないとする。$A$ の 2 つの部分対象 $\operatorname{id}_A$ と $0\rightarrowtail A$ の特性射を $\chi_1,\chi_0\colon A\to\Omega$ とする。$A$ には元がないので、「すべての元 $x$ で $\chi_1\circ x=\chi_0\circ x$」は成り立ち、条件 3(a) により $\chi_1=\chi_0$ である。特性射と部分対象は一対一に対応する（部分対象分類子 の命題「特性射と部分対象の対応」）ので、$\operatorname{id}_A$ と $0\rightarrowtail A$ は同じ部分対象であり、ある同型 $u\colon A\to0$ がある。よって $A\cong0$ である。
2：$m\colon U\rightarrowtail1$ をモノ射とする。$U$ が元 $u\colon1\to U$ をもてば、$m\circ u\colon1\to1$ は $\operatorname{id}_1$ に等しい。すると $m\circ(u\circ m)=m=m\circ\operatorname{id}_U$ で、$m$ はモノ射なので $u\circ m=\operatorname{id}_U$ である。よって $m$ は同型で、$m$ は $\operatorname{id}_1$ と同じ部分対象である。$U$ が元をもたなければ、1 により $U$ は始対象で、$m$ は $0\rightarrowtail1$ と同じ部分対象である。
3：$\Omega$ の元 $1\to\Omega$ は $1$ の部分対象と一対一に対応し、$\mathrm{true}$ は $\operatorname{id}_1$ に、$\mathrm{false}$ は $0\rightarrowtail1$ に対応する。2 により $\Omega$ の元はこの 2 つである。$0\rightarrowtail1$ と $\operatorname{id}_1$ が同じ部分対象なら $1\cong0$ となり、射 $1\to0$ があることになって条件 3(b) に反する。よって $\mathrm{true}\ne\mathrm{false}$ である。$\square$
さらに、well-pointed なトポスは Boolean である。すなわち任意の部分対象 $S\rightarrowtail E$ について $S\vee\neg S=E$ が成り立つ（MM92 第 VI 章 §1 Proposition 7, p. 276。この記事では証明しない）。ETCS の内部では、古典論理の推論がそのまま使える。
ETCS のモデルで、どの対象 $A$ についても、エピ射 $A\to\Omega^A$ は存在しない。
確かめを開く
$\neg\colon\Omega\to\Omega$ を、モノ射 $\mathrm{false}\colon1\to\Omega$ の特性射とする。$\Omega$ の元 $x$ について、引き戻しの性質から「$\neg\circ x=\mathrm{true}$ ⟺ $x$ が $\mathrm{false}$ を経由する ⟺ $x=\mathrm{false}$」である（$1\to1$ は $\operatorname{id}_1$ だけなので、経由するなら $x=\mathrm{false}$）。prop-etcs-two-valued の 3 により、$\neg\circ\mathrm{false}=\mathrm{true}$、$\neg\circ\mathrm{true}=\mathrm{false}$ であり、$\neg$ は元の不動点をもたない。一方、エピ射 $g\colon A\to\Omega^A$ があれば、thm-etcs-elements の 2 により $g$ は元について全射であり、Cartesian閉圏 の定義「弱い点全射」の後の段落により弱い点全射である。すると同じ記事の定理「Lawvere の不動点定理」により $\neg$ は不動点をもつことになり、矛盾する。
自然数対象については、Lawvere が ETCS の公理から Peano の公理（後者関数が単射であること、$0$ が後者でないこと、部分対象についての帰納法）を導いている（Law05 Theorem 2, pp. 20–21）。一般のトポスでの帰納法と $1+N\cong N$ は 自然数対象 の定理「帰納法」と定理「Lambek の同型と商」にある。
主定理：集合の圏は ETCS のモデルである
ZFC で、すべての集合と写像のなす圏 $\mathbf{Set}$ は def-etcs-main の条件 1〜4 を満たす。
1 点集合 $1=\{\emptyset\}$ を終対象、$\emptyset$ を始対象とし、写像 $x\colon1\to A$ を元 $x(\emptyset)\in A$ と同一視する。これは $A$ の元と、$\mathbf{Set}$ での $A$ の元（def-etcs-element）との一対一対応である。
条件 1。積は直積集合 $A\times B$ と射影、等化子は $f,g\colon A\to B$ に対する $\{a\in A\mid f(a)=g(a)\}$ と包含写像、和は $(\{0\}\times A)\cup(\{1\}\times B)$、余等化子は $B$ を $\{(f(a),g(a))\mid a\in A\}$ が生成する同値関係で割った商集合である。どれも分出の公理で作れ、普遍性はふつうの集合の議論で確かめられる。指数 $B^A$ は $A$ から $B$ への写像全体（$\mathcal P(A\times B)$ の部分集合）で、$\operatorname{ev}(h,a)=h(a)$ とする。写像 $u\colon X\times A\to B$ に $x\mapsto(a\mapsto u(x,a))$ を対応させると $\operatorname{Hom}(X\times A,B)\to\operatorname{Hom}(X,B^A)$ の全単射になる。部分対象分類子は $\Omega=\{0,1\}$ と $\mathrm{true}(\emptyset)=1$ である。
部分対象分類子の確かめを開く
単射 $m\colon S\to X$ に対し、$\chi_m(x)=1$ が $x\in m(S)$ と同値になるように $\chi_m\colon X\to\Omega$ を定める。$\mathrm{true}$ の $\chi_m$ に沿う引き戻しは $\{x\in X\mid\chi_m(x)=1\}=m(S)$ と包含写像であり、$m\colon S\to m(S)$ は全単射なので、$m$ を左辺とする正方形も引き戻しである。逆に $\chi\colon X\to\Omega$ で同じ正方形が引き戻しになるなら、$x\in X$ について「$\chi(x)=1$ ⟺ $x$ が $m$ を経由する ⟺ $x\in m(S)$」なので $\chi=\chi_m$ である。
条件 2。無限の公理による $\omega$ と $0=\emptyset$、$s(n)=n\cup\{n\}$ が自然数対象である（自然数対象 の例「集合の圏」）。
条件 3。(a) $f\ne g\colon A\to B$ なら $f(a)\ne g(a)$ となる $a\in A$ があり、対応する元 $x$ で $f\circ x\ne g\circ x$ である。(b) $\{\emptyset\}$ から $\emptyset$ への写像はない。
条件 4。まずエピ射 $p\colon X\to I$ は全射である。実際、$i\in I$ が $p$ の像にないとすると、$i$ でだけ $1$ をとる写像 $\chi\colon I\to\{0,1\}$ と定数写像 $c_0$ は異なるが、$\chi\circ p=c_0\circ p$ となり、エピ射であることに反する。よって $\{p^{-1}(i)\}_{i\in I}$ は空でない集合の族であり、選択公理による選択関数 $s$（$s(i)\in p^{-1}(i)$）が $p\circ s=\operatorname{id}_I$ を満たす。$\square$
確かめに使ったのは、外延性・空集合・対・合併・冪集合・無限と、有界な論理式（量化子がすべて「$\forall x\in b$」「$\exists x\in b$」の形）についての分出、それに条件 4 のための選択公理だけである（MM92 第 VI 章 §10, p. 332）。この確かめは ETCS の ZFC の中への解釈を与えるので、ETCS から矛盾が導かれれば ZFC からも矛盾が導かれる。すなわち ZFC が無矛盾なら ETCS も無矛盾である。
逆向きには、ETCS のモデルの中で、整礎で外延的な根付きグラフを集合とみなすことにより、所属関係をもつ集合論のモデルが作れる（Shu18 p. 2、MM92 第 VI 章 §10, pp. 334–337。MM92 は整礎な剛い木を使う）。その結果、次が知られている。ここで 有界 Zermelo 集合論 BZC とは、外延性・空集合・対・合併・冪集合・基礎・無限・選択の公理と、有界な論理式についての分出図式からなる体系である（MM92 p. 332）。
BZC の公理はすべて $V_{\omega+\omega}$ で成り立つ（ZFC公理系 の定理「$V_{\omega+\omega}$ は置換を満たさない」）ので、ZFC は BZC の無矛盾性を証明する。1 の両向きの構成は初等算術の中で形式化できる（MM92 p. 332）ので、ZFC は ETCS の無矛盾性も証明する。置換にあたる公理を加えると、ZFC と等無矛盾になる（2）。
例と反例
- 集合と写像の圏 $\mathbf{Set}$ は ETCS のモデルである（thm-etcs-set-model）。
- 有限集合と写像の圏 $\mathbf{FinSet}$ は条件 1・3・4 を満たすが、自然数対象をもたない（自然数対象 の例「反例：有限集合の圏には自然数対象がない」）。
- 集合の対の圏 $\mathbf{Set}\times\mathbf{Set}$（対象は集合の対 $(A,A')$、射は写像の対）は条件 1・2・3(b)・4 を満たすが、3(a) を満たさない。
- ただ 1 つの対象とその恒等射だけからなる圏は、条件 1・2・3(a)・4 を満たすが、$0\cong1$ なので 3(b) を満たさない。
条件 3(a)・3(b)・2 を 1 つずつ外した反例を表にまとめる（条件 4 を外しても thm-etcs-elements の 3 は成り立つ）。最後の行は Lawvere の元の公理系（rem-etcs-lawvere-axioms）についてのもので、その行の圏は Lawvere の公理のうち公理 5 だけを満たさない（Law05 pp. 16–17）。
| 外す条件 | 反例 | 成り立たなくなること |
|---|---|---|
| 3(a) $1$ が生成する | $\mathbf{Set}\times\mathbf{Set}$ | 元をもたない対象は始対象（prop-etcs-two-valued の 1） |
| 3(b) 退化していない | 1 対象 1 射の圏 | $\mathrm{true}\ne\mathrm{false}$（prop-etcs-two-valued の 3） |
| 2 自然数対象 | $\mathbf{FinSet}$ | 自然数対象の存在 |
| Lawvere の公理 5（選択） | 半順序集合と単調写像の圏 | 元について全単射なら同型（thm-etcs-elements の 3） |
反例の確かめを開く
1 行目：$\mathbf{Set}\times\mathbf{Set}$ では極限・余極限・指数・部分対象分類子 $(\{0,1\},\{0,1\})$・自然数対象 $(\omega,\omega)$ を成分ごとにとれ、エピ射は成分ごとにエピ射、したがって成分ごとに全射なので、成分ごとに切断をもつ。終対象は $(1,1)$、始対象は $(\emptyset,\emptyset)$ で、$(1,1)\to(\emptyset,\emptyset)$ はない。$(1,1)$ から $(\{0\},\emptyset)$ への射はないので $(\{0\},\emptyset)$ は元をもたないが、$(\{0\},\emptyset)$ から $(\emptyset,\emptyset)$ への射がないので始対象ではない。3(a) も実際に破れる：$(\emptyset,\{0,1\})$ の恒等射と、第 2 成分の入れ替えは異なるが、元がないので元での値では区別できない。
2 行目：唯一の対象 $\ast$ は終対象かつ始対象で、この圏はすべての極限・余極限・指数をもち、$(\ast,\operatorname{id})$ は部分対象分類子かつ自然数対象である。射が 1 つなので 3(a) と 4 は成り立つ。$\Omega=\ast$ の元は 1 つで、$\mathrm{true}=\mathrm{false}$ である。
3 行目：$\mathbf{FinSet}$ がトポスであることは トポス の例「反例：有限集合の圏」にあり、有限集合の写像は値で決まり、空でない有限集合の間の全射は選択公理を使わずに切断をもつ（各元の逆像の要素を 1 つずつ有限回選ぶ）。自然数対象がないことは 自然数対象 の例に証明がある。
4 行目：2 元集合 $\{a,b\}$ に自明な順序を入れたもの $D$ と、$a< b$ の順序を入れたもの $C$ をとり、$f\colon D\to C$ を恒等写像とする。$f$ は単調で元について全単射だが、逆写像 $C\to D$ は $a\le b$ を保たないので単調でなく、$f$ は同型でない。Lawvere の公理 5 も、$f\circ g\circ f=f$ を満たす単調な $g$ がないので破れる（Law05 p. 17）。
関連項目
- 前提: トポス, 部分対象分類子, 自然数対象, Cartesian閉圏
- 比較: ZFC公理系, 構成的集合論, Martin-Löf型理論
- 発展: ホモトピー型理論, Grothendieck宇宙
参考文献
Mathpediaは寄付と、参考文献の書籍リンク（Amazonアソシエイト）の紹介料で運営されています。 支援について ／ 寄付する
