同次関係

数学において、集合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$ の場合にのみ成立します。

例

プレートの集合における「隣接する」関係の行列表現
		Af	An	Ar	Au	Ca	Co	Eu	In	Ju	NA	Na	Pa	Ph	SA	Sc	So
アフリカ	Af
南極	An
アラビア	Ar
オーストラリア	Au
カリブ海	Ca
ココナッツ	Co
ユーラシア	Eu
インディアン	In
ファン・デ・フカ	Ju
北アメリカ	NA
ナスカ	Na
太平洋	Pa
フィリピン	Ph
南アメリカ	SA
スコットランド	Sc
ソマリア	つまり

地球の地殻を構成する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]厳密な全順序は、厳密な線型順序、厳密な単純順序、または厳密な連鎖とも呼ばれ、非反射的、反対称的、推移的、かつ連結的な関係です

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

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

同次二項関係の性質間の含意と矛盾
同次二項関係の性質（黄色）間の含意（青）と矛盾（赤）。例えば、すべての非対称関係は非反射的（「ASym ⇒ Irrefl」）であり、空でない集合上の関係は非反射的と反射的の両方になることはできません（「Irrefl # Refl」）。赤い辺を省略するとハッセ図になります。

演算

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）。

異なるタイプのn元二項関係の数
元	任意	推移的	反射的	対称的	先順序	半順序	全先行順序	全順序	同値関係
0	1	1	1	1	1	1	1	1	1
1	2	2	1	2	1	1	1	1	1
2	16	13	4	8	4	3	3	2	2
3	512	171	64	64	29	19	13	6	5
4	65,536	3,994	4,096	1,024	355	219	75	24	15
n	2 ^{n ²}		2 ^{n ( n −1)}	2 ^{n ( n +1)/2}			∑ⁿ _{k =0} k ! S ( n , k )	n !	∑ⁿ _{k =0} S ( n , k )
OEIS	A002416	A006905	A053763	A006125	A000798	A001035	A000670	A000142	A000110

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。

[Winter2007-1] Michael Winter (2007). Goguen Categories: A Categorical Approach to L-fuzzy Relations. Springer. pp. x–xi. ISBN 978-1-4020-6164-6.

[Müller2012-2] M. E. Müller (2012). Relational Knowledge Discovery. Cambridge University Press. p. 22. ISBN 978-0-521-19021-3.

[PahlDamrath2001-p496-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.

[4] 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.

[5] 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.

[6] 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.

[7] 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.

[8] Smith, Douglas; Eggen, Maurice; St. Andre, Richard (2006). A Transition to Advanced Mathematics (6th ed.). Brooks/Cole. p. 160. ISBN 0-534-39900-2.

[9] Nievergelt, Yves (2002). Foundations of Logic and Mathematics: Applications to Computer Science and Cryptography. Springer. p. 158..

[10] 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".

[11] Since neither 5 divides 3, nor 3 divides 5, nor 3=5.

[12] 「Well-foundednessの条件」ProofWiki。2019年2月20日時点のオリジナルからのアーカイブ。2019年2月20日閲覧。

[13] Fraisse, R. (2000年12月15日). Theory of Relations. Vol. 145 (第1版). Elsevier. p. 46. ISBN 9780444505422. 2019年2月20日閲覧。

[14] Schmidt, Gunther; Strohlein, Thomas (2012) [初版1993]. Relations and Graphs: Discrete Mathematics for Computer Scientists. Berlin, Heidelberg: Springer. p. 54.

[15] Rosenstein, Joseph G. (1982). Linear orderings . Academic Press. p. 4. ISBN 0-12-597680-1。

[16] 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。