集合上の関係

ウィキペディア小見出し辞書

集合上の関係

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/08/02 03:27 UTC 版)

「二項関係」の記事における「集合上の関係」の解説

X = Y で二項関係の始集合 X と終集合 Y とが一致しているならば、簡単に X 上の二項関係（あるいはもう少し明示的に X 上の自己関係 (endorelation)）と呼ぶ。自己関係のいくつかのクラスについては有向グラフとしてグラフ理論において広く調べられている。 集合 X 上の二項関係全体の成す集合 B(X) は、関係をその逆関係へ写す対合を備えた対合付き半群を成す。 集合 X 上の二項関係のいくつか重要なクラスとして、以下のようなものを挙げることができる： 反射的 (reflexive) X の各元 x について x R x が満たされる関係 R は反射的であるという。 例えば「大なりイコール」"≥" は反射関係だが、「大なり」">" は反射的ではない。 非反射的 (irreflexive) あるいは狭義 (strict) X のどの元 x についても x R x が満たされることが無いとき、R は非反射的あるいは無反射的な関係であるという。 「大なり」">" は非反射的関係の例である。 余反射的 (coreflexive) X の各元 x, y について、x R y ならば x = y が成り立つとき、R は余反射的であるという。 「等しくて奇数である」という関係は余反射関係の例を与える。 対称的 (symmetric) X の各元 x, y について、x R y ならば y R x となるような関係は対称であるという。 「血縁である」という関係は対称関係である。実際、x が y の血縁であるための必要十分条件は y が x の血縁であることである。 反対称的 (antisymmetric) X の各元 x, y について、x R y かつ y R x ならば x = y となるならば、関係 R は反対称であるという。 「大なりイコール」"≥" は x ≥ y かつ y ≥ x ならば x = y ゆえ反対称関係の例を与える。 非対称 (asymmetric) X の各元 x, y について、x R y なるときは常に y R x が成立しないような関係 R は非対称であるという。 「大なり」">" は x > y ならば y > x は成立しないから非対称である。 推移的 (transitive) X の各元 x, y, z について、x R y かつ y R z ならば x R z となるとき、関係 R は推移的であるという。 「先祖である」という関係は推移的である。実際、x が y の先祖で、y が z の先祖ならば、x は z の先祖である。 完全性 (total) X の任意の二元 x, y について、x R y または y R x の一方あるいは両方が必ず満足されるとき、R は完全であるという。 全順序集合における「大なりイコール」"≥" は完全関係の例である。本節にいう total は前節の total とは意味が異なる。 三分的 (trichotomous) X の任意の元 x, y に対して、x R y, y R x, x = y のうちの何れか一つのみが成り立つとき、R は三分的（三分法的）であるという。 「大なり」">" は三分的関係の例である。 ユークリッド的 (Euclidean) X の任意の元 x, y, z について、x R y かつ x R z が成り立てば必ず y R z かつ z R y が成り立つような関係 R は右ユークリッド的であるという (通常、単に「ユークリッド的関係」とされていたら「右ユークリッド的関係」を指す)。 X の任意の元 x, y, z について、x R z かつ y R z が成り立てば必ず x R y かつ y R x が成り立つような関係 R は左ユークリッド的であるという。 恒等関係 "=" は x = y かつ x = z ならば y = z となるから(右)ユークリッド関係であり、また、勿論左ユークリッド関係でもある。 連続的 (serial) X の各元 x に対して、x R y となるような y ∈ X がそれぞれとれるとき、関係 R は連続的であるという。 「大なり」">" は整数全体の成す集合 Z 上の連続的関係だが、正の整数全体の成す集合 N 上の連続的関係ではない（1 > y となるような正の整数 y は存在しない）。一方で「小なり」"<" は N 上の（あるいは有理数全体の成す集合 Q または実数全体の成す集合 R 上の）連続的関係である。 集合的 (set-like) 集合 X の任意の元 x に対して、y R x となるような y 全体の成すクラスが集合であるような関係は、集合的（あるいは集合状、集合様）であるという。 （これは真のクラス上の関係を認める場合でないと意味を持たない） 順序数全体の成すクラス上の通常の順序関係 "<" は集合的関係だが、その逆順序 ">" は集合的ではない。 整礎的 (well-founded) X の任意の空でない部分集合Aが極小元a(Aのどの元xもxRaとならない)を持つときR は整礎的であるという。 自然数上の大小関係"≤"は整礎的である。正則性公理を仮定すると∈は任意の集合上で整礎的である。 外延的 (extensive) X の任意の元 x, y について、X の任意の元 z について zRx ⇔ zRy が成り立てば必ず x = y となるとき R は外延的であるという。 全順序は外延的である。∈は任意の集合上で外延的である。 反射的、対称的かつ推移的な関係は同値関係（あるいは等値関係）と呼ばれる。反射的、反対称的かつ推移的な関係は半順序である。半順序が完全ならば全順序、単純順序、線型順序あるいは鎖などと呼ばれる。整礎的な線型順序は整列順序と呼ばれる。ある関係が対称、推移的かつ連続的ならば必ず反射的である。