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
Ron a setXis the smallest relation onXthat containsRand 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.