推移関係

この記事は英語版の対応するページを翻訳することにより充実させることができます。（2024年5月） 翻訳前に重要な指示を読むには右にある[表示]をクリックしてください。 英語版記事を日本語へ機械翻訳したバージョン（Google翻訳）。 万が一翻訳の手がかりとして機械翻訳を用いた場合、翻訳者は必ず翻訳元原文を参照して機械翻訳の誤りを訂正し、正確な翻訳にしなければなりません。これが成されていない場合、記事は削除の方針G-3に基づき、削除される可能性があります。 信頼性が低いまたは低品質な文章を翻訳しないでください。もし可能ならば、文章を他言語版記事に示された文献で正しいかどうかを確認してください。 履歴継承を行うため、要約欄に翻訳元となった記事のページ名・版について記述する必要があります。記述方法については、Wikipedia:翻訳のガイドライン#要約欄への記入を参照ください。 翻訳後、{{翻訳告知|en|Transitive relation|…}}をノートに追加することもできます。 Wikipedia:翻訳のガイドラインに、より詳細な翻訳の手順・指針についての説明があります。

推移関係（すいいかんけい、英: Transitive relation）は、数学における二項関係の一種。集合 X の二項関係 R が推移的であるとは、Xの任意の元 a、b、c について、a と b に R が成り立ち、b と c に R が成り立つとき、a と c にも R が成り立つことをいう。推移的関係とも。

一階述語論理でこれを表すと、次のようになる。

${\displaystyle \forall a,b,c\in X,\ a\,R\,b\land b\,R\,c\;\Rightarrow a\,R\,c}$

他の関係とは異なり、ある有限集合における推移関係の数を数える一般的方法は存在しない（N個のノードにおける推移関係数の数列）^[1]。しかし、同時に反射的で対称的な関係の数を数える方法は定式化されている（N個の番号付きボールをN個の区別の無い箱に入れる組み合わせ）。また、対称的で推移的な場合、対称的な場合、非推移的な場合、完全かつ推移的で非対称的な場合についても定式化されている。Pfeiffer による研究があり、これらの属性の組み合わせの関係数を定式化した^[2]。しかし、個々の属性の関係を数えることはまだ困難とされている。

例えば、${\displaystyle x=y}$ でかつ ${\displaystyle y=z}$ であれば、${\displaystyle x=z}$ である。以下は推移関係である。

• ${\displaystyle x=y}$（${\displaystyle x}$ と ${\displaystyle y}$ は等しい）
• ${\displaystyle x<y}$（${\displaystyle x}$ は ${\displaystyle y}$ より小さい）
• ${\displaystyle x\leq y}$（${\displaystyle x}$ は ${\displaystyle y}$ 以下である）
• ${\displaystyle x}$ は ${\displaystyle y}$ で割り切れる
• ${\displaystyle S\subset T}$（${\displaystyle S}$ は ${\displaystyle T}$ の部分集合である）
• ${\displaystyle p\rightarrow q}$（${\displaystyle p}$ ならば ${\displaystyle q}$ である）
• A は B の祖先である

一方、以下は推移関係でない。

• ${\displaystyle x\neq y}$（${\displaystyle x}$ と ${\displaystyle y}$ は等しくない）
• A は B の母である

推移関係のもとでは以下の関係は同値である。

• 非反射関係（irreflexivity）
• 非対称関係（asymmetry）
• 強半順序関係（strict partial order）

• 半順序 - 反対称的な擬順序
• 擬順序 - 推移的であると同時に反射的
• 全擬順序 - 完全的な擬順序
• 同値関係 - 対称的な擬順序
• 厳密弱順序 - 強半順序関係で等価関係での比較が不可能な場合
• 全順序 - 推移的で反対称的な完全関係

1. ^ Steven R. Finch, "Transitive relations, topologies and partial orders", 2003.
2. ^ Götz Pfeiffer, "Counting Transitive Relations", Journal of Integer Sequences, Vol. 7 (2004), Article 04.3.2.

• Discrete and Combinatorial Mathematics - Fifth Edition - by Ralph P. Grimaldi ISBN 0-201-19912-2

• 推移閉包
• 反射関係
• 対称関係

• Transitivity in Action at cut-the-knot