集合と位相

　順序関係：

(2-1a)  x £ x

(2-1b)  ( x £ y  Ù  y £ z )  Þ  x £ z

(2-1c)  ( x £ y  Ù  y £ x )  Þ  x = y

の与えられた類（集合）を順序類（集合）といい（「数学の基礎」第５節 (5-3) の直後及び「数学の基礎」第６節 (6-24) 直後の注意参照）、その順序が全順序：

(2-2)  x £ y  Ú  y £ x

であるとき全順序類（集合）といいます（「数学の基礎」第11節 (11-20) 参照）。本稿の議論では排中律が成り立つので、

(2-3a)  x ¹ y :º Øx = y

(2-3b)  x < y :º ( x £ y  Ù  x ¹ y )

という略記法を用いることにします。x £ y を y ³ x とも書き、“y は x より大きい”又は“x は y より小さい”と読みます。また、x < y を y > x とも書き、“y は x より真に大きい”又は“x は y より真に小さい”と読みます。
　古典論理なので、¹ は「数学の基礎」第８節 (8-33) の不等号の条件を満たします。

　さて、順序集合を対象、順序集合 X から順序集合 Y への単調増加写像、すなわち

(2-4)  x £ y  Þ  f(x) £ f( y)

を満たす写像 f を射とよべば、これは一つの圏（「数学の基礎」第７節参照）を構成します。この圏を順序集合の圏とよびます。
　特に f が一対一のときは、f が単調増加写像であるための条件は

(2-5)  x < y  Þ  f(x) < f( y)

となります。ちなみに X が全順序集合なら、x ¹ y なら x < y 又は y < x ですから、(2-5) から f が一対一であることが導けます。
　更に X , Y が共に全順序集合で f が Y の上への写像の場合、(2-5) から f は一対一、従って逆写像が存在し、しかも (2-5) の対偶から f ^-1 が (2-4) を満たすことがわかるので、条件 (2-5) は、 f が順序集合の圏における同型、すなわち順序同型であるための必要十分条件になります。

　順序類（集合） O の部分類（集合） A に対し、"xÎA x £ a を満たす aÎO を、A の上界といいます（下界も同様に定義されます）。上界（下界）は、それが A に属すとき A の最大元（最小元）といい max A（min A）と書きます。(2-1c) により、最大元（最小元）は、存在すれば一意的です。
　また A の上界（下界）の最小元（最大元）が存在するとき、これを A の上限（下限）といい sup A（inf A）と書きます。A に最大元（最小元）が存在すれば、それは明らかに A の上限（下限）です。

　順序類（集合）は、その空でない任意の部分類（集合）が最小元を持つとき整列類（集合）といいます。
　整列類（集合） O では、任意の２元 x, yÎO に対し、O の部分集合 {x, y} が最小元を持つので、これは (2-2) が成り立つことを意味します。すなわち整列類（集合）は全順序類（集合）です。

　整列類（集合） O では、次の超限帰納法が成り立ちます：

(2-6)  { A Ì O  Ù  "xÎO (( "y < x  yÎA )  Þ  xÎA )}  Þ  A = O

　実際、(2-6) の左辺が成り立つにもかかわらず A ¹ O と仮定すると、O \ A は O の空でない部分ですから、整列類（集合）の定義により最小元 a を持ちます。ところが a の最小性により、x < a なら xÏO \ A すなわち xÎA となりますから、(2-6) 左辺の仮定により aÎA となって矛盾します。

　整列類（集合） O の元 x は、それが O の最大元でない限り { yÎO |  y > x } は空でないので、最小元を持ちます。これを x の次の元とよんで x + 1 と書きます。

　さて、整列類（集合） O の任意の元 a に対し、O の a における切片を

(2-7)  Oa :º { xÎO | x < a }

で定義すると、a は O_a のすべての元より真に大きい最小の元です。
　実際、b が O_a のどの元よりも真に大きいとすると、O は全順序類（集合）ですから、a £ b 又は b < a が成り立ちます。ところが後者の場合、bÎO_a ですから b < b となって矛盾しますから a £ b が成り立ちます。

　さて、O_a が最大元を持つ場合、それを b とすれば、a は b より真に大きい最小の元ですから

(2-8a)  $bÎO : a = b + 1

が成り立ちます。逆に (2-8a) が成り立てば、明らかに b は O_a の最大元です。従って特に (2-8a) を満たす b は一意的です。
　また O_a が最大元を持たない場合、"xÎO_a x £ b のとき、等号を満たす x は存在し得ないので "xÎO_a x < b となるので a £ b が得られ、これは

(2-8b)  a = sup Oa

であることを意味します。aÏO_a ですから、逆に (2-8b) が成り立てば O_a は最大元を持ちません。
　以上で任意の aÎO に対して (2-8a),(2-8b) のいずれか一方が排他的に成立することがわかりました。

　さて次に、整列集合の“ものさし”となる順序数の概念を導入します。
　正則な集合 a は、a Ì P (a) のとき、言い換えると xÎa  Þ  xÌa 、すなわち

(2-9)  yÎxÎa  Þ  yÎa

が成り立つとき推移的であるといいます。推移的な集合は、その元もすべて推移的であるとき順序数といいます。
　順序数の元は順序数です。実際、a を順序数、bÎa とすると、定義から b は推移的です。また xÎb なら a が推移的であることから xÎa となるので、定義から x は推移的になり、これは b が順序数であることを意味しています。

　順序数全体のなす類を Ord と書きます。Ord は集合ではありません。なぜなら、もし集合だとすると、順序数の元が順序数であることから Ord は推移的で、その元ももちろん推移的です。また元がすべて正則であることから Ord も正則、従って Ord 自身が順序数です。つまり OrdÎOrd となりますが、これは Ord の正則性に反します。

　さて、類 A が条件：

(2-10)  "aÎOrd : ( a Ì A  Þ  aÎA )

を満たせば Ord Ì A となることを証明しましょう（順序数に対する超限帰納法）。
　実際、B :º Ord \ A と置くと、(2-10) の括弧の中の対偶を取ることにより、aÎB  Þ  $bÎa : bÎB が成り立ち、これは B が無限降下的であることを意味しています。ところが B の元はすべて順序数なので正則ですから、B は元を持てば矛盾します。すなわち B = Æ 、言い換えると Ord Ì A であることがわかりました。

　さて、超限帰納法の応用例として、任意の順序数 a , b に対して

(2-11)  aÎb  Ú  a = b  Ú  bÎa

が成り立つことを証明しましょう。そのために、すべての順序数 b に対して (2-11) が成り立つような順序数 a の全体を A とし、a Ì A を満たす任意の順序数 a を取ります。この a に対し、すべての順序数 b が (2-11) を満たすことが示せれば、aÎA となり、(2-10) が成立するので Ord Ì A となり、証明が完成します。
　そこで、(2-11) を満たさない順序数 b の全体を B とし、bÎB を任意に取ります。このとき

(2-12)  aÏb  Ù  a ¹ b  Ù  bÏa

が成り立っています。さて、任意に gÎa を取ると、a Ì A により gÎA ですから、仮定により

(2-13)  gÎb  Ú  g = b  Ú  bÎg

が成り立ちます。ここで g = b と仮定すると、gÎa により bÎa となって (2-12) と矛盾し、bÎg と仮定すると、gÎa と a の推移性により bÎa となり、やはり (2-12) と矛盾します。ゆえに gÎb でなければならず、g は任意ですから a Ì b がわかりました。
　一方、(2-12) により a ¹ b ですから、a は b の真部分集合、すなわちある gÎb \ a が存在します。
　さて、このとき明らかに gÏa です。
　また g = a と仮定すると gÎb により aÎb となって (2-12) に反するので g ¹ a です。
　また aÎg と仮定しても gÎb と b の推移性により aÎb となって (2-12) に反するので aÏg です。
　これは gÎB を意味しており、以上で B が無限降下的であることがわかりました。ところが B の元はすべて順序数で正則ですから、B は元を持てば矛盾します。ゆえに B = Æ となり、これはすべての順序数 b が (2-11) を満たすことを意味し、証明は完成しました。

　次に、順序数 a , b について

(2-14)  aÎb  Û  ( a Ì b  Ù  a ¹ b )

が成り立つことを確かめます。
　実際、左辺を仮定すると、b の推移性により a Ì b となりますが、もし a = b なら aÎa となって a の正則性に反します。
　逆に右辺を仮定すると、(2-11) の３とおりの可能性のうち、まず a = b の可能性が仮定により否定され、また bÎa とすると a Ì b により bÎb となって b の正則性に反するのでこの可能性も否定され、結局 aÎb が成り立つことがわかります。

　以上により、(2-11) は排他的に成立し、順序数の全体 Ord は、包含関係を順序とする全順序類になることがわかります。ところが実はさらに強く、Ord は整列類であることを証明しましょう。
　A を Ord の空でない任意の部分類とします。a :º ÇA と置くと、A はある元 b を持つので a Ì b となり、分出公理により a は集合です。
　また xÎa なら、ある bÎA に対して xÎb ですから x は順序数、従って正則で、さらに任意の bÎA に対して xÎb で、b の推移性により x Ì b ですから b の任意性により x Ì a となって a の推移性がわかるので、a は順序数です。
　一方、任意の bÎA に対して a Ì b ですから、(2-14) により a = b 又は aÎb 、従って $bÎA : a = b 又は "bÎA : aÎb が成り立ちます。ところが後者の場合、aÎÇA = a となって a の正則性に反するので前者が成り立ち、これは a が A の最小元であることを意味しています：

(2-15)  min A = ÇA

　さて、定義から明らかに Æ は最小の順序数です。このことを強調するために、Æ のかわりに 0 と書くこともあります：

(2-16)  0 = Æ = min Ord

　また、順序数 a に対し、

(2-17)  a + 1 = aÈ{a}

が成り立ちます。
　実際、右辺の集合は、元がすべて正則なので正則です。また、xÎaÈ{a} なら xÎa 又は x = a ですから、前者なら (2-9) により x Ì a Ì aÈ{a} 、後者の場合も x = a Ì aÈ{a} となるので aÈ{a} は推移的です。また a が順序数ですから x は推移的で、以上により (2-17) の右辺は順序数であることがわかります。
　また b を a Ì b かつ a ¹ b であるような順序数とすると、(2-14) により aÎb となりますが、b の推移性により a Ì b ですから aÈ{a}Ì b が成り立つので、確かに (2-17) の右辺は a より大きい最小の順序数、すなわち α の次の順序数であることがわかります。

　また、A を順序数からなる集合とするとき、明らかに ÈA は順序数です。これが A の上限：

(2-18)  sup A = ÈA

であることも明らかです。

　順序数のうち (2-8a) を満たすもの、すなわちある順序数の次の順序数であるようなものを後続順序数とよんでその全体を OS と書き、(2-8b) を満たすもの、すなわち自分自身の切片の上限になっている順序数を極限順序数とよんでその全体を OL と書くことにすれば、Ord は OS と OL の排他的合併になります。

　次に、前節 (1-14) を満たす最小の集合 a を w と書きます。これが順序数であることを証明しましょう。
　まず前節の議論により w は正則な集合です。
　また、w の元 x のうち x Ì w であるようなものの全体を A と置くと、明らかに ÆÎA であり、また xÎA なら xÎw かつ x Ì w ですから xÈ{x}Ì w であり、w が (1-14) の a の条件を満たすことから xÈ{x}Îw がわかります。これは xÈ{x}ÎA を意味します。
　以上で A が (1-14) の a の条件を満たすことがわかったので、w の最小性から w Ì A となりますが、これは w が推移的であることを意味します。
　次に、w の元のうち推移的なものの全体を A と置くと、明らかに ÆÎA であり、また (2-17) の証明と同様にして xÎA なら xÈ{x}ÎA もわかるので、w の最小性により w Ì A 、すなわち w の元はすべて推移的であることがわかります。
　以上で w が順序数であることがわかりました。w の元を自然数又は有限順序数といいます。w は N と書くこともあります。

　なお、Ord が整列類であることと、順序数の元はすべて順序数であることから、すべての順序数は、それ自身包含関係を順序とする整列集合であることがわかります。

　さて、O を整列類とし、O の切片を定義域とする写像 F に対して、ある小さい項 T(F ) を対応させる対応が与えられているものとします：

(2-19)  "map F : [ ( $xÎO : D(F ) = Ox )  Þ  small(T(F )) ]

　ただし map(F ) は F が写像であることを意味するものとします。
　このとき O 全体で定義された写像 F で、その各切片 O_x への制限 F|_x :º { ( y, z)ÎF | y < x } に対して

(2-20)  "xÎO : F(x) = T(F|x)

が成り立つようなものが唯一つ存在することを超限帰納法で証明しましょう。そのために、O_x を定義域に持つ写像の全体を M_x と書くことにし、条件

(2-21)  "xÎO : "fÎMx : [ f Ì R  Þ  (x, T( f ))ÎR ]

を満たす二項関係 R すべての共分を F とします。(2-21) が R に F を代入しても成り立つことに注意します。以下、F は写像であることを証明しましょう。そのためには、任意の xÎO に対して F|_x :º { (x, h)ÎF | x < x } が写像であることを証明すれば十分なので、これを x に関する超限帰納法で証明します。
　xÎO を任意に取り、任意の y < x に対して F|_y が写像であると仮定します。
　まず x = z + 1 となる z が存在しない場合を考えます。任意の y < x に対して z = y + 1 と置けば y < z < x ですから F|_z は写像で yÎO_z ですから、特に F は y で一価、すなわち ( y, x), ( y, h)ÎF なら x = h です。ゆえに yÎO_x は任意なので、F|_x は写像です。
　次に x = z + 1 となる z が存在する場合を考えます。任意の y < x に対し、y < z 又は y = z です。y < z のときは、F|_z は写像で yÎO_z ですから、特に F は y で一価です。
　また y = z のときは

(2-22)  R = FÇ{ (x, h) | x = z  Þ  h = T(F|z) }

と置きます。このとき R は (2-21) を満たすことを確かめましょう。それには "fÎM_z : [ f Ì R  Þ  (z, T( f ))ÎR ] を示せば十分です。
　そこでまず、fÎM_z かつ f Ì R なら、R|_z = F|_zÎM_z ですから f = F|_z となり、従って (z, T( f )) = (z, T(F|_z))Î{ (x, h) | x = z  Þ  h = T(F|_z) } となります。
　一方、f Ì F が成り立ち、(2-21) の x に z を、R に F を代入したものが成り立つので (z, T( f ))ÎF も成り立ち、(2-22) により (z, T( f ))ÎR が成り立つ、すなわち "fÎM_z : [ f Ì R  Þ  (z, T( f ))ÎR ] が成り立つことがわかりました。
　ゆえに、F が (2-21) を満たす最小の二項関係であることから、R = F となり、(2-22) により R は、従って F は z で一価です。
　以上で F|_x は写像であることがわかり、超限帰納法が完成しました。
　さて、F は写像であることがわかったので、fÎM_x かつ f Ì F なら f = F|_x となり、(2-21) の R に F を代入した式から (x, T(F|_x)) = (x, T( f ))ÎF がわかり、これは F が (2-20) を満たすことを意味しています。

　以上のようにして (2-20) を満たす F を求めることを、関数の超限帰納的構成といい、w 上の帰納的構成（数学の基礎第10節参照）の拡張になっています。

　さて、任意の整列集合 O に対し、F[O]ÎOrd となる順序同型写像 F がただ一つ存在することを証明しましょう。

　もしそのような F が存在すれば、任意の xÎO に対し、F(x) は順序数の元ですから順序数です。y < x なら、F は順序同型ですから F( y)ÎF(x) が成り立ち、逆に aÎF(x) なら、F(x)ÎF[O] で F(x) も F[O]も順序数ですから、順序数の推移性により aÎF[O] すなわち a = F( y) となる yÎO が存在し、F( y)ÎF(x) となりますが、F は順序同型なので y < x がわかります。以上により

(2-23)  F(x) = F[Ox]

が成り立つことがわかりました。これは F の一意性を示しています。なぜなら、G[O]ÎOrd となる順序同型写像 G ¹ F が存在すれば、G(a) ¹ G(a) となる最小の aÎO が存在しますが、xÎO_a なら F(x) = G(x) なので、F(a) = F[O_a] = G[O_a] = G(a) となって矛盾します。

　次に、F の存在を証明するため、O_x ( xÎO ) を定義域とする写像 f に対して

(2-24)  T( f ) :º R( f )

と置いて、この T から超限帰納的に構成した写像を F とすれば、F は (2-23) を満たします。
　このとき F(x) がすべて順序数であることを x に関する超限帰納法で証明しましょう。そこで、すべての y < x に対して F( y) が順序数であると仮定します。bÎaÎF(x) なら、(2-23) により aÎF[O_x] ですから、ある y < x により a = F( y) と書けます。すると、(2-23) の x を y に置き換えた式により bÎa = F[O_y] Ì F[O_x] = F(x) が得られ、これは F(x) が推移的であることを示しています。F(x) の元は順序数ですからもちろん推移的で、これは F(x) が順序数であることを示しており、超限帰納法が完成しました。

　ゆえに

(2-25)  F[O] = È{ F[{ yÎO | y £ x }] | xÎO } = È{ F[Ox]È{F(x)} | xÎO } = È{ F(x)È{F(x)} | xÎO } = È{ F(x) + 1 | xÎO }

は順序数からなる集合の和集合なので順序数です。以上で F[O]ÎOrd となる順序同型写像 F の存在が証明されました。

　以上により、どんな整列集合 O も唯一つの順序数 a と順序同型であることがわかったので、この a のことを O の順序型といい、ord O と書くことにします。
　２つの順序数は、必ず一方が他方の部分集合ですから、２つの整列集合 O と O' は必ず比較可能、すなわち一方が他方の部分集合と順序同型であることがわかります。