関係かんけいrelationの合成ごうせいcompositionと閉包へいほうclosure

Composition合成ごうせい and closure閉包へいほう of relations関係かんけい

1導入どうにゅう

関係かんけいrelationを一回いっかいだけ確認かくにんするのではなく、「関係かんけいを続つづけて使つかうとどこへ到達とうたつできるか」を扱あつかいたい場合ばあいがある。たとえば、駅えきどうしの直通ちょくつうの関係かんけいが与あたえられたとき、乗のり換かえを許ゆるせばどこへ行いけるかを知しりたい。この発想はっそうが関係かんけいrelationの合成ごうせいcompositionである。

閉包へいほうclosureは、ある性質せいしつpropertyを満みたすために不足ふそくしている順序対じゅんじょついordered pairを最小限さいしょうげん追加ついかする操作そうさである。

合成ごうせいcompositionでは「1 回かいで行いける」ことと「何回なんかいか使つかえば行いける」ことを区別くべつする。閉包へいほうclosureは元もとの関係かんけいrelationを含ふくんだまま性質せいしつを満みたすようにするので、既存きそんの順序対じゅんじょついordered pairは失うしなわれない。

1Introduction

Sometimes we do not want to check a relation関係かんけい only once; we want to know where repeated use of the relation can reach. For example, if direct train connections are given, we may want to know what stations are reachable with transfers. This idea is composition合成ごうせい of relations.

A closure閉包へいほう is an operation that adds the minimum missing ordered pairs順序対じゅんじょつい needed to satisfy a property性質せいしつ.

Composition distinguishes what is reachable in one use of a relation from what is reachable after finitely many uses. A closure retains every pair in the original relation while adding what is needed, so no existing pair is lost.

2用語ようごと定義ていぎ：合成ごうせいcomposition

$$R\subseteq A\times B$$R\subseteq A\times B、$$S\subseteq B\times C$$S\subseteq B\times C を関係かんけいrelationとする。合成関係ごうせいかんけいcomposite relation $$S\circ R\subseteq A\times C$$S\circ R\subseteq A\times C を

で定義ていぎする。これは「$$a$$a から $$b$$b へ $$R$$R で進すすみ、$$b$$b から $$c$$c へ $$S$$S で進すすめる」ことを表あらわす。

2Terms and definition: composition合成ごうせい

Let $$R\subseteq A\times B$$R\subseteq A\times B and $$S\subseteq B\times C$$S\subseteq B\times C be relations関係かんけい. Define the composite relation合成関係ごうせいかんけい $$S\circ R\subseteq A\times C$$S\circ R\subseteq A\times C by

This says that we can move from $$a$$a to $$b$$b by $$R$$R and then from $$b$$b to $$c$$c by $$S$$S.

3用語ようごと定義ていぎ：恒等関係こうとうかんけいidentity relationと逆関係ぎゃくかんけいinverse relation

$$A$$A 上うえの恒等関係こうとうかんけいidentity relationを

と書かく。また、$$R\subseteq A\times B$$R\subseteq A\times B に対たいする逆関係ぎゃくかんけいinverse relation $$R^{-1}\subseteq B\times A$$R^{-1}\subseteq B\times A を

で定義ていぎする。

3Terms and definitions: identity relation恒等関係こうとうかんけい and inverse relation逆関係ぎゃくかんけい

The identity relation恒等関係こうとうかんけい on $$A$$A is written

For $$R\subseteq A\times B$$R\subseteq A\times B, the inverse relation逆関係ぎゃくかんけい $$R^{-1}\subseteq B\times A$$R^{-1}\subseteq B\times A is

4閉包へいほうclosureとは何なにか

この節せつでは $$R\subseteq A\times A$$R\subseteq A\times A を $$A$$A 上うえの関係かんけいrelationとする。

反射閉包はんしゃへいほうreflexive closureは、反射性はんしゃせいreflexivityを満みたすために必要ひつような $$(a,a)$$(a,a) を追加ついかした関係かんけいrelationである。

対称閉包たいしょうへいほうsymmetric closureは、逆向ぎゃくむきの順序対じゅんじょついordered pairを追加ついかした関係かんけいrelationである。

推移閉包すいいへいほうtransitive closureは、$$aRb$$aRb と $$bRc$$bRc から必要ひつようになる $$aRc$$aRc を繰くり返かえし追加ついかした最小さいしょうの推移的すいいてきtransitiveな関係かんけいrelationであり、$$R^{+}$$R^+ と書かく。

4What is closure閉包へいほう?

In this section, let $$R\subseteq A\times A$$R\subseteq A\times A be a relation関係かんけい on $$A$$A.

The reflexive closure反射閉包はんしゃへいほう adds the self-pairs $$(a,a)$$(a,a) needed for reflexivity反射性はんしゃせい.

The symmetric closure対称閉包たいしょうへいほう adds reverse ordered pairs順序対じゅんじょつい.

The transitive closure推移閉包すいいへいほう, denoted by $$R^{+}$$R^+, is the smallest transitive推移的すいいてき relation関係かんけい obtained by repeatedly adding pairs $$aRc$$aRc forced by $$aRb$$aRb and $$bRc$$bRc.

5方針ほうしん

閉包へいほうclosureを作つくるときは、「性質せいしつを満みたすまで何なにを追加ついかするか」を追跡ついせきする。ただし、元もとの関係かんけいrelationを壊こわしてはいけない。閉包へいほうclosureは削除さくじょではなく追加ついかの操作そうさである。

ここで経路けいろpathとは、$$aRb$$aRb、$$bRc$$bRc のように関係かんけいrelationの矢印やじるしを有限回ゆうげんかい続つづけて辿たどる列れつである。有向ゆうこうグラフdirected graphという語ごは、元げんelementを点てん、順序対じゅんじょついordered pairを矢印やじるしとして描えがく見方みかただけを指さす。

反射閉包はんしゃへいほうreflexive closureは対角成分たいかくせいぶんを追加ついかし、対称閉包たいしょうへいほうsymmetric closureは矢印やじるしを逆向ぎゃくむきにも追加ついかし、推移閉包すいいへいほうtransitive closureは経路けいろで到達とうたつできる先さきを直接ちょくせつの関係かんけいrelationとして追加ついかする。

最小さいしょうの追加ついかminimal additionであることも閉包へいほうの一部いちぶである。つまり、元もとの関係かんけいrelationを含ふくみ、求もとめる性質せいしつを満みたすどの関係かんけいrelationにも、閉包へいほうで追加ついかした順序対じゅんじょついordered pairは含ふくまれる。

5Strategy

When constructing a closure閉包へいほう, track what must be added until the desired property性質せいしつ holds. The original relation関係かんけい must not be destroyed. A closure is an adding operation, not a deleting operation.

Here a path経路けいろ means a finite chain that follows relation arrows, such as $$aRb$$aRb and then $$bRc$$bRc. The term directed graph有向ゆうこうグラフ means only the viewpoint of drawing elements元げん as points and ordered pairs順序対じゅんじょつい as arrows.

The reflexive closure反射閉包はんしゃへいほう adds diagonal pairs, the symmetric closure対称閉包たいしょうへいほう adds reverse arrows, and the transitive closure推移閉包すいいへいほう adds direct relation pairs for destinations reachable by paths.

Being a minimal addition最小さいしょうの追加ついか is also part of closure. That is, every relation関係かんけい that contains the original relation and satisfies the desired property must contain the ordered pairs順序対じゅんじょつい added by the closure.

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

関係かんけいrelationを有向ゆうこうグラフとして見みると、合成ごうせいcompositionは 2 本ほんの矢印やじるしを続つづけて進すすむことである。推移閉包すいいへいほうtransitive closureは、何本なんぼんかの矢印やじるしを辿たどって到達とうたつできるなら、直接ちょくせつの矢印やじるしも追加ついかしたものと考かんがえられる。

この見方みかたでは、推移閉包すいいへいほうtransitive closureは到達可能性とうたつかのうせいを記録きろくする関係かんけいrelationである。元もとの関係かんけいrelationは「1 歩ぽで行いける」、推移閉包すいいへいほうtransitive closureは「何なに歩ぽかで行いける」を表あらわす。

経路けいろpathの長ながさで考かんがえると、反射閉包はんしゃへいほうreflexive closureは長ながさ 0 の移動いどうを許ゆるし、推移閉包すいいへいほうtransitive closureは正せいの長ながさの経路けいろで到達とうたつできる先さきを直接ちょくせつの関係かんけいとして加くわえる。

6Intuitive explanation

If a relation関係かんけい is viewed as a directed graph, composition合成ごうせい means following two arrows in sequence. The transitive closure推移閉包すいいへいほう can be thought of as adding a direct arrow whenever a destination is reachable by following some number of arrows.

In this view, the transitive closure is the relation関係かんけい that records reachability. The original relation means “reachable in one step,” while the transitive closure means “reachable in some positive number of steps.”

In terms of path length, the reflexive closure反射閉包はんしゃへいほう allows movement of length $$0$$0, while the transitive closure推移閉包すいいへいほう adds destinations reachable by paths of positive length as direct relation pairs.

7例題れいだい：推移閉包すいいへいほうtransitive closureを作つくる

7.1問題もんだい

$$A=\{1,2,3\}$$A=\{1,2,3\} 上うえの関係かんけいrelation $$R=\left\{\right(1,2),(2,3\left)\right\}$$R=\{(1,2),(2,3)\} の推移閉包すいいへいほうtransitive closureを求もとめよ。

7Worked example: construct a transitive closure推移閉包すいいへいほう

7.1Problem

Find the transitive closure推移閉包すいいへいほう of the relation関係かんけい $$R=\left\{\right(1,2),(2,3\left)\right\}$$R=\{(1,2),(2,3)\} on $$A=\{1,2,3\}$$A=\{1,2,3\}.

7.2解説かいせつ

$$1R2$$1R2 かつ $$2R3$$2R3 なので、推移性すいいせいtransitivityを満みたすには $$1R3$$1R3 が必要ひつようである。したがって $$(1,3)$$(1,3) を追加ついかする。

追加後ついかごの関係かんけいrelationは

である。これ以上いじょう新あたらしく追加ついかする順序対じゅんじょついordered pairはない。よってこれが推移閉包すいいへいほうtransitive closureである。

7.2Explanation

Because $$1R2$$1R2 and $$2R3$$2R3, transitivity推移性すいいせい requires $$1R3$$1R3. Therefore add $$(1,3)$$(1,3).

The resulting relation関係かんけい is

No further ordered pair順序対じゅんじょつい is forced, so this is the transitive closure推移閉包すいいへいほう.

8証明しょうめい補足ほそく：推移閉包すいいへいほうtransitive closureの最小性さいしょうせい

集合しゅうごう $$A$$A 上うえの関係かんけい $$R$$R に対たいして、$$R$$R の反復はんぷくを

と再帰的さいきてきに定義ていぎする。$$(a,b)\in R^n$$(a,b)\in R^n は、$$a$$a から $$b$$b へ $$R$$R の矢印やじるしをちょうど $$n$$n 本ほん辿たどる経路けいろpathがあることを意味いみする。この記法きほうを用もちいると、推移閉包すいいへいほうtransitive closureは

と書かける。

$$R^{+}$$R^+ は $$R$$R を含ふくむ。また、$$(a,b)\in R^{+}$$(a,b)\in R^+、$$(b,c)\in R^{+}$$(b,c)\in R^+ なら、ある $$m,n\text{[PARSE ERROR: Undefined("Command("ge")")]}1$$m,n\ge 1 が存在そんざいして $$(a,b)\in R^m$$(a,b)\in R^m、$$(b,c)\in R^n$$(b,c)\in R^n である。経路けいろpathを連結れんけつすれば $$(a,c)\in R^{m+n}$$(a,c)\in R^{m+n} なので $$(a,c)\in R^{+}$$(a,c)\in R^+ である。

さらに、$$S\subseteq A\times A$$S\subseteq A\times A が $$R\subseteq S$$R\subseteq S を満みたす $$A$$A 上うえの推移的すいいてきな関係かんけいなら、すべての $$n\text{[PARSE ERROR: Undefined("Command("ge")")]}1$$n\ge1 について $$R^n\subseteq S$$R^n\subseteq S であることを数学的帰納法すうがくてききのうほうmathematical inductionで示しめせる。基底段階きていだんかいでは $$R^1=R\subseteq S$$R^1=R\subseteq S である。帰納法きのうほうの仮定かてい $$R^n\subseteq S$$R^n\subseteq S のもとで $$(a,c)\in R^{n+1}=R\circ R^n$$(a,c)\in R^{n+1}=R\circ R^n とすると、ある $$b\in A$$b\in A が存在そんざいして $$(a,b)\in R^n\subseteq S$$(a,b)\in R^n\subseteq S かつ $$(b,c)\in R\subseteq S$$(b,c)\in R\subseteq S となる。$$S$$S の推移性すいいせいより $$(a,c)\in S$$(a,c)\in S なので、$$R^{n+1}\subseteq S$$R^{n+1}\subseteq S である。よって $$R^{+}\subseteq S$$R^+\subseteq S であり、$$R^{+}$$R^+ は $$R$$R を含ふくむ推移的すいいてきな関係かんけいの中なかで最小さいしょうである。

8Proof supplement: minimality of the transitive closure推移閉包すいいへいほう

For a relation関係かんけい $$R$$R on a set $$A$$A, define its iterates recursively by

The statement $$(a,b)\in R^n$$(a,b)\in R^n means that a path経路けいろ of exactly $$n$$n arrows of $$R$$R leads from $$a$$a to $$b$$b. With this notation, the transitive closure推移閉包すいいへいほう is

The relation $$R^{+}$$R^+ contains $$R$$R. Also, if $$(a,b)\in R^{+}$$(a,b)\in R^+ and $$(b,c)\in R^{+}$$(b,c)\in R^+, then for some $$m,n\text{[PARSE ERROR: Undefined("Command("ge")")]}1$$m,n\ge 1, $$(a,b)\in R^m$$(a,b)\in R^m and $$(b,c)\in R^n$$(b,c)\in R^n. Concatenating the paths gives $$(a,c)\in R^{m+n}$$(a,c)\in R^{m+n}, so $$(a,c)\in R^{+}$$(a,c)\in R^+.

Finally, let $$S\subseteq A\times A$$S\subseteq A\times A be any transitive relation on $$A$$A with $$R\subseteq S$$R\subseteq S. We prove $$R^n\subseteq S$$R^n\subseteq S for every $$n\text{[PARSE ERROR: Undefined("Command("ge")")]}1$$n\ge1 by mathematical induction数学的帰納法すうがくてききのうほう. The base case is $$R^1=R\subseteq S$$R^1=R\subseteq S. For the induction step, assume $$R^n\subseteq S$$R^n\subseteq S and take $$(a,c)\in R^{n+1}=R\circ R^n$$(a,c)\in R^{n+1}=R\circ R^n. There is some $$b\in A$$b\in A with $$(a,b)\in R^n\subseteq S$$(a,b)\in R^n\subseteq S and $$(b,c)\in R\subseteq S$$(b,c)\in R\subseteq S. Transitivity of $$S$$S gives $$(a,c)\in S$$(a,c)\in S, so $$R^{n+1}\subseteq S$$R^{n+1}\subseteq S. Hence $$R^{+}\subseteq S$$R^+\subseteq S, and $$R^{+}$$R^+ is the smallest transitive relation containing $$R$$R.

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

• 関係かんけいを続つづけて使つかうなら、合成ごうせいcompositionを考かんがえる。
• 足たりない自己じこループを追加ついかするなら、反射閉包はんしゃへいほうreflexive closureである。
• 逆向ぎゃくむきの矢印やじるしを追加ついかするなら、対称閉包たいしょうへいほうsymmetric closureである。
• 到達可能性とうたつかのうせいを直接ちょくせつの関係かんけいrelationとして記録きろくするなら、推移閉包すいいへいほうtransitive closureである。

9How to identify it and related links

• If a relation is used repeatedly, think of composition合成ごうせい.
• If missing self-loops are added, it is the reflexive closure反射閉包はんしゃへいほう.
• If reverse arrows are added, it is the symmetric closure対称閉包たいしょうへいほう.
• If reachability is recorded as a direct relation関係かんけい, it is the transitive closure推移閉包すいいへいほう.

10演習えんしゅうリンク

10Exercise links