利用者:Nayuta Ito/高校数学から巨大基数まで最速でたどる
この記事はジョークではありません。
前提知識: 高校数学(主に「集合と論理」)。(2012～2021年度の教育課程における)数Ⅲの知識は(たぶん)全く必要ない。
目標知識: 到達不可能基数の定義。あわよくばマーロ基数まで行きたい。
参考文献: 巨大数研究Wiki
第0章 記号の定義
\( \mathbb{N} \)で\( 0 \)以上の整数の集合を表すことにする。
\( \mathbb{R} \)で実数全体の集合を表すことにする。
第1章 順序数
参考文献: 巨大数研究Wiki「順序数」
第1節 直積
集合\( A \)と\( B \)に対し、\( A \)と\( B \)の直積とは、\( \{ (a,b) \mid a \in A, b \in B \} \)のことであり、\( A \times B \)で表す。
以下に例を示す。
$$ \{ 1, 2, 3 \} \times \{ a, b\} = \{ (1,a), (1,b), (2,a), (2,b), (3,a), (3,b) \} $$
$$ \mathbb{N} \times \{ 1 \} = \{ (0,1), (1,1), (2,1), \cdots \} = \{ (x,1) | x \in \mathbb{N} \} $$
\( \mathbb{R} \times \mathbb{R} = \{ (x,y) \mid x, y \in \mathbb{R} \} \)であるが、\( (x,y) \)を座標だと思うと、これは座標平面全体に対応する。
第2節 関係
集合\( A \)に対し、\( A \)上の関係とは、\( A \times A \)の部分集合のことである。関係は英語でrelationと呼ばれるため、その頭文字を取って\( R \)で表されることが多い。
\( (a,b) \in R \)であるとき、\( a R b \)と書くこともある。
以下に例を示す。
\( A = \{ 1, 2, 3 \} \)上の関係\( R \)を\( \{ (1,1), (1,2), (2,1), (2,2), (3,3) \} \)とすると、\( 1R1, 1R2, 2R1, 2R2, 3R3 \)であるが、\( 1R3, 2R3, 3R1, 3R2 \)ではない。
\( \mathbb{R} \)上の関係\( L \)を\( \{ (x,y) \mid x \leq y \} \)で定義する。このとき\( xLy \)と\( x \leq y \)は同値である。
\( \mathbb{R} \)上の関係\( E \)を\( \{ (x,x) \mid x \in \mathbb{R} \} \)で定義する。このとき\( xRy \)と\( x = y \)は同値である。
第3節 全順序集合
集合\( T \)とその上の関係\( R \)の組\( \langle T , R \rangle \)が全順序集合であるとは、\( R \)が次の性質を満たすことである。
- どんな\( x \in T \)に対しても、\( xRx \)が成り立つ。(反射性)
- 「\( xRy \) かつ \( yRx \)」 ならば、 「\( x=y \)」。(反対称性)
- 「\( xRy \) かつ \( yRz \)」 ならば、 「\( xRz \)」。(推移性)
- どんな\( x,y \in T \)に対しても、\( xRy \)と\( yRx \)の少なくとも一方が成り立つ。(比較可能性)
全順序集合とは、\( \langle T , R \rangle \)という組のことであって、\( T \)そのものや\( R \)そのものを指しているわけではない。
以下に例を示す。
\( A = \{ 1, 2, 3 \} \)上の関係\( B \)を\( \{ (1,1), (1,2), (2,1), (2,2), (3,3) \} \)とすると、\( B \)は反射性と推移性を満たすが、反対称性と比較可能性は満たしていないので、\( \langle A , B \rangle \)は全順序集合ではない。
\( T = \{ R, P, S \} \)上の関係\( M \)を\( \{ (R,R), (R,P), (P,P), (P,S), (S,S), (S,R) \} \)とすると、\( M \)は反射性、反対称性、比較可能性を満たすが、推移性は満たしていないので、\( \langle T , M\rangle \)は全順序集合ではない。
\( A = \{ 1, 2, 3 \} \)上の関係\( C \)を\( \{ (1,1), (2,1), (2,2), (3,1), (3,2), (3,3) \} \)とすると、\( C \)は反射性、反対称性、推移性、比較可能性の全てを満たすので、\( \langle A , C \rangle \)は全順序集合である。
\( \mathbb{R} \)上の関係\( L \)を\( \{ (x,y) \mid x \leq y \} \)とすると、\( L \)は反射性、反対称性、推移性、比較可能性の全てを満たすので、\( \langle \mathbb{R} , L \rangle \)は全順序集合である。
全順序集合は\( \leq \)や\( \geq \)に似たものだと思えばわかりやすい。実際、3番目の例は\( \geq \)、4番目の例は\( \leq \)に対応している。
しかし、全順序集合はすべて\( \leq, \geq \)になるかというとそうではない。実際、\( \mathbb{N} \)上の関係\( R \)を次のように定義すると、\( \langle \mathbb{N}, R \rangle \)は全順序集合である。
$$ \{ (x,y) \mid 「y = 0」 または 「x \neq 0 かつ x \leq y」 \} $$
この関係は、\( 1R2, 2R3, 3R4, \cdots \)かつ\( 1R0, 2R0, 3R0, \cdots \)という式を満たす。すなわち、「基本的には普通の大小関係だが、\( 0 \)だけは例外的に一番大きいとみなす」という大小関係における\( \leq \)の関係であると言える。すなわち、次のような序列が成り立っている。
$$ 1R2R3R4 \cdots \cdots R0 $$
\( \geq \)は「要素の符号を反転させたときの\( \leq \)」とみなせるので、以下では全順序集合の関係として\( \leq \)のようなものを想定する。しかし、\( \geq \)も全順序集合の関係になりうることに注意されたい。
第4節 整列集合
全順序集合\( \langle T, R \rangle \)が整列集合であるとは、どんな\( T \)の\( \emptyset \)ではない部分集合\( S \)に対しても、その中に「どんな\( s \in S \)に対しても\( m R s \)となるような\( m \)」が存在することである。
もし\( R \)を\( \leq \)だと思えば、「」内は単に「\( S \)の最小値」と言い換えられる。
「\( \emptyset \)ではない」という条件は「空集合に最小値がないのは当たり前である」ということを表しているだけであり、整列集合の条件は「\( T \)の要素が1個以上集まればその中には必ず最小値がある」と言い換えることもできる。
以下に例を示す。
\( A = \{ 1, 2, 3 \} \)上の関係\( X \)を\( \{ (1,1), (1,2), (1,3), (2,2), (2,3), (3,3) \} \)とすると、\( a X b \)は\( a \leq b \)と同値であり、\( \emptyset \)ではない\( A \)のどんな部分集合に対しても最小値が存在するので、\( \langle A, X \rangle \)は全順序集合である。
\( \mathbb{R} \)上の関係\( L \)を\( \{ (x,y) \mid x \leq y \} \)とすると、\( aLb \)は\( a \leq b \)と同値であるが、\( \mathbb{R} \)の部分集合の中には\( \emptyset \)ではなくて最小値が存在しないものが存在するので、\( \langle \mathbb{R}, L \rangle \)は全順序集合ではない。
実際、\( \mathbb{N} \)上の関係\( R \)を\( \{ (x,y) \mid 「y = 0」 または 「x \neq 0 かつ x \leq y」 \} \)とすると、\( a R b \)は\( a \leq b \)と同値ではないが、\( \mathbb{N} \)のどんな\( \emptyset \)ではない部分集合にも\( 1R2R3R4 \cdots \cdots R0 \)という特殊な大小関係の下での最小値は存在するので、全順序集合である。
第5節 推移的集合
集合\( A \)が推移的集合であるとは、\( A \)の全ての要素がそれ自体\( A \)の部分集合であることである。「要素がそれ自体部分集合」とはいささか奇妙だが、以下の例を見れば納得するだろう。
\( \{ \emptyset \} \)は推移的集合である。なぜなら、\( \{ \emptyset \} \)の要素\( \emptyset \)は\( \{ \emptyset \} \)の部分集合だからである(どんな集合に対しても\( \emptyset \)はその部分集合となることに注意しよう)。
\( \{ \{ \emptyset \} \} \)は推移的集合でない。なぜなら、\( \emptyset \) は\( \{ \{ \emptyset \} \} \)の要素ではなく、したがって\( \{ \{ \emptyset \} \} \)の要素\( \{ \emptyset \} \)は\( \{ \{ \emptyset \} \} \)の部分集合ではないからである。
\( \{ \emptyset, \{\emptyset\}, \{\{\emptyset\}\} \} \)は推移的集合である。証明は読者への演習問題とする。
特殊な例として、\( \emptyset \)がある。\( \emptyset \)はそれ自身が推移的集合である。なぜなら、もし「\( \emptyset \)の全ての要素がそれ自体\( \emptyset \)の部分集合である」が偽だとすると、「\( \emptyset \)の要素だが\( \emptyset \)の部分集合でないもの」という反例が存在することになるが、そのような反例は存在しないからである。
