So, as far as binary relations go, I have a firm grasp on the symmetric, anti-symmetric, and reflexive relations. However, when it comes to transitive relations, I run into a block.
In this problem, for example, I had to determine the transitive closures for the given set that contained: (1,1) (1,2) (2,3) (3,2) (4,4)
The additional elements that would enable this set to be a transitive relation were: (1,3) (2,2) (3,3)
I think I understand that if there is a (1,2) and a (2,3) then there must also be a (1,3). I see that there is a (2,3), but why doesn't there have to be a (3, 4) and a (2,4)? I need some enlightenment as to how I can properly go about determining transitive closures, or determining if a completed relation set includes the right elements to make it transitive.
Best Answer
Let's make a list of the pairs together with the ones that can be chained with them by transitivity \begin{array}{cccc} 1 & 2 & \to \\ \hline (1,1) & (1,1) & (1,1) \\ (1,1) & (1,2) & (1,2) \\ (1,2) & (2,3) & \color{red}{(1,3)} \\ (2,3) & (3,2) & \color{red}{(2,2)} \\ (3,2) & (2,3) & \color{red}{(3,3)} \\ (4,4) & (4,4) & (4,4) \end{array} In the first column, a pair; in the second column a pair that can be chained to the first one; in the third column, what's necessary to satisfy transitivity. Red color means the needed pair is missing.
Now we have to repeat the check with the newly added pairs \begin{array}{cccc} 1 & 2 & \to \\ \hline (1,1) & (1,1) & (1,1) & *\\ (1,1) & (1,2) & (1,2) & * \\ (1,2) & (2,2) & (2,2) \\ (1,2) & (2,3) & (1,3) & * \\ (1,3) & (3,2) & (1,2) \\ (1,3) & (3,3) & (1,3) \\ (2,2) & (2,2) & (2,2) \\ (2,2) & (2,3) & (2,3) \\ (2,3) & (3,2) & (2,2) & * \\ (2,3) & (3,3) & (2,3) \\ (3,2) & (2,3) & (3,3) & * \\ (3,3) & (3,2) & (3,2) \\ (3,3) & (3,3) & (3,3) \\ (4,4) & (4,4) & (4,4) & * \end{array} None has been marked red, because all pairs in the third column belong to the “second stage” relation. The $*$ denotes a row that has already been considered in the first stage.
If at this stage still some pairs had been missing, a third stage would be necessary.
In this case, however, we're done: the transitive closure is $$ \{(1,1),(1,2),(1,3),(2,2),(2,3),(3,2),(3,3),(4,4)\} $$