自然数対象

同義語:natural numbers object

概要

自然数対象(natural numbers object)とは、終対象 $1$ をもつ圏の対象 $N$ と射 $0\colon1\to N$、$s\colon N\to N$ の組で、どの $x\colon1\to X$ と $f\colon X\to X$ に対しても $u\circ0=x$、$u\circ s=f\circ u$ を満たす射 $u\colon N\to X$ がただ一つあるものであり、集合では通常の自然数である。余積 $1+N$ があれば $[0,s]$ は同型であり、$0$ を含み $s$ で閉じた部分対象は全体に一致する。終対象を保つ左随伴は自然数対象を保つので、前層と層のトポスでは定数前層 $\Delta\mathbb N$ やその層化が自然数対象になる一方、有限集合の圏には自然数対象がない。Cartesian閉圏ではパラメータ付きの再帰で加法が定義できる。

$$\newcommand{C}[0]{\mathbb{C}} \newcommand{div}[0]{\mathbin{÷}} \newcommand{N}[0]{\mathbb{N}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$

前提知識: 終対象, 再帰的定義, 随伴関手, 余積(圏論)

自然数の集合 $\mathbb N$ は、$0$ と後者関数 $n\mapsto n+1$ によって「再帰で写像を定義できる」という性質で特徴づけられる。集合 $X$ の元 $x$ と写像 $f\colon X\to X$ が与えられると、$h(0)=x$、$h(n+1)=f(h(n))$ を満たす写像 $h\colon\mathbb N\to X$ がただ一つ存在する(再帰的定義 の定理「再帰定理」)。この性質は元を使わずに、終対象 $1$ からの射と自己射の言葉だけで述べられる。そのように述べたものを任意の圏で要求したものが Lawvere の 自然数対象(natural numbers object)である。
自然数対象は、トポスを「集合の宇宙」とみて算術や実数を展開するための基本的な対象であり、Cohenトポス のように層のトポスで連続体仮説を扱うときにも、その中の「自然数」として使われる。主な結果は次のとおりである。自然数対象 $N$ について、余積 $1+N$ があれば $[0,s]\colon1+N\to N$ は同型であり、$N$ の部分対象について帰納法が成り立つ(thm-nno-lambek、thm-nno-induction)。終対象を保つ左随伴は自然数対象を保ち、そのため前層や層のトポスの自然数対象は定数(前)層で与えられる(thm-nno-left-adjoint、cor-nno-sheaves)。Cartesian閉圏ではパラメータ付きの再帰ができ、加法が定義できる(thm-nno-parameter)。一方、有限集合の圏には自然数対象がない(ex-nno-finset)。

定義

自然数対象

終対象 $1$ をもつ圏 $\mathcal C$ の 自然数対象(natural numbers object)とは、対象 $N$ と射 $0\colon1\to N$、$s\colon N\to N$ の組 $(N,0,s)$ で、次を満たすものをいう:任意の対象 $X$ と射 $x\colon1\to X$、$f\colon X\to X$ に対し、
$$ u\circ0=x,\qquad u\circ s=f\circ u $$
を満たす射 $u\colon N\to X$ がただ一つ存在する。

定義は MM92 VI.1(pp. 268–269)、BW05 7.5(p. 222)による。$(X,x,f)$ の形の組を 点付き自己射、$u\circ0=x$ と $u\circ s=f\circ u$ を満たす射を点付き自己射の 射 と呼ぶことにすると、自然数対象とは点付き自己射の圏の始対象にほかならない。とくに次が成り立つ。

自然数対象の一意性

$(N,0,s)$ と $(N',0',s')$ が自然数対象ならば、$v\circ0=0'$、$v\circ s=s'\circ v$ を満たす同型射 $v\colon N\to N'$ がただ一つ存在する。

定義から点付き自己射の射 $v\colon N\to N'$ と $v'\colon N'\to N$ がただ一つずつある。$v'\circ v\colon N\to N$ は $(N,0,s)$ からそれ自身への点付き自己射の射であり、$\operatorname{id}_N$ もそうなので、一意性から $v'\circ v=\operatorname{id}_N$ である。同様に $v\circ v'=\operatorname{id}_{N'}$ である。$\square$

直感

$u$ は「$n$ を $f^n(x)$ へ送る射」である。集合では $N$ の元は $0,s(0),s(s(0)),\dots$ だけなので $u$ はそれで決まるが、一般の圏では $N$ の点($1$ からの射)が $N$ を決めるとは限らない。それでも定義は「$u$ が存在してただ一つ」という形で全体を縛るので、$N$ は余分なものを含まず(帰納法)、足りないものもない(再帰)対象になる。後者関数が単射であることや $0$ が後者でないことは、$1+N\cong N$ という形で表れる(thm-nno-lambek)。

例

集合の圏

$\mathbf{Set}$ では、通常の自然数の集合 $\mathbb N$ と $0\colon1\to\mathbb N$($1$ の元を $0$ へ送る)、$s(n)=n+1$ が自然数対象である。これは 再帰的定義 の定理「再帰定理」の言い換えである(MM92 VI.1, p. 269)。

反例:有限集合の圏には自然数対象がない

有限集合と写像のなす圏 $\mathbf{FinSet}$ には自然数対象がない。$(N,0,s)$ が自然数対象だったとし、$N$ の元の個数を $k$ とする。$X=\{0,1,\dots,k\}$、$x=0$、$f(j)=\min(j+1,k)$ とおくと、$u\circ0=x$、$u\circ s=f\circ u$ を満たす $u\colon N\to X$ がある。$n_j:=s^j(0)\in N$ とおくと $u(n_j)=f^j(0)=\min(j,k)$ であり、$j=0,1,\dots,k$ について $u(n_j)=j$ は相異なる。よって $n_0,\dots,n_k$ は $N$ の相異なる $k+1$ 個の元であり、$N$ の元が $k$ 個であることに反する。

主な性質

Lambek の同型と商

$(N,0,s)$ を圏 $\mathcal C$ の自然数対象とする。

  1. $\mathcal C$ が余積 $1+N$ をもつならば、$[0,s]\colon1+N\to N$ は同型である。
  2. $N$ から終対象への射 $!\colon N\to1$ は、$\operatorname{id}_N$ と $s$ の余等化子である。
  1. 余積の入射を $i_1\colon1\to1+N$、$i_2\colon N\to1+N$ とし、$t:=i_2\circ[0,s]\colon1+N\to1+N$ とおく。定義により $u\circ0=i_1$、$u\circ s=t\circ u$ を満たす $u\colon N\to1+N$ がある。$[0,s]\circ i_1=0$、$[0,s]\circ t=[0,s]\circ i_2\circ[0,s]=s\circ[0,s]$ なので、$[0,s]\circ u$ は
    $$ ([0,s]\circ u)\circ0=[0,s]\circ i_1=0,\qquad([0,s]\circ u)\circ s=[0,s]\circ t\circ u=s\circ([0,s]\circ u) $$
    を満たす。$\operatorname{id}_N$ も同じ 2 式を満たすので、定義の一意性から $[0,s]\circ u=\operatorname{id}_N$ である。逆向きは、余積の普遍性により入射との合成で確かめる。$u\circ[0,s]\circ i_1=u\circ0=i_1$、および
    $$ u\circ[0,s]\circ i_2=u\circ s=t\circ u=i_2\circ[0,s]\circ u=i_2 $$
    なので $u\circ[0,s]=\operatorname{id}_{1+N}$ である。
  2. $h\colon N\to X$ が $h\circ s=h$ を満たすとし、$x:=h\circ0$ とおく。$h$ と $x\circ{!}$ はどちらも、点付き自己射 $(X,x,\operatorname{id}_X)$ について $u\circ0=x$、$u\circ s=\operatorname{id}_X\circ u$ を満たす($!\circ0=\operatorname{id}_1$、$!\circ s={!}$ による)。定義の一意性から $h=x\circ{!}$ である。$k\circ{!}=h$ となる $k\colon1\to X$ は $k=k\circ{!}\circ0=h\circ0$ に限るので、分解は一意である。$\square$

1 は「$0$ は後者でなく、後者関数は単射で、$N$ は $0$ と後者からなる」ことの圏論的な表現である。証明は BW05 Theorem 7.5.6 の前半(pp. 227–228)と同じである。

帰納法

$(N,0,s)$ を自然数対象、$m\colon M\rightarrowtail N$ をモノ射とする。射 $0'\colon1\to M$ と $s'\colon M\to M$ で $m\circ0'=0$、$m\circ s'=s\circ m$ を満たすもの($M$ が $0$ を含み $s$ で閉じていること)があれば、$m$ は同型である。

定義により $u\circ0=0'$、$u\circ s=s'\circ u$ を満たす $u\colon N\to M$ がある。$m\circ u$ は $m\circ u\circ0=m\circ0'=0$、$m\circ u\circ s=m\circ s'\circ u=s\circ m\circ u$ を満たすので、定義の一意性から $m\circ u=\operatorname{id}_N$ である。すると $m\circ u\circ m=m=m\circ\operatorname{id}_M$ で $m$ はモノ射だから $u\circ m=\operatorname{id}_M$ であり、$m$ は同型である。$\square$

随伴による移送と層のトポス

終対象を保つ左随伴は自然数対象を保つ

$L\colon\mathcal C\to\mathcal D$、$R\colon\mathcal D\to\mathcal C$ を $L\dashv R$ とし、$\mathcal C,\mathcal D$ は終対象をもち、$L$ は終対象を保つとする(同型 $\iota\colon L1\to1$ がある)。$(N,0,s)$ が $\mathcal C$ の自然数対象ならば、$(LN,\ L(0)\circ\iota^{-1},\ L(s))$ は $\mathcal D$ の自然数対象である。

随伴の全単射を $\varphi\colon\mathcal D(LC,Y)\cong\mathcal C(C,RY)$ と書く。自然性により、$\mathcal C$ の射 $c\colon C'\to C$ と $\mathcal D$ の射 $g\colon Y\to Y'$ について $\varphi(g\circ v\circ L(c))=R(g)\circ\varphi(v)\circ c$ である。
$\mathcal D$ の対象 $Y$ と射 $y\colon1\to Y$、$f\colon Y\to Y$ をとり、$y^\flat:=\varphi(y\circ\iota)\colon1\to RY$ とおく。$(RY,y^\flat,R(f))$ に自然数対象の定義を当てると、$w\circ0=y^\flat$、$w\circ s=R(f)\circ w$ を満たす $w\colon N\to RY$ がただ一つある。射 $v\colon LN\to Y$ について、自然性から
$$ \varphi(v\circ L(0))=\varphi(v)\circ0,\qquad\varphi(v\circ L(s))=\varphi(v)\circ s,\qquad\varphi(f\circ v)=R(f)\circ\varphi(v) $$
であり、$v\circ L(0)\circ\iota^{-1}=y$ は $v\circ L(0)=y\circ\iota$、すなわち $\varphi(v)\circ0=y^\flat$ と同値である。よって $v$ が $v\circ L(0)\circ\iota^{-1}=y$、$v\circ L(s)=f\circ v$ を満たすことは、$\varphi(v)$ が $\varphi(v)\circ0=y^\flat$、$\varphi(v)\circ s=R(f)\circ\varphi(v)$ を満たすことと同値である。$\varphi$ は全単射なので、そのような $v$ は $\varphi^{-1}(w)$ ただ一つである。$\square$

この観察は MM92 VI.1(p. 269 の (4)・(5))にある。これを前層と層に当てる。

前層と層のトポスの自然数対象

$\mathcal C$ を小さい圏とする。

  1. 集合 $S$ を値とする定数前層を $\Delta S$ と書くと、$(\Delta\mathbb N,\Delta0,\Delta s)$ は前層(圏論)の圏 $\mathbf{Set}^{\mathcal C^{\mathrm{op}}}$ の自然数対象である。
  2. $J$ を $\mathcal C$ の Grothendieck 位相、$\mathbf a$ を層化関手とすると、$\mathbf a\Delta\mathbb N$ は層の圏 $\operatorname{Sh}(\mathcal C,J)$ の自然数対象である。
  1. 前層 $P$ について、$\lim P$ を「$\mathcal C$ の各射 $c'\to c$ で制限すると互いに移り合う元の族 $(p_c)_c$($p_c\in P(c)$)」の集合とする。自然変換 $\Delta S\to P$ は写像の族 $\alpha_c\colon S\to P(c)$ で、各射 $g\colon c'\to c$ について $P(g)\circ\alpha_c=\alpha_{c'}$ を満たすもの、すなわち写像 $S\to\lim P$ と同じものであり、この対応は $S$ と $P$ について自然である。よって $\Delta\dashv\lim$ である。$\Delta1$ は各対象で 1 点の前層、すなわち前層の圏の終対象であり、ex-nno-set と thm-nno-left-adjoint から主張が従う。
  2. 層化関手 $\mathbf a$ は包含関手 $\operatorname{Sh}(\mathcal C,J)\to\mathbf{Set}^{\mathcal C^{\mathrm{op}}}$ の左随伴で有限極限を保つ(MM92 III.5 Theorem 1, p. 128)。とくに終対象を保つので、1 と thm-nno-left-adjoint から $\mathbf a\Delta\mathbb N$ は自然数対象である。$\square$

位相空間 $X$ 上の層の圏では、$\mathbf a\Delta\mathbb N$ は各開集合 $U$ に局所定数関数 $U\to\mathbb N$ の集合を対応させる定数層 $\mathbb N_X$ である(MM92 VI.8, p. 319)。Cohenトポス の記事が自然数対象として使う $\widehat{\mathbb N}=\mathbf a\Delta\mathbb N$ は 2 の場合であり、その冪対象 $\Omega^{\widehat{\mathbb N}}$ と組み合わせて連続体仮説の否定を述べる。$\mathbf a$ と $\Delta$ は余積を保つので、$\mathbf a\Delta\mathbb N$ は終対象の可算個の余積でもある(MM92 VI.1 (8), p. 270)。

パラメータ付きの再帰

集合では、加法 $a+n$ は $n$ についての再帰 $a+0=a$、$a+(n+1)=(a+n)+1$ で定義され、その規則は $a$ に依存してよい。定義の $x\colon1\to X$ には「パラメータ」が入らないが、Cartesian閉圏では指数対象を使ってパラメータを組み込める。以下、$\mathcal C$ の指数対象を $X^A$、評価射を $\mathrm{ev}\colon X^A\times A\to X$ とし、射 $g\colon Z\times A\to X$ に対応する射 $Z\to X^A$ を $\lambda g$ と書く($\mathrm{ev}\circ(\lambda g\times\operatorname{id}_A)=g$。射 $k\colon Z'\to Z$ について $\lambda(g\circ(k\times\operatorname{id}_A))=\lambda g\circ k$)。$1\times A$ と $A$ は射影で同一視する。

パラメータ付きの再帰

$\mathcal C$ を Cartesian閉圏、$(N,0,s)$ を自然数対象とする。射 $g\colon A\to X$ と $h\colon X\times A\to X$ に対し、
$$ u\circ(0\times\operatorname{id}_A)=g,\qquad u\circ(s\times\operatorname{id}_A)=h\circ\langle u,\pi_A\rangle $$
を満たす射 $u\colon N\times A\to X$ がただ一つ存在する($\pi_A\colon N\times A\to A$ は射影)。集合では $u(0,a)=g(a)$、$u(n+1,a)=h(u(n,a),a)$ である。

$\bar g:=\lambda g\colon1\to X^A$ と、$F:=\lambda\bigl(h\circ\langle\mathrm{ev},\pi_A\rangle\bigr)\colon X^A\to X^A$($\langle\mathrm{ev},\pi_A\rangle\colon X^A\times A\to X\times A$)をとる。定義により $v\circ0=\bar g$、$v\circ s=F\circ v$ を満たす $v\colon N\to X^A$ がただ一つある。
存在。 $u:=\mathrm{ev}\circ(v\times\operatorname{id}_A)$ とおく。$u\circ(0\times\operatorname{id}_A)=\mathrm{ev}\circ(\bar g\times\operatorname{id}_A)=g$ である。また
$$ u\circ(s\times\operatorname{id}_A)=\mathrm{ev}\circ(F\times\operatorname{id}_A)\circ(v\times\operatorname{id}_A)=h\circ\langle\mathrm{ev},\pi_A\rangle\circ(v\times\operatorname{id}_A)=h\circ\langle u,\pi_A\rangle $$
である(最後は $\langle\mathrm{ev},\pi_A\rangle\circ(v\times\operatorname{id}_A)=\langle\mathrm{ev}\circ(v\times\operatorname{id}_A),\pi_A\rangle$ による)。
一意性。 $u'$ が 2 式を満たすとし、$v':=\lambda u'$ とおく。$v'\circ0=\lambda(u'\circ(0\times\operatorname{id}_A))=\lambda g=\bar g$ である。さらに $\lambda$ の性質から
$$ \lambda^{-1}(F\circ v')=h\circ\langle\mathrm{ev},\pi_A\rangle\circ(v'\times\operatorname{id}_A)=h\circ\langle u',\pi_A\rangle=u'\circ(s\times\operatorname{id}_A)=\lambda^{-1}(v'\circ s) $$
であり($\lambda^{-1}(w)=\mathrm{ev}\circ(w\times\operatorname{id}_A)$)、$\lambda$ は全単射なので $F\circ v'=v'\circ s$ である。よって $v'=v$ であり、$u'=\mathrm{ev}\circ(v'\times\operatorname{id}_A)=u$ である。$\square$

加法

thm-nno-parameter を $A=X=N$、$g=\operatorname{id}_N$、$h=s\circ\pi_1\colon N\times N\to N$ に当てると、$\mathrm{add}\circ(0\times\operatorname{id})=\operatorname{id}$、$\mathrm{add}\circ(s\times\operatorname{id})=s\circ\mathrm{add}$ を満たす射 $\mathrm{add}\colon N\times N\to N$ がただ一つ得られる。集合では $\mathrm{add}(n,a)=n+a$ である。乗法も同じように $\mathrm{add}$ を使った再帰で定義できる(MM92 VI.1, p. 269 と第 VI 章の演習 1)。トポスでは、自然数対象から整数・有理数・実数の対象を作り、算術を展開できる(MM92 VI.8, pp. 319–322)。

Freyd の特徴づけ

thm-nno-lambek は、自然数対象 $N$ について「$[0,s]$ が同型」と「$\operatorname{id}_N$ と $s$ の余等化子が $1$」が成り立つことを示した。トポスでは逆も成り立つ。すなわち、トポスの点付き自己射 $(A,a,t)$ で $[a,t]\colon1+A\to A$ が同型かつ $\operatorname{id}_A$ と $t$ の余等化子が $1$ であるものは自然数対象である(Freyd の定理、BW05 Theorem 7.5.6, pp. 226–228)。その帰結として、有限極限と有限余極限を保つトポスの間の関手は自然数対象を自然数対象へ送る(BW05 Corollary 7.5.9, p. 228)。これらはこの記事では証明しない。

反例の表

外す条件反例成り立たなくなること
$u$ の一意性(存在は保つ)$\mathbf{Set}$ の $\mathbb N\times\{0,1\}$、点 $(0,0)$、自己射 $(n,i)\mapsto(n+1,i)$。$u(n,i)=f^n(x)$ が条件を満たすが、$u(0,1)$ は任意に選べる$[0,s]$ の像は $(0,1)$ を含まず、thm-nno-lambek の 1 の同型が成り立たない
$u$ の存在(一意性は保つ)$\mathbf{Set}$ の 1 点集合 $\{\ast\}$、点 $\ast$、自己射 $\operatorname{id}$。$u$ は $\ast\mapsto x$ しかありえないが、$f(x)\ne x$ なら条件を満たさない$[\ast,\operatorname{id}]\colon1+1\to1$ は同型でない
$L$ が終対象を保つ(thm-nno-left-adjoint)$\mathbf{Set}$ の左随伴 $L=-\times\{0,1\}$(右随伴は $Y\mapsto Y^{\{0,1\}}$)。$L1$ は 2 点$LN=\mathbb N\times\{0,1\}$ に $1$ からのどの点 $p$ と $L(s)$ を与えても、1 行目と同じく $[p,L(s)]$ は全射でなく、自然数対象にならない

関連項目

参考文献

[1]
Saunders Mac Lane, Ieke Moerdijk, Sheaves in Geometry and Logic: A First Introduction to Topos Theory, Universitext, Springer, 1992, III.5 Theorem 1(層化関手は有限極限を保つ左随伴、p. 128);VI.1(自然数対象の定義と集合の例、pp. 268–269、終対象を保つ左随伴による移送 (4)・(5)、p. 269、前層と層のトポスの自然数対象 (6)–(8)、pp. 269–270);VI.8(空間上の層の自然数対象は定数層、p. 319、整数・有理数・実数の対象、pp. 320–322);第 VI 章の演習 1

Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する