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

Basics of relations関係かんけい

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が入はいっているかで性質せいしつを判定はんていできる。したがって、後あとで反射性はんしゃせい・対称性たいしょうせい・反対称性はんたいしょうせい・推移性すいいせいを調しらべるときも、同おなじ集合しゅうごうとしての見方みかたを使つかう。

1Introduction

The central question for a relation関係かんけい is whether connections between objects対象たいしょう can be recorded by choosing which ordered pairs順序対じゅんじょつい to include. A relation is not a vague word; it is a subset部分集合ぶぶんしゅうごう of a Cartesian product直積集合ちょくせきしゅうごう.

This definition lets statements that look different, such as “$$a$$a equals $$b$$b,” “$$a$$a is below $$b$$b,” “$$a$$a divides $$b$$b,” and “$$a$$a and $$b$$b have the same remainder when divided by a fixed positive integer $$m$$m,” be treated in the same form形式けいしき.

Once these statements are formalized, their properties can be determined by which ordered pairs順序対じゅんじょつい are included rather than by differences in wording. The same set-theoretic viewpoint will be used below to test reflexivity, symmetry, antisymmetry, and transitivity.

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の特別とくべつな場合ばあいである。

2Terms and definitions

For sets集合しゅうごう $$A,B$$A,B, a relation関係かんけい from $$A$$A to $$B$$B is a subset部分集合ぶぶんしゅうごう of $$A\times B$$A\times B.

When $$(a,b)\in R$$(a,b)\in R, we say that $$a$$a is related to $$b$$b by $$R$$R, and often write

When $$A=B$$A=B, a relation $$R\subseteq A\times A$$R\subseteq A\times A is called a binary relation二項関係にこうかんけい on $$A$$A. Equivalence relations同値関係どうちかんけい and order relations順序関係じゅんじょかんけい are special kinds of binary relations.

3方針ほうしん

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

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

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

3Strategy

When studying a relation関係かんけい, first identify the ambient Cartesian product直積集合ちょくせきしゅうごう. Then identify which ordered pairs順序対じゅんじょつい are included.

To prove a property性質せいしつ, check that the condition holds for all relevant elements元げん. One example cannot prove reflexivity反射性はんしゃせい or transitivity推移性すいいせい. To show failure, one counterexample反例はんれい is enough.

To prove a universal condition全称条件ぜんしょうじょうけん, begin with arbitrary elements. To show that a property fails, exhibit one ordered pair順序対じゅんじょつい or tuple that violates its condition.

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を経由けいゆすることにも接続せつぞくする。

4Intuitive explanation

A relation関係かんけい can be viewed as marking cells in a table. Each ordered pair順序対じゅんじょつい $$(a,b)$$(a,b) in $$A\times B$$A\times B corresponds to the cell at row $$a$$a and column列れつ $$b$$b. The relation $$R$$R is the set of cells judged to hold.

Changing a relation means changing which ordered pairs are included. As long as the ambient product $$A\times B$$A\times B is fixed, the type is preserved: first components come from $$A$$A and second components come from $$B$$B.

The table viewpoint also prepares for later operations: an inverse relation逆関係ぎゃくかんけい swaps rows and columns, while composition合成ごうせい of relations follows a connection through an intermediate element元げん.

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

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

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

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

5Important properties性質せいしつ

For a binary relation二項関係にこうかんけい $$R$$R on $$A$$A, consider the following properties性質せいしつ. In the table, $$a,b,c$$a,b,c denote arbitrary elements元げん of $$A$$A.

Symmetry対称性たいしょうせい and antisymmetry反対称性はんたいしょうせい have similar names, but their meanings are not opposites.

They may hold simultaneously, and they may also both fail. Equality is a standard example satisfying both, so their names alone should not be used to treat them as opposite properties.

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を満みたすことを確認かくにんせよ。

6Worked example: check the divisibility relation整除関係せいじょかんけい

6.1Problem

On $$A=\{1,2,3,6\}$$A=\{1,2,3,6\}, define a relation関係かんけい $$R$$R by letting $$aRb$$aRb mean “$$a$$a divides $$b$$b.” Check that $$R$$R satisfies reflexivity反射性はんしゃせい, antisymmetry反対称性はんたいしょうせい, and 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 である。

6.2Explanation

For reflexivity反射性はんしゃせい, every $$a\in A$$a\in A satisfies $$a=a·1$$a=a\cdot1, so $$a$$a divides itself. Hence $$aRa$$aRa.

For antisymmetry反対称性はんたいしょうせい, suppose $$aRb$$aRb and $$bRa$$bRa. Then there are positive integers整数せいすう $$k,\ell$$k,\ell such that $$b=ak$$b=ak and $$a=b\ell$$a=b\ell. Hence $$a=ak\ell$$a=ak\ell. Since $$a\in A$$a\in A, $$a\ne 0$$a\ne0, so dividing by $$a$$a gives $$1=k\ell$$1=k\ell. Because $$k,\ell$$k,\ell are positive integers, $$k=\ell =1$$k=\ell=1, and therefore $$a=b$$a=b.

For transitivity推移性すいいせい, suppose $$aRb$$aRb and $$bRc$$bRc. Then $$b=ak$$b=ak and $$c=b\ell$$c=b\ell. Thus $$c=a\left(k\ell \right)$$c=a(k\ell), so $$aRc$$aRc.

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

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

7How to identify it and related links

• If the question is whether $$a$$a and $$b$$b are connected, think of a relation関係かんけい.
• If objects in the same set集合しゅうごう are compared, think of a binary relation二項関係にこうかんけい.
• If objects are grouped into classes, suspect an equivalence relation同値関係どうちかんけい.
• If objects are compared by size or order, suspect an order relation順序関係じゅんじょかんけい.

8演習えんしゅうリンク

8Exercise links