[Image 1]
Hey it's a me again @drifter1!
Today we continue with Mathematics, and more specifically the branch of "Discrete Mathematics", in order to get into Relation Closures.
So, without further ado, let's get straight into it!
Consider a set A and the wide range of relations on A. In the previous part it was shown that these relations can satisfy various properties, such as being reflexive, symmetric or transitive. If P is such a property than a relation with property P is a P-relation.
A P-closure of any arbitrary relation R on A, indicated by P(R), is a P-relation, which is related to relation R as follows:
In other words, a P-closure is simply the process of adding the least amount of ordered pairs to R, such that R satisfies a given property P.
The reflexive closure is easy to obtain.
For a given set A, Δ is the diagonal or equality relation on A, defined as:
Δ is basically the smallest possible relation which satisfies the reflexive property on A.
Thus, for any given relation R on set A, obtaining the reflexive closure is simply a union operation of R with Δ:
The symmetric closure is also easy to obtain.
For a relation R on set A, R-1 is the inverse of R, such that:
Obtaining the symmetric closure is thus simply a union operation of R with R-1:
Obtaining a transitive closure is more complicated.
The transitive closure or connectivity relation or star closure of a relation R on set A with n-elements is obtained from the following equation:
The exponentials of R indicate compositions of relations:
For two given sets R and S, the composition is defined as follows:
This is easier to calculate using a matrix multiplication technique, which will be explained in the example below...
Consider the following set and relation:
Let's calculate the three closures!
The equality relation is:
And so, the reflexive closure is:
The inverse relation is:
And thus, the symmetric closure is:
The relation can be re-written as a matrix:
where the rows are the first members and columns the second members. A '0' specifies the absence of the pair, whilst a '1' the presence of the pair.
The transitive (star) closure is the union of R, R2, R3 and R4.
Obtaining the corresponding MR2 matrix is as simple as multiplying the MR matrix by itself:
Only the absence or presence matters and so the result is kept in 0-1 format.
Obtaining MR3 is a multiplication of MR2 by MR, resulting in:
And lastly, MR4 = MR3 x MR, yielding:
The transitive closure in matrix form, MR*, is the union of all these matrices and thus equal to:
which can be represented in "set form" as follows:
Mathematical equations used in this article, have been generated using quicklatex.
Block diagrams and other visualizations were made using draw.io.
And this is actually it for today's post!
Next time we will continue on with more on Equivalence Relations and maybe even on Partial Order Relations, and the corresponding Partially Ordered Sets (POSET)...
See ya!
Keep on drifting!
