関係かんけいrelationの基本きほん

1導入どうにゅう

関係かんけいrelationを学まなぶときの中心ちゅうしんの問といは、「対象たいしょうobjectどうしの結むすびつきを、どの順序対じゅんじょついordered pairを採用さいようするかで記録きろくできるか」である。関係かんけいrelationは曖昧あいまいな言葉ことばではなく、直積集合ちょくせきしゅうごうCartesian productの部分集合ぶぶんしゅうごうsubsetである。

この定義ていぎにより、「$$a$$a は $$b$$b と等ひとしい」「$$a$$a は $$b$$b 以下いかである」「$$a$$a は $$b$$b を割わり切きる」「固定こていした正せいの整数せいすう $$m$$m で割わった $$a$$a と $$b$$b の余あまりが同おなじ」のような異ことなる見みた目めの主張しゅちょうを、同おなじ形式けいしきformで扱あつかえる。

この形式化けいしきかにより、言葉ことばの違ちがいではなく、どの順序対じゅんじょついordered pairが入はいっているかで性質せいしつを判定はんていできる。したがって、後あとで反射性はんしゃせい・対称性たいしょうせい・反対称性はんたいしょうせい・推移性すいいせいを調しらべるときも、同おなじ集合しゅうごうとしての見方みかたを使つかう。

2用語ようごと定義ていぎ

集合しゅうごうset $$A,B$$A,B に対たいして、$$A$$A から $$B$$B への関係かんけいrelationとは、$$A\times B$$A\times B の部分集合ぶぶんしゅうごうsubsetである。

と書かく。$$(a,b)\in R$$(a,b)\in R のとき、$$a$$a は $$b$$b と関係かんけいrelation $$R$$R で結むすばれるといい、しばしば

と書かく。

$$A=B$$A=B の場合ばあい、$$R\subseteq A\times A$$R\subseteq A\times A を $$A$$A 上うえの二項関係にこうかんけいbinary relationという。同値関係どうちかんけいequivalence relationや順序関係じゅんじょかんけいorder relationは、どちらも二項関係にこうかんけいbinary relationの特別とくべつな場合ばあいである。

3方針ほうしん

関係かんけいrelationを調しらべるときは、まず母体ぼたいとなる直積集合ちょくせきしゅうごうCartesian productを確認かくにんする。次つぎに、その内うち採用さいようされている順序対じゅんじょついordered pairがどれかを確認かくにんする。

性質せいしつpropertyを判定はんていするときは、全すべての元げんelementについて条件じょうけんが成立せいりつするかを確認かくにんする。1 例れいだけで反射性はんしゃせいreflexivityや推移性すいいせいtransitivityを証明しょうめいすることはできない。失敗しっぱいを示しめすには 1 つの反例はんれいcounterexampleで十分じゅうぶんである。

全称条件ぜんしょうじょうけんuniversal conditionを示しめすときは、任意にんいの元げんelementから始はじめる。一方いっぽう、性質せいしつが成立せいりつしないことを示しめすときは、その条件じょうけんを破やぶる順序対じゅんじょついordered pairや組くみを 1 つ示しめせばよい。

4直感的ちょっかんてきな説明せつめい

関係かんけいrelationは、表ひょうのマスに印しるしを付つけることとして見みるとよい。$$A\times B$$A\times B の各かく順序対じゅんじょついordered pair $$(a,b)$$(a,b) は、行ぎょう $$a$$a と列れつcolumn $$b$$b の交点こうてんに対応たいおうする。関係かんけいrelation $$R$$R は、その表ひょうの内うち「成立せいりつする」と判断はんだんしたマスの集合しゅうごうである。

関係かんけいrelationを変かえるとは、採用さいようする順序対じゅんじょついordered pairを変かえることである。母体ぼたいとなる $$A\times B$$A\times B を固定こていしている限かぎり、第だい 1 成分せいぶんは $$A$$A から、第だい 2 成分せいぶんは $$B$$B から来くるという型かたは保存ほぞんされる。

表ひょうの見方みかたは、逆関係ぎゃくかんけいinverse relationでは行ぎょうと列れつcolumnを入いれ替かえること、関係かんけいの合成ごうせいcomposition of relationsでは中間ちゅうかんの元げんelementを経由けいゆすることにも接続せつぞくする。

5重要じゅうような性質せいしつproperty

$$A$$A 上うえの二項関係にこうかんけいbinary relation $$R$$R に対たいして、次つぎの性質せいしつpropertyを考かんがえる。表ひょうの $$a,b,c$$a,b,c はすべて $$A$$A の任意にんいの元げんelementとする。

対称性たいしょうせいsymmetryと反対称性はんたいしょうせいantisymmetryは名前なまえが似にているが、意味いみは反対はんたいではない。

対称性たいしょうせいsymmetryと反対称性はんたいしょうせいantisymmetryは同時どうじに成立せいりつすることも、両方りょうほうとも失敗しっぱいすることもある。等号とうごうの関係かんけいは両方りょうほうを満みたす典型例てんけいれいであり、名前なまえだけで反対はんたいの性質せいしつだと判断はんだんしない。

6例題れいだい：整除関係せいじょかんけいdivisibility relationを判定はんていする

6.1問題もんだい

$$A=\{1,2,3,6\}$$A=\{1,2,3,6\} 上うえの関係かんけいrelation $$R$$R を、$$aRb$$aRb とは「$$a$$a が $$b$$b を割わり切きる」ことだと定義ていぎする。$$R$$R が反射性はんしゃせいreflexivity、反対称性はんたいしょうせいantisymmetry、推移性すいいせいtransitivityを満みたすことを確認かくにんせよ。

6.2解説かいせつ

反射性はんしゃせいreflexivityについて、任意にんいの $$a\in A$$a\in A に対たいして $$a=a·1$$a=a\cdot1 なので、$$a$$a は $$a$$a を割わり切きる。したがって $$aRa$$aRa である。

反対称性はんたいしょうせいantisymmetryについて、$$aRb$$aRb かつ $$bRa$$bRa とする。すると $$b=ak$$b=ak、$$a=b\ell$$a=b\ell を満みたす正せいの整数せいすうinteger $$k,\ell$$k,\ell が存在そんざいする。したがって $$a=ak\ell$$a=ak\ell である。$$a\in A$$a\in A なので $$a\ne 0$$a\ne0 であり、両辺りょうへんを $$a$$a で割わって $$1=k\ell$$1=k\ell を得える。$$k,\ell$$k,\ell は正せいの整数せいすうintegerなので $$k=\ell =1$$k=\ell=1 であり、$$a=b$$a=b である。

推移性すいいせいtransitivityについて、$$aRb$$aRb かつ $$bRc$$bRc とする。すると $$b=ak$$b=ak、$$c=b\ell$$c=b\ell と書かける。したがって $$c=a\left(k\ell \right)$$c=a(k\ell) であり、$$aRc$$aRc である。

7見分みわけ方かたと関連かんれんリンク

• 「$$a$$a と $$b$$b が結むすばれるか」を判定はんていするなら、関係かんけいrelationである。
• 同おなじ集合しゅうごうsetの中なかで対象たいしょうどうしを比較ひかくするなら、二項関係にこうかんけいbinary relationである。
• 「同類どうるいに分わける」なら同値関係どうちかんけいequivalence relationを疑うたがう。
• 「大小だいしょうや前後ぜんごとして比較ひかくする」なら順序関係じゅんじょかんけいorder relationを疑うたがう。

8演習えんしゅうリンク