推移関係
数学における二項関係の一種
(推移的関係から転送)
🔥 Top keywords: デジモンストーリー ロストエボリューションヴァンガード火曜日の女シリーズ藤原宮子豊見城警察署メインページ特別:検索魔法騎士レイアース古川琴音ヒコロヒー鬼滅の刃海のはじまり石丸伸二渋沢栄一高木聡一朗三淵嘉子森川智之北里柴三郎桜井日奈子津田梅子ベルサイユのばら星野リゾート トマム新浜レオン天羽しろっぷ安斉星来目黒蓮蓮舫無脳症アポロドーロスチェ・ジウ小林鷹之岡田将生Taka (ONE OK ROCKのメンバー)山本リンダブラック・ジャック三輪勝恵藤原彰子NewJeansすすきのホテル殺人事件生方美久暇空茜虎に翼佐藤友美 (女優)石橋静河
この記事は英語版の対応するページを翻訳することにより充実させることができます。(2024年5月) 翻訳前に重要な指示を読むには右にある[表示]をクリックしてください。
|
推移関係(すいいかんけい、英: Transitive relation)は、数学における二項関係の一種。集合 X の二項関係 R が推移的であるとは、Xの任意の元 a、b、c について、a と b に R が成り立ち、b と c に R が成り立つとき、a と c にも R が成り立つことをいう。推移的関係とも。
一階述語論理でこれを表すと、次のようになる。
推移関係の数え上げ
編集他の関係とは異なり、ある有限集合における推移関係の数を数える一般的方法は存在しない(N個のノードにおける推移関係数の数列)[1]。しかし、同時に反射的で対称的な関係の数を数える方法は定式化されている(N個の番号付きボールをN個の区別の無い箱に入れる組み合わせ)。また、対称的で推移的な場合、対称的な場合、非推移的な場合、完全かつ推移的で非対称的な場合についても定式化されている。Pfeiffer による研究があり、これらの属性の組み合わせの関係数を定式化した[2]。しかし、個々の属性の関係を数えることはまだ困難とされている。
例
編集例えば、 でかつ
であれば、
である。以下は推移関係である。
一方、以下は推移関係でない。
(
と
は等しくない)
- A は B の母である
推移性の属性
編集推移関係のもとでは以下の関係は同値である。
推移性を必要とする他の属性
編集脚注
編集- ^ 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