順序のはなし・その2
さて今日は「半順序」の話をします.
昨日の全順序 (total order) に比べやや足りないところがあるので,「半順序」(partial order) と言います. どこが足りないかをこれから見ていきましょう.
半順序の定義
さて, まずは定義から行きましょう. 全順序のときと同じように記号「≦」が満たすルールを並べて定義します.
- どんな a でも a ≦ a
- a ≦ b かつ b ≦ a ならば a = b
- a ≦ b かつ b ≦ c ならば a ≦ c
昨日の全順序と比べてどこが違うでしょうか?
そうです, 1つ目のルール以外は全く一緒です. そして, 全順序の1つ目のルール「a ≦ b または b ≦ a が成立する」から b が a だった場合を考えると,「a ≦ a」が出てきます. 今何を示したかというと, 全順序の1つ目のルールから半順序の1つ目のルールが導き出せることを示しました.
その逆はどうなるかと言うと導き出すことはできません. つまり全順序のルールは半順序のルールよりも強い (別の言い方だと「厳しい」) ものなのです. ここに全順序と半順序の違いがあります.
全順序の1つ目のルールが何を言っていたかと言うと,「a ≦ b または b ≦ a」つまり「どんな2つのものでも比較できる」ということでした. 半順序では「自分自身とは比較できる」ということしか保証されていません. この性質が足りないことを指して「半」(partial) という名前なのだと思います.
半順序の例
さて, 昨日扱った「全順序」は「順序」と呼ぶに相応しい感じがしましたが, 今日の「半順序」にはどんな例があるのでしょうか? 果たして自然な例はあるのでしょうか?
私はある集団を考えたときに, そこに入る順序はほとんどは「半順序」で「全順序」は無理矢理付けないと付けられない序列だと思っています.
例えば, とある試験の5教科の成績があったときにそれ比較するときのことを考えてみましょう.
A 君は「国語: 50, 数学: 100, 理科: 80, 社会: 60, 英語: 60」B 君は「国語: 80, 数学: 70, 理科 50, 社会: 70, 英語: 70」という成績だったとします. さて2人のうち「成績が良い」方はどちらでしょうか?
良くある評価方法は合計点で競う方法です. A 君は合計点 350 点, B 君は合計点 340 点なので A 君の方が成績が良いと言うことができます.
他には教科ごとに点数を比較する方法があります. A 君は2勝 (数学, 理科) B 君は3勝 (国語, 社会, 英語) なので, この観点では Β 君の方が成績が良いと言えます.
しかしどちらもあまり釈然としないところが残らないでしょうか?
合計点で競っても,「国語の1点」と「数学の1点」は本当に同じものなのでしょうか? 単純に足してしまって良いのでしょうか? また教科ごとの勝敗で見ても大差で勝っているものもあれば, 僅差で負けているものもあります. そんな状況でそれらを同じ1勝として数えて良いのでしょうか?
ここで全て100点だった人 (C 君) がいれば比較は簡単ですよね? その人はどんな人と比べても, 同じかより成績が良いと言えます.
ここに「半順序」が現れているのです. 1つ目のルールで全順序に対し欠けているのは比較可能性でした. 別の言い方をすると「ある2つのものが比較できないこともある」ということです. 上の例では5教科の成績というものに無理矢理全順序を入れようとしたためやや不自然な順序が入りましたが,「そもそも全順序を入れるのがおかしい」と考える考え方も有りです.
そこで半順序です.「A 君が B 君に対し全ての教科において同じか負けているときに A ≦ B」と定義すれば, これは半順序のルール (公理) を満たします. さすがにこのルールで順序を付ければ文句は無いでしょう.
さて, 今日はこれくらいにします. 順序のイメージが付いてきたでしょうか?
明日は「前順序」(全順序の typo ではない) を扱います.
それでは.
おまけ
順序の例として学校が舞台に上がるのは偶然なのでしょうか. (反語)
余談
このネタは @kinaba さんのブログの 正規表現しちへんげ！ シリーズだったり, @alg_d さんの一連のつぶやきに刺激されて書いています.
