推移関係

数学における二項関係の一種

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

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

推移関係の数え上げ

編集

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

例えば、  でかつ   であれば、  である。以下は推移関係である。

  •    等しい
  •     より小さい
  •     以下である)
  •   割り切れる
  •    部分集合である)
  •    ならば   である)
  • A は B の祖先である

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

  •     は等しくない)
  • A は B の母である

推移性の属性

編集

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

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

編集

脚注

編集
  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

関連項目

編集

外部リンク

編集