I have a question regarding an image. I'm currently studying binary relations and the following image confused me:

Binary relations

What got me confused is that the page from which I got the link (http://www.cs.odu.edu/~toida/nerzic/content/relation/property/property.html) says that the graph in (a) is reflexive, symmetric and transitive.

According to what I've learned so far a set is reflexive if for all $x$, $x$ bears a relation to $x$, the graph has this property. Now, for the other two relations, symmetric and transitive, it does not hold. Because for it to be symmetric it would need a path from both points back to each other (because a relation is symmetric iff $x$ has a relation to $y$ and back). The transitive property also does not hold because there are only 2 points and transitivity needs at least three.

I would like some proof that explains why the graph is transitive and symmetric.


2 Answers 2


It's somewhat of a logical subtlety.

  1. A relation $R$ is transitive iff: $\forall x,y,z : (xRy \wedge yRz) \Rightarrow xRz$.
  2. A relation $R$ is symmetric iff: $\forall x,y : xRy \Rightarrow yRx$.

Universally quantified formulas like 1 and 2 are only false if you can find a counter-example. This is because an implication $P \Rightarrow Q$ is true whenever $P$ is false, irrespective of the truth value of $Q$. Since there are no counter-examples in (a), transitivity and symmetry are trivially true.

Similarly, and for your information, over an empty domain a relation $R$ would be trivially reflexive, since you would not be able to find an element $x$ for which $xRx$ does not hold.


The relation $\sim$ is reflexive if whenever $x \sim y$, it is also true that $y \sim x$. In other words, if there is no pair $x, y$ with $x \sim y$ and $y \not\sim x$, then the relation is symmetric. Think of it this way: If there is no asymmetry, then it is symmetric. The same goes for transitivity. If there is no violation of transitivity, then the relation is transitive.

Consider this - do you agree that the relation in example $(e)$ is transitive? I am quite sure you do. But observe that the bottom element is not related to any other element. Is that a violation of transitivity? No, of course not. Similarly, even if no element is related to any other (like in $(a)$), there is no actual violation of transitivity.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .