Fandom

数学 Wiki

整列集合

131このwikiの
ページ数
新しいページをつくる
コメント0 シェアする

定義編集

整列集合 (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編集

無題.png

半順序集合{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 は反射律と推移律は満たすが11' は比較できない。つまり 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 である最小の i3a_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 である最大の i2b_2<a_2 だから b <  a である。反例3の X で同じように順序を定めようとすると、「最大の i 」というものが一般には存在できず上手くいかないことに注意されたい。

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

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

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

整列集合の演算 編集

整列集合の演算を参照。

広告ブロッカーが検出されました。


広告収入で運営されている無料サイトWikiaでは、このたび広告ブロッカーをご利用の方向けの変更が加わりました。

広告ブロッカーが改変されている場合、Wikiaにアクセスしていただくことができなくなっています。カスタム広告ブロッカーを解除してご利用ください。

Fandomでも見てみる

おまかせWiki