推移関係

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

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

\forall a,b,c\in X,\ a\,R\,b\land b\,R\,c\;\Rightarrow a\,R\,c

推移関係の数え上げ

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

例

例えば「AはBより大きい」「AはB以上である」「AはBと等しい」といった関係は推移関係である。例えば、a = b でかつ b = c であれば、a = c が成り立つ。

一方、「AはBの母である」は推移関係ではない。アリスがブレンダの母で、ブレンダがクレアの母だった場合、アリスがクレアの母であるとは言えない。

推移関係の例として以下のものがある。

「AはBと等しい」（等式）
「AはBの部分集合である」
「AはBより小さい」、「AはB以下である」（不等式）
「AはBで割り切れる」（約数）
「AならばBである」（含意）

「AとBは等しくない」は非推移関係の例である（集合に少なくとも2つ以上の元がある場合）。

推移性の属性

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

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

推移性を必要とする他の属性

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

脚注

^ Steven R. Finch, "Transitive relations, topologies and partial orders", 2003.
^ 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

[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.

[1]

[2]

ウィキペディア	ランダム
毎日	カテゴリ