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