整列集合の定義
全順序集合について簡単に復習した上で、特別な全順序集合である整列集合と呼ばれる概念をフォーマルな形で定義します。その上で、全順序集合が整列集合であることの意味を様々な形で理解します。
集合\(A\)上に定義された二項関係\(\leq \)が全順序であることとは、反射律、反対称律、推移律、そして完備律を満たすこと、すなわち、\begin{eqnarray*}&&\left( O_{1}\right) \ \forall x\in A:x\leq x \\
&&\left( O_{2}\right) \ \forall x,y\in A:\left[ \left( x\leq y\wedge y\leq
x\right) \Rightarrow x=y\right] \\
&&\left( O_{3}\right) \ \forall x,y,z\in A:\left[ \left( x\leq y\wedge y\leq
z\right) \Rightarrow x\leq z\right] \\
&&\left( O_{4}\right) \ \forall x,y\in A:\left( x\leq y\vee y\leq x\right)
\end{eqnarray*}が成り立つこととして定義されます。集合\(A\)上に全順序\(\leq \)が定義されている場合、これらの組\begin{equation*}\left( A,\leq \right)
\end{equation*}を全順序集合と呼びます。ただし、全順序集合について言及していることが文脈から明らかである場合には、全順序集合をシンプルに、\begin{equation*}
A
\end{equation*}と表記できます。全順序集合の要素\(x,y\in A\)について、\begin{equation*}x\leq y
\end{equation*}が成り立つ場合には、\(x\)は\(y\)以下であるとか、\(y\)は\(x\)以上であるなどと言います。
全順序集合\(A\)が与えられたとき、任意の要素\(x,y\in A\)に対して、\begin{equation*}x<y\Leftrightarrow \left( x\leq y\wedge x\not=y\right)
\end{equation*}を満たすものとして\(A\)上の二項関係\(<\)を新たに定義すると、この\(<\)は狭義全順序になることが保証されます。つまり、\(<\)は非対称律と推移律に加えて三分律を満たすということ、具体的には、\begin{eqnarray*}&&\left( S_{1}\right) \ \forall x,y\in A:\left[ x<y\Rightarrow \lnot \left(
y<x\right) \right] \\
&&\left( S_{2}\right) \ \forall x,y,z\in A:\left[ \left( x<y\wedge
y<z\right) \Rightarrow x<z\right] \\
&&\left( S_{3}\right) \ \forall x,y\in A:x<y,\ y<x,\ x=y\text{の中の1つだけが成り立つ}
\end{eqnarray*}が成り立つということです。全順序集合の要素\(x,y\in A\)について、\begin{equation*}x<y
\end{equation*}が成り立つ場合には、\(x\)は\(y\)より小さいとか、\(y\)は\(x\)より大きいなどと言います。
集合に同一の要素が含まれる場合にはそれらの要素を区別しません。したがって、集合が与えられたとき、そのすべての要素がお互いに異なる状況を想定しても一般性は失われません。以上を踏まえると、全順序\(\leq \)から先の要領で定義された二項関係\(<\)が狭義全順序になるという事実は、全順序集合\(A\)のすべての要素は\(<\)のもとで、\begin{equation*}x_{1}<x_{2}<x_{3}<x_{4}<\cdots
\end{equation*}という形で一列に並べられることを意味します。
\end{equation*}が得られます。
全順序集合\(A\)の非空な部分集合\(B\)が与えられたとき、任意の\(x,y\in B\)に対して、\begin{equation*}x\leq _{B}y\Leftrightarrow x\leq y
\end{equation*}を満たすものとして\(B\)上の二項関係\(\leq _{B}\)を新たに定義すれば、これは\(B\)上の全順序になることが保証されます。つまり、\begin{eqnarray*}&&\left( O_{1}\right) \ \forall x\in B:x\leq _{B}x \\
&&\left( O_{2}\right) \ \forall x,y\in B:\left[ \left( x\leq _{B}y\wedge
y\leq _{B}x\right) \Rightarrow x=y\right] \\
&&\left( O_{3}\right) \ \forall x,y,z\in B:\left[ \left( x\leq _{B}y\wedge
y\leq _{B}z\right) \Rightarrow x\leq _{B}z\right] \\
&&\left( O_{4}\right) \ \forall x,y\in B:\left( x\leq _{B}y\vee y\leq
_{B}x\right)
\end{eqnarray*}が成り立つということです。したがって、\begin{equation*}
\left( B,\leq _{B}\right)
\end{equation*}は全順序集合になります。言い換えると、集合\(A\)上に定義された全順序\(\leq \)の始集合と終集合を\(A\)の部分集合\(B\)に制限しても全順序のままであるということです。多くの場合、このような全順序\(\leq _{B}\)をもとの全順序と同じ記号\(\leq \)を用いて表記します。
&&\left( \mathbb{Z} ,\leq _{\mathbb{Z} }\right) \\
&&\left( \mathbb{N} ,\leq _{\mathbb{N} }\right)
\end{eqnarray*}はいずれも全順序集合になります。ただし、慣例として\(\leq _{\mathbb{Q} },\leq _{\mathbb{Z} },\leq _{\mathbb{N} }\)をいずれも\(\leq \)で表記します。
全順序集合\(A\)の非空な部分集合\(B\)が与えられたとき、この集合\(B\)に属するある要素\(b\)が、集合\(B\)に属する任意の要素以下である場合には、つまり、\begin{equation*}\exists b\in B,\ \forall x\in B:b\leq x
\end{equation*}が成り立つ場合には、この要素\(b\)を集合\(B\)の最小元と呼び、そのことを、\begin{equation*}b=\min B
\end{equation*}で表記します。つまり、集合\(B\)の最大元\(\min B\)は以下の条件\begin{equation*}\forall x\in B:\min B\leq x
\end{equation*}を満たす\(B\)の要素として定義されるということです。集合\(B\)の最小元は\(B\)の要素である必要があります。つまり、\begin{equation*}\min B\in B
\end{equation*}です。\(B\)に属さない要素は\(B\)の最小元にはなり得ません。
逆に、全順序集合\(A\)の非空な部分集合\(B\)が与えられたとき、集合\(B\)に属する要素\(b\)がその集合\(B\)の最小元でないことは、\begin{equation*}\exists x\in B:\lnot \left( b\leq x\right)
\end{equation*}が成り立つことを意味しますが、\(\leq \)が全順序である場合には以下の関係\begin{equation*}\lnot \left( b\leq x\right) \Leftrightarrow x<b
\end{equation*}が成り立つため、\(b\)が\(B\)の最小元でないことは、\begin{equation*}\exists x\in X:x<b
\end{equation*}が成り立つことと必要十分です。つまり、集合\(B\)の要素である\(b\)に対して、それよりも小さい要素が\(B\)の中に存在する場合、\(b\)は\(B\)の最小元ではありません。
\end{equation*}に注目します。要素\(0\in \left[ 0,1\right] \)は、\begin{equation*}\forall x\in \left[ 0,1\right] :0\leq x
\end{equation*}を満たすため、\begin{equation*}
\min \left[ 0,1\right] =0
\end{equation*}であることが明らかになりました。
全順序集合の部分集合が非空であったとしても、その部分集合は最小元を持つとは限りません。以下の例より明らかです。
\end{equation*}を定義します。\(\min A\)が存在しないことを示すために\(\min A\)が存在するものと仮定して矛盾を導きます。\(\min A\)が存在するとき、最小元の定義より\(\min A\in A\)ですが、すると\(A\)の定義より、\begin{equation}a<\min A<b \quad \cdots (1)
\end{equation}が成り立ちます。\(\min A\)と\(a\)はともに実数であるため、有理数の稠密性より、\begin{equation}a<x<\min A \quad \cdots (2)
\end{equation}を満たす有理数\(x\)が存在します。有理数は実数であるため\(x\)は実数です。\(\left( 1\right) ,\left( 2\right) \)および\(<\)の推移律より、\begin{equation*}a<x<b
\end{equation*}が成り立ちますが、\(A\)の定義より、これは\(x\in A\)であることを意味します。つまり、\(\min A\)よりも小さい\(A\)の要素\(x\)が存在することが示されましたが、これは\(\min A\)が\(A\)の最小元であることと矛盾します。したがって背理法より\(\min A\)が存在しないことが明らかになりました。
全順序集合\(A\)が与えられたとき、その非空な部分集合は最小元を持つとは限らないことが明らかになりました。逆に、全順序集合\(A\)の非空な部分集合が必ず最小元を持つ場合には、すなわち、\begin{equation*}\forall B\subset A:\left( B\not=\phi \Rightarrow \exists \min B\right)
\end{equation*}が成り立つ場合には、このような全順序集合\(A\)を整列集合（well-ordered set）と呼びます。
\end{equation*}を定義します。\(A\)は\(\mathbb{R} \)の非空な部分集合ですが、先に示したように\(\min A\)は存在しません。したがって\(\mathbb{R} \)は整列集合ではありません。
以上が整列集合の定義です。では、全順序集合が整列集合であることには、どのような意味があるのでしょうか。また、整列集合であるような全順序集合の具体例として、どのようなものが存在するのでしょうか。順番に考えます。
整列集合の直感的な意味
私たちがモノの個数を数える際には無秩序に数えるのではなく、多くの場合、数えようとしているモノを並べた上で、1つずつ順番に数えていきます。
A=\left\{ a,b,c\right\}
\end{equation*}に属する要素の個数を数える際には、集合に属する要素を、\begin{equation*}
a<b<c
\end{equation*}と1列に並べた上で、左から順番に、\begin{equation*}
1\rightarrow 2\rightarrow 3
\end{equation*}と数えていきます。その結果、集合\(A\)に属する要素の個数が\(3\)であることが判明します。
上の例が示唆するように、モノの個数を数えることと順序の間には深い関係があります。
議論の一般化を見据えた上で、先の例を利用しつつ、集合に属する要素の個数を数えるプロセスを体系化します。
A=\left\{ a,b,c\right\}
\end{equation*}に属する要素の個数を数えるために、まずは、集合\(A\)上に全順序\(\leq \)を導入します。全順序を利用すればすべての要素を1列に並べることができます。ここでは、以下の形\begin{equation*}a<b<c
\end{equation*}に要素が1列に並んだ状況を想定します。以上の順序を踏まえた上で、要素の個数を数えていきます。
- 初期時点は空集合\(\phi \)であり、そこに含まれる要素の個数は\(0\)です。
- 要素の個数が\(0\)である集合\(\phi \)に最初の要素\(a\)を加えることにより、要素の個数が\(0+1=1\)である集合\(\left\{ a\right\} \)が得られます。
- 要素の個数が\(1\)である集合\(\left\{ a\right\} \)に\(a\)の次の要素\(b\)を加えることにより、要素の個数が\(1+1=2\)である集合\(\left\{ a,b\right\} \)が得られます。
- 要素の個数が\(2\)である集合\(\left\{ a,b\right\} \)に\(b\)の次の要素\(c\)を加えることにより、要素の個数が\(2+1=3\)である\(\left\{ a,b,c\right\} \)すなわち\(A\)が得られます。
- 以上により、集合\(A\)に属する要素の個数は\(3\)であることが明らかになりました。
このようなプロセスを滞りなく進行させるためには、集合\(A\)は以下の2つの条件を満たしている必要があります。
前提として、集合\(A\)のすべての要素を1列に並べる必要があるため、集合\(A\)は全順序集合である必要があります。つまり、集合\(A\)上に全順序\(\leq \)が定義されているということです。
先の例では、集合\(A\)の部分集合\begin{equation*}\phi \rightarrow \left\{ a\right\} \rightarrow \left\{ a,b\right\}
\rightarrow \left\{ a,b,c\right\}
\end{equation*}を次々と生成しながら要素の個数を1つずつ数えていきましたが、これらの集合を\(A\)の始部（initial part）と呼びます。その際、始部\(\phi \)に要素\(a\)を加えることにより新たな始部\(\left\{ a\right\} \)を生成し、その始部\(\left\{ a\right\} \)に要素\(b\)を加えることにより新たな始部\(\left\{ a,b\right\} \)を生成し、その始部\(\left\{a,b\right\} \)に要素\(c\)を加えることにより\(\left\{ a,b,c\right\} \)すなわち\(A\)を得る、という形でプロセスを進めました。したがって、このようなプロセスを滞りなく進行させるためには、それぞれの始部に対して、そこに加えるべき1つの要素を必ず特定できることが保証されている必要があります。始部に加えるべき要素を、その始部の直後の要素（successor）と呼びます。
$$\begin{array}{cc}
\hline
始部 & 直後の要素 \\ \hline
\phi & a \\ \hline
\left\{ a\right\} & b \\ \hline
\left\{ a,b\right\} & c \\ \hline
\end{array}$$
以上の議論から明らかになったように、先のプロセスを通じて集合\(A\)の要素の個数を数えるためには、集合\(A\)は全順序集合であるとともに、集合\(A\)の任意の始部が直後の要素を1つずつ持つことを保証する必要があります。集合\(A\)が以上の2つの性質を満たす場合、集合\(A\)は整列集合（well-ordered set）であると言います。
ここでは有限集合を例として挙げましたが、以降では、無限集合を含めた一般の全順序集合を対象に同様の議論を行います。
全順序集合の始切片と終切片
全順序集合\(A\)の要素\(a\in A\)が与えられたとき、\(a\)以下であるような\(A\)の要素をすべて集めることにより得られる集合を、\begin{equation*}L\left( a\right) =\left\{ x\in A\ |\ x\leq a\right\}
\end{equation*}で表記し、これを要素\(a\)に関する集合\(A\)の広義の始切片（weak initial segment of the set \(A\) with respect to the element \(a\)）や要素\(a\)に関する集合\(A\)の広義の下方位集合（weak lower contour set of the set \(A\) withrespect to the element \(a\)）などと呼びます。
A=\left\{ a,b,c\right\}
\end{equation*}上に定義されている全順序\(\leq \)のもとでは、\begin{equation*}a<b<c
\end{equation*}が成り立つものとします。\(A\)のそれぞれの要素に関する広義の始切片は、\begin{eqnarray*}L\left( a\right) &=&\left\{ x\in A\ |\ x\leq a\right\} =\left\{ a\right\}
\\
L\left( b\right) &=&\left\{ x\in A\ |\ x\leq b\right\} =\left\{ a,b\right\}
\\
L\left( c\right) &=&\left\{ x\in A\ |\ x\leq c\right\} =\left\{
a,b,c\right\}
\end{eqnarray*}となります。
全順序集合の要素\(a\in A\)が与えられたとき、\(a\)より小さい\(A\)の要素をすべて集めることにより得られる集合を、\begin{equation*}L_{s}\left( a\right) =\left\{ x\in A\ |\ x<a\right\}
\end{equation*}で表記し、これを要素\(a\)に関する集合\(A\)の狭義の始切片（strict initial segment of the set \(A\) with respect to the element \(a\)）や要素\(a\)に関する集合\(A\)の狭義の下方位集合（strict lower contour set of the set \(A\)with respect to the element \(a\)）などと呼びます。
A=\left\{ a,b,c\right\}
\end{equation*}上に定義されている全順序\(\leq \)のもとでは、\begin{equation*}a<b<c
\end{equation*}が成り立つものとします。\(A\)のそれぞれの要素に関する狭義の始切片は、\begin{eqnarray*}L_{s}\left( a\right) &=&\left\{ x\in A\ |\ x<a\right\} =\phi \\
L_{s}\left( b\right) &=&\left\{ x\in A\ |\ x<b\right\} =\left\{ a\right\}
\\
L_{s}\left( c\right) &=&\left\{ x\in A\ |\ x<c\right\} =\left\{ a,b\right\}
\end{eqnarray*}となります。
全順序集合の要素\(a\in A\)が与えられたとき、\(a\)以上であるような\(A\)の要素をすべて集めることにより得られる集合を、\begin{equation*}U\left( a\right) =\left\{ x\in A\ |\ x\geq a\right\}
\end{equation*}で表記し、これを要素\(a\)に関する集合\(A\)の広義の終切片（weak final segment of the set \(A\) with respect to the element \(a\)）や要素\(a\)に関する集合\(A\)の広義の上方位集合（weak upper contour set of the set \(A\) withrespect to the element \(a\)）などと呼びます。
A=\left\{ a,b,c\right\}
\end{equation*}上に定義されている全順序\(\leq \)のもとでは、\begin{equation*}a<b<c
\end{equation*}が成り立つものとします。\(A\)のそれぞれの要素に関する広義の終切片は、\begin{eqnarray*}U\left( a\right) &=&\left\{ x\in A\ |\ x\geq a\right\} =\left\{
a,b,c\right\} \\
U\left( b\right) &=&\left\{ x\in A\ |\ x\geq b\right\} =\left\{ b,c\right\}
\\
U\left( c\right) &=&\left\{ x\in A\ |\ x\geq c\right\} =\left\{ c\right\}
\end{eqnarray*}となります。
全順序集合の要素\(a\in A\)が与えられたとき、\(a\)より大きい\(A\)の要素をすべて集めることにより得られる集合を、\begin{equation*}U_{s}\left( a\right) =\left\{ x\in A\ |\ x>a\right\}
\end{equation*}で表記し、これを要素\(a\)に関する集合\(A\)の狭義の始切片（strict final segment of the set \(A\) with respect to the element \(a\)）や要素\(a\)に関する集合\(A\)の狭義の上方位集合（strict upper contour set of the set \(A\)with respect to the element \(a\)）などと呼びます。
A=\left\{ a,b,c\right\}
\end{equation*}上に定義されている全順序\(\leq \)のもとでは、\begin{equation*}a<b<c
\end{equation*}が成り立つものとします。\(A\)のそれぞれの要素に関する狭義の終切片は、\begin{eqnarray*}U_{s}\left( a\right) &=&\left\{ x\in A\ |\ x>a\right\} =\left\{ b,c\right\}
\\
U_{s}\left( b\right) &=&\left\{ x\in A\ |\ x>b\right\} =\left\{ c\right\}
\\
U_{s}\left( c\right) &=&\left\{ x\in A\ |\ x>c\right\} =\phi
\end{eqnarray*}となります。
全順序集合の要素の直前の要素と直後の要素
全順序集合の2つの要素\(x,y\in A\)が与えられたとき、以下の条件\begin{equation*}\exists z\in A:\left( x<z<y\right) \vee \left( y<z<x\right)
\end{equation*}を満たす\(A\)の要素\(z\)が存在する場合には、すなわち、\(z\)は\(x\)より大きく\(y\)より小さいか、または\(y\)より大きく\(x \)より小さい場合には、このような\(z\)を\(x\)と\(y\)の間にある要素（element between \(x\) and \(y\)）と呼びます。
全順序集合の2つの要素\(x,y\in A\)が与えられたとき、\(y\)が\(x\)より大きく、なおかつ\(x\)と\(y\)の間には要素が存在しない場合には、すなわち、以下の条件\begin{eqnarray*}&&\left( a\right) \ x<y \\
&&\left( b\right) \ \forall z\in A:\lnot \left( x<z<y\right) \wedge \lnot
\left( y<z<x\right)
\end{eqnarray*}がともに成り立つ場合には、\(x\)は\(y\)の直前の要素である（\(x\)is the predecessor of \(y\)）と言います。同じことを、\(y\)は\(x\)の直後の要素である（\(y\) is the successor of \(x\)）と言うこともできます。
全順序集合の要素が与えられたとき、その直前の要素や直後の要素は存在するとは限りません。以下の例より明らかです。
A=\left\{ a,b,c\right\}
\end{equation*}上に定義されている全順序\(\leq \)のもとでは、\begin{equation*}a<b<c
\end{equation*}が成り立つものとします。\(a\)の直後の要素は\(b\)であり、\(b\)の直後の要素は\(c\)です。しかし、\(c\)の直後の要素は存在しません。また、\(c\)の直前の要素は\(b\)であり、\(b\)の直前の要素は\(a\)ですが、\(a\)の直前の要素は存在しません。
全順序集合の要素が与えられたとき、その直前の要素や直後の要素は存在するとは限らないことが明らかになりました。一方、全順序集合の要素の直前の要素や直後の要素が存在する場合、それらはそれぞれ一意的に定まることが保証されます。
全順序集合の部分集合の直後の要素
全順序集合\(A\)の部分集合\(B\)が与えられたとき、\(A\)の要素\(a\)が以下の2つの条件\begin{eqnarray*}&&\left( a\right) \ \forall x\in B:x<a \\
&&\left( b\right) \ \forall x\in A:\left( x<a\Rightarrow \exists b\in
B:x\leq b<a\right)
\end{eqnarray*}を満たす場合には、すなわち、\(a\)は\(B\)の任意の要素よりも大きく、なおかつ、\(a\)より小さい\(A\)の任意の要素に関しては、それが\(B\)の任意の要素よりも大きくなる事態が起こり得ない場合には、このような要素\(a\)を集合\(B\)の直後の要素（successor of \(B\)）と呼びます。
A=\left\{ a,b,c\right\}
\end{equation*}上に定義されている全順序\(\leq \)のもとでは、\begin{equation*}a<b<c
\end{equation*}が成り立つものとします。空集合は任意の集合の部分集合であるため、\begin{equation*}
\phi \subset A
\end{equation*}です。\(A\)の要素である\(a \)に注目すると、\begin{eqnarray*}&&\left( a\right) \ \forall x\in \phi :x<a \\
&&\left( b\right) \ \forall x\in \left\{ a,b,c\right\} :\left(
x<a\Rightarrow \exists y\in \phi :x\leq y<a\right)
\end{eqnarray*}となります。\(x\in \phi \)は偽であるため\(\left( a\right) \)は真であり、\(x<a\)は偽であるため\(\left( b\right) \)は真です。したがって\(\phi \)の直後の要素は\(a\)です。続いて、以下の部分集合\begin{equation*}\left\{ a\right\} \subset A
\end{equation*}に対しては、\(A\)の要素である\(b\)に注目すると、\begin{eqnarray*}&&\left( a\right) \ \forall x\in \left\{ a\right\} :x<b \\
&&\left( b\right) \ \forall x\in \left\{ a,b,c\right\} :\left(
x<b\Rightarrow \exists y\in \left\{ a\right\} :x\leq y<b\right)
\end{eqnarray*}がともに成り立つため、\(\left\{ a\right\} \)の直後の要素は\(b\)です。続いて、以下の部分集合\begin{equation*}\left\{ a,b\right\} \subset A
\end{equation*}に対しては、\(A\)の要素である\(c\)に注目すると、\begin{eqnarray*}&&\left( a\right) \ \forall x\in \left\{ a,b\right\} :x<c \\
&&\left( b\right) \ \forall x\in \left\{ a,b,c\right\} :\left(
x<c\Rightarrow \exists y\in \left\{ a,b\right\} :x\leq y<c\right)
\end{eqnarray*}がともに成り立つため、\(\left\{ a,b\right\} \)の直後の要素は\(c\)です。
全順序集合\(A\)は自身の部分集合であるため、\(A\)の直後の要素が存在するか検討可能ですが、全順序集合\(A\)自身は直後の要素を持ちません。
空集合は任意の集合の部分集合であるため、空集合の直後の要素が存在するか検討可能ですが、全順序集合\(A\)が最小元を持つ場合、そしてその場合にのみ空集合の直後の要素が存在します。
全順序集合の部分集合が与えられたとき、その直後の要素は存在するとは限りません。以下の例より明らかです。
\end{equation*}は直後の要素を持ちません。そのことを示すために、\(B\)の直後の要素\(a\in \mathbb{R} \)が存在するものと仮定して、すなわち、\begin{eqnarray*}&&\left( a\right) \ \forall x\in B:x<a \\
&&\left( b\right) \ \forall x\in \mathbb{R} :\left( x<a\Rightarrow \exists b\in B:x\leq b<a\right)
\end{eqnarray*}がともに成り立つものと仮定して矛盾を導きます。\(B\)の定義と\(\left( a\right) \)より、\begin{equation*}a>1
\end{equation*}を得ます。このとき、\begin{equation*}
1<\frac{1+a}{2}<a
\end{equation*}が成り立ちますが、このような実数\(\frac{1+a}{2}\)が存在することは\(\left(b\right) \)と矛盾です。したがって背理法より、\(B\)の直後の要素は存在しないことが明らかになりました。
全順序集合の部分集合が与えられたとき、その直後の要素は存在するとは限らないことが明らかになりました。一方、全順序集合の部分集合の直後の要素が存在する場合、それは一意的に定まることが保証されます。
全順序集合\(A\)の要素\(a\)に関する狭義の始切片\(L_{s}\left( a\right) \)は必ず直後の要素を持つとともに、それは\(a\)と一致します。集合の直後の要素が存在する場合には一意的に定まるため、\(L_{s}\left( a\right) \)の直後の要素は\(a\)だけです。
\end{equation*}は直後の要素を持つとともに、それは\(a\)と一致する。
全順序集合\(A\)の2つの要素\(a,b\)が与えられたとき、\(b\)が\(a\)の直後の要素であることと、\(b\)が\(a\)に関する広義の始切片\(L\left( a\right) \)の直後の要素であることは必要十分です。
\end{equation*}と定義される。
全順序集合の始部
全順序集合\(A\)の部分集合\(B\)が以下の条件\begin{equation*}\forall x\in B,\ \forall y\in A:\left( y<x\Rightarrow y\in B\right)
\end{equation*}を満たす場合には、すなわち、\(B\)の要素を任意に選んだとき、それより小さい要素もまた\(B\)の要素になることが保証される場合には、このような部分集合\(B\)を\(A\)の始部（initial part）と呼びます。
A=\left\{ a,b,c\right\}
\end{equation*}上に定義されている全順序\(\leq \)のもとでは、\begin{equation*}a<b<c
\end{equation*}が成り立つものとします。空集合は任意の集合の部分集合であるため、\begin{equation*}
\phi \subset A
\end{equation*}です。\(x\in \phi \)は偽であるため以下の命題\begin{equation*}\forall x\in \phi ,\ \forall y\in A:\left( y<x\Rightarrow y\in \phi \right)
\end{equation*}は真であり、したがって\(\phi \)は\(A\)の始部です。続いて、以下の部分集合\begin{equation*}\left\{ a\right\} \subset A
\end{equation*}に注目します。\(y<a\)を満たす\(A\)の要素\(y\)は存在しないため以下の命題\begin{equation*}\forall x\in \left\{ a\right\} ,\ \forall y\in A:\left( y<x\Rightarrow y\in
\left\{ a\right\} \right)
\end{equation*}は真であり、したがって\(\left\{ a\right\} \)は\(A\)の始部です。続いて、以下の部分集合\begin{equation*}\left\{ a,b\right\} \subset A
\end{equation*}に注目します。以下の命題\begin{equation*}
\forall x\in \left\{ a,b\right\} ,\ \forall y\in A:\left( y<x\Rightarrow
y\in \left\{ a,b\right\} \right)
\end{equation*}は真であるため\(\left\{ a,b\right\} \)は\(A\)の始部です。続いて、以下の部分集合\begin{equation*}A\subset A
\end{equation*}に注目します。以下の命題\begin{equation*}
\forall x\in A,\ \forall y\in A:\left( y<x\Rightarrow y\in A\right)
\end{equation*}は真であるため\(A\)は\(A\)の始部です。
空集合は全順序集合の始部です。
全順序集合\(A\)自身は\(A\)の始部です。
全順序集合\(A\)の任意の要素の広義の始切片は\(A\)の始部です。
\end{equation*}は\(A\)の始部である。
全順序集合\(A\)の任意の要素の狭義の始切片もまた\(A\)の始部です。
\end{equation*}は\(A\)の始部である。
全順序集合\(A\)の始部\(B\)が直後の要素\(a\)を持つ場合、\(B\)は\(a\)に関する狭義の始切片\(L_{s}\left( a\right) \)と一致することが保証されます。
\end{equation*}が成り立つ。ただし、\(L_{s}\left( a\right) \)は\(a\)に関する狭義の始切片であり、\begin{equation*}L_{s}\left( a\right) =\left\{ x\in A\ |\ x<a\right\}
\end{equation*}と定義される。
議論を整理しましょう。全順序集合の要素\(a\in A\)を任意に選んだとき、\(a\)に関する狭義の始切片\(L_{s}\left( a\right) \)は直後の要素\(a\)を持つとともに、\(L_{s}\left( a\right) \)は\(A\)の始部です。逆に、\(A\)の始部\(B\)が与えられたとき、\(B\)が直後の要素\(a\)を持つ場合には、\(B\)は狭義の始切片\(L_{s}\left( a\right) \)と一致します。以上より、始部\(B\)が直後の要素\(a\)を持つことと、その始部が\(a\)に関する狭義の始切片であることは必要十分であることが明らかになりました。
a\right)
\end{equation*}が成り立つ。さらにこのとき、\(B\)の直後の要素は\(a\)と一致する。ただし、\(L_{s}\left( a\right) \)は\(a\)に関する狭義の始切片であり、\begin{equation*}L_{s}\left( a\right) =\left\{ x\in A\ |\ x<a\right\}
\end{equation*}と定義される。
整列集合
全順序集合\(A\)の始部は\(A \)の部分集合であるため、\(A\)のそれぞれの始部が直後の要素を持つか検討できます。\(A\)は自身の始部であり、\(A\)自身は直後の要素を持たないことは先に示した通りです。そこで、\(A\)自身とは異なる\(A\)の任意の始部が直後の要素を持つ場合、そのような全順序集合\(A\)を整列集合（well-ordered set）と呼びます。
A=\left\{ a,b,c\right\}
\end{equation*}上に定義されている全順序\(\leq \)のもとでは、\begin{equation*}a<b<c
\end{equation*}が成り立つものとします。先に示したように\(A\)の始部は\(\phi ,\left\{ a\right\},\left\{ a,b\right\} ,A\)ですが、この中でも\(A\)とは異なる始部である\(\phi ,\left\{ a\right\} ,\left\{a,b\right\} \)はいずれも直後の要素を持ちます。
$$\begin{array}{cc}
\hline
始部 & 直後の要素 \\ \hline
\phi & a \\ \hline
\left\{ a\right\} & b \\ \hline
\left\{ a,b\right\} & c \\ \hline
\end{array}$$
以上より、\(A\)は整列集合であることが明らかになりました。
逆に、全順序集合\(A\)自身とは異なる\(A\)の始部の中に直後の要素を持たないものが存在する場合、\(A\)は整列集合ではありません。全順序集合は整列集合であるとは限りません。以下の例より明らかです。
\end{equation*}は\(\mathbb{R} \)自身とは異なる\(\mathbb{R} \)の始部ですが、先に示したように、この集合\(A\)は直後の要素を持ちません。したがって、\(\mathbb{R} \)は全順序集合ではありません。
全順序集合\(A\)が整列集合である場合には、すべての要素を、\begin{equation*}x_{1}<x_{2}<x_{3}<\cdots
\end{equation*}という形で1列に並べることができるとともに、\(A\)自身とは異なる任意の始部に直後の要素が存在することが保証されるため、空集合\(\phi \)を出発点として、それぞれの始部に直後の要素を加えていくことにより始部の列\begin{equation*}\phi \rightarrow \left\{ x_{1}\right\} \rightarrow \left\{
x_{1},x_{2}\right\} \rightarrow \left\{ x_{1},x_{2},x_{3}\right\}
\rightarrow \cdots
\end{equation*}を生成することができます。その結果、集合\(A\)の要素の個数を、\begin{equation*}0\rightarrow 1\rightarrow 2\rightarrow 3\rightarrow \cdots
\end{equation*}という形で滞りなく数えていくことができます。
整列集合の代替的な定義
整列集合は以下のように様々な形で定義可能です。
全順序集合\(\left( A,\leq \right) \)に関して、以下の3つの命題はお互いに必要十分である。
- \(A\)は整列集合である。すなわち、\(A\)自身とは異なる\(A\)の任意の始部が直後の要素を持つ。
- \(A\)自身とは異なる\(A\)の任意の始部が、\(A\)の何らかの要素に関する狭義の始切片である。つまり、\(A\)とは異なる\(A\)の始部\(B\)を任意に選んだとき、それに対して、\begin{equation*}\exists a\in A:B=L_{s}\left( a\right) \end{equation*}が成り立つ。
- \(A\)の任意の非空な部分集合が最小元を持つ。
整列集合の具体例：有限集合
全順序集合が有限集合である場合には、それが整列集合であることが保証されます。
A=\left\{ a,b,c\right\}
\end{equation*}上に定義されている全順序\(\leq \)のもとでは、\begin{equation*}a<b<c
\end{equation*}が成り立つものとします。\(A\)は有限集合であるため整列集合です。始部と直後の要素は以下の通りです。
$$\begin{array}{cc}
\hline
始部 & 直後の要素 \\ \hline
\phi & a \\ \hline
\left\{ a\right\} & b \\ \hline
\left\{ a,b\right\} & c \\ \hline
\end{array}$$
つまり、\begin{equation*}
\phi \rightarrow \left\{ a\right\} \rightarrow \left\{ a,b\right\}
\rightarrow A
\end{equation*}という形で始部の列を生成できるため、集合\(A\)の要素の個数を、\begin{equation*}0\rightarrow 1\rightarrow 2\rightarrow 3
\end{equation*}と滞りなく数えていくことができます。
整列集合の具体例：自然数集合
すべての自然数からなる集合\(\mathbb{N} \)上に大小関係\(\leq \)を定義すれば全順序集合\(\left( \mathbb{N} ,\leq \right) \)が得られますが、これは整列集合です。
自然数集合\begin{equation*}\mathbb{N} =\left\{ 1,2,3,\cdots \right\}
\end{equation*}上に定義された大小関係\(\leq \)のもとで、すべての自然数を、\begin{equation*}1<2<3<\cdots
\end{equation*}という形で1列に並べることができます。先の命題より\(\left( \mathbb{N} ,\leq \right) \)は全順序集合であるため、空集合\(\phi \)を出発点として、それぞれの始部に直後の要素を加えていくことにより始部の列\begin{equation*}\phi \rightarrow \left\{ 1\right\} \rightarrow \left\{ 1,2\right\}
\rightarrow \left\{ 1,2,3\right\} \rightarrow \cdots
\end{equation*}を生成することができます。その結果、自然数の個数を、\begin{equation*}
0\rightarrow 1\rightarrow 2\rightarrow 3\rightarrow \cdots
\end{equation*}という形で滞りなく数えていくことができます。
演習問題
A=\left\{ \sqrt{2},\sqrt{3},\sqrt{4},\sqrt{5},\sqrt{6},\sqrt{7}\right\}
\end{equation*}上に大小関係\(\leq \)を定義します。\(\left( A,\leq \right) \)は整列集合でしょうか。議論してください。
A=\left\{ \frac{1}{x}\ |\ x\in \mathbb{N} \wedge x\leq 100\right\}
\end{equation*}上に大小関係\(\leq \)を定義します。\(\left( A,\leq \right) \)は整列集合でしょうか。議論してください。
A=\left\{ x\ |\ x\in \mathbb{Q} \wedge x>5\right\}
\end{equation*}上に大小関係\(\leq \)を定義します。\(\left( A,\leq \right) \)は整列集合でしょうか。議論してください。
\left[ 0,1\right] =\left\{ x\in \mathbb{R} \ |\ 0\leq x\leq 1\right\}
\end{equation*}上に大小関係\(\leq \)を定義します。\(\left( \left[ 0,1\right] ,\leq\right) \)は整列集合でしょうか。議論してください。
プレミアム会員専用コンテンツです
【ログイン】【会員登録】