この記事は英語版の対応するページ
を翻訳することにより充実させることができます。（2024年5月）翻訳前に重要な指示を読むには右にある[表示]をクリックしてください。推移関係（すいいかんけい、英: Transitive relation）は、数学における二項関係の一種。集合 X の二項関係 R が推移的であるとは、Xの任意の元 a、b、c について、a と b に R が成り立ち、b と c に R が成り立つとき、a と c にも R が成り立つことをいう。推移的関係とも。
一階述語論理でこれを表すと、次のようになる。 ∀ a , b , c ∈ X , a R b ∧ b R c ⇒ a R c {\displaystyle \forall a,b,c\in X,\ a\,R\,b\land b\,R\,c\;\Rightarrow a\,R\,c} 他の関係とは異なり、ある有限集合における推移関係の数を数える一般的方法は存在しない（ ⇒N個のノードにおける推移関係数の数列）[1]。しかし、同時に反射的で対称的な関係の数を数える方法は定式化されている（ ⇒N個の番号付きボールをN個の区別の無い箱に入れる組み合わせ）。また、対称的で推移的な場合、対称的な場合、非推移的な場合、完全かつ推移的で非対称的な場合についても定式化されている。Pfeiffer による研究があり、これらの属性の組み合わせの関係数を定式化した[2]。しかし、個々の属性の関係を数えることはまだ困難とされている。 例えば、 x = y {\displaystyle x=y} でかつ y = z {\displaystyle y=z} であれば、 x = z {\displaystyle x=z} である。以下は推移関係である。 一方、以下は推移関係でない。 推移関係のもとでは以下の関係は同値である。
推移関係の数え上げ
例
x = y {\displaystyle x=y} （ x {\displaystyle x} と y {\displaystyle y} は等しい）
x < y {\displaystyle x<y} （ x {\displaystyle x} は y {\displaystyle y} より小さい）
x ≤ y {\displaystyle x\leq y} （ x {\displaystyle x} は y {\displaystyle y} 以下である）
x {\displaystyle x} は y {\displaystyle y} で割り切れる
S ⊂ T {\displaystyle S\subset T} （ S {\displaystyle S} は T {\displaystyle T} の部分集合である）
p → q {\displaystyle p\rightarrow q} （ p {\displaystyle p} ならば q {\displaystyle q} である）
A は B の祖先である
x ≠ y {\displaystyle x\neq y} （ x {\displaystyle x} と y {\displaystyle y} は等しくない）
A は B の母である
推移性の属性
非反射関係（irreflexivity）
非対称関係（asymmetry）
強半順序関係（strict partial order）
推移性を必要とする他の属性
半順序 - 反対称的な擬順序
擬順序 - 推移的であると同時に反射的
全擬順序
同値関係 - 対称的な擬順序
厳密弱順序
全順序 - 推移的で反対称的な完全関係
脚注^ Steven R. Finch, ⇒"Transitive relations, topologies and partial orders", 2003.
^ Gotz Pfeiffer, " ⇒Counting Transitive Relations", Journal of Integer Sequences, Vol. 7 (2004), Article 04.3.2.