# Transitive closure

Apart of learning more about Reactive programming, I came across the term Transitive Closure which has roots in Mathematics. Below I set out to decompose the concept into smaller concepts to clarify understanding.

A “set” is a strict list of elements. For example, `set X` can be a list of numbers `{1,2,3}`. An element, or number in this case, is said to be a member of the `set X` if it is found in `set X`. The number `1` has membership in `set X`.

Let’s also define another `set Y` to be `{4,5,6}`.

2 elements can be paired together to represent a list. The numbers 1 and 2 is a list of 2 elements or a pair. In addition to defining what elements are included and how many elements are in the list, the order can be specified. We can order `1` to be first and `2` second, or we can order `2` to be first and `1` second. In Mathematics, this list usually is written via a tuple, more specifically a 2-tuple to specify that there are only 2 elements, by arranging the elements in a specific order within `"( )"` Parenthesis. The tuple is a limited or finite ordered list able to contain an arbitrary number of elements. The lists described above can be written as two 2-tuples or ordered pairs; `(1,2)` and `(2,1)`.

Multiple ordered pairs can be grouped in a relation which represents elements within an ordered pair are related. In this example, the specific relation is a binary or 2-place relation. The word “binary” indicates or involves the quantity of two. This is typically found in Computer Science to mean the Binary numbers `0` and `1`; `On` or `Off`.

Here is a binary relation for the sets X and Y denoted by the letter `R`.
`R = {(1,4), (1,5), (5,1)}`
`1` is related to `4`“. “`1` is related to `5`“. “`5` is related to `1`“.

Notice there are only 3 ordered pairs in this binary relation. This is a subset of the Cartesian product of the `sets X and Y`. The Cartesian product is a set of all combinations of all the elements in the sets. The full Cartesian products of `sets X and Y` is

```X * Y = {1,2,3} * {4,5,6} = {(1,4), (1,5), (1,6), (2,4), (2,5), (2,6), (3,4), (3,5), (3,6)} Y * X = {4,5,6} * {1,2,3} = {(4,1), (4,2), (4,3), (5,1), (5,2), (5,3), (6,1), (6,2), (6,3)}```

With the ordered pairs and binary relation defined, the word transitive can be explained. The transitive relation means by knowing the two relationships of some elements, a third relationship can be established. If we said a is related to b and b is related to c, then the relationship a is related to c can be established.

A more concrete example can be the following. John is friends with Jane. Jane is friends with Fred. There is a transitive relation between John and Friend since they both share the friend Jane in common.

The second word in Transitive Closure is Closure. In Mathematics, a set can be said to be closed or exhibit the Closure property when some operation or procedure done on a set only strictly outputs members already in the set. In the context of sets and binary relations, the relevant operation or procedure can be finding the relations of elements in a set.

Let’s now pull all of this together along with continuing with the previously defined `set X`, `set Y`, and the binary relation `R`.

```set X = {1,2,3} set Y = {4,5,6} R = {(1,4), (1,5), (5,1)}```

We see “`1` is related to `4`“. “`1` is related to `5`“. “`5` is related to `1`“. Looking at the two relationships “`5` is related to `1`” and “`1` is related to `4`“, we can establish a new transitive relation “`5` is related to `4`“. No other transitive relations can be established. This new pair `(5,4)` can be added to the ordered pairs in R. Since R is a strict set, we’d have to define a new set which includes the new ordered pair. The new set can be written as

`R' = {(1,4), (1,5), (5,1), (5,4)}`.

Since no other ordered pairs are necessary to represent all the relations of the numbers in the original `R` set, we have found the transitive closure of the binary relation `R`.

The formal definition of a transitive closure is:

In mathematics, the transitive closure of a binary relation `R` on a set `X` is the smallest relation on `X` that contains `R` and is transitive. Wikipedia

This was an explanation of the concept Transitive Closure using underlying concepts.

For more resources, I found this video helpful in understanding Transitive Closures since it explains the concept further with a graph: Transitive Closure Video.

Let me know your thoughts or whether there are any inaccuracies in the explanation.