順序のはなし

古来より日本のプログラマの間には、「正月はフラクタル」という風習があります。

http://d.hatena.ne.jp/ku-ma-me/20110101/p1

ほぉ〜寡聞にして知らなんだ。

じゃあ、俺は「正月は数学」という風習を始めてみようと思います。

よしっ、今年のテーマは「順序 (ordering)」。順序に関わる話題を1ヶ月続けてみます。
「大学数学に興味があるけれどどう勉強していいか分からない。とっかかりが欲しい。」という人を対象に、平易なところから始めてみることにします。

全順序 (total order) の定義

最初は各順序の定義から始めます。

順序には色んな種類があるのでまず全順序から話をしていきます。
この順序は普段使っている「順序」のことで、どんな2つのものに対して大小が付けられるものを言います。

順序を記号で「a ≦ b」と書いて、「a は b 以下」と読みます。

定義の形で書くと、以下の3つのルール (公理) を満たすものとなります。

  1. どんな a でも a ≦ a どんな a, b でも a ≦ b または a ≧ b のどちらかが成り立つ
  2. a ≦ b かつ b ≦ a ならば a = b
  3. a ≦ b かつ b ≦ c ならば a ≦ c

どれも当たり前のことを言ってると思いますが、それを改めてルールとして抽出するのが重要なのです。
ある命題を示すときには、この抽出したルールのみを使って証明を進めていきます。

余談

「<」じゃなく「≦」を使うのはなぜか? と思われたかもしれませんが、特に大きな意味は無いと思います。
上記の全順序に対して「<」を「≦ かつ ≠」と定義できます。そして、逆に

  1. a < b, a = b, a > b のどれか1つのみ成立する
  2. a < b かつ b < c ならば a < c

と「より小さい」ことを定義して、「≦」を「< または =」と別の定義を与えることができます。
(「『=』の定義は何だ!?」というツッコミは確かにあるのですが、今回は「順序」シリーズなので同値に関してはまた別のシリーズで扱いたいと思います。
ひとまず、普通にイメージする等号「=」と思ってください。)

こうやって「<」を経由して「≦」を定義することができ、当然最初に出した定義と同じことを言ってます。

ちょっとそれを確かめてみましょう。さて、何を示せば良いのでしょうか?

定義が同じことを言うには、片方の定義に出てくるルール (公理) からもう一方の定義のルール (この場合は気分的には「命題」と読んだりしたいです。) が成り立っていることを示せば良いです。
つまり、「<」が上のように定義されているとき「≦」=「< または =」についての3つの命題を示します。

  1. どんな a でも「a = a」は成立しているので、「a < a または a = a」も成立しています。 a < b, a = b, a > b のどれかが成立しているので, a ≦ b または a ≧ b のどちらかが成り立ちます.
  2. 「「a < b または a = b」かつ「a > b または a = b」」を変形すると「「a < b かつ a > b」または「a < b かつ a = b」または「a = b かつ a > b」または「a = b かつ a = b」」となり、定義より a < b, a = b, a > b のどれか1つのみ成立するので「a = b」が成立することが分かります。(この変形はいわゆる分配法則です。)
  3. 「「a < b または a = b」かつ「b < c または b = c」」を変形すると「「a < b かつ b < c」または「a < b かつ b = c」または「a = b かつ b < c」または「a = b かつ b = c」」となり、まとめると「a < c または a < c または a < c または a = c」つまり「a ≦ c」となって欲しかった結論が出ます。

定義が同等である、ということのイメージが付いたでしょうか?
こういう議論はある程度の慣れが必要かと思いますので、何度も考えてみてください。

全順序の例

さて余談が長くなりましたが、本筋に戻って全順序が出てくる例を見ていきます。

まず自然数 (ここでは正の整数、1、2、3… とします) には全順序が出てきます。
通常の意味での大小関係があり、上の「≦」が満たすべきルール (公理) を満たしているので自然数には全順序があります。
(より正確に言うと「自然数は通常の大小関係が全順序となる集合」のような表現になるのですが、ここでは敢えて端折った不正確な表現をしています。)

次に整数 (0、±1、±2…) を考えてみましょう。
これにもさっきの自然数と同じく通常の意味での大小関係が全順序となります。

自然数と大きく違うところは整数には最小元はありません。自然数には「1」という「一番小さい数」がありますが、
整数では常にどんな数にもそれより小さい数 (例えば1つ小さい数) が存在して底無しに続いていきます。
この特徴は後で無限降下法を扱うところで効いてくるので、覚えておいてください。(そして俺も書くのを忘れないようにします!)

ちょっと複雑な例を出しましょう。
文字列の辞書順について見てみましょう。

辞書順とは「先頭の文字から比較していって50音順で早いものが前の方に、同じだった場合は次の文字で比較。さらに同じだったらさらに次の文字へ。」という比較の仕方でしたね。「は」と「ば」など細かいところに関しては今は解説は省きます。

当然、辞書は単語を辞書順で並べています。また学校の出席番号も姓名に関する辞書順です。
(私のときは男女別に番号を振っていたが、今は男女一緒に番号を振ったりするのだろうか?)

そしてこの並べ方だとどっちの出席番号がより後ろに来るのかはっきり決まります。
「こっちの人が前だけれど、考えようによっては別の人の方が前」というような曖昧さはありません。
この順序に関して曖昧さが無い、というのは別の言い方をすれば「1列に並べられる」ということです。
ここが「全順序」の特徴が強く出ているところなので、よく意識に焼き付けておいてください。

小学校の算数や国語の授業中は出席番号順に並んで勉強することが (特に新学年が始まった頃は) ありますが、体育の時間はまた別の順序で並びますね?
そうです「身長順」です。同じ集団に2つ以上の順序が入ることがあるのです。

これは裏を返せば、「ある集団 (集合) には好きに全順序が入れられる」ということです。もちろん上記の定義の3つの公理 (ルール) を守っている必要はありますが。

なので「誕生日の早い順」だったり「住所の辞書順」だったり色々な順序を作ることができます。順序はただ与えられるものではなく自分で定義できるものなのです。

明日以降は「半順序」「前順序」について扱っていきます。

おまけ

ただの思い付きです。

♪順序全順序順序、順序半順序順序、順序前順序ポセット順序、序順序順序最小元
(ポセット (poset) とかについては今後扱っていきます。)