同次関係

数学において、集合X上の同次関係（自己内関係とも呼ばれる）は、 Xとそれ自身との間の二項関係、すなわち直積X $\times$ $X$ $の$ 部分集合です。^[1]^[2]^{[3]これは一般的に「}X上の関係」^{[4]または「}X上の（二項）関係」 ^[5 ] と表現されます。^[6]同次関係の例としては、人と人との間の血縁関係が挙げられます

自己相関の一般的な種類には、順序、グラフ、同値などがあります。順序理論とグラフ理論の専門的な研究により、自己相関の理解が深まりました。説明にはグラフ理論特有の用語が使用され、通常の（無向）グラフは対称関係に対応し、一般的な自己相関は有向グラフに対応すると想定されます。自己相関Rは0と1の論理行列に対応し、式xRy（xはyとR関連）はグラフ内のxとyの間の辺、およびRの正方行列内の1に対応します。グラフ用語では隣接行列と呼ばれます

特殊同次関係

集合X（任意の要素 $x 1$ 、 $x 2$ ）上の特殊同次関係には、以下のものがあります。

空関係: $E = \emptyset$ 。
つまり、 $x 1 Ex 2$ は決して成立しません。
普遍関係: $U = X \times X$ 。
つまり、 $x 1 Ux 2$ は常に成立します。
恒等関係（恒等関数も参照）: $I = {(x, x) | x \in X$ } 。
つまり、 $x 1 Ix 2 は、$ $x 1 = x 2$ の場合にのみ成立します。

例

地球の地殻を構成する16の大きなプレートは、互いに同質的な関係で接触しています。この関係は、1（「」で示される）が接触を示し、0（「」）が接触していないこと

プロパティ

集合 $X$ 上の同次関係 $R$ が持ち得る重要な性質には、次のようなものがあります。

反射的: $すべてのx \in X$ 、 $xRx$ に対して。例えば、≥ は反射関係ですが、> は反射関係ではありません。
非反射的（または厳密）: $すべてのx \in X$ 、 $xRx$ に対して。例えば、> は非反射関係ですが、≥ は反射関係ではありません。
コア反射的: $すべてのx 、 y \in X$ について、 $xRy$ ならば $x = y$ 。^[7]例えば、各奇数が自身と関係する整数上の関係は、共反射関係です。等式関係は、反射的かつ共反射的な関係の唯一の例であり、任意の共反射関係は恒等関係の部分集合です。
左準反射: $すべてのx 、 y \in X$ について、 $xRy$ ならば $xRx$ 。
右準反射: $すべてのx 、 y \in X$ について、 $xRy$ ならば $yRy$ 。
準反射: $すべてのx 、 y \in X$ について、 $xRy$ ならば $xRx$ かつ $yRy$ 。関係が準反射的である場合、そしてその場合に限り、それは左準反射的であり、右準反射的でもあります

前の6つの選択肢は、網羅的とは程遠いものです。例えば、 $y$ $=$ $x$ $2$ で定義される二項関係 $xRy$ $は、 (0, 0)$ と $(2, 4)$ のペアを含み、 $(2, 2) を$ 含まないため、非反射的でも、コア反射的でも、反射的でもありません。後者の2つの事実は、（あらゆる種類の）準反射性も排除します。

対称的: $すべてのx 、 y \in X$ について、 $xRy$ ならば $yRx$ です。例えば、「は～の血縁者である」は対称関係です。なぜなら、 $x が$ $y$ の血縁者である必要かつ限り、 $y が$ $x$ の血縁者であるからです。
反対称的: $すべてのx 、 y \in X$ について、 $xRy$ かつ $yRx$ ならば $x = y$ です。例えば、≥ は反対称関係です。> も同様ですが、空虚です（定義の条件は常に偽です）。^[8]
非対称: $すべてのx 、 y \in X$ について、 $xRyならば$ $yRx$ ではない。関係が非対称的であるのは、反対称かつ非反射的である場合に限ります。^[9]例えば、 > は非対称関係ですが、 ≥ はそうではありません。

繰り返しますが、前の3つの選択肢は網羅的ではありません。自然数上の例として、 $x$ $> 2$ で定義される関係 $xRy は$ 、対称でも反対称でもなく、ましてや非対称ではありません。

推移的: すべての $x 、 y 、 z \in X$ について、 $xRy$ かつ $yRz$ ならば $xRz で$ ある。推移的関係が非反射的であるのは、非対称的である場合に限ります。^[10]例えば、「～の祖先である」は推移的関係ですが、「～の親である」は推移的関係ではありません。
反推移: $すべてのx 、 y 、 z \in X$ について、 $xRy$ かつ $yRzならば、$ $xRz$ ではない。
共推移的: Rの補集合が推移的である場合。つまり、すべての $x 、 y 、 z\inX$ について、xRzならば $xRy$ または $yRz$ で $ある$ $。$ $これは構成的数学における$ 擬似順序で用いられる。
準推移的: $すべてのx 、 y 、 z \in X$ について、 $xRy$ と $yRz$ であるが $yRx$ と $zRy$ のどちらもない場合、 $xRz であるが$ $zRx$ ではない。
比較不可能性の推移性: すべての $x 、 y 、 z \in X$ について、 $x$ と $y が$ $R$ に関して比較不可能であり、 $y$ と $z$ についても同じことが当てはまる場合、 $x$ と $zも$ $R$ に関して比較不可能である。これは弱い順序付けで用いられる。

繰り返しますが、前の5つの選択肢は網羅的ではありません。例えば、 ( $y$ $= 0$ または $y$ $=$ $x$ $+1$ ) の場合の関係 $xRy$ は、これらの性質のいずれも満たしません。一方、空の関係は、これらすべてを自明に満たします。

稠密: $任意のx, y \in Xであって$ $xRy$ となるものに対して、何らかの $z \in X$ であって $xRz$ かつ $zRy$ となるものが存在する。これは稠密順序で用いられる。
連結: $すべてのx 、 y \in X$ に対して、 $x \neq y$ ならば $xRy$ または $yRx が$ 成り立ちます。この性質は^[要出典]「全体」と呼ばれることもあり、これは以下に示す「左／右全体」の定義とは異なります。
強連結: すべての $x 、 y \in X$ 、 $xRy$ 、または $yRx$ に対して。この性質も^[要出典]「全体」と呼ばれることもあり、これは以下に示す「左／右全体」の定義とは異なります。
三分関係: $すべてのx, y \in X$ に対して、 $xRy$ 、 $yRx$ 、または $x = y$ のいずれか1つが成立する。例えば、 > は実数上の三分関係であるが、自然数上の「割り切る」関係はそうではない。^[11]
右ユークリッド（または単にユークリッド）: $すべてのx 、 y 、 z \in X$ に対して、 $xRy$ かつ $xRz$ ならば $yRz$ 。例えば、 = はユークリッド関係です。なぜなら、 $x = y$ かつ $x = z$ ならば $y = z$ だからです。
左ユークリッド: $すべてのx 、 y 、 z \in X$ に対して、 $yRx$ かつ $zRx$ ならば $yRz$ 。
整根拠: $X$ のすべての空でない部分集合 $S は、$ $R$ に関して極小元を含みます。整根拠は、降順連鎖条件（つまり、無限連鎖 $...$ $x$ $n$ $R$ $...$ $Rx$ $3$ $Rx$ $2$ $Rx$ $1$ は存在し得ない）を意味します。従属選択公理が仮定される場合、両方の条件は同値です。^[12]^[13]

さらに、一般に二項関係のすべての特性は、同次関係にも適用できます。

集合のような: $すべてのx \in X$ に対して、 $yRx$ が集合となるようなすべての $y$ のクラス。（これは、真クラス上の関係が許される場合にのみ意味をなす。）
左一意: すべての $x 、 z \in X$ 、およびすべての $y \in Y$ に対して、 $xRy$ および $zRy$ ならば $x = z$ 。
単価: すべての $x \in X$ 、およびすべての $y 、 z \in Y$ に対して、 $xRy$ および $xRz$ ならば $y = z$ 。^[14]
全集合（左完全とも呼ばれる）: $すべてのx \in X$ に対して、 $xRy$ となるような $y \in Y$ が存在する。この性質は連結集合（一部の著者は全集合とも呼ぶ）の定義とは異なる。^[^要出典^]
全射（右完全とも呼ばれる）: $すべてのy \in Y$ に対して、 xRyとなる $x \in X$ が存在する。

前順序は、反射的かつ推移的な関係です。全前順序は、線型前順序または弱い順序とも呼ばれ、反射的、推移的、かつ連結的な関係です。

半順序は、順序とも呼ばれ、^[要出典]反射的、反対称的、かつ推移的な関係です。厳密な半順序は、厳密な順序とも呼ばれ、^[要出典]非反射的、反対称的、かつ推移的な関係です。全順序は、線型順序、単純順序、または連鎖とも呼ばれ、反射的、反対称的、推移的、かつ連結的な関係です。^[15]厳密な全順序は、厳密な線型順序、厳密な単純順序、または厳密な連鎖とも呼ばれ、非反射的、反対称的、推移的、かつ連結的な関係です

部分同値関係は、対称かつ推移的な関係です。同値関係は、反射的、対称的、推移的な関係です。また、これらの特性は反射性を意味するため、対称的、推移的、かつ全的な関係でもあります。

一価関係は部分関数とも呼ばれます。（全）関数は左全関数です。単価関数（または部分関数）は逆関数が一価関数です。全射関数は右全関数です。

演算

Rが集合X上の同次関係である場合、以下のそれぞれはX上の同次関係です。

反射閉包、 R ⁼: $R = = {(x, x) | x \in X} \cup R$ 、またはRを含むX上の最小の反射関係として定義されます。これは、 Rを含むすべての反射関係の積と等しいことが証明できます。
反射的縮約、R ^≠: $R ≠ = R \ {( x , x ) | x ∈ X$ } 、またはRに含まれるX上の最大の非反射関係として定義されます。
推移閉包、 R ⁺: Rを含むX上の最小の推移関係として定義されます。これは、 Rを含むすべての推移関係の積と等しいことが分かります。
反射的推移閉包、R *: $R * = (R +) =$ 、 Rを含む最小の順序として定義されます。
反射的推移対称閉包、 R ^≡: Rを含むX上の最小の同値関係として定義されます。

二項関係§演算で定義されているすべての演算は、同次関係にも適用されます

列挙

集合X上のすべての同次関係の集合は $2$ $X$ $\times$ $X$ であり、これは関係からその逆関係への写像の反転が拡張されたブール代数である。関係の合成を上の二項演算と考えると、反転を持つモノイドが形成され、単位元は単位関係となる。^[16] ${\mathcal {B}}(X)$ ${\mathcal {B}}(X)$

n元集合上の異なる同次関係の数は $2 n 2$ である（OEISのシーケンスA002416）。

S ( n , k )は第二種スターリング数を指すことに注意してください。

注：

非反射関係の数は反射関係の数と同じです。
厳密な半順序（非反射推移関係）の数は半順序の数と同じです。
厳密な弱順序の数は全前順序の数と同じです
全順序は、全事前順序でもある部分順序です。したがって、部分順序でも全事前順序でもない事前順序の数は、事前順序の数から部分順序の数を引いて、全事前順序の数を引いて、全順序の数を加えたもので、それぞれ0、0、0、3、85です。
同値関係の数は分割数であり、ベル数です

同次関係は、 $n$ $= 0の場合、関係が自身の補関係であることを除き、ペア（関係、$ 補関係）にグループ化できます。非対称関係は、4つ組（関係、補関係、逆関係、逆補関係）にグループ化できます。

例

順序関係（厳密な順序を含む）
- より大きい
- 以上
- より小さい
- 以下
- 割り切る（均等に）
- 〜の部分集合
同値関係
- 等価性
- と平行（アフィン空間の場合）
- 同数性または「〜と一対一である」
- 同型
- 同形線分
許容関係（反射的かつ対称的な関係）
- 依存関係（有限許容関係）
- 独立関係（ある依存関係の補関係）
親族関係

一般化

一般に二項関係は同次である必要はなく、任意の集合XとYに対して部分集合R⊆X×Yとして定義されます。
有限関係は、ある自然_数nと_任意の集合X1、…、Xnに対して部分集合R⊆X1 ×_… × _Xnであり、n項関係_とも呼ばれます。

参考文献

^ Michael Winter (2007). Goguen Categories: A Categorical Approach to L-fuzzy Relations. Springer. pp. x–xi. ISBN 978-1-4020-6164-6.
^ M. E. Müller (2012). Relational Knowledge Discovery. Cambridge University Press. p. 22. ISBN 978-0-521-19021-3.
^ Peter J. Pahl; Rudolf Damrath (2001). Mathematical Foundations of Computational Engineering: A Handbook. Springer Science & Business Media. p. 496. ISBN 978-3-540-67995-0.
^ Mordeson, John N.; Nair, Premchand S. (8 November 2012). Fuzzy Mathematics: An Introduction for Engineers and Scientists. Physica. p. 2. ISBN 978-3-7908-1808-6.
^ Tanaev, V.; Gordon, W.; Shafransky, Yakov M. (6 December 2012). Scheduling Theory. Single-Stage Systems. Springer Science & Business Media. p. 41. ISBN 978-94-011-1190-4.
^ Meyer, Bertrand (29 June 2009). Touch of Class: Learning to Program Well with Objects and Contracts. Springer Science & Business Media. p. 509. ISBN 978-3-540-92145-5.
^ Fonseca de Oliveira, J. N. & Pereira Cunha Rodrigues, C. D. J. (2004). Transposing Relations: From Maybe Functions to Hash Tables. Mathematics of Program Construction, 7th International Conference. Stirling, Scotland. p. 337.
^ Smith, Douglas; Eggen, Maurice; St. Andre, Richard (2006). A Transition to Advanced Mathematics (6th ed.). Brooks/Cole. p. 160. ISBN 0-534-39900-2.
^ Nievergelt, Yves (2002). Foundations of Logic and Mathematics: Applications to Computer Science and Cryptography. Springer. p. 158..
^ Flaška, V.; Ježek, J.; Kepka, T.; Kortelainen, J. (2007). Transitive Closures of Binary Relations I (PDF). Prague: School of Mathematics – Physics Charles University. p. 1. Archived from the original (PDF) on 2013-11-02. Lemma 1.1 (iv). This source refers to asymmetric relations as "strictly antisymmetric".
^ Since neither 5 divides 3, nor 3 divides 5, nor 3=5.
^ 「Well-foundednessの条件」ProofWiki。2019年2月20日時点のオリジナルからのアーカイブ。2019年2月20日閲覧。
^ Fraisse, R. (2000年12月15日). Theory of Relations. Vol. 145 (第1版). Elsevier. p. 46. ISBN 9780444505422. 2019年2月20日閲覧。
^ Schmidt, Gunther; Strohlein, Thomas (2012) [初版1993]. Relations and Graphs: Discrete Mathematics for Computer Scientists. Berlin, Heidelberg: Springer. p. 54.
^ Rosenstein, Joseph G. (1982). Linear orderings . Academic Press. p. 4. ISBN 0-12-597680-1。
^ Schmidt, Gunther; Ströhlein, Thomas (1993). "Homogeneous Relations" . Relations and Graphs: Discrete Mathematics for Computer Scientists . Berlin, Heidelberg: Springer. p. 14. doi :10.1007/978-3-642-77968-8_2. ISBN 978-3-642-77968-8。