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

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.

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.

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

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.

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.

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.

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.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推移閉包すいいへいほう.

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.

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推移閉包すいいへいほう.

10Exercise links