同次関係

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

例

プレート集合上の「隣接している」関係の行列表現
		アフ	アン	アル	オー	カルシウム	共同	欧州連合	で	ジュ	該当なし	ナ	パ	電話番号	南アフリカ	Sc	それで
アフリカ	アフ
南極	アン
アラビア	アル
オーストラリア人	オー
カリブ海	カルシウム
ココス	共同
ユーラシア	欧州連合
インド人	で
フアン・デ・フカ	ジュ
北米	該当なし
ナスカ	ナ
パシフィック	パ
フィリピン	電話番号
南米	南アフリカ
スコシア	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 \in X$ に対して、 $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つの選択肢は網羅的ではありません。例えば、関係 $xRy$ if ( $y = 0$ or $y = x +1$ ) はこれらの性質をどれも満たしません。一方、空の関係はこれらの性質をすべて自明に満たします。

密集: $任意のx, y \in Xであって$ $xRy$ となるものに対して、 $xRz$ かつ $zRy$ となるような $z \in X$ が存在する。これは稠密順序において用いられる。
接続: $すべての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\inX と$ すべての $y$ $、 z\inY に対して$ 、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	2n2		2 ^{n ( n −1)}	2 ^{n ( n +1)/2}			∑ⁿ _{k =0} k ! S ( n , k )	ん！	∑ⁿ _{k =0} S ( n , k )
OEIS	A002416	A006905	A053763	A006125	A000798	A001035	A000670	A000142	A000110

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

注:

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

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

例

厳密な順序を含む順序関係:
- より大きい
- より大きいか等しい
- 未満
- 以下
- 均等に割る
- サブセット
同値関係：
- 平等
- と平行（アフィン空間の場合）
- 同数性または「単射である」
- 同型
- 等分線分
許容関係、反射的かつ対称的な関係：
- 依存関係、有限許容関係
- 独立関係、依存関係の補完
親族関係

一般化

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

参考文献

^ Michael Winter (2007). Goguen Categories: A Categorical Approach to L-fuzzy Relations . Springer. pp. x– xi. ISBN 978-1-4020-6164-6。
^ ME Müller (2012).リレーショナル・ナレッジ・ディスカバリー. ケンブリッジ大学出版局. p. 22. ISBN 978-0-521-19021-3。
^ Peter J. Pahl; Rudolf Damrath (2001). 『計算工学の数学的基礎：ハンドブック』 Springer Science & Business Media. p. 496. ISBN 978-3-540-67995-0。
^ モルデソン, ジョン・N.; ネア, プレムチャンド・S. (2012年11月8日). ファジー数学：エンジニアと科学者のための入門. Physica. p. 2. ISBN 978-3-7908-1808-6。
^ Tanaev, V.; Gordon, W.; Shafransky, Yakov M. (2012年12月6日). スケジューリング理論. シングルステージシステム. Springer Science & Business Media. p. 41. ISBN 978-94-011-1190-4。
^ マイヤー、ベルトラン（2009年6月29日）『Touch of Class：オブジェクトとコントラクトを使ったプログラミング学習』Springer Science & Business Media、509ページ。ISBN 978-3-540-92145-5。
^ フォンセカ・デ・オリベイラ、JN & ペレイラ・クーニャ・ロドリゲス、CDJ (2004)。リレーションの転置：Maybe 関数からハッシュテーブルまで。プログラム構築の数学、第 7 回国際会議。スターリング、スコットランド。 p. 337.
^ スミス、ダグラス、エッゲン、リチャード・セント・アンドレ (2006). 『上級数学への移行』（第6版）ブルックス/コール社. p. 160. ISBN 0-534-39900-2。
^ Nievergelt, Yves (2002). 『論理と数学の基礎：コンピュータサイエンスと暗号への応用』 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. 2013年11月2日時点のオリジナル(PDF)からのアーカイブ。補題1.1 (iv)。この文献では、非対称な関係を「厳密に反対称的な」関係と呼んでいます。
^ 5 は 3 を割り切れず、3 は 5 を割り切れず、3=5 でもありません。
^ “Well-Foundednessの条件”. ProofWiki . 2019年2月20日時点のオリジナルよりアーカイブ。2019年2月20日閲覧。
^ フレイス、R.（2000年12月15日）関係理論第145巻（第1版）エルゼビアp.46. ISBN 9780444505422. 2019年2月20日閲覧。
^ Schmidt, Gunther; Strohlein, Thomas (2012) [初版1993年]. Relations and Graphs: Discrete Mathematics for Computer Scientists. ベルリン、ハイデルベルク: Springer. p. 54.
^ Rosenstein, Joseph G. (1982).線形順序付け. Academic Press. p. 4. ISBN 0-12-597680-1。
^ シュミット、グンター、シュトレーライン、トーマス (1993). 「同次関係」 . 『関係とグラフ：コンピュータ科学者のための離散数学』 . ベルリン、ハイデルベルク: シュプリンガー. 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] ME Müller (2012).リレーショナル・ナレッジ・ディスカバリー. ケンブリッジ大学出版局. p. 22. ISBN 978-0-521-19021-3。

[PahlDamrath2001-p496-3] Peter J. Pahl; Rudolf Damrath (2001). 『計算工学の数学的基礎：ハンドブック』 Springer Science & Business Media. p. 496. ISBN 978-3-540-67995-0。

[4] モルデソン, ジョン・N.; ネア, プレムチャンド・S. (2012年11月8日). ファジー数学：エンジニアと科学者のための入門. Physica. p. 2. ISBN 978-3-7908-1808-6。

[5] Tanaev, V.; Gordon, W.; Shafransky, Yakov M. (2012年12月6日). スケジューリング理論. シングルステージシステム. Springer Science & Business Media. p. 41. ISBN 978-94-011-1190-4。

[6] マイヤー、ベルトラン（2009年6月29日）『Touch of Class：オブジェクトとコントラクトを使ったプログラミング学習』Springer Science & Business Media、509ページ。ISBN 978-3-540-92145-5。

[7] フォンセカ・デ・オリベイラ、JN & ペレイラ・クーニャ・ロドリゲス、CDJ (2004)。リレーションの転置：Maybe 関数からハッシュテーブルまで。プログラム構築の数学、第 7 回国際会議。スターリング、スコットランド。 p. 337.

[8] スミス、ダグラス、エッゲン、リチャード・セント・アンドレ (2006). 『上級数学への移行』（第6版）ブルックス/コール社. p. 160. ISBN 0-534-39900-2。

[9] Nievergelt, Yves (2002). 『論理と数学の基礎：コンピュータサイエンスと暗号への応用』 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. 2013年11月2日時点のオリジナル(PDF)からのアーカイブ。補題1.1 (iv)。この文献では、非対称な関係を「厳密に反対称的な」関係と呼んでいます。

[11] 5 は 3 を割り切れず、3 は 5 を割り切れず、3=5 でもありません。

[12] “Well-Foundednessの条件”. ProofWiki . 2019年2月20日時点のオリジナルよりアーカイブ。2019年2月20日閲覧。

[13] フレイス、R.（2000年12月15日）関係理論第145巻（第1版）エルゼビアp.46. ISBN 9780444505422. 2019年2月20日閲覧。

[14] Schmidt, Gunther; Strohlein, Thomas (2012) [初版1993年]. Relations and Graphs: Discrete Mathematics for Computer Scientists. ベルリン、ハイデルベルク: Springer. p. 54.

[15] Rosenstein, Joseph G. (1982).線形順序付け. Academic Press. p. 4. ISBN 0-12-597680-1。

[16] シュミット、グンター、シュトレーライン、トーマス (1993). 「同次関係」 . 『関係とグラフ：コンピュータ科学者のための離散数学』 . ベルリン、ハイデルベルク: シュプリンガー. p. 14. doi :10.1007/978-3-642-77968-8_2. ISBN 978-3-642-77968-8。