Reflexive, Transitive and Symmetric Relations

Question

I am having difficulty grasping the concepts of and the relations (Transitive, Reflexive, Symmetric) while there is one way that given a relation we can determine which property it has. but if we want to define sets that are for example both symmetric and transitive, or all three, or any two? some examples in the following table would be really helpful to clear stuff out.

For each of the eight lines of the table below, a relation on { 1 , 2 , 3 } that fits the description.

Reflexive Symmetric Transitive

True True True

True True False

True False True

True False False

False True True

False True False

False False True

False False False

Answer 1

In all examples, $x$ and $y$ range over elements of the set $\{1, 2, 3\}$.

All combinations of Reflexive, Symmetric, Transitive:

True True True: $\{(x, y) : x = y\}$

True True False: $\{(x, y) : |x - y| \leq 1\}$

True False True: $\{(x, y) : x \leq y\}$

True False False: $\{(x, y) : x \leq y $ and $|x - y| \leq 1\}$

False True True: $\{(x, y) : x + y = 5\}$

False True False: $\{(x, y) : |x - y| = 1\}$

False False True: $\{(x, y) : x < y\}$

False False False: $\{(x, y) : x = y + 1\}$

Answer 2

The following might be helpful:

In the case of reflexive being "true", this requires that you have $\left(1,1\right), \left(2,2\right), \left(3,3\right)$ in your relation, so that can be used as a building block of the first four cases.

Furthermore: $\{ \left(1,1\right), \left(2,2\right), \left(3,3\right) \}$ is reflexive, symmetric, and transitive, so you can modify this to remove some of the properties. For example:

$\{ \left(1,1\right), \left(2,2\right), \left(3,3\right), \left(1,2\right) \}$ is reflexive, not symmetric, and transitive.

$\{ \left(1,1\right), \left(2,2\right), \left(3,3\right), \left(1,3\right), \left(3,2\right) \}$ is reflexive, not symmetric, and not transitive.

I hope this helps.

Answer 3

The best way to see the properties of a relation $R$ is if you make a 2D table where you put a check mark in row $a$, column $b$ whenever $aRb$ holds. For example, the following is a random relation on $\{1,2,3\}$: \begin{array}{c|ccc} R & 1 & 2 & 3 \\ \hline 1 & \checkmark & & \checkmark\\ 2 & \checkmark & \checkmark & \\ 3 & & \checkmark \end{array} Note that you have to be careful to have the elements in the same order in the top row and left column. As set, this relation reads $$R = \{(1, 1), (1, 3), (2, 1), (2, 2), (3, 2)\}$$

Then you can easily read off the various properties from the table.

Reflexivity

A relation is reflexive if there is a check mark in every field of the diagonal. The relation $R$ above clearly is not reflexive because there is no check mark in position $(3,3)$: \begin{array}{c|ccc} R & 1 & 2 & 3 \\ \hline 1 & {\color{red}\checkmark} & & \checkmark\\ 2 & \checkmark & {\color{red}\checkmark} & \\ 3 & & \checkmark & {\color{red}{\unicode{10008}}} \end{array} This can easily be fixed to give a new, reflexive relation $R_2$: \begin{array}{c|ccc} R_r & 1 & 2 & 3 \\ \hline 1 & {\color{red}{\checkmark}} & & \checkmark\\ 2 & \checkmark & {\color{red}{\checkmark}} & \\ 3 & & \checkmark & {\color{red}{\checkmark}} \end{array} This procedure of adding in the missing diagonal entries is known as reflexive closure.

Obviously the smallest reflexive relation is the one which has check marks only in the diagonal, that is, every element only relates to itself. This is the equality relation: \begin{array}{c|ccc} = & 1 & 2 & 3 \\ \hline 1 & {\color{red}{\checkmark}} & & \\ 2 & & {\color{red}{\checkmark}} & \\ 3 & & & {\color{red}{\checkmark}} \end{array}

Symmetry

A relation is symmetric if its table is symmetric under mirroring. Clearly the relation $R$ above is not symmetric, as the condition fails for example on the first two elements: \begin{array}{c|ccc} R & 1 & 2 & 3 \\ \hline 1 & \checkmark & {\color{red}{\unicode{10008}}} & \checkmark\\ 2 & {\color{red}\checkmark} & \checkmark & \\ 3 & & \checkmark \end{array} One way to fix this is to add a check mark whenever there is one on the opposite side: \begin{array}{c|ccc} R_s & 1 & 2 & 3 \\ \hline 1 & \checkmark & {\color{red}{\checkmark}} & {\color{green}\checkmark}\\ 2 & {\color{red}\checkmark} & \checkmark & {\color{blue}\checkmark}\\ 3 & {\color{green}\checkmark} & {\color{blue}\checkmark} \end{array} This method of making a relation symmetric is known as symmetric closure.

The simplest symmetric relation is the empty relation which doesn't relate anything to anything, that is, $aRb$ is always false: \begin{array}{c|ccc} E & 1 & 2 & 3 \\ \hline 1 & & & \\ 2 & & & \\ 3 & & & \end{array}

Transitivity

Transitivity is the most complex property to check. We start by selecting one of the check marks: \begin{array}{c|ccc} R & 1 & 2 & 3 \\ \hline 1 & \checkmark & & \checkmark\\ 2 & {\color{red}{\checkmark}} & \checkmark & \\ 3 & & \checkmark \end{array} Next we look at the element of that column, and consider the corresponding row: \begin{array}{c|ccc} R & {\color{blue}1} & 2 & 3 \\ \hline {\color{blue}1} & {\color{blue}{\checkmark}} & & {\color{blue}\checkmark} \\ 2 & {\color{red}{\checkmark}} & \checkmark & \\ 3 & & \checkmark \end{array} Next, we select from that row another check mark: \begin{array}{c|ccc} R & {\color{blue}1} & 2 & 3 \\ \hline {\color{blue}1} & {\color{blue}{\checkmark}} & & {\color{red}\checkmark} \\ 2 & {\color{red}{\checkmark}} & \checkmark & \\ 3 & & \checkmark \end{array} Then if the relation is transitive, no matter which of the available check marks we selected in the first and third step, there has to also be a check mark in the same row as the first and the same column as the second check mark. In our case, we see that $R$ is not transitive, as the check mark for our selection is missing: \begin{array}{c|ccc} R & {\color{blue}1} & 2 & 3 \\ \hline {\color{blue}1} & {\color{blue}{\checkmark}} & & {\color{red}\checkmark} \\ 2 & {\color{red}{\checkmark}} & \checkmark & {\color{red}{\unicode{10008}}}\\ 3 & & \checkmark \end{array} Again, we can fix this by recursively adding all the missing check marks to our relation: \begin{array}{c|ccc} R_t & 1 & 2 & 3 \\ \hline 1 & \checkmark & {\color{red}\checkmark} & \checkmark\\ 2 & \checkmark & \checkmark & {\color{red}\checkmark} \\ 3 & {\color{red}\checkmark} & \checkmark & {\color{red}\checkmark} \end{array} As you probably have guessed by now, this procedure is known as transitive closure. In the case of $R$, this happens to result in the full relation, in which every element is related to every element.

As we have seen before, to check for transitivity, we have to choose two check marks, therefore the smallest relation where transitivity can fail has two entries (while technically it is possible to select the same check mark twice, this is only possible if that check mark is on the diagonal, in which case the check mark which has to be there is also the same check mark, which obviously is there, or we could not have selected it). Therefore the smallest transitive relation again is the empty relation.

Systematically constructing relations that have a certain subset of those properties

Since for each of the relations we have a closure operation that adds that property to a relation, the obvious idea to systematically construct relations that have a certain subset of those properties is to start with a relation that has no such property, and do the appropriate closures.

However one has to be careful, as a closure can also add other properties; for example, the relation $R$ above was neither reflexive, nor symmetric, nor transitive, but its transitive closure is the full relation, which has all three properties.

Now the reflexive closure is harmless in that respect: It can cause neither symmetry nor transitivity in a set that wasn't symmetric or transitive to begin with.

For the other two closures, it is easy to see that if the starting relation is a subset of a strict order (that is, when sorting the elements in the table accordingly, all check marks are in the upper triangle outside the diagonal), then the transitive closure will also be a subset of that strict order (and thus not symmetric), while the symmetric closure will never cause transitivity (because the missing check marks are on the same side of the diagonal, but symmetric closure adds only check marks on the other side). For the three numbers in our set, the obvious choice is the standard order of the numbers, $1<2<3$.

None of the properties

So let's start with constructing such a relation that has none of the three properties. Let's start by filling in the first check mark in the upper triangle: \begin{array}{c|ccc} & 1 & 2 & 3 \\ \hline 1 & & {\color{red}\checkmark} & \\ 2 & & & \\ 3 & & \end{array} Having just one check mark, this is still transitive. Since the check mark is in column $2$, to make the transitivity test fail, we need a check mark in row $3$. For the reasons mentioned before, we also want to stay in the upper triangle, which in this case already fixes our choice: \begin{array}{c|ccc} R_0 & 1 & 2 & 3 \\ \hline 1 & & \checkmark & \\ 2 & & & {\color{red}\checkmark}\\ 3 & & \end{array} We now can check that this is indeed neither reflexive, nor symmetric, nor transitive. As set this relation reads: $$R_0=\{(1,2),(2,3)\}$$ Indeed, for the reasons explained above, a relation having none of the properties cannot be any simpler than this.

Only reflexive

To get a relation that's reflexive, but neither symmetric nor transitive, we now can simply do the reflexive closure of $R_0$, which adds the diagonal elements: \begin{array}{c|ccc} R_1 & 1 & 2 & 3 \\ \hline 1 & {\color{red}\checkmark} & \checkmark & \\ 2 & & {\color{red}\checkmark} & \checkmark \\ 3 & & & {\color{red}\checkmark} \end{array} As set, this relation reads $$R_1 = \{(1, 1), (1, 2), (2, 2), (2, 3), (3, 3)\}$$

Only symmetric

Similarly, to get a relation that is symmetric, but not reflexive or transitive, we do the symmetric closure on $R_0$, adding to check marks: \begin{array}{c|ccc} R_2 & 1 & 2 & 3 \\ \hline 1 & & \checkmark & \\ 2 & {\color{red}\checkmark} & & \checkmark\\ 3 & & {\color{red}\checkmark} \end{array} As set this relation reads $$R_2 = \{(1, 2), (2, 1), (2, 3), (3, 2)\}$$

Reflexive and symmetric

To get a relation that is both reflexive and symmetric, but not transitive, we can just do the reflexive closure on $R_2$: \begin{array}{c|ccc} R_3 & 1 & 2 & 3 \\ \hline 1 & {\color{red}\checkmark} & \checkmark & \\ 2 & {\checkmark} & {\color{red}\checkmark} & \checkmark\\ 3 & & {\checkmark} & {\color{red}\checkmark} \end{array} As set this relation reads $$R_3 = \{(1, 1), (1, 2), (2, 1), (2, 2), (2, 3), (3, 2), (3, 3)\}$$

Only transitive

To get a relation that is transitive, but neither reflexive nor symmetric, we apply transitive closure on the starting relation $R_0$. This happens to add only one check mark: \begin{array}{c|ccc} R_4 & 1 & 2 & 3 \\ \hline 1 & & \checkmark & {\color{red}\checkmark} \\ 2 & & & \checkmark \\ 3 & & \end{array} As set this relation reads $$R_4 = \{(1, 2), (1, 3), (2, 3)\}$$ Note that this is the less-than relation.

Transitive and reflexive

To get a transitive and reflexive relation, we apply reflexive closure to $R_5$: \begin{array}{c|ccc} R_4 & 1 & 2 & 3 \\ \hline 1 & {\color{red}\checkmark} & \checkmark & {\checkmark} \\ 2 & & {\color{red}\checkmark} & \checkmark \\ 3 & & & {\color{red}\checkmark} \end{array} As set this relation reads $$R_5 = \{(1, 1), (1, 2), (1, 3), (2, 2), (2, 3), (3, 3)\}$$ Note that this is the less-or-equal relation.

Symmetric and transitive

To get a transitive and symmetric, but not reflexive relation, we apply symmetric closure to $R_4$: \begin{array}{c|ccc} R_6 & 1 & 2 & 3 \\ \hline 1 & & \checkmark & {\checkmark} \\ 2 & {\color{red}\checkmark} & & \checkmark \\ 3 & {\color{red}\checkmark} & {\color{red}\checkmark} \end{array} As set this relation reads $$R_6 = \{(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)\}$$ Note that this is the not-equal relation.

Reflexive, symmetric and transitive

Finally, to get a relation that has all three properties, we apply reflexive closure to $R_6$: \begin{array}{c|ccc} R_7 & 1 & 2 & 3 \\ \hline 1 & {\color{red}\checkmark} & \checkmark & {\checkmark} \\ 2 & {\checkmark} & {\color{red}\checkmark} & \checkmark \\ 3 & {\checkmark} & \checkmark & {\color{red}\checkmark} \end{array} As set this relation reads $$R_7 = \{(1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3)\}$$ Note that this is the full relation.