推移関係

数学において、集合X上の二項関係Rは、 Xのすべての要素a、b、cに対して、R がa とbおよびbとcを関連付ける場合、R がaとcも関連付ける場合に推移的である。

すべての半順序関係とすべての同値関係は推移的です。たとえば、実数間の「より小さい」と「等しい」はどちらも推移的です。a < bかつb < cならばa < cであり、x = yかつy = zならばx = zです。

集合X上の同次関係Rは、次の条件を満たす場合に推移的関係である。 ^{[ 1 ]}

すべてのa、b、c ∈ Xに対して、a R bかつb R cならば、a R c。

あるいは一階述語論理で言えば：

${\displaystyle \forall a,b,c\in X:(aRb\wedge bRc)\Rightarrow aRc}$、

ここで、a R bは( a , b ) ∈ Rの接中記法です。

数学以外の例を挙げると、「～の祖先である」という関係は推移的です。例えば、エイミーがベッキーの祖先であり、ベッキーがキャリーの祖先である場合、エイミーもキャリーの祖先です。

一方、「～の生みの母である」という関係は推移的ではありません。なぜなら、アリスがブレンダの生みの母であり、ブレンダがクレアの生みの母であるとしても、アリスがクレアの生みの母であるとは限らないからです。実際、この関係は反推移的です。つまり、アリスがクレアの生みの母になることは決してありません。

非推移的、非反推移的な関係には、スポーツの試合日程（プレーオフのスケジュール）、「知っている」、「話す」などが含まれる。

「より大きい」、「少なくとも～以上である」、「～と等しい」（等号）といった例は、様々な集合における推移関係です。実数の集合や自然数の集合も同様です。

x > yかつy > zの場合には、x > zも成り立つ。

x ≥ yかつy ≥ zの場合には、x ≥ zも成り立つ。

x = yかつy = zの場合には、x = zも成り立つ。

推移関係のその他の例：

• 「～の部分集合である」（集合の包含関係、集合上の関係）
• 「割り切れる」（自然数における可除性）
• 「含意する」（含意、命題間の関係を表す記号「⇒」で表される）

非推移的関係の例：

• 「 ～の後継者である」（自然数に関する関係）
• 「集合の要素である」（「∈」と表記される）^{[ 2 ]}
• 「 ～に垂直である」（ユークリッド幾何学における直線の関係）

任意の集合上の空のリレーション${\displaystyle X}$推移的である^{[ 3 ]}要素がないため${\displaystyle a,b,c\in X}$そのため${\displaystyle aRb}$そして${\displaystyle bRc}$したがって、推移性条件は自明に真である。順序対を1つだけ含む関係Rも推移的である。順序対が次の形式である場合。${\displaystyle (x,x)}$一部の人にとって${\displaystyle x\in X}$そのような要素は${\displaystyle a,b,c\in X}$は${\displaystyle a=b=c=x}$そして実際この場合${\displaystyle aRc}$、ただし、順序対が次の形式でない場合は${\displaystyle (x,x)}$そうすれば、そのような要素は存在しない${\displaystyle a,b,c\in X}$そしてそれゆえに${\displaystyle R}$空虚な推移性を持つ。

空虚な推移性とは、関係において ( a , b ) および ( b , c ) の形の順序対が存在しない場合の推移性のことである。

R を集合X上の二項関係とする。Rの推移的拡張R 1は、 R _{1 がR}を含み、( a , b ) ∈ Rかつ ( b , c ) ∈ R ならば( a , c ) ∈ R 1となるような、_X上の最小の二項関係である。^{[ 7 ]}例えば、Xが町の集合であり、そのうちのいくつかが道路で接続されていると仮定する。町Aと町Bを直接結ぶ道路がある場合に( A , B ) ∈ Rとなるような町上の関係をRとする。この関係は推移的である必要はない。この関係の推移的拡張は、町AとCの間を最大 2 つの道路を使って移動できる場合に( A , C ) ∈ R ₁となることで定義できる。

関係が推移的である場合、その推移的拡張はそれ自身である。つまり、Rが推移的関係である場合、 R ₁ = Rとなる。

R ₁の推移的拡張はR ₂で表され、このように続けると一般にR _iの推移的拡張はR _{i + 1}となります。Rの推移的閉包はR *またはR ^∞で表され、R、R ₁、R ₂ 、...の集合和です。^{[ 8 ]}

関係の推移閉包は推移関係である。^{[ 8 ]}

人々の集合における「～の生みの親である」という関係は推移的関係ではありません。しかし、生物学では、任意の世代にわたる生みの親関係を考慮する必要が生じることがよくあります。「～の出生の祖先である」という関係は推移的関係であり、「～の生みの親である」という関係の推移閉包です。

上記の町と道路の例では、( A、C ) ∈ R *は、任意の数の道路を使用して町AとCの間を移動できることを意味します。

• 先行順序–反射的かつ推移的な関係
• 部分順序–反対称前順序
• 総予約注文–連結された（以前は総予約注文と呼ばれていた）予約注文
• 同値関係–対称的な前順序
• 厳密弱順序付け– 比較不能性が同値関係である厳密な半順序
• 全順序付け– 連結（全順序付け）、反対称性、推移性を持つ関係

有限集合上の推移関係の数を数える一般的な公式（OEISのシーケンスA006905）は知られていない。^{[ 9 ]}しかし、反射的、対称的、推移的である関係（つまり同値関係）の数（ OEISのシーケンスA000110）、対称的かつ推移的である関係、対称的、推移的、反対称的である関係、および全的、推移的、反対称的である関係の数を求める公式は存在する。Pfeiffer ^{[ 10 ]}はこの方向でいくらか進歩しており、これらの性質の組み合わせを持つ関係を互いの観点から表現しているが、いずれかを計算することは依然として困難である。Brinkmann と McKay (2005) ^{[ 11 ]}および Mala (2022) ^{[ 12 ]も参照のこと。}

任意の推移関係の反射化は前順序であるため、 n要素集合上の推移関係の数は前順序の数より最大で 2 ^{n倍多く、したがって漸近的に}${\displaystyle 2^{(1/4+o(1))n^{2}}}$クレイトマンとロスチャイルドの結果による。^{[ 13 ]}

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

関係Rは、推移的でない場合、つまり、あるx、y、zに対してxRyかつ yRz であるが xRz ではない場合、非推移的であると呼ばれる。対照的に、関係R は、xRyかつyRzが常にxRz が成り立たないことを意味する場合、反推移的であると呼ばれる。たとえば、xy が偶数である場合にxRyと定義される関係は非推移的であるが^{[ 14 ]}、反推移的ではない^{[ 15 ]} 。xが偶数でy が奇数である場合にxRyと定義される関係は、推移的かつ反推移的である^{[ 16 ]。x}が yの後継数である場合にxRy と定義される関係は、非推移的^{[ 17 ]}かつ反推移的である^{[ 18 ]}。非推移性の予期せぬ例は、政治的な問題や集団の選好などの状況で発生する^{[ 19 ] 。}

確率的バージョン（確率的推移性）に一般化された推移性の研究は、意思決定理論、心理測定学、効用モデルに応用されている。^{[ 20 ]}

準推移関係は別の一般化であり、^{[ 5 ]}非対称部分のみで推移的であることが求められます。このような関係は、社会選択理論やミクロ経済学で使用されます。^{[ 21 ]}

命題：Rが単葉である ならば、R;R ^Tは推移的である。

証明:${\displaystyle xR;R^{T}yR;R^{T}z.}$すると、 aとbが存在して、${\displaystyle xRaR^{T}yRbR^{T}z.}$Rは単葉であるため、yRbおよびaR ^T y はa = bを意味します。したがって、x R a R ^T zとなり、x R;R ^T zおよび R;R ^Tは推移的です。

系：Rが単葉である場合、R;R ^TはRの定義域上の同値関係である。

証明：R;R ^Tは定義域上で対称かつ反射的である。R の単葉性により、同値性の推移的要件が満たされる。

• 推移的還元
• 自動詞 サイコロ
• 合理的選択理論
• 仮言三段論法―実質条件文の推移性

• Liu, CL (1985), Elements of Discrete Mathematics , McGraw-Hill, ISBN 0-07-038133-X
• スミス、ダグラス；エッゲン、モーリス；セント・アンドレ、リチャード（2006）、『高等数学への移行』（第6 版）、ブルックス/コール、ISBN 978-0-534-39900-9

• グリマルディ、ラルフ・P. (1994)、『離散数学と組合せ数学』（第3 版）、アディソン・ウェスリー、ISBN 0-201-19912-2
• グンター・シュミット、2010年。 『関係数学』ケンブリッジ大学出版局、ISBN 978-0-521-76268-7。

• 「推移性」、数学百科事典、EMS Press、2001年 [1994年]
• cut-the-knotにおける推移性の実践