一価性公理(univalence axiom)とは、型理論の宇宙 $\mathcal U$ の型 $A,B$ について、等しさの証明を同値に送る標準的な関数 $\mathrm{idtoeqv}\colon(A=_{\mathcal U}B)\to(A\simeq B)$ が同値であることを要請する公理で、Voevodsky が導入した。単一性公理ともいう。公理のもとでは同値な型は等しく、同値についての主張は恒等写像の場合に帰着でき(同値帰納法)、互いに導きあう命題は等しく、点ごとに等しい関数は等しい(関数外延性)。到達不能基数のもとで単体的集合のモデルをもつ。
前提知識: Martin-Löf型理論, ホモトピー型理論
一価性公理(univalence axiom、単一性公理ともいう)は、型理論の宇宙 $\mathcal U$ の 2 つの型 $A,B$ について、等しさの型 $A=_{\mathcal U}B$ と、同値の型 $A\simeq B$ を同一視する公理である。正確には、等しさの証明を同値に送る標準的な関数 $\mathrm{idtoeqv}$ が同値であることを要請する。V. Voevodsky が導入し(UFP13 第 2 章の注、p. 102)、ホモトピー型理論 の中心にある。
公理のもとでは、同値な型は等しく、等しい型について成り立つことは同値な型にそのまま移る。この記事では、ホモトピー型理論 の記事が述べた公理の定義を出発点に、公理から得られる 同値帰納法(prop-ua-equiv-induction)、命題についての外延性(prop-ua-prop-ext)、そして関数外延性(thm-ua-funext)を証明する。宇宙が集合でないこと、円周のループが自明でないことは ホモトピー型理論 にあり、ここでは繰り返さない。
型理論は Martin-Löf型理論 に従い、依存積 $\prod$、依存和 $\sum$、恒等型、空型 $\mathbf 0$、単位型 $\mathbf 1$(項 $\star$)、真偽値の型 $\mathbf 2$(項 $0_{\mathbf 2},1_{\mathbf 2}$)と、それらで閉じた宇宙 $\mathcal U$ をもつとする。関数については定義上の $\eta$ 規則 $f\equiv\lambda x.\,f(x)$ を仮定し、関数外延性は仮定しない。$\equiv$ は定義上の等しさ、$=$ は恒等型である。
$f,g\colon A\to B$ の間の ホモトピー $f\sim g$ は $\prod_{x:A}(f(x)=g(x))$ の項である。$f$ が 同値 であるとは、$f\circ s\sim\mathrm{id}_B$ となる $s\colon B\to A$(切断)と $r\circ f\sim\mathrm{id}_A$ となる $r\colon B\to A$(引き込み)がそれぞれ与えられていることで、その型を $\mathrm{isequiv}(f)$、同値全体の型を $A\simeq B:\equiv\sum_{f:A\to B}\mathrm{isequiv}(f)$ と書く(ホモトピー型理論 の定義「ホモトピーと同値」、UFP13 (2.4.10)・(2.4.11)、p. 78)。$f\circ g\sim\mathrm{id}_B$ と $g\circ f\sim\mathrm{id}_A$ をともに満たす 擬逆 $g$ があれば、$s=r=g$ として $f$ は同値である。とくに $\mathrm{id}_A$ は同値で、その証明の項を $\varepsilon_A$ と書く(UFP13 Example 2.4.7、p. 78)。
型 $P$ が 命題 であるとは、任意の $x,y:P$ について $x=y$ の項があることをいう(UFP13 Definition 3.3.1、p. 111)。$\mathbf 1$ は命題である。
$A,B:\mathcal U$ と $p:A=_{\mathcal U}B$ について、族 $X\mapsto X$ に沿う輸送 $p_*\colon A\to B$ は、道の帰納法で $p\equiv\mathrm{refl}_A$ の場合に $\mathrm{id}_A$ になる。これに同値であることの証明を添えて
$$
\mathrm{idtoeqv}\colon(A=_{\mathcal U}B)\to(A\simeq B),\qquad \mathrm{idtoeqv}(\mathrm{refl}_A)\equiv(\mathrm{id}_A,\varepsilon_A)
$$
を定める(UFP13 Lemma 2.10.1、p. 88)。
宇宙 $\mathcal U$ について、すべての $A,B:\mathcal U$ で関数 $\mathrm{idtoeqv}\colon(A=_{\mathcal U}B)\to(A\simeq B)$ が同値であるという主張を 一価性公理 といい、これを満たす宇宙を 一価的(univalent)という(UFP13 Axiom 2.10.3、p. 88)。
公理を仮定すると、$\mathrm{isequiv}(\mathrm{idtoeqv})$ の切断の成分から関数 $\mathrm{ua}\colon(A\simeq B)\to(A=_{\mathcal U}B)$ と、各 $e:A\simeq B$ についての等しさ $\mathrm{idtoeqv}(\mathrm{ua}(e))=e$ が得られる。同値な型は等しく、その等しさの証明として同値そのものが使える。
$\mathcal U$ は一価的とする。$A,B:\mathcal U$ について次が成り立つ。
1. 道の帰納法により、すべての $q:A=_{\mathcal U}B$ について $\mathrm{pr}_1(\mathrm{idtoeqv}(q))=q_*$ である($q\equiv\mathrm{refl}_A$ ではどちらも $\mathrm{id}_A$)。これを $q:=\mathrm{ua}(e)$ に使い、等しさ $\mathrm{idtoeqv}(\mathrm{ua}(e))=e$ に関数 $\lambda e'.\,\mathrm{pr}_1(e')(x)$ を施せば、$\mathrm{ua}(e)_*(x)=e_0(x)$ を得る。
2. $\mathrm{idtoeqv}$ は同値なので、切断 $\mathrm{ua}$ のほかに引き込み $r$ と、各 $q$ についての $r(\mathrm{idtoeqv}(q))=q$ がある。各 $e$ について、等しさ $\mathrm{idtoeqv}(\mathrm{ua}(e))=e$ に $r$ を施すと $\mathrm{ua}(e)=r(\mathrm{idtoeqv}(\mathrm{ua}(e)))=r(e)$ となる。$e:=\mathrm{idtoeqv}(p)$ とおけば $\mathrm{ua}(\mathrm{idtoeqv}(p))=r(\mathrm{idtoeqv}(p))=p$ である。$p:=\mathrm{refl}_A$ とすれば $\mathrm{idtoeqv}(\mathrm{refl}_A)\equiv(\mathrm{id}_A,\varepsilon_A)$ なので後半を得る。$\square$
1 は「等しさ $\mathrm{ua}(e)$ に沿って元を移すことは、同値 $e$ で移すことである」と読める。2 により、$\mathrm{ua}$ と $\mathrm{idtoeqv}$ は互いの擬逆になっている。
集合論と比べると、公理の意味がはっきりする。集合論では、同じ濃度の 2 つの集合は全単射で移り合っても等しいとは限らず、等しさは真か偽かの命題である。一価性公理のもとでは、$\mathbf 2$ の恒等写像と入れ替えという 2 つの同値が $\mathbf 2=_{\mathcal U}\mathbf 2$ の異なる 2 つの項を与える(ex-ua-examples の 1)。型の等しさは、それを示す同値という「データ」をもつ。そのため、恒等型の項 $p:x=y$ があれば $x\equiv y$ とする反映規則を加えた型理論では、ループはすべて $\mathrm{refl}$ に定義上等しくなり(UFP13 Exercise 2.14、p. 104)、宇宙は一価的になりえない(ホモトピー型理論 の反例の表の 1 行目)。
同値の定義に擬逆の組 $\sum_{g}(f\circ g\sim\mathrm{id})\times(g\circ f\sim\mathrm{id})$ をそのまま使うのは公理にとって不適切で、上の定義のように「同値であること」の項がどの 2 つも等しくなる型を使う必要がある(UFP13 §2.4、p. 78、Remark 2.10.4、p. 88)。
$\mathcal U$ は一価的とする。型の族 $Q(A,B,e)$($A,B:\mathcal U$、$e:A\simeq B$)と、各 $A:\mathcal U$ についての項 $d(A):Q(A,A,(\mathrm{id}_A,\varepsilon_A))$ が与えられれば、すべての $A,B:\mathcal U$ と $e:A\simeq B$ について $Q(A,B,e)$ の項が得られる。
まず、すべての $A,B$ と $p:A=_{\mathcal U}B$ について $Q(A,B,\mathrm{idtoeqv}(p))$ の項を作る。道の帰納法により $p\equiv\mathrm{refl}_A$ の場合に作ればよく、そのとき $\mathrm{idtoeqv}(\mathrm{refl}_A)\equiv(\mathrm{id}_A,\varepsilon_A)$ なので $d(A)$ が求める項である。
次に $e:A\simeq B$ をとる。$p:=\mathrm{ua}(e)$ に上の構成を使うと $Q(A,B,\mathrm{idtoeqv}(\mathrm{ua}(e)))$ の項が得られる。等しさ $\mathrm{idtoeqv}(\mathrm{ua}(e))=e$ に沿って族 $Q(A,B,-)$ で輸送すれば、$Q(A,B,e)$ の項が得られる。$\square$
この命題は、同値について何かを示すには恒等写像の場合に示せば十分であることを述べている。UFP13 は Lemma 4.9.2 の証明(p. 145)でこの論法を使う。特別な場合として、族 $P\colon\mathcal U\to\mathcal U$ と $e:A\simeq B$ があれば、$\mathrm{ua}(e)$ に沿う輸送で写像 $P(A)\to P(B)$ が得られる。たとえば $P(X)$ を「$X$ の上の群の構造」の型にとれば、同値な型の一方の上の群の構造が他方に移る。構造を保つ同型と構造の等しさが一致することは UFP13 §2.14(pp. 96–99)で半群について調べられている。
$\mathcal U$ は一価的とする。$P,Q:\mathcal U$ が命題で、関数 $f\colon P\to Q$ と $g\colon Q\to P$ があれば、$P=_{\mathcal U}Q$ である。
$x:P$ について、$g(f(x))$ と $x$ はともに命題 $P$ の項なので $g(f(x))=x$ である。同様に $y:Q$ について $f(g(y))=y$ である。よって $g$ は $f$ の擬逆で、$f$ は同値である(UFP13 Lemma 3.3.3、p. 112)。この同値に $\mathrm{ua}$ を施せば $P=_{\mathcal U}Q$ が得られる。$\square$
命題を論理式と読めば、互いに導きあう 2 つの命題は等しい。宇宙の中の命題の全体を「真理値」の型と見ると、その等しさは真理値の一致で決まる。
関数外延性は、点ごとに等しい関数は等しい、すなわち $f\sim g$ から $f=g$ が得られるという原理である。これは Martin-Löf型理論 の基本の規則からは導けない(UFP13 第 1 章の注、p. 54)。一価性公理からは導ける。
$\mathcal U$ は一価的とする。$A,B,X:\mathcal U$ と $e\equiv(e_0,\theta):A\simeq B$ について、$e_0$ を後ろから合成する関数 $\lambda f.\,e_0\circ f\colon(X\to A)\to(X\to B)$ は同値である。
$Q(A,B,e):\equiv\mathrm{isequiv}\bigl(\lambda f.\,\mathrm{pr}_1(e)\circ f\bigr)$ に prop-ua-equiv-induction を使う。$e\equiv(\mathrm{id}_A,\varepsilon_A)$ の場合、関数は $\lambda f.\,\mathrm{id}_A\circ f\equiv\lambda f.\,\lambda x.\,f(x)\equiv\lambda f.\,f$($\eta$ 規則)で、$(X\to A)$ の恒等写像だから同値である。$\square$
$\mathcal U$ は一価的とする。$A,B:\mathcal U$ と $f,g\colon A\to B$ について、$f\sim g$ の項から $f=g$ の項が得られる。
$B$ の 道の空間 $\Delta:\equiv\sum_{x:B}\sum_{y:B}(x=y)$ と、$\delta\colon B\to\Delta$、$\delta(x):\equiv(x,x,\mathrm{refl}_x)$、射影 $\pi_1(x,y,p):\equiv x$、$\pi_2(x,y,p):\equiv y$ を考える。$\Delta:\mathcal U$ である。
$\delta$ は同値. $\pi_1(\delta(x))\equiv x$ なので $\pi_1\circ\delta\sim\mathrm{id}_B$ である。逆向きには、$\sum$ の帰納法で $w\equiv(x,y,p)$ とし、道の帰納法で $p\equiv\mathrm{refl}_x$(このとき $y\equiv x$)の場合に $\delta(\pi_1(w))\equiv(x,x,\mathrm{refl}_x)\equiv w$ なので、$\delta\circ\pi_1\sim\mathrm{id}_\Delta$ である。よって $\pi_1$ は $\delta$ の擬逆で、$\delta$ は同値である。
後ろからの合成. lem-ua-postcomp を $X:=A$ と同値 $\delta$ に使うと、$D:\equiv\lambda f.\,\delta\circ f\colon(A\to B)\to(A\to\Delta)$ は同値である。その切断 $s\colon(A\to\Delta)\to(A\to B)$ と、各 $k$ についての $H(k):D(s(k))=k$ をとる。$i=1,2$ について $L_i:\equiv\lambda k.\,\pi_i\circ k\colon(A\to\Delta)\to(A\to B)$ とおくと、$f\colon A\to B$ について
$$
L_i(D(f))\equiv\lambda a.\,\pi_i(\delta(f(a)))\equiv\lambda a.\,f(a)\equiv f
$$
である。よって各 $k:A\to\Delta$ について、$H(k)$ に $L_i$ を施した道の逆から $L_i(k)=L_i(D(s(k)))\equiv s(k)$ を得る。2 つを合わせて $L_1(k)=L_2(k)$ である。
結論. $h:f\sim g$ に対し $k:\equiv\lambda a.\,(f(a),g(a),h(a)):A\to\Delta$ とおくと、$L_1(k)\equiv\lambda a.\,f(a)\equiv f$、$L_2(k)\equiv g$ なので、前段から $f=g$ である。$\square$
上の定理は、依存しない関数について $f\sim g$ から $f=g$ を作るものである。一価性公理からは、依存関数についても、写像 $\mathrm{happly}\colon(f=g)\to(f\sim g)$ が同値であるという完全な形が導ける(UFP13 §4.9、Theorem 4.9.4・4.9.5、pp. 145–146)。UFP13 は、族の各ファイバーが可縮なら依存積も可縮であるという「弱い関数外延性」を経由する。また、依存関数について $f\sim g$ から $f=g$ を作る関数があるだけで完全な形が従うことが知られている(Voevodsky による。UFP13 Exercise 2.16、p. 105)。この記事ではこれらを証明しない。
| 外す条件 | 反例 | 成り立たなくなること |
|---|---|---|
| prop-ua-prop-ext の「$P,Q$ は命題」 | $P=\mathbf 1$、$Q=\mathbf 2$ | $P=_{\mathcal U}Q$ |
| lem-ua-postcomp の「$e$ は同値」 | $A=\mathbf 2$、$B=X=\mathbf 1$、$e_0=\lambda b.\,\star$ | 後ろからの合成が同値であること |
| thm-ua-funext の一価性公理 | 公理を加えない Martin-Löf 型理論 | $f\sim g$ から $f=g$ を導くこと |
まず $0_{\mathbf 2}=1_{\mathbf 2}$ の項はない。$F\colon\mathbf 2\to\mathcal U$ を $F(0_{\mathbf 2}):\equiv\mathbf 1$、$F(1_{\mathbf 2}):\equiv\mathbf 0$ と定めると、$q:0_{\mathbf 2}=1_{\mathbf 2}$ に沿う輸送 $q_*(\star):\mathbf 0$ が空型の項になるからである。
1 行目:$\lambda u.\,0_{\mathbf 2}\colon\mathbf 1\to\mathbf 2$ と $\lambda b.\,\star\colon\mathbf 2\to\mathbf 1$ がある。$p:\mathbf 1=_{\mathcal U}\mathbf 2$ があったとすると、$\mathrm{idtoeqv}(p)$ の写像 $e_0$ と切断 $s$ について $e_0(s(0_{\mathbf 2}))=0_{\mathbf 2}$、$e_0(s(1_{\mathbf 2}))=1_{\mathbf 2}$ で、$\mathbf 1$ は命題なので $s(0_{\mathbf 2})=s(1_{\mathbf 2})$ となり、$0_{\mathbf 2}=1_{\mathbf 2}$ が従って矛盾する。$\mathbf 2$ は $0_{\mathbf 2}=1_{\mathbf 2}$ を満たさないので命題でない。
2 行目:$c_0:\equiv\lambda u.\,0_{\mathbf 2}$ と $c_1:\equiv\lambda u.\,1_{\mathbf 2}$ はどちらも $e_0\circ c_i\equiv\lambda u.\,\star$ に送られる。合成が同値なら引き込み $r$ があって $c_0=r(\lambda u.\,\star)=c_1$ となり、この道に $\star$ での値をとる関数を施せば $0_{\mathbf 2}=1_{\mathbf 2}$ となって矛盾する。$e_0$ が同値なら引き込み $r'$ があって $0_{\mathbf 2}=r'(\star)=1_{\mathbf 2}$ となるので、$e_0$ は同値でない。
3 行目:UFP13 は、関数外延性が第 1 章の規則(Martin-Löf 型理論の基本の規則)からは導けないことを述べ、公理として加えている(第 1 章の注、p. 54、§2.9、p. 86)。
一価性公理は単体的集合のモデルで成り立つ。到達不能基数 $\beta<\alpha$ があれば、Kan 複体からなる宇宙をもつ Martin-Löf 型理論のモデルが単体的集合の圏の中に作られ、その宇宙は一価的である(KL21 Theorem 3.4.1–3.4.3、pp. 35–36)。したがって、ZFC に到達不能基数を 2 つ加えた体系が無矛盾なら、Martin-Löf 型理論に一価的な宇宙を 1 つ加えた体系は無矛盾である。ただし KL21 はモデルを型理論の構文ではなく文脈圏で述べており、構文との対応はいわゆる始対象性に依存する(同 Introduction、p. 3、§1.2、p. 9)。公理の動機は、この単体的集合のモデルの意味論的な考察にあった(UFP13 第 2 章の注、p. 102)。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する