推移関係

推移関係

タイプ	二項関係
分野	初等代数学
声明	集合上の関係が推移的であるとは、内のすべての要素 に対して、が およびに関連している場合に、もに関連している場合を指します。${\displaystyle R}$${\displaystyle X}$${\displaystyle a}$${\displaystyle b}$${\displaystyle c}$${\displaystyle X}$${\displaystyle R}$${\displaystyle a}$${\displaystyle b}$${\displaystyle b}$${\displaystyle c}$${\displaystyle R}$${\displaystyle a}$${\displaystyle c}$
象徴的な声明	${\displaystyle \forall a,b,c\in X:(aRb\wedge bRc)\Rightarrow aRc}$

数学において、集合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]
• 「垂直である」（ユークリッド幾何学における線上の関係）

任意の集合上の空関係は推移的である^[3]。なぜなら、および となる要素は存在せず、したがって推移条件は空に真であるからである。 1 つの順序付きペアのみを含む関係Rも推移的である。つまり、順序付きペアがに対して という形式である場合、そのような要素は、そしてこの場合は確かに であるが、順序付きペアが という形式でない場合、そのような要素は存在せず、したがって は空に推移的である。 ${\displaystyle X}$${\displaystyle a,b,c\in X}$${\displaystyle aRb}$${\displaystyle bRc}$${\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}$

• 推移関係の逆(逆)は常に推移的です。たとえば、「サブセットである」が推移的であり、「スーパーセットである」がその逆であることがわかっている場合、後者も推移的であると結論付けることができます。
• 2つの推移関係の交差は常に推移的です。^[4]たとえば、「以前生まれた」と「と同じ名前を持つ」が推移的であることがわかれば、「以前生まれ、同じ名前を持つ」も推移的であると結論付けることができます。
• 2 つの推移的関係の結合は、必ずしも推移的である必要はありません。たとえば、「より前に生まれた、または同じ名前を持つ」は推移的関係ではありません。これは、たとえば、ハーバート・フーバーはフランクリン・D・ルーズベルトと関連があり、フランクリン・ルーズベルトはフランクリン・ピアースと関連があるのに対し、フーバーはフランクリン・ピアースと関連がないためです。
• 推移関係の補語は推移的である必要はありません。^[5]たとえば、「等しい」は推移的ですが、「等しくない」は最大で1つの要素を持つ集合に対してのみ推移的です。

推移的関係は、それが非反射的である場合にのみ非対称的である。^[6]

推移的な関係は必ずしも反射的である必要はありません。反射的である場合、それは前順序と呼ばれます。たとえば、集合X = {1,2,3} の場合:

• R = { (1,1), (2,2), (3,3), (1,3), (3,2) } は反射的であるが推移的ではない。なぜなら (1,2) のペアが存在しないからである。
• R = { (1,1), (2,2), (3,3), (1,3) } は反射的かつ推移的であるため、前置順序である。
• R = { (1,1), (2,2), (3,3) } は推移的であると同時に反射的であり、別の順序付けです。

反例として、実数上の関係は推移的ですが、反射的ではありません。 ${\displaystyle <}$

R を集合X上の二項関係とする。Rの推移的拡大( R ₁と表記) は、R _{1 が}R を含み、 ( a , b ) ∈ Rかつ( b , c ) ∈ Rならば( a , c ) ∈ R ₁となるような、 X上の最小の二項関係である。^[7]たとえば、X が町の集合であり、そのうちのいくつかは道路でつながっているとします。町Aと町Bを直接結ぶ道路がある場合、R を( A , B ) ∈ 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の間を移動できる場合、 ( A、C ) ∈ R *となります。

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

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

任意の推移関係の反射化は前順序であるため、 n要素集合上の推移関係anの数は前順序の数より最大で2n^倍多く、したがってKleitmanとRothschildの結果により漸近的となる。 ^[12]${\displaystyle 2^{(1/4+o(1))n^{2}}}$

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

関係R は、推移的でない場合、つまり、何らかのx、y、zに対して、 xRyかつyRzであるが、 xRz ではない場合、非推移的と呼ばれます。対照的に、関係Rは、 xRyおよびyRz が常にxRz が成立しないことを意味する場合、反推移的と呼ばれます。たとえば、xyが偶数の場合にxRyによって定義される関係は非推移的ですが、^[13]反推移的ではありません。^[14] xが偶数でyが奇数の場合にxRyによって定義される関係は、推移的かつ反推移的です。^[15] xがyの次の数の場合にxRy によって定義される関係は、非推移的^[16]かつ反推移的です。^[17]予期しない非推移性の例は、政治的な問題やグループの好みなどの状況で発生します。^[18]

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

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

命題: R が一価である 場合、R;R ^{T は}推移的です。

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

系: Rが単価である場合、 R;R ^{T は}Rの定義域上の同値関係です。

証明: R;R ^{T は}その定義域で対称かつ反射的です。Rが単価であるため、同値性の推移的要件が満たされます。

• 推移的還元
• 自動詞のサイコロ
• 合理的選択理論
• 仮説的三段論法— 物質的条件の推移性

• グリマルディ、ラルフ P. (1994)、離散数学と組合せ数学(第 3 版)、Addison-Wesley、ISBN 0-201-19912-2
• Liu, CL (1985)、離散数学の要素、McGraw-Hill、ISBN 0-07-038133-X
• Gunther Schmidt、2010年。リレーショナル数学。ケンブリッジ大学出版局、ISBN 978-0-521-76268-7。 
• スミス、ダグラス、エッゲン、モーリス、セントアンドレ、リチャード（2006）、上級数学への移行（第6版）、ブルックス/コール、ISBN 978-0-534-39900-9
• Pfeiffer, G. (2004). 推移関係の計数。整数シーケンスジャーナル、7 (2), 3。

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