数学の基礎

　今後、同値関係を持つ集合 (A, =_A ) のことを、単にその左成分 A で代表して表し、=_A のことも = と略記する“ルーズな表記法”をしばしば用いることにします。

　理論 t 上の再帰的集合論上の集合論 t'* において、同値関係を持つ集合 A と、A の元 a と、A からそれ自身への関数 j の３つ組 (A, a, j) を対象とよび、２つの対象 (A, a, j) と (B, b, y) に対して A から B への関数 f で

(10-1a)  f(a) = b

(10-1b)  y ° f = f ° j

を満たすものを (A, a, j) から (B, b, y) への射とよべば、これは一つの圏を構成します。この圏を仮に自然圏とよぶことにします。そして、この圏に始対象が存在するとき、理論 t' は無限公理を満たすといい、その始対象の一つを (N, 0, s) と書きます。
　このとき N の元を自然数、0 を零（zero）、s(n) を n の次の元（successor）とよびます。
　なお、零元を 0 でなく 1 と書く流儀もありますが、その場合は零元のかわりに単位（unity）あるいは一とよばれます。どちらの流儀でも公理の内容としては同じことですが、あとで出てくる加法の定義が若干違ってきます。

　以下しばらく、理論 t' が無限公理を満たす場合を考えます（無限公理を満たす理論の作り方の例は後ほど解説します）。

　さて、最初に、自然圏の始対象 (N, 0, s) として、N の同値関係が等号 º であるようなものが存在することを証明しましょう。
　自然圏の始対象 (N, 0, s) を任意に取ります。N と集合としては同じで、附随する同値関係を N に附随する = ではなく、等号 º に置き換えたものを N' と書くことにすれば、明らかに (N', 0, s) は自然圏の対象になります。ゆえに始対象の定義により、(N, 0, s) から (N', 0, s) への射 j が存在します。そこで N" :º j[N] と置き、N" に附随する同値関係は º であると定義します。
　すると、j が自然圏の射であることから s _° j = j _° s が成り立つので、任意の nÎN に対して s(j(n)) º j(s(n)) が成り立ちますが、これは

(10-2a)  s[N"] Ì N"

を意味しています。また、j(0) º 0 ですから

(10-2b)  0ÎN"

が成り立ちます。ゆえに s の N" への制限写像を s" と書けば、(10-2) により、(N", 0, s" ) は自然圏の対象です。以下、これが自然圏の始対象になっていることを証明しましょう。
　自然圏の任意の対象 (A, a, y) に対し、始対象 (N, 0, s) から (A, a, y) への射 f が存在します。すなわち

(10-3)  y ° f = f ° s

が成り立ちます。そこで、N" から A への写像 g を g(n) :º f(n) で定義すると、N" の同値関係は等号 º ですから、g は自動的に関数になります。
　また任意の nÎN" に対し、(10-2a) により s(n)ÎN" であることと、(10-3) により、y(g(n)) º y( f(n)) = f(s(n)) º g(s"(n)) すなわち y _° g = g _° s" が成り立つので、g は (N", 0, s" ) から (A, a, y) への射です。
　一方、g と g' が (N", 0, s" ) から (A, a, y) への射なら、g _° j と g' _° j は共に始対象 (N, 0, s) から (A, a, y) への射ですから一致します：

(10-4)  g ° j = g' ° j

　一方、任意の nÎN" は、ある mÎN によって n º j(m) と書けるので、これと (10-4) により g(n) º g(j(m)) = g'(j(m)) º g(n) すなわち g = g' がわかり、以上で (N", 0, s" ) が自然圏の始対象であることが証明されました。

　そこで、今後は N の同値関係は等号 º であるものとします。その結果、N から A への写像は、A の同値関係を º に置き換えた場合でもすべて関数になるので、写像と関数の区別をする必要はなくなります。

　さて次に、N の任意の部分集合 A に対し、次のような（数学的）帰納法：

(10-5)  ( 0ÎA  Ù  s[A] Ì A )  Þ  A = N

が成り立つことを証明しましょう。
　実際、0ÎA 及び s[A] Ì A を仮定します。すると、s の A への制限を s|_A と書けば、明らかに (A, 0, s|_A ) は自然圏の対象になります。
　ゆえに始対象の定義により、(N, 0, s) から (A, 0, s|_A ) への射 f が存在し、一方 A からそれ自身への恒等射 i は、(A, 0, s|_A ) から (N, 0, s) への射になります。
　すると、合成射 if は始対象 (N, 0, s) からそれ自身への射となるので、始対象の定義により (N, 0, s) からそれ自身への射は唯一つなので、if は (N, 0, s) 上の恒等射に一致します。
　すなわち i( f(n)) º n となり、しかも i は恒等関数なので、これは f(n) º n を意味し、N = f [N] Ì A となるので A = N がわかります。以上で (10-5) は証明されました。

　帰納法の簡単な応用例として次の命題を証明してみましょう：

(10-6)  "nÎN : ( n º 0  Ú  $kÎN : n º s(k) )

　実際、(10-6) の括弧の中を満たす自然数 n の全体を A と書くと、明らかに 0ÎA が成り立ちます。また、任意の自然数 n に対し、s(n) º s(n) ですから s(n)ÎA が成り立つので、特に s[A] Ì A が成り立ちます。ゆえに (10-5) により A = N が言え、(10-6) は証明されました。

　さて次に、帰納的構成について考察します。
　同値関係を持つ集合 A 、A の元 c 、N と A の集合の圏における積 N ´ A から A への関数 F が任意に与えられたとき、

(10-7a)  j(0) = c

(10-7b)  j(s(n)) = F(n, j(n))

を満たす N から A への写像 j が唯一つ存在することが証明できます。

　まず最初に一意性を証明しましょう。
　j と y が共に (10-7) を満たすと仮定します。A :º {nÎN | j(n) = y(n) } と置くと、(10-7a) により j(0) = c = y(0) なので 0ÎA が成り立ち、nÎA なら j(n) = y(n) なので、F が関数であることと (10-7b) により

(10-8)  j(s(n)) = F(n, j(n)) = F(n, y(n)) = y(s(n))

ですから s(n)ÎA となるので、(10-5) により A = N がわかり、関数の相等の定義により j = y が成り立ちます。

　さて、次に j の存在証明ですが、N ´ A からそれ自身への写像 f を

(10-9)  f(n, x) :º (s(n), F(n, x))

で定義すると、３つ組 ( N ´ A, (0, c),  f ) は自然圏の対象になります。ゆえに始対象 (N, 0, s) から ( N ´ A, (0, c),  f ) への射 Φ が存在します。
　そこで、N ´ A の元の左成分、右成分を与える写像をそれぞれ π_L 、π_R と書き、y :º π_{L °} Φ ，j :º π_{R °} Φ と置きます。Φ は自然圏の射ですから、定義により Φ(0) = (0, c) 及び f _° Φ = Φ _° s が成り立ちますが、これらを j と y によって書き直せば、

(10-10a)  (y(0), j(0)) = (0, c)

(10-10b)  (s(y(n)) , F(y(n), j(n))) =  f(y(n), j(n)) =  f(Φ(n)) = Φ(s(n)) = (y(s(n)), j(s(n)))

となるので、これらを成分ごとに分けると、N の同値関係が等号 º であることに注意すれば、

(10-11a)  y(0) º 0

(10-11b)  j(0) = c

(10-11c)  s(y(n)) º y(s(n))

(10-11d)  F(y(n), j(n)) = j(s(n))

となります。ここで y が恒等写像、すなわち任意の nÎN に対して y(n) º n が成り立つことを証明しましょう。
　A :º { nÎN | y(n) º n } と置くと、(10-11a) により 0ÎA が成り立ちます。また、nÎA なら (10-11c) により

(10-12)  y(s(n)) º s(y(n)) º s(n)

すなわち s(n)ÎA となるので、(10-5) により A = N すなわち y が恒等写像であることがわかります。
　ゆえに (10-11b) と、(10-11d) で y(n) を n で置き換えたものが成り立つことがわかり、これは (10-7) に他なりません。

　さて、帰納的構成の原理 (10-7) を使って様々な関数を定義することができます。
　まず、(10-7) において A :º N ，c :º 0 ，F(n, x) :º n と置いた場合に唯一つ存在する j を pd と書くことにします。これは

(10-13a)  pd 0 º 0

(10-13b)  pd s(n) º n

が成り立つことを意味します。ゆえに、もし s(n) º s(m) なら、両辺に pd を施して (10-13b) を用いることにより n º m が得られます。

　次に、互いに等しくない t' 元 a , b を一組用意し（例えば a :º Æ , b :º {Æ} と置けばよい）、(10-7) において A :º {a, b} , c :º a , F(n, x) :º b と置いた場合の j は

(10-14a)  j(0) º a

(10-14b)  j(s(n)) º b

を満たしますが、0 º s(n) と仮定すると a º b となって矛盾するので Ø 0 º s(n) が得られます。

　以上の結果から、nÎN という命題を nat(n) と書けば、Peanoの公理と呼ばれる次の５つの命題が成り立つことがわかりました：

(P-1)  nat(0)

(P-2)  "nat n  nat(s(n))

(P-3)  "nat n  Ø s(n) º 0

(P-4)  "nat n, m : ( s(n) º s(m)  Þ  n º m )

(P-5)  ( P(0)  Ù  "nat n ( P(n) Þ P(s(n)) ) )   Þ   "nat n P(n)

　ただし (P-5) は (10-5) を集合の概念を使わないで表現したもので、P は任意の命題を表わし、P(T ) は (T | n)P を表わします。(10-5) Þ (P-5) は P として命題 xÎA を取ればよく、逆に (P-5) Þ (10-5) は A として集合 { nÎN | P(n) } を取れば、両者の同値性は明らかです。

　さて、上記のPeanoの公理は自然数を完全に特徴付けている、すなわち (P-1)〜(P-5) を満たす述語 nat が作る類 N :º { n | nat(n) } が集合ならば、N と 0 と s の３つ組 (N, 0, s) が自然圏の始対象になることが証明できます。
　実際、(A, a, j) を自然圏の任意の対象とし、条件：

(10-15a)  (0, a)ÎG

(10-15b)  "nÎN : ( (n, x)ÎG  Þ  (s(n), j(x))ÎG )

を満たすすべての集合 G Ì N ´ A に属す (n, x)ÎN ´ A の全体を G₀ と書くと、これはやはり (10-15) を満たし、(10-15) を満たす最小の集合になります。そこで G₀ が、任意の mÎN に対して

(10-16)  $!xÎA : (m, x)ÎG0

を満たすことを、m に関する帰納法によって証明しましょう。まず

(10-17)  G' :º { (n, x)ÎG0 | n º 0  Þ  x º a }

と置くと、明らかに (0, a)ÎG' が成り立ちます。
　また、(n, x)ÎG' ならば、当然 (s(n), j(x))ÎG₀ ですが、(P-3) により Ø s(n) º 0 ですから (s(n), j(x))ÎG' も成り立っています。いいかえると、G' は (10-15) を満たします。したがって、G₀ の最小性により G₀ Ì G' が成り立ち、これは (0, x)ÎG₀  Þ  x º a が成り立つことを意味します。
　以上により、(10-16) が m º 0 の場合に成り立つことがわかりました。

　次に、(10-16) が特定の m で成り立つと仮定します。(m, c)ÎG₀ を満たす c が唯一つ存在するので、

(10-18)  (m, x)ÎG0  Þ  x º c

となります。そこで

(10-19)  G" :º { (n, x)ÎG0 | n º s(m)  Þ  x º j(c) }

と置くと、(P-3) により Ø 0 º s(m) ですから、明らかに (0, a)ÎG" が成り立ちます。
　また (n, x)ÎG" と仮定すると、(10-15b) により (s(n), j(x))ÎG₀ であり、(P-4),(10-18) により

(10-20)  s(n) º s(m)  Þ  n º m  Þ  (m, x)ÎG" Ì G0  Þ  x º c  Þ  j(x) º j(c)

ですから、(s(n), j(x))ÎG" がわかります。
　これは、G" が (10-15) を満たしていることを意味しますから、G₀ の最小性により G₀ Ì G" が成り立ち、これは (s(m), x)ÎG₀  Þ  x º j(c) が成り立つことを意味します。
　一方 (m, c)ÎG₀ と (10-15b) により (s(m), j(c))ÎG₀ が成り立つので、(10-16) で m に s(m) を代入したものが成り立つことがわかります。

　以上で帰納法が完成し、(P-5) により (10-16) がすべての mÎN について成立することがわかりました。
　ゆえに、G₀ はある写像 f : N ® A のグラフになっていて、しかも (10-15a) により f(0) º a が、また (10-15b) により j( f(n)) º  f(s(n)) が成り立つことがわかり、これは f が (N, 0, s) から (A, a, j) への射になっていることを意味します。
　逆に、(N, 0, s) から (A, a, j) への任意の射 g は、g(0) = a º f(0) を満たし、g(n) = f(n) を仮定すると g(s(n)) = j(g(n)) = j( f(n)) º f(s(n)) が得られるので、帰納法 (P-5) により "_nat n : g(n) = f(n) すなわち g = f となるので、射の一意性も得られます。
　以上で (N, 0, s) が自然圏の始対象であることが証明されました。

　さてここで、任意の理論 s に対し、その上の再帰的集合論上の集合論 s'* において、Peanoの公理を満たす１変項述語 nat で、nat 項は必ず s' 項であるようなものが作れることを示しましょう。
　実際、

(10-21a)  0 :º Æ

(10-21b)  s(x) :º {x}

(10-21c)  ind(A) :º ( s' P(A)  Ù  ÆÎA  Ù  "xÎA : s(x)ÎA )

(10-21d)  nat(x) :º "A ( ind(A)  Þ  xÎA )

と置いて、これらがPeanoの公理を満たすことを確かめます。
　まず (P-1) と (P-3) と (P-4) が成り立つことは明らかです。
　また、nat(x) と ind(A) を仮定すると、nat の定義から xÎA となり、ind の定義から s(x)ÎA となり、再度 nat の定義から nat(s(x)) が得られ、(P-2) が成り立つこともわかります。
　また (P-5) については、その前提が成り立つとき、A :º { x | nat(x) Ù P(x) } と置けば ind(A) が成り立つので、nat(x) なら xÎA すなわち P(x) が得られ、これは (P-5) の成立を意味します。

　以上により、任意の理論 s に対し、理論 s'* には、Peanoの公理を満たす１変項述語 nat で、nat 項は常に s' 項であるようなものが存在することがわかりました。
　ゆえに、s' の更に再帰的集合論 s" を作れば、nat(n) を満たす n の全体からなる集合 N :º { nÎ[s' ] | nat(n) } が存在するので、上で示したことから、理論 s" は無限公理を満たします。
　従って、与えられた任意の理論 t に対し、空な理論、すなわち何も公理を仮定しない１変項述語 s を導入して、その再帰的集合論 s' を作り、これと t との和理論を改めて t と書けば、理論 t' は無限公理を満たすことがわかります。
　以上の理由により、今後考察する理論 t は、すべてその再帰的集合論 t' が無限公理を満たすと仮定することにします。

　さて、以下では帰納的構成を利用して自然数に対する演算を定義していきます。

　最初は加法です。(10-7) において任意に選んだ自然数 m に対して A :º N ，c :º m ，F(n, x) :º s(x) と置いた場合に唯一つ存在する j に対する j(n) を m + n と書くことにすれば、任意の自然数 m , n に対して

(10-22a)  m + 0 º m

(10-22b)  m + s(n) º s(m + n)

が成り立ちます。m + n を m と n の和といいます。一般に同値関係を持つ集合 A に対し、A ´ A から A への関数を２項演算とよびますが、+ は自然数に対する２項演算です。

(10-23)  1 :º s(0)

と置くと、(10-22) により m + 1 º m + s(0) º s(m + 0) º s(m) ですから

(10-24)  s(m) º m + 1

と書けることがわかります。
　なお、0 , 1 に続けて 2 :º s(1) , 3 :º s(2) , 4 :º s(3) , 5 :º s(4) , 6 :º s(5) , 7 :º s(6) , 8 :º s(7) , 9 :º s(8) と定義して、これらを（十進）数字といいます。

　さて、加法に対して結合律、すなわち任意の自然数 l , m , n に対して

(10-25)  (l + m) + n º l + (m + n)

が成り立つことを n に関する帰納法で証明しましょう。まず (10-22a) により

(10-26a)  (l + m) + 0 º l + m º l + (m + 0)

ですから 0 に対しては成立します。また、特定の n に対して (10-25) を仮定すると、(10-22b) により

(10-26b)  (l + m) + s(n) º s((l + m) + n)) º s(l + (m + n)) º l + s(m + n) º l + (m + s(n))

すなわち (10-25) の n を s(n) に置き換えたものが成り立ちます。よって帰納法により、(10-25) が証明されました。
　そこで、今後は (10-25) の左辺の形の式では括弧を省略することにします。これは一般の結合律を満たす演算についても同様です。

　次に、任意の自然数 n に対して

(10-27)  0 + n º n

が成り立つことを n に関する帰納法で証明します。まず (10-22a) により

(10-28a)  0 + 0 º 0

ですから 0 に対しては成立します。また、特定の n に対して (10-27) を仮定すると、(10-22b) により

(10-28b)  0 + s(n) º s(0 + n) º s(n)

すなわち (10-27) の n を s(n) に置き換えたものが成り立ちます。よって帰納法により、(10-27) が証明されました。
　一般に、集合 A で定義された２項演算 * に対し、

(10-29)  "aÎA : a * e = e * a = a

が成り立つような eÎA を演算 * の単位元といいますが、(10-22a),(10-27) は、0 が加法 + の単位元であることを意味しています。
　次に、任意の自然数 m , n に対して

(10-30)  s(m) + n º s(m + n)

が成り立つことを n に関する帰納法で証明します。まず (10-22a) により

(10-31a)  s(m) + 0 º s(m) º s(m + 0)

ですから 0 に対しては成立します。また、特定の n に対して (10-30) を仮定すると、(10-22b) により

(10-31b)  s(m) + s(n) º s(s(m) + n) º s(s(m + n)) º s(m + s(n))

すなわち (10-30) の n を s(n) に置き換えたものが成り立ちます。よって帰納法により、(10-30) が証明されました。(10-30) を用いると、加法に関する交換律、すなわち任意の自然数 m , n に対して

(10-32)  m + n º n + m

が成り立つことが n に関する帰納法で証明できます。実際、(10-22a) と (10-27) により

(10-33a)  m + 0 º m º 0 + m

ですから 0 に対しては成立します。また、特定の n に対して (10-32) を仮定すると、(10-22b) と (10-30) により

(10-33b)  m + s(n) º s(m + n) º s(n + m) º s(n) + m

すなわち (10-32) の n を s(n) に置き換えたものが成り立ちます。よって帰納法により、(10-32) が証明されました。

　さて、同値関係 = の与えられた集合 A と、= と両立し結合律を満たす A 上の演算 · と、演算 · の単位元 e が与えられたとき、(10-7) において c :º e , F(n, x) :º x · a と置いた場合に唯一つ存在する j に対する j(n) を aⁿ と書くことにすれば、任意の自然数 n に対して

(10-34a)  a0 º e

(10-34b)  as(n) º an · a

が成り立ちます。このとき任意の自然数 m , n に対して

(10-35)  am+n = am · an

が成り立つことが n に関する帰納法により証明できます。実際、(10-22a),(10-29),(10-34a) により

(10-36a)  am+0 º am = am · e º am · a0

ですから 0 に対しては成立します。また、特定の n に対して (10-35) を仮定すると、(10-22b) と (10-34b) 及び · に関する結合律により

(10-36b)  am+s(n) º as(m+n) º am+n · a = (am · an ) · a = am · (an · a) º am · as(n)

すなわち (10-35) の n を s(n) に置き換えたものが成り立ちます。よって帰納法により、(10-35) が証明されました。また、(10-34b) で n に 0 を代入して (10-23) を用いれば、a¹ º a^s(0) º a⁰ · a º e · a = a すなわち

(10-37)  a1 = a

が成り立ちます。また、任意の自然数 n に対して

(10-38)  en = e

が成り立つことが n に関する帰納法により証明できます。実際、(10-34a) により 0 に対しては成立します。また、特定の n に対して (10-38) を仮定すると、(10-34b) により

(10-39)  es(n) º en · e = e · e = e

すなわち (10-38) の n を s(n) に置き換えたものが成り立ちます。よって帰納法により、(10-38) が証明されました。

　特に · が可換なとき、これを + と書いて加法とよぶことがあり、その場合は e を 0 と書き、aⁿ を na と書いて、これを a の n倍と読みます。この表記のもとでは (10-34) は

(10-40a)  0a º 0

(10-40b)  s(n)a º na + a

と書け、(10-35),(10-37),(10-38) は、それぞれ

(10-41)  (m + n)a = ma + na

(10-42)  1a = a

(10-43)  n0 = 0

と書かれます。また、A の任意の元 a , b に対し、

(10-44)  n(a + b) = na + nb

が成り立つことが n に関する帰納法により証明できます。実際、(10-40a) と 0 が単位元であることにより

(10-45a)  0(a + b) º 0 = 0 + 0 º 0a + 0b

ですから 0 に対しては成立します。また、特定の n に対して (10-44) を仮定すると、(10-40b) 及び A の演算 + の結合律と交換律により

(10-45b)  s(n)(a + b)	º n(a + b) + (a + b)
	= (na + nb) + (a + b)
	= na + (nb + (a + b))
	= na + (nb + (b + a))
	= na + ((nb + b) + a)
	= na + (a + (nb + b))
	= (na + a) + (nb + b)
	º s(n)a + s(n)b

すなわち (10-41) の n を s(n) に置き換えたものが成り立ちます。よって帰納法により、(10-44) が証明されました。
　性質 (10-41),(10-44) を併せて分配律とよびます。なお、(10-44) は、演算 + を乗法的に（つまり本来の記法で）表わした場合は

(10-46)  (a · b)n = an · bn

となります。

　さて、特に A が N で + が N の加法のとき、mn を、m と n の積といい、この２項演算を自然数の乗法といいます。
　自然数の乗法を用いると、(10-34) で定義される演算 aⁿ に対して

(10-47)  (am )n = an m

が成り立つことが n に関する帰納法により証明できます。実際、(10-40a) により 0 º 0m ですから、これと (10-34a) により

(10-48a)  (am )0 º e º a0 º a0m

ですから 0 に対しては成立します。また、特定の n に対して (10-47) を仮定すると、(10-34b),(10-35),(10-40b) により

(10-48b)  (am )s(n) º (am )n · am = an m · am = an m + m º as(n) m

すなわち (10-47) の n を s(n) に置き換えたものが成り立ちます。よって帰納法により、(10-47) が証明されました。(10-47) は、演算 · を加法的に書く場合は

(10-49)   n(ma) = (nm)a

となります。これを自然数の乗法の場合に適用すれば、自然数の乗法に対して結合律が成つことがわかります。
　次に、任意の自然数 n , m に対して

(10-50)   nm + n º ns(m)

が成り立つことを n に関する帰納法で証明しましょう。まず (10-40a),(10-28a) により

(10-51a)   0m + 0 º 0 + 0 º 0 º 0s(m)

ですから 0 に対しては成立します。また、特定の n に対して (10-50) を仮定すると、(10-40b),(10-25),(10-22b),(10-32) により

(10-51b)   s(n)m + s(n)	º (nm + m) + s(n)
	º nm +(m + s(n))
	º nm + s(m + n)
	º nm + s(n + m)
	º nm + (n + s(m))
	º (nm + n) + s(m)
	º ns(m) + s(m)
	º s(n)s(m)

すなわち (10-50) の n を s(n) に置き換えたものが成り立ちます。よって帰納法により、(10-50) が証明されました。(10-50) を用いると、自然数の乗法に対する交換律：

(10-52)  nm º mn

が証明できます。実際、(10-40a),(10-43) により

(10-53a)  0m º 0 º m0

ですから 0 に対しては成立します。また、特定の n に対して (10-52) を仮定すると、(10-40b),(10-50) により

(10-53b)  s(n)m º nm + m º mn + m º ms(n)

すなわち (10-52) の n を s(n) に置き換えたものが成り立ちます。よって帰納法により、(10-52) が証明されました。(10-52),(10-42) により、1 は自然数の乗法の単位元であることがわかります。
　演算 · を自然数の乗法としたとき (10-34) で定義される演算 aⁿ を、a のn乗とよびます。自然数の乗法は交換律を満たすので、(10-35),(10-47) に加えて (10-46) が成り立ちます（これらを指数法則とよぶことがあります）。