推移関係のソースを表示

{{Expand English|Transitive relation|date=2024年5月}}
'''推移関係'''（すいいかんけい、{{lang-en-short|Transitive relation}}）は、[[数学]]における[[二項関係]]の一種。[[集合]] ''X'' の[[二項関係]] ''R'' が'''推移的'''であるとは、''X''の任意の元 ''a''、''b''、''c'' について、''a'' と ''b'' に ''R'' が成り立ち、''b'' と ''c'' に ''R'' が成り立つとき、''a'' と ''c'' にも ''R'' が成り立つことをいう。'''推移的関係'''とも。

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

:<math>\forall a, b, c  \in X,\ a  \,R\, b \land b \,R\, c \; \Rightarrow a \,R\, c</math>

== 推移関係の数え上げ ==
他の関係とは異なり、ある有限集合における推移関係の数を数える一般的方法は存在しない（[http://www.research.att.com/~njas/sequences/A006905 N個のノードにおける推移関係数の数列]）<ref>Steven R. Finch, [http://algo.inria.fr/csolve/posets.pdf "Transitive relations, topologies and partial orders"], 2003.</ref>。しかし、同時に反射的で対称的な関係の数を数える方法は定式化されている（[http://www.research.att.com/~njas/sequences/A000110 N個の番号付きボールをN個の区別の無い箱に入れる組み合わせ]）。また、対称的で推移的な場合、対称的な場合、非推移的な場合、完全かつ推移的で非対称的な場合についても定式化されている。Pfeiffer による研究があり、これらの属性の組み合わせの関係数を定式化した<ref>Götz Pfeiffer, "[http://www.cs.uwaterloo.ca/journals/JIS/VOL7/Pfeiffer/pfeiffer6.html Counting Transitive Relations]", ''Journal of Integer Sequences'', Vol. 7 (2004), Article 04.3.2.</ref>。しかし、個々の属性の関係を数えることはまだ困難とされている。

==例==
例えば、<math>x=y</math> でかつ <math>y=z</math> であれば、<math>x=z</math> である。以下は推移関係である。
*<math>x=y</math>（<math>x</math> と <math>y</math> は[[等式|等しい]]）
*<math>x<y</math>（<math>x</math> は <math>y</math> より[[不等式|小さい]]）
*<math>x\le y</math>（<math>x</math> は <math>y</math> [[以上・以下|以下]]である）
*<math>x</math> は <math>y</math> で[[約数|割り切れる]]
*<math>S\sub T</math>（<math>S</math> は <math>T</math> の[[部分集合]]である）
*<math>p\rarr q</math>（<math>p</math> [[論理包含|ならば]] <math>q</math> である）
*A は B の祖先である

一方、以下は推移関係でない。
*<math>x\ne y</math>（<math>x</math> と <math>y</math> は等しくない）<!--集合に複数の元がある場合-->
*A は B の母である

== 推移性の属性 ==
推移関係のもとでは以下の関係は同値である。
* [[非反射関係]]（irreflexivity）
* [[非対称関係]]（asymmetry）
* 強半順序関係（strict partial order）

== 推移性を必要とする他の属性 ==
* [[半順序集合|半順序]] - 反対称的な擬順序
* [[擬順序]] - 推移的であると同時に反射的
* [[全擬順序]] - [[完全関係|完全的]]な擬順序
* [[同値関係]] - 対称的な擬順序
* [[厳密弱順序]] - 強半順序関係で等価関係での比較が不可能な場合
* [[全順序]] - 推移的で反対称的な完全関係

== 脚注 ==
<references />

== 参考文献 ==
* ''Discrete and Combinatorial Mathematics'' - Fifth Edition - by Ralph P. Grimaldi ISBN 0-201-19912-2

== 関連項目 ==
* [[推移閉包]]
* [[反射関係]]
* [[対称関係]]

== 外部リンク ==
* [http://www.cut-the-knot.org/triangle/remarkable.shtml Transitivity in Action] at [http://www.cut-the-knot.org/index.shtml cut-the-knot]

{{DEFAULTSORT:すいいかんけい}}
[[Category:推移関係|*]]
[[Category:数学的関係]]
[[Category:集合論]]
[[Category:数理論理学]]
[[Category:数学に関する記事]]