推移関係
[Wikipedia|▼Menu]
□記事を途中から表示しています
[最初から表示]

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.

参考文献

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

関連項目

推移閉包

反射関係

対称関係

外部リンク

Transitivity in Action at ⇒cut-the-knot


記事の検索
おまかせリスト
▼オプションを表示
ブックマーク登録
mixiチェック!
Twitterに投稿
オプション/リンク一覧
話題のニュース
列車運行情報
暇つぶしWikipedia

Size:9 KB
出典: フリー百科事典『ウィキペディア(Wikipedia)
担当:undef