Given a relation $R$, what is the most efficient approach to extend $R$ such that it is reflexive, transitive and antisymmetric?

Question

I'm working on some exercises from my text book about discrete mathematics. I have given some relations $R_1,...,R_n$, which I have to extend such that the relations are reflexive, transitive and antisymmetric. Afterwards, I need the extended relations for subsequent tasks.

Is there a more efficient way than just going through each tuple via a brute force approach to see if there are any missing tuples? The brute force approach is really time-consuming.

What is the easiest ways to extend, e.g., $R=\{(7, 1), (9, 8), (2, 6), (0, 6), (3, 9), (4, 6), (1, 8), (6, 7), (5, 6)\}$ on $[0,9]$ such that it is reflexive, transitive and antisymmetric?

Answer 1

A more convenient way of organizing the problem is as follows:

Given a set $A = [0,9]$ and a relation $R=\{(7, 1), (9, 8), (2, 6), (0, 6), (3, 9), (4, 6), (1, 8), (6, 7), (5, 6)\}$ on $A$.

1. For all $a\in A$, add $(a,a)$ to $R$
2. Draw a directed graph $G=(V,E)$ with $V=A$ and $E=\{(i,j)|(i,j) \in R\}$
3. For transitivity: Starting with any $x\in V$, add $(x,y)$ to $R$ where $y$ can be reached via directed edges from $x$. Repeat this for all $x\in V$.
4. For antisymmetry: Check that there is no directed edge between two vertices in both directions.

Answer 2

Given $R=\{(7, 1), (9, 8), (2, 6), (0, 6), (3, 9), (4, 6), (1, 8), (6, 7), (5, 6)\}$, we want first extend it to be transitive, because that's the biggest one.

What we do is we take the first pair $(7,1)$, compare it to every pair that comes after it, and see if transitivity has anything to say. What that means is we look for pairs that have $1$ as first element of $7$ as second element. There are two of those: $(1, 8)$ and $(6, 7)$. That means you need to add $(7, 8)$ and $(6, 1)$. Put them at the end.

We now have $\{(7, 1), (9, 8), (2, 6), (0, 6), (3, 9), (4, 6), (1, 8), (6, 7), (5, 6), (7,8), (6,1)\}$, and we've taken care of the first pair. Now take the second pair, $(9,8)$ and do the same thing (looking only at pairs that come after it, since we've already compared it to $(7,1)$). This time we see that we need to add $(3, 8)$, so we do that. Keep going, going until you get to the end, and you've added the bare minimum to make $R'$ transitive.

Then to make it reflexive, we need to add all pairs $(n, n)$, so we do that. Lastly, you need to check that you haven't made it non-anti-symmetric, and you're done.

Edit: One way of transitivifying that doesn't feel as much like brute force (but really is the same thing) would be to draw. Take a piece of paper, or a blackboard, or whatever your preferred medium is, and write all numbers from $0$ to $9$. Then take each pair $(i,j)$ and draw an arrow from $i$ to $j$. Once you've done that for all the pairs, can take any number that has both an arrow $a$ pointing to it and an arrow pointing $b$ away from it. Now draw an arrow pointing from the origin of $a$ to the target of $b$, if there isn't one there already. Keep doing this until all such arrows have been drawn. Now every arrow represents a pair that needs to be in $R'$ for it to be transitive.

A few pointers on how to do this more easily: Don't draw the numbers randomly or in order or in a circle at the start. Rather, look at the pairs that are in $R$ and take some hints from them, like start by drawing $1$ above $7$ with some room between them. Draw $9$ below $8$. Draw $8$ above $1$. This way, most arrows will be pointing upwards, and it's easier to follow them and see whether you've missed any.