同質関係

数学において、集合X上の同次関係（同次関係とも呼ばれる）は、Xとそれ自身との間の二項関係、すなわち直積X × Xのサブセットである。^{[1] [2] [3]これは一般に「} X上の関係」^{[4]または「} X上の（二項）関係」と表現される。^{[5] [6]}同次関係の例としては、人と人との間の親族関係がある。

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

集合X (任意の要素x ₁、x ₂ ) 上の特定の同次関係は次のとおりです。

• 空の関係

  E = ∅、
  つまりx ₁ Ex ₂は決して成り立たない。

• 普遍的な関係

  U = X × X、
  つまりx ₁ Ux ₂が常に成り立ちます。

• 恒等関係（恒等関数も参照）

  I = {( x , x ) | x ∈ X };
  つまり、 x ₁ = x ₂の場合にのみ、 x ₁ Ix ₂が成立します。

地球の地殻の15 個の大きな構造プレートは、均質な関係で互いに接触しています。この関係は、接触を示す 1 と接触していないことを示す 0 の論理マトリックスとして表すことができます。この例は対称的な関係を表しています。

集合X上の同次関係Rが持つ可能性のある重要な特性には次のものがあります。

反射的

すべてのx ∈ Xに対してxRx が成り立ちます。たとえば、 ≥ は反射関係ですが、 > はそうではありません。

非反射的（または厳密）

すべてのx ∈ Xに対して、xRxではありません。たとえば、 > は非反射的な関係ですが、 ≥ はそうではありません。

コアリフレクシブ

すべてのx、y ∈ Xに対して、xRyならばx = y。^[7]たとえば、各奇数が自分自身と関係している整数上の関係は、コア反射関係です。等式関係は反射的かつコア反射的な関係の両方の例であり、コア反射的な関係はすべて恒等関係のサブセットです。

左準反射

すべてのx、y ∈ Xに対して、xRyならばxRxです。

右準再帰

すべてのx、y ∈ Xに対して、xRyならばyRy。

準反射的

すべてのx、y ∈ Xについて、xRyならばxRxかつyRy。関係が準反射的となるのは、左と右の両方が準反射的である場合のみです。

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

対称的

すべてのx、y ∈ Xについて、xRyならばyRx。たとえば、「は〜の血縁者である」は対称関係です。なぜなら、x がyの血縁者であるためには、 yがxの血縁者である必要があるからです。

反対称

すべてのx、y ∈ Xに対して、xRyかつyRxならばx = y。たとえば、 ≥ は反対称関係であり、 > も同様だが、意味をなさない（定義内の条件は常に偽である）。^[8]

非対称

すべてのx、y ∈ Xに対して、xRyならばyRxではない。関係が非対称となるのは、反対称かつ非反射的な場合のみである。^[9]たとえば、 > は非対称関係だが、 ≥ はそうではない。

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

推移的

すべてのx、y、z ∈ Xに対して、xRyかつyRzならばxRz。推移関係は、非対称である場合にのみ非反射的である。^{[10]たとえば、「} 〜の祖先である」は推移関係であるが、「〜の親である」は推移関係ではない。

反推移的

すべてのx、y、z ∈ Xについて、xRyかつyRzならばxRz は成り立ちません。

共推移的

Rの補集合が推移的である場合。つまり、すべてのx、y、z ∈ Xに対して、xRzであればxRyまたはyRz である。これは構成的数学の擬似順序で使用されます。

準推移的

すべてのx、y、z ∈ Xについて、xRyかつyRzであるがyRxとzRy のいずれでもない場合は、xRzであるがzRxではない。

比較不可能性の推移性

すべてのx、y、z ∈ Xについて、xとy がRに関して比較不可能であり、同じことがyとzについても当てはまる場合、xとz もRに関して比較不可能です。これは弱い順序付けで使用されます。

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

密集

すべてのx、y ∈ XであってxRyであるものに対して、あるz ∈ X であってxRzかつzRyであるものが存在する。これは稠密な順序で使われる。

接続

すべてのx、y ∈ Xに対して、x ≠ yであればxRyまたはyRx。この特性は「合計」と呼ばれることもあります^{[引用が必要]。}これは、以下に示す「左合計/右合計」の定義とは異なります。

強く結びついた

すべてのx、y ∈ X、xRy、yRxに対して。この特性も「合計」と呼ばれることがあります^[要出典]。これは、以下に示す「左合計/右合計」の定義とは異なります。

三分法

すべてのx、y∈Xに対して、 xRy、yRx、x = yのいずれか1つが成り立つ。例えば、>は実数上の三分関係であるが、自然数上の「割り切る」関係はそうではない。[ 11 ^]

右ユークリッド（または単にユークリッド）

すべてのx、y、z ∈ Xについて、xRyかつxRzならばyRz。たとえば、x = yかつx = zならばy = zであるため、 = はユークリッド関係です。

左ユークリッド

すべてのx、y、z ∈ Xについて、yRxかつzRxならばyRzです。

根拠がしっかりしている

Xの空でない部分集合S はすべてRに関して極小元を含む。整根拠性は降順連鎖条件（つまり、無限連鎖 ... x _n R ... Rx ₃ Rx ₂ Rx _{1 は}存在し得ない）を意味する。従属選択公理を仮定すると、両方の条件は同値である。^{[12] [13]}

さらに、一般的な二項関係のすべての特性は同次関係にも当てはまる可能性があります。

セットのような

すべてのx ∈ Xに対して、yRxが集合となるようなすべてのyのクラス。(これは、適切なクラス上の関係が許される場合にのみ意味を持ちます。)

左ユニーク

すべてのx、z ∈ Xおよびすべてのy ∈ Yに対して、xRyおよびzRyであればx = zです。

単価

全てのx∈Xと全てのy、z∈Yに対して、 xRyかつxRzならばy = zとなる。 [ 14 ^]

合計（左合計とも呼ばれる）

すべてのx ∈ Xに対して、xRyとなるy ∈ Y が存在する。この性質は連結の定義（一部の著者は全連結とも呼ぶ）とは異なる。^[要出典]

全射（右全とも呼ばれる）

すべてのy ∈ Yに対して、 xRyとなるx ∈ Xが存在する。

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

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

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

R が集合X上の同次関係である場合、次の各式はX上の同次関係です。

反射的閉鎖、 R ⁼

R ⁼ = {( x , x ) | x ∈ X } ∪ 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上の同次関係全体の集合は2X ^{× X}であり、これは関係をその逆関係に写像する反転を加えたブール代数である。関係の合成を上の^二項演算と考えると、反転を持つモノイドが形成され、単位元は恒等関係となる。^[16]${\displaystyle {\mathcal {B}}(X)}$${\displaystyle {\mathcal {B}}(X)}$

n要素の集合上の異なる同次関係の数は2 ^{n 2}である（OEISのシーケンスA002416）。

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項関係とも呼ばれます。