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

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?

• I deleted my answer because I misread the question - it is asking for antisymmetric and not symmetric (which would make an equivalence relation). Nov 27, 2016 at 12:54
• I'm puzzled as to the notion of "most efficient" or "easiest". For some relations $R$ it may be impossible to extend it to be reflexive, transitive, and antisymmetric. Nov 27, 2016 at 13:15
• @hardmath Sorry for being not that precise in my answer, I'm not a mathematician, not very good at that :) Nov 27, 2016 at 13:18
• @MichaelBurr still Thank's a lot for your time! Nov 27, 2016 at 13:19
• @Javiator: For this $R$ you’d have a $10\times10$ matrix with rows $0$ through $9$ and columns $0$ through $9$. The entry in row $i$, column $j$ is $1$ if $\langle i,j\rangle\in R$ and $0$ otherwise. There is an algorithm, Warshall’s algorithm, that starts with this matrix and mechanically constructs the matrix of the transitive closure of $R$. However, if you’ve not worked with this approach, the algorithm will probably seem rather complicated. I explained it with a smaller example in an answer to this question. Nov 28, 2016 at 0:39

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.
• This is a good way to organize the problem (and what I would do on paper). Nov 27, 2016 at 12:54

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.

• Thank you very much for your answer, but this is exactly the brute force way I'm talking about. Nov 27, 2016 at 12:20
• @Javiator The transitivifying must in some sense be done by brute force. You could structure it differently to make it look smarter, but in some sense, every pair needs to be compared to every other pair to see if transitivity has anything to say about it. Nov 27, 2016 at 12:21
• @Javiator I added an alternative method that is basically the same thing, but may feel better. It's how I would personally do it, as long as the original $R$ isn't too large. Nov 27, 2016 at 13:10