Checking if a relation on a set is reflexive, transitive, symmetric

relations

I am trying to understand how one can check to see if a relation on a set satisfies the properties of reflexivity, transitivity and symmetry.

To be more specific, I work with two examples in which I try to figure out whether these 3 properties hold. As you will see, within the examples I have some questions, but overall I am interested to know if this is how someone would "rigorously" check if the 3 properties hold. I apologize for the lengthy examples but I think that by writing my answers as detailed as I can , this will help others understand if there is a gap in my thinking.

Example 1:

Let $R_1$ be a relation on the set $X = \{a, b, c\}$

$R_1 = \{ (a,c) , (c,a) , (a,b) , (b,a) , (b,c) , (c,b) , (a,a)\} $

Reflexivity requires that $\forall x \in X: xR_1x$ , or in other words that $\forall x \in X: (x,x) \in R_1$

Since $(b,b)$ and $(c,c)$ do not belong in $R_1$, the relation $R_1$ on $X$ is not symmetric.

For transitivity, I want to check if $\forall x,x',x'' \in X :$ if $xR_1x'$ and $x'R_1x''$ , then this implies that $xR_1x''$

I observe that:

$aR_1b$ and $bR_1c$ $\Rightarrow$ $aR_1c$ , which is true

$aR_1c$ and $cR_1b$ $\Rightarrow$ $aR_1b$ , true

$bR_1a$ and $aR_1c$ $\Rightarrow$ $bR_1c$ , true

$bR_1c$ and $cR_1a$ $\Rightarrow$ $bR_1a$ , true

$cR_1a$ and $aR_1b$ $\Rightarrow$ $cR_1b$ , true

$cR_1b$ and $bR_1a$ $\Rightarrow$ $cR_1a$ , true

Thus, I believe that the relation is indeed transitive.

For symmetry, I check if $\forall x,x' \in X:$ if $xR_1x'$ then this implies that $x'R_1x$

Again, I observe that:

$aR_1b$ $\Rightarrow$ $bR_1a$ , which is true

$aR_1c$ $\Rightarrow$ $cR_1a$ , true

$bR_1a$ $\Rightarrow$ $aR_1b$ , true

$bR_1c$ $\Rightarrow$ $cR_1b$ , true

$cR_1a$ $\Rightarrow$ $aR_1c$ , true

$cR_1b$ $\Rightarrow$ $bR_1c$ , true

If I have correctly applied the definitions in order to check if the properties hold, then the second example is the one that puzzles me.

Example 2:

Let $R_2$ be a second relation on the set $X$.

$R_2= \{ (b,c) , (c,b) , (a,a) , (b,b) , (c,c)\}$

$R_2$ is reflexive since $(x,x) \in R_2$ $\forall x \in X$

My question is how can I check if the transitivity property holds, given that I cannot find 3 distinct elements $x,x',x'' \in X$ for which $xR_2x'$ and $x'R_2x'$' , so that I can check if $xR_2x''$ holds or not.

Lastly for symmetry, I think that the relation is indeed symmetric since the only pairs which I can test for symmetry are the following:

$bR_2c$ $\Rightarrow$ $cR_2b$ , which is true

and

$cR_2b$ $\Rightarrow$ $bR_2c$ , which is also true.

Best Answer

Your $R_1$ is not reflexive, is symmetric, is not transitive. Your $R_2$ is reflexive, is symmetric, and is transitive.

With regards to checking quickly by inspection small examples like this... I refer you to what I have already written here many years ago.

Restated again, you can draw yourself a graph (technically a directed multigraph) of your relation by drawing a vertex corresponding to each of your elements in your set, and then drawing a directed edge (with an arrow) from one element to the other if the first element is related to the second according to your relation. In the event that you have a pair $(x,y)$ such that both $x$ is related to $y$ and also that $y$ is related to $x$, instead draw a double-edged arrow between these. In the event that you have an element related to itself, draw a "loop" for that edge instead.

The different types of properties relations could have can be reworded in terms of what you see in these graphs:

  • Reflexive: All vertices have loops

  • Symmetric: If any arrows exist, they are all double-sided. (Still counts as symmetric even if no arrows exist. Loops don't matter)

  • Antisymmetric: If any arrows exist, they are all single-sided. (Still counts as antisymmetric even if no arrows exist. Loops don't matter)

  • Transitive: If there exists a directed path along arrows from a point to another (not necessarily distinct) point that takes any number of steps... then there must also be a direct path that can get you there in a single step.

In your first example, there was a path you could take from $b$ back to $b$, so we needed a way to do that in a single step, but you failed to have the pair $(b,b)$ in your relation and so it was not transitive.

With regards to equivalence relations, the corresponding graph of an equivalence relation would be one where each connected component were a complete graph with all possible self-loops. Those different connected components of course corresponding to the equivalence classes for the equivalence relation.

You ask if there is a rigorous way to check. If you insist, you could rephrase all of these again using matrices. By building yourself a matrix $M$ where the $i$'th row $j$'th column entry is a $1$ if the $i$'th element is related to the $j$'th in the relation... then you have the following properties:

  • Reflexivity: The main diagonal consists of all $1$'s
  • Symmetry: The matrix is symmetric
  • Transitivity: All of the zero elements of the matrix $M$ are also zero in $M^n$ for all $n>1$, in particular for $M^2$. Alternatively phrased, all nonzero entries of $M^2$ must correspond to nonzero entries in $M$.

For such small examples I prefer just looking at the graph, possibly just with my mind's eye and not even drawing it out on paper. I almost never find a situation where I need to organize my thoughts with a matrix like this, however I suppose if all of the information were presented in a jumbled up or convoluted manner I might.

Related Question