「順序の理論」の数学的な基礎（その

(1)

構造の数理

ÎÁÁº

「順序の理論」の数学的な基礎（その

^½

）

渕野昌

神戸大学大学院システム情報学研究科

神戸大学年度後期の講義

!"

(2)

数の大小関係 ^{構造の数理}

を，のどれかとする． ^解説このとき上の（通常の）大小関係は次の性質を満たす

すべてのに対し，反射律

すべてのに対し，かつならが成

り立つ反対称律

すべてのに対し，かつなら，が

成り立つ推移律

すべてのに対し，またはの少なくとも片

方は成り立つ比較可能性

任意の集合上の二項関係が上のの性質に相当する性質を満たすとき，は上の線型順序であるという．

(3)

線形順序 ^{構造の数理} を任意の集合とするとき，上の二項関係が次の性質を満たすとき，は上の線形順序あるいは，全順序であるという

すべてのに対し，かつならが成り

立つ反対称律

すべてのに対し，またはの少なくとも片

方は成り立つ比較可能性

(4)

線型順序の例 ^{構造の数理}

を任意の集合とするとき，上の二項関係が次の性質を満たすとき，

は上の線形順序 ^!^#$あるいは，全順序 ^!^#$であるという

すべての^¾ に対し，反射律

すべての ^¾ に対し，かつなら^% 反対称律

すべての ^¾ に対し，かつなら，推移律

すべての ^¾ に対し，またはの少なくとも片方は成り

立つ比較可能性

をのどれかとするとき，上の通常の大小関係

は上の線形順序である．

ぐーちょきぱーとする．上の二項関係を，

となるの組は，ぐーぐーちょきちょきぱーぱーちょきぐーぐーぱーぱーちょきであるとして定義する．つまりはじゃんけんで，あいこになるか，がに勝つこと，

として定義する．このときは上の線型順序かは線形順序の性質のうちどれを満たすか

(5)

線形順序の例その ^{構造の数理}

とするとき，上の二項関係を，に対し， ^¼^¼ とするとき（ただし，^¼

¼

で ^¼ とする），

または ^¼ かつ ^¼ または ^¼ と定義する． ^¼ は前回の記号を使うととも書ける， ^¼ をと書くことにすると，

かつまたは

ともあらわせる．は上の線形順序となる（演習）．をに関して小さい順に並べると，

となる．のときには，上の順序は通常のと一致する．

のときには，上の順序での部分（無限に続くプロセス）

が個あらわれる．

(6)

半順序 ^{構造の数理} 集合上の二項関係が線形順序の性質のうち，比較可能性以外の性質を満たすとき（比較可能性は成り立っていても成り立っていなくてもどちらでもよい），は半順序

であるという．つまり

が上の半順序であるとは，が次のつの性質を満たすことである

すべてのに対し，かつならが成り

立つ反対称律

(7)

半順序の例 ^{構造の数理}

が上の半順序であるとは，が次の^&つの性質を満たすことである

すべての^¾ に対し，反射律

すべての ^¾ に対し，かつなら^% 反対称律

すべての ^¾ に対し，かつなら，推移律

上の任意の線形順序は上の半順序でもある．

上の関係をで定義すると，は半順序である．

上の半順序をはを割りきるで定義すると，は半順序となる．たとえば，かつだから，このは線形順序ではないことがわかる．

(8)

半順序の線形順序への拡張 ^{構造の数理}

定理

有限集合上の任意の半順序は，上の線形順序 ^¼ に拡張できる．

上の二項関係 ^¼ が，別の上の二項関係の拡張であるとは，すべてのに対し，なら，^¼ となることである．

定理の証明の方針の要素の数に関する帰納法で証明する．

例としてとする．に対し，

¼

かつ

¼¼

かつまたはとする．^¼ はの拡張で，^¼¼は ^¼ の拡張である．^¼¼は

線型順序の最後の例での関係と一致するから，線型順序である．

(9)

構造の数理

(10)

Ê É 構造の数理

は実数

実数数直線上の点に対応する数．

は有理数

有理数分数として表わせる数．

の要素は整数と呼ばれるのだった．

前回に導入した記号を用いて

戻る