Transitive Closure and Reflexive-Transitive Closure \(R^+, R^*\)

Closure (Mathematics)

Closure is a property said to be satisfied by a set under a given operation if and only if performing the operation on members of the set always produces a member of the same set. (Wikipedia)

• binary relation: 2-ary relation (\(R \subseteq S \times S\))
• P closure operator: cl(R) is the strongest or the smallest relation (\(cl(R) \subseteq S \times S\)) that contains R (\(R \subseteq cl(R)\)) and the property P holds (P(Q)=true).
• a binary relation R is transitive: \(\forall x,y,z: S \bullet (((x,y) \in R \land (y, z) \in R) \implies (x,z) \in R)\)
• for example, \(>, =, \geq, \leq\) are transitive, but "is parent of" is not.
• a binary relation R is reflexive: \(\forall x: S \bullet ((x,x) \in R)\)
• for example, \(=,\geq,\leq\) are reflexive, but > is not reflexive

For example,

• reflexive closure: \(cl_{ref}(R)\) is the smallest relation that contains R and is reflexive.
• transitive closure: \(cl_{trn}(R)\), or \(R^+\) is the smallest relation that contains R and is transitive.
• reflexive–transitive closure: \(R^*\) is the smallest relation that contains R and is both transitive and reflexive.

Definitions

• \(R^r=R \cup id\ S\) - reflexive closure
• \(R^s=R \cup R^\sim\) - symmetric closure 
• \(R^*=R^+ \cup id\ S\)

Alternative Definitions in terms of iterations (Z notation)

• iteration of relation: \(R^k=R;R;...;R = R;R^{k-1}=R^{k-1};R\)
• \(R^0=id\ S\)
• \(R^+=\bigcup\{k:\mathbb{N}_1 \bullet R^k\}\) 
• \(R^+=\bigcup\{k:\mathbb{N} \bullet R^k\}\) 

Applications

• transitive closure of a directed graph likes cities connection by railways or airplanes: means all possible routes from one city to another city, then can be used to calculate the shortest path from one place to another place
• \(R = \{(A,B),(B,C),(B,D),(C,A)\}\) - direct routes between two cities
• \(R^2=R;R=\{(A,C), (A,D),(B,A),(C,B)\}\) - one stop routes between two cities
• \(R^3=R^2;R=\{(A,C), (A,D),(B,A),(C,B)\};\{(A,B),(B,C),(B,D),(C,A)\}=\{(A,A),(B,B),(C,C),(C,D)\}\) - two stop routes between two cities
• \(R^4=R^3;R=\{(A,A),(B,B),(C,C),(C,D)\};\{(A,B),(B,C),(B,D),(C,A)\}=\{(A,B),(B,C),(B,D),(C,A)\}\) - equal to R
• finally, \(R^+=R \cup R^2 \cup R^3=\{(A,B),(B,C),(B,D),(C,A),(A,C), (A,D),(B,A),(C,B),(A,A),(B,B),(C,C),(C,D)\}\)

Example