泸州龙马潭区：酒业在创新提质中倾力谋变

百度 伟大创造精神，体现在诸子百家、诗词曲赋，体现在影响世界的四大发明，体现在有形的无形的文化遗存；伟大奋斗精神，体现在大好河山、辽阔海疆、广袤良田，体现在中国人民千百年来的生产生活、日用伦常；伟大团结精神，体现在56个民族多元一体、交织相融，体现在中华民族大家庭同心同德、守望相助；伟大梦想精神，体现在小康的理念、大同的情怀，体现在勇于追求和实现梦想的执着精神。

推移関係（すいいかんけい、英: 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個のノードにおける推移関係数の数列）。しかし、同時に反射的で対称的な関係の数を数える方法は定式化されている（N個の番号付きボールをN個の区別の無い箱に入れる組み合わせ）。また、対称的で推移的な場合、対称的な場合、非推移的な場合、完全かつ推移的で非対称的な場合についても定式化されている。Pfeiffer による研究があり、これらの属性の組み合わせの関係数を定式化した。しかし、個々の属性の関係を数えることはまだ困難とされている。

例

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

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

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

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

推移性の属性

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

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

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

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

参考文献

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

関連項目

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

外部リンク

• Transitivity in Action at cut-the-knot