出典: フリー百科事典『ウィキペディア(Wikipedia)』
この記事は
英語版の対応するページ を翻訳することにより充実させることができます。 (2024年5月 ) 翻訳前に重要な指示を読むには右にある[表示]をクリックしてください。
英語版記事を日本語へ機械翻訳したバージョン (Google翻訳)。
万が一翻訳の手がかりとして機械翻訳を用いた場合、翻訳者は必ず翻訳元原文を参照して機械翻訳の誤りを訂正し、正確な翻訳にしなければなりません。これが成されていない場合、記事は削除の方針G-3 に基づき、削除される可能性があります。
信頼性が低いまたは低品質な文章を翻訳しないでください。もし可能ならば、文章を他言語版記事に示された文献で正しいかどうかを確認してください。
履歴継承 を行うため、要約欄 に翻訳元となった記事のページ名・版について記述する必要があります。記述方法については、Wikipedia:翻訳のガイドライン#要約欄への記入 を参照ください。
翻訳後、{{翻訳告知 |en|Transitive relation|…}}
をノート に追加することもできます。
Wikipedia:翻訳のガイドライン に、より詳細な翻訳の手順・指針についての説明があります。
推移関係 (すいいかんけい、英 : Transitive relation )は、数学 における二項関係 の一種。集合 X の二項関係 R が推移的 であるとは、X の任意の元 a 、b 、c について、a と b に R が成り立ち、b と c に R が成り立つとき、a と c にも R が成り立つことをいう。推移的関係 とも。
一階述語論理 でこれを表すと、次のようになる。
∀
a
,
b
,
c
∈
X
,
a
R
b
∧
b
R
c
⇒
a
R
c
{\displaystyle \forall a,b,c\in X,\ a\,R\,b\land b\,R\,c\;\Rightarrow a\,R\,c}
推移関係の数え上げ [ 編集 ]
他の関係とは異なり、ある有限集合における推移関係の数を数える一般的方法は存在しない(N個のノードにおける推移関係数の数列 )[1] 。しかし、同時に反射的で対称的な関係の数を数える方法は定式化されている(N個の番号付きボールをN個の区別の無い箱に入れる組み合わせ )。また、対称的で推移的な場合、対称的な場合、非推移的な場合、完全かつ推移的で非対称的な場合についても定式化されている。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.
^ 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
関連項目 [ 編集 ]
外部リンク [ 編集 ]