Animated Logo

半順序集合

目次

関係とは

半順序集合

同値関係

写像のグラフ

テストの前に

TEST

 関係にもいろいろな性質があります。関係 R と集合 X について

 (∀x)(x ∈ X imp (x,x) ∈ R)  (ここで (x,x) は対である) 

がいえるとき、関係 R は集合 X で反射的である(reflexive)といいます。

 一般に (x,y) ∈ R のとき、 x 〜R y というような書き方をすることがあります。

 この書き方をすると、R が X で反射的とは X の任意の要素 x について

  x 〜R x

が成立するときである、といえます。

 同様に

  (∀x)(∀y)(x ∈ X and y ∈ X and (x,y) ∈ R imp (y,x) ∈ R)

がいえるとき、関係 R は集合 X で対称的である(symmetric)といいます。対称的であることの条件はX の任意の要素 x,y について

   x 〜R y imp y 〜R x

とも書けます。

 また

  (∀x)(∀y)(∀z)(x ∈ X and y ∈ X and z ∈ X and (x,y) ∈ R and (y,z) ∈ R imp (x,z) ∈ R)

がいえるとき、関係 R は集合 X で推移的である(transitive)といいます。推移的であることの条件はX の任意の要素 x,y,z について

   x 〜R y and y 〜R z imp x 〜R z

とも書けます。

 また次のような条件もあります。

 (∀x)(∀y)(x ∈ X and y ∈ X and (x,y) ∈ R and (y,x) ∈ R imp x = y)

がいえるとき、関係 R は集合 X で反対称的である(antisymmetric)といいます。反対称的であることの条件はX の任意の要素 x,y について

   x 〜R y and y 〜R x imp x=y

とも書けます。

 例1 X = R1, R = {(x,y): x ≦ y} のとき、関係 R は反射的、推移的 かつ  反対称的である。 しかし 対称的ではない。

 例2 X = R1, R = {(x,y): x < y} のとき、関係 R は推移的 かつ  反対称的である。 しかし 反射的ではない。また対称的ではない。

 例3 X = R1, R = {(x,y): x = y} のとき、関係 R は反射的、推移的、対称的 かつ反対称的である。

 例4 X = R1, R = {(x,y): x - y または y - x が 5 で割り切れる} のとき、関係 R は反射的、推移的 かつ 対称的であるが、反対称的ではない。

 関係 R が X で反射的、反対称的、推移的であるとき、半順序(partially order)といいます。上の例1の ≦ と例2の = は半順序になっています。

 集合 X の方に注目して 半順序 R をもっている X を半順序集合(partially ordered set, 略して POSET )といいます。正確には対 (X,R) を半順序集合といいます。

 例5 U を集合とします。X を U の部分集合の全体( X = bool U と書きます)とし、 R = {(D,E): D ⊆ E } とする。すると R は半順序で、X または (X,R) は半順序集合になる。

上の関係 R は集合の包含関係 (relation of set inclusion) といいます。