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^+=\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 |
