Team TripleFalcon. http://www.triplefalcon.com/

概要

 関係が「ある」とか「ない」ということを言葉上我々はよく言います。集合論の言葉に従っても関係を定義することが出来ます。 例えば、a と b に関係があるとき (a,b) という組が存在し、a と b に関係がないとき (a,b) が存在しないように組の集合 R を作ったとき、それを関係(relation)と呼びます。(参照→集合,対応,直積集合)

 関係では、ある要素と別の要素につながりが「ある」か「ない」かに着目します。人間の集合であれば、親子(uとvは親子)とか兄弟(uとvは兄弟)は関係になります。

 関係とは、集合ですから記号 ∩,∪,⊂ などを直接適用できます。関係 R と Q で R∩Q を定義してもかまわないということです。

 関係は、関係データモデル(relation data model) などの基礎を与えます。

 関係は対応によく似ています。X から Y へという広い定義を対応、X から X へという狭い定義を関係と言葉上区別します。(参照→対応,関数)

名称 概要 (R⊂U×U)
反射的関係 ∀u∈U ,uRu
対称的関係 ∀u,v∈U ,uRv⇒vRu
推移的関係 ∀u,v,w∈U ,uRv∧vRw⇒uRw
反対称関係 ∀u,v∈U ,uRv∧vRu⇒u=v
同値関係 反射的,対称的,かつ 推移的関係
半順序関係 反射的,推移的,かつ 反対称的
全順序関係 反射的,推移的,反対称的, かつ比較可能

Team TripleFalcon. http://www.triplefalcon.com/

定義

 集合 U,V があるとき、直積集合 U×V部分集合 R⊂U×V を U と V の対応(correspondence) といいます。(参照→集合,直積集合) U×U の部分集合は特別に関係(relation) といいます。

定義1) R が U 上の関係 
def
 R⊂U×U

 集合 R⊂U×U を2項関係(binary relation) といいます。集合が3個以上、例えば U×U×U の部分集合も関係で、3項関係(ternary relation) といいます。一般に n 個の集合の直積から定義した場合は n項関係(n-ary relation) といいます。

 (u,v) がRの元のとき u,v に関係Rがあるといいます。このとき、uRv と表記することがあります。

定義2) uRv 
def
 (u,v)∈R

 一般的に関係とだけいった場合は対称的とは限りません。例えば、a から b へ関係があっても b から a への関係があるかどうかは別問題です。

Team TripleFalcon. http://www.triplefalcon.com/

反射的

 もし、U 上の関係 R が自分自身への関係を必ず持つ場合は、反射的関係(reflexive relation) といいます。

定義3) R が反射的 
def
 ∀u∈U ,( uRu)

 例えば、学級委員長の推薦を募ったとき、全員が"自分"を推薦した場合は、この関係推薦(uはvを推薦する) は反射的関係といえます。(次の対称的関係と勘違いしやすいので注意してください。)

 関係「親」は反射的関係ではありません。自分は自分の親ではないからです。

Team TripleFalcon. http://www.triplefalcon.com/

対称的

 u から vへの関係と vから uへの関係が同様にある場合は対称的関係(symmetric relation) といいます。u が v の配偶者なら v は u の?

定義4) R が対称的 
def
 ∀u,v∈U ,( uRv ならば vRu )

 人間の集合上の関係配偶者(uはvの配偶者)は対称的関係でしょう。一夫多妻でも成立します。関係(uはvの親である)は対称的関係ではありません。関係好意(uはvに好意をもつ) も対称的関係では無いです。(好意が常に対称的関係だったら人間界のトラブルはかなり少なくなるでしょう。古にも、トロイア戦争は好意の非対称性が引き起こしたとされています。[本当か?])

 関係「兄弟」(uはvの兄弟である) は対称的関係です。関係「兄」(uはvの兄である)や「弟」(uはvの弟である)は対称的関係ではありません。

Team TripleFalcon. http://www.triplefalcon.com/

推移的

 関係が連鎖出来る場合は推移的関係(transitive relation) といいます。αのαはαですのように連鎖できる場合です。

定義5) R が推移的 
def

 ∀u,v,w∈U ,(uRv かつ vRw ならば uRw)

 例えば、関係(uはvの親である) は推移的関係ではありません。親の親は親ではありませんから。関係兄弟推移的関係です。兄の兄は兄ですし、弟の弟も弟ですから。もちろん兄弟の兄弟も兄弟です。関係祖先推移的関係です。祖先の祖先は祖先ですから。

 一般に、ある関係が示されたときに、その関係が推移的であることを効率的に確かめるのは難しい問題です。与えられた関係が推移的かどうか効率的に確かめるというそれだけで重要な研究課題になることもあります。

Team TripleFalcon. http://www.triplefalcon.com/

反対称的

 U の元 u,v∈Uu=v の場合を除いて uRvvRu を両立しないとき、反対称的関係(antisymmetric relation) といいます。

定義6) R が反対称的 
def

 ∀u,v∈U ,(uRv かつ vRu ならば u=v)

 初めて定義6だけ見たときは、何のことかピンときませんでした。対偶という言葉を知っていると" u=v でない限り uRv と vRu は両立しない。" と同じ意味だとわかります。この対偶のほうが直感的にはわかりやすいでしょう。

 じゃんけんでいう勝ち(uはvに勝つ) も反対称的関係です。勝ちまたは引き分けでも反対称的関係です。

Team TripleFalcon. http://www.triplefalcon.com/

同値関係

 集合 U 上の関係 R が反射的で、対称的で、推移的な関係を同値関係(equivalence relation) といいます。同値関係 R は、U を分割し、独立したブロックを作ります。(参照→分割)ブロックの集合はRの同値類(equivalence classes) と呼ばれます。

定義7) R が同値関係 
def
 R が反射的,対称的,かつ推移的

 U の同値関係 R1 と R2 があり、R1 が作る同値類を P1、 R2が作る同値類を P2 とします。ここで、R1⊂R2 のとき、P1 を P2 の細分といいます。

 関係同部屋(uとvはルームメート) は同値関係です。関係同苗字(uとvは苗字が同じ)も同値関係です。もちろん同姓同名同値関係です。

  しかし、関係苗字か名前が同じ同値関係ではありません。 "A.B."と"A.D."の苗字が同じで、"A.D."と"C.D"の名も同じですが、"A.B."と"C.D."は苗字も名も違います。

 学生の集合上の関係を考えたとき、同学級が作る同値類は同学年が作る同値類の細分になります。

Team TripleFalcon. http://www.triplefalcon.com/

半順序関係

 集合 U 上の関係 R が、反射的推移的反対称的関係のとき、半順序関係(partially ordered relation) といいます。半順序関係は、特に ≦ で表記し、関係がある場合は u≦v のように表記します。

定義8) R が半順序 
def
 R が反射的,推移的,反対称的

 一般に、U 上で半順序関係が成り立つだけでは集合 U の上で比較ができるかどうかわかりません。学生同士に関係優秀(uはvより優秀である) を導入してみます。例えば、数学も文学も得点が高い学生を優秀と定義します。優秀は uとv が常に比較できるとは限りません。数学はできるけど文学がダメな学生 u と文学ができるけど数学がダメな学生 v は優秀では比較できません。この関係は半順序関係です。

 集合 U 上の関係 ≦が半順序関係であるとき、(U,≦) を半順序集合(partially ordered set) といいます。

Team TripleFalcon. http://www.triplefalcon.com/

全順序関係

 U 上の関係 ≦ がすべての u,v について、 u≦v か v≦u の少なくとも一方が成り立つとき、関係 ≦ は比較可能であるといいます。半順序集合 (U,≦) の関係 ≦ が比較可能のとき全順序関係(totally ordered relation) といいます。

定義9) R が比較可能 
def
 ∀u,v ∈U , uRv または vRu
定義10) R が全順序 
def
 R が半順序で比較可能

 ≦ が U の全順序関係のとき、(U,≦) を全順序集合(totally ordered set) といいます。

 感覚的には、全順序集合は要素が一列に並ぶ集合です。実数や整数のように小さい順に並べることが可能になります。

Team TripleFalcon. http://www.triplefalcon.com/

閉包

 関係に閉包(transitive closure)という概念を導入します。一般に、集合 S の閉包 S' というのは操作に対して閉じるように元を新たに補った集合で最小のものを差します。

 関係 R の推移閉包(transitive closure) というのは、R が必ず推移的関係であるように拡張した関係です。他に良く使われるものに、対称閉包(symmetric closure)、反射閉包(reflexive closure)、反射推移閉包(reflexive transitive closure)、などがあります。

 まず、推移閉包から定義しますが、その前に推移拡張(transitive extension) を定義します。

定義11) Rext が R の推移拡張
def
Rext =R∪{(u,w)|(u,v),(v,w)∈R}

 R0=R として、Ri+1 を Ri推移拡張とします。従って、R2 は R1 の推移拡張です。R の推移拡張は、R が2回推移してたどり着くような別地点までバイパス推移をつなぐ感覚です。

定義12) R* が R の推移閉包
def
R∪R1∪R2∪・・・=
i=0
i=∞
Ri

 同様に反射閉包反射推移閉包対称閉包も定義できます。

Team TripleFalcon. http://www.triplefalcon.com/

Team TripleFalcon. http://www.triplefalcon.com/

Team TripleFalcon. http://www.triplefalcon.com/

Team TripleFalcon. http://www.triplefalcon.com/

Team TripleFalcon. http://www.triplefalcon.com/


Team TRIPLE FALCON

アクション&シミュレーション ゲーミングとゲーム製作を真面目に考える 新進気鋭の研究者集団

   
 
用語集TOP

関係(relation)

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
あ-お か-こ さ-そ た-と な-の
は-ほ ま-も や-よ ら-ろ わ-ん

数学、哲学、工学を横断する事典です。よろしければ活用してください。 ゲーム, アクション,シューティング,シミュレーション,リアルタイム, 計量経済学,計量心理学, コンピュータ,用語集,計算機科学用語集,コンピュータ用語集, 3DCG, グラフィックス,ゲームグラフィックス,美少女, 光反射,鏡面反射,拡散反射,屈折,散乱,異方性反射,影, シェーディング,レンダリング,透視変換, 発光,爆発,爆炎,煙, 物理, 人物,表情,表現,運動,力学,流体, 計算幾何学, グラフ,アフィン変換,アフィン写像,凸包,超平面,3D,3Dの数理, コンピュータサイエンス,コンピュータ, 計算機科学, チューリングマシン,チューリング機械,線形有界オートマトン,プッシュダウンオートマトン,有限オートマトン, オートマトン,状態遷移,遷移関数,対角線論法,文字列,記号, FA,NFA,PDA,NPDA,LBA,NLBA,TM, 計算量,P,NP,PSPACE,NP完全,NP困難,P完全,PSPACE完全,PP,APX,APX完全, 確率チューリング機械,確率オートマトン, 音声, 音階,音量,音律,和音,和声,無限上昇音,MIDI, 色彩, 表色系,顕色系,混色系,RGB,CMY,YCbCr,YUV,YIQ,CIE,L*a*b*, 符号, 圧縮,符号化,情報源符号化, 符号,ブロック符号,ストリーム符号,符号理論, 離散数学, 集合,写像,関数,全単写,単写,全写,対応関係,関係,反射,反射推移閉包, 代数系, 群,環,体,モノイド,半群,準同型写像,同型写像, 形式言語, 言語,正則言語,文脈自由言語,文脈依存言語,確率言語, 文法,正則文法,文脈自由文法,文脈依存文法,確率文脈自由言語, 文字,文字列, 3型言語,2型言語,1型言語,0型言語, 信号処理, 変換,フィルタ,信号処理,DFT,DCT,DST,FFT,Wavelet,フーリエ変換, 離散,コサイン変換,サイン変換,ウェーブレット, 基礎数学, 数学,応用数学,基礎数学,フィボナッチ数列, 解析学, 位相空間,線形空間,距離空間,ベクトル空間,vector,バナッハ空間,Banach,ヒルベルト空間,Hilbert,ユークリッド空間,Euclid, ノルム,内積,可算濃度,非可算濃度, 情報理論, 情報源,情報量,エントロピー,相互情報量,記号,記号列, 複雑系, カオス,フラクタル,フラクタル幾何学,カオス写像, インターネット, セキュリティ,HTTP,SMTP,FTP,プロトコル, その他理論,理論, 紅茶,自転車通勤,備忘録, 暗号, モンゴメリ演算,高速計算法,素因数分解,離散対数問題, 暗号,ブロック暗号,ストリーム暗号,楕円暗号, 乱数,乱数生成,共通鍵暗号,公開鍵暗号,公開鍵署名,鍵共有,鍵交換, 線形攻撃,差分攻撃,補間攻撃,スライド攻撃,量子暗号, 依頼計算,ゼロ知識対話証明,ハッシュ,

AES,Rijndael,RSA,ElGamal,Twofish,Serpent,

RC6,MARS,CAST,IDEA,GOST,

MQV,DH,EC-DH,EC-ElGamal,

終了,

フィリピンパブ
アミューズメント企画はお任せ
資産運用はお任せ
メール お問い合わせ お問い合わせ メール メール メール メール メール メール