FANDOM


定義

整列集合 (Well ordered set) とは、集合 $ X $ で以下を満たすものである。

  • $ X $全順序集合である。つまり、以下の4つの公理を満たす。
    1. $ X $ に二項関係 $ \le $ が備わっており、$ X $ の任意の元 $ x, y $ に対して $ x \le y $ または $ y \le x $ のいずれか(両方でもよい)が必ず成り立つ。
    2. $ x \le x $$ \forall x \in X $) [反射律]
    3. $ x \le y $ かつ $ y \le x $ ならば $ x=y $$ \forall x,y \in X $) [反対称律]
    4. $ x \le y $ かつ $ y \le z $ ならば $ x \le z $$ \forall x,y,z \in X $) [推移律]
  • $ X $ の任意の空でない部分集合 $ A $ に対し、$ A $ の最小元 $ a_0 $ が存在する。つまり、任意の $ A $ の元 $ a $ に対して、$ a_0 \le a $ が成り立つ。(このことを、二項関係 $ \le $整礎であると言う。)

  1. 『二項関係 $ \leq $ が備わっており』とは『$ X $ の2つの元の組からなる集合 $ X \times X = \{(x,y); x, y \in X \} $ の部分集合 $ R $ が与えられており』という意味である。$ (x,y) \in R $ のとき $ x\leq y $ と書く、と思えばいい(反例2を参照)。集合 $ X $ に公理1. ~3. を満たす関係 $ \leq $ を与えることを、 「集合 $ X $ に全順序 $ \leq $ を定める(あるいは、入れる)」と言う。同じ集合に別の全順序を入れることもできるし、公理さえ満たしていれば $ \leq $ は必ずしも「順序っぽく」定めなくてもよい。(公理絶対主義!)
  2. $ a \leq b $ かつ $ a \neq b $ のとき、$ a < b $ と書く。

例1

自然数全体の集合 $ \mathbb{N}= \{0,1,2,3,\ldots\} $ に通常の大小関係 $ \le $ を入れると、$ \mathbb{N} $ は整列集合になる。例えば$ \{3,5,8\} $ の最小元は $ 3 $ だし、$ \{2,4,6,8,\ldots\} $ の最小元は $ 2 $

反例1

$ 0 $ 以上の実数全体の集合 $ \mathbb{R}_{\ge 0} $ に通常の大小関係 $ \le $ を入れると、 $ \mathbb{R}_{\ge 0} $ は全順序集合だが、整列集合ではない。実際、部分集合として開区間 $ (0,1)=\{x; 0<x<1 \} $ を取ると、これには最小限が存在しない。どんなに小さい数、例えば0.0000000001などを取っても、さらにそれより小さい数、例えば0.0000000000000000001などが $ (0,1) $ には入ってるわけである。

反例2

無題

半順序集合{0,1,1'}

$ X=\{0,1,1'\} $ という3元からなる集合(各 $ 0,1,1' $ はただの記号と思ってほしい)に関係 $ \le $

$ 0\le 0,\, 1\le 1,\, 1'\le 1',\, 0 \le 1,\, 0\le 1' $

で定めると、$ X $ は反射律と推移律は満たすが$ 1 $$ 1' $ は比較できない。つまり $ 1\le 1' $$ 1'\le 1 $ のいずれも成り立たない。

このように反射律と推移律を満たすものの、全ての2つの元が比較できるとは限らない集合のことを半順序集合という(私と仕事とどっちが大切なの!)。 ちなみに$ X $ の部分集合 $ \{1,1'\} $ に最小元は存在しない。

$ X \times X = \{(0,0),(0,1),(0,1'),(1,0),(1,1),(1,1'),(1',0),(1',1),(1',1')\} $ であり、注1. の $ R $$ \{(0,0),(1,1),(1',1'),(0,1),(0,1')\} $ である。

反例3

自然数の無限列全体の集合 

$ X=\{(a_0,a_1,a_2,\ldots); a_i \in \mathbb{N}\, (i=0,1,2,\ldots) \} $

を考える。これに「辞書式順序」を入れてみよう。つまり、$ X $ の元 $ a=(a_0,a_1,a_2,\ldots), b=(b_0,b_1,b_2,\ldots) $ に対して、 

$ a \leq b :\Leftrightarrow a=b $ または「$ a \neq b $ かつ、 $ a_i \neq b_i $ である最小の $ i $ に対して $ a_i < b_i $」。 

と定める。これは「左から順番に勝負していって最初に勝った(大きい)方が勝ち(大きい)」というルールである。例えば $ a=(1,3,2,99,0,0,\ldots) $, $ b=(1,3,4,0,0,0,\ldots) $ ならば $ a_i \neq b_i $ である最小の $ i $$ 3 $$ a_3<b_3 $ だから $ a < b $ である。

このとき$ X $は全順序集合だが、整列集合ではない。 実際、$ X $ の部分集合 $ A $ を  $ A=\{(1,0,0,0,0,\ldots), (0,1,0,0,0,\ldots), (0,0,1,0,0,\ldots), (0,0,0,1,0,\ldots) \} $

と定めると、$ A $ には最小元が存在しない。なぜなら $ A $ の元は右に行けば行くほど小さくなり、それが無限に続いているからである(「真の無限降下列」という)。

$ X $ は非可算濃度である: $ |X|=|\mathbb{N}^\mathbb{N}|=|\mathbb{R}| $

例2

今度は反例2を改良して、整列集合をつくろう。

$ Y=\{(a_0,a_1,a_2,\ldots); a_i \in \mathbb{N}\, (i=0,1,2,\ldots), a_i \neq 0 $ となる $ i $ は有限個 $ \} $

とおく。最後の条件を付け加えたので、例えば $ (1,1,1,1,\ldots) $ は反例3の $ X $ の元だが $ Y $ の元ではない。
この $ Y $ に「辞書式順序」を入れてみよう。つまり、$ Y $ の元 $ a=(a_0,a_1,a_2,\ldots), b=(b_0,b_1,b_2,\ldots) $ に対して、

$ a \leq b :\Leftrightarrow a=b $ または「$ a \neq b $ かつ、 $ a_i \neq b_i $ である最大$ i $ に対して $ a_i < b_i $

と定める。これは「から順番に勝負していって最初に勝った(大きい)方が勝ち(大きい)」というルールである。例えば $ a=(1,3,2,1,0,0,\ldots) $, $ b=(99,2,2,1,0,0,\ldots) $ ならば $ a_i \neq b_i $ である最大の $ i $$ 2 $$ b_2<a_2 $ だから $ b < a $ である。反例3の $ X $ で同じように順序を定めようとすると、「最大の $ i $ 」というものが一般には存在できず上手くいかないことに注意されたい。

このとき、$ Y $ は全順序集合で、しかも整列集合であることが証明できる。たとえば反例3の $ A $ は今度は「無限上昇列」になるので、最小元 $ (1,0,0,0,0,\ldots) $ がとれる。 

$ Y $ は順序数 $ \omega^\omega $ と順序同型である。

$ Y $ は可算濃度である: $ |Y|=|\mathbb{N}| $

整列集合の演算

整列集合の演算を参照。