二項関係
今回からは二項関係というものを考えていきます。二項関係というと聞き慣れないかもしれませんが、要するに名前の通り2つの項の関係です。恒等関係(=で結ばれる関係)とか、合同関係(≡で結ばれる関係)とかが代表的な二項関係ですね。
一般的には、次のような小難しい定義になります。
◆定義
を集合とし、
の部分集合
とする。三つ組
を
と
との二項関係
という。
について、
であるとき、
と
は
関係を持つといい、
などと書く。特に、
のとき、
上の二項関係という。
というのが二項関係の最も一般的な定義ですが、こんな一般的なことは結構どうでもいいです。
実際によく使われる2種類の二項関係を押さえておけば大体OKです。それが順序と同値関係です。
同値関係は次回やるとして、今回は順序について見ていきましょう。
順序
順序というのは、その名の通り順序を表す関係を一般的に定義したものです。順序というものが満たすべき性質をまとめて定義としています。次のようになります。
◆定義
集合 上に定義された二項関係
が順序(あるいは順序関係)であるとは、次を満たすことを言う。
・反射律
・推移律
・反対称律
順序が定義された集合のことを順序集合という。
さらに上記3つの条件に加えて次を満たすとき、全順序という。
・全順序律
全順序が定義された集合のことを全順序集合という。全順序でない順序を半順序とも言う。
記号の由来にもなっている普通の実数での大小関係 を考えてみると、順序の典型例となっています。(自分で確かめてみて下さい。結構当たり前のことを言っています)
いくつか例を見ていきましょう。
◇例
は通常の大小関係
によって順序集合となります。しかもこれは全順序です。
一方で、 は通常の大小関係というものを定めることができないため、このやり方では順序集合にはできません。
に全順序を入れるためには、例えば次のような辞書式順序を考えます。
この種の順序は、あたかも辞書を引くかのように手前から順序を参照しているので、辞書式順序と言われています。
実際にこれが全順序であることを、一つ一つの定義に立ち戻って示してみましょう。
・反射律
とすると、
かつ
なので、上の辞書式順序の定義より、
です。
・推移律
とし、
かつ
が成り立っているとします。すると、上の辞書式順序の定義から、
が成り立ちます。ここから、
を示せば、上の辞書式順序の定義から、
が言えます。
では、示しましょう。論理式の演算を行います。(演算のしかたは論理記号 その5を参考)
多少見やすくするために、
で表すと、
は、
と書けます。ここから、
を代入して、
したがって、推移律は成立します。
・反対称律
とし、
かつ
が成り立っているとします。すると、上の辞書式順序の定義から、
が成り立ちます。ここから、
を示しましょう。
やはり、見やすくするために、
とします。すると、
は、
と書けます。推移律のときと同様に論理式を変形して、
を代入して、
ここで、 は成り立たないので、結局、
したがって、 が成り立つので、示されました。
・全順序律
とし、
または
が成り立つことを示します。すなわち、
を示します。
論理式の変形を行い、示すべき命題を同値変形で簡単にしていきましょう。
ここでも、
とします。すると、
は
と書けます。ここから( に注意して)、
を代入して、
ここで、 と
は常に成り立つことから、この式は常に成り立ちます。
よって、示されました。
ところで、 への全順序の入れ方は一つとは限りません。例えば、複素数平面上からの距離の大小で順序付けすると、これは全順序となります。式で書くと、
について、
実数の大小関係が全順序であることから、この順序が全順序であることが従います。
このように、 に全順序を入れる方法は色々あるのですが、いかなる全順序を持ってきたとしても、
における通常の大小関係が持っている次の性質
… 条件1
… 条件2
は満たさないということが知られています。
実際、もし に全順序
が入っているとすると、
か
が成り立ちます。
のとき、条件2より
となります。
ここで、 は全順序なので、
か
が成り立ちます。
と仮定すれば、条件1より
となり、反対称律から
となり矛盾。
と仮定すれば、
より条件2から
となり、反対称律から
となり矛盾。
のとき、条件1より
となり、条件2より
となります。
あとは のときと同様にして矛盾が導けます。
したがって、条件1、2を満たすような の全順序は存在しません。
◇例2
集合 のべき集合
上に包含関係
によって順序を導入します。これは順序(半順序)ですが全順序ではありません。
・反射律
・推移律
・反対称律
を満たすことは簡単なので自分自身で確かめてみて下さい。
全順序律については、簡単な反例があります。
とすると、
となりますが、ここで、
と
は
かつ
です。
◇例3
集合 から
への関数全体の集合
を考えます。
には次のようにして順序が導入できます。
について、
これは順序(半順序)ですが全順序ではありません。
・反射律
・推移律
・反対称律
は、 において反射律、推移律、反対称律が成り立つことから、上の定義に立ち返って考えれば成り立つことがわかります。
一方で、全順序律については簡単な反例があります。
として、
で定義される関数
と、
で定義される関数
について、
かつ
です。
この記事へのコメントはありません。