5
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.