Relations - 5
Properties of Binary Relations
A binary relation $R$ on a set $A$ is:
Reflexive
When $xRx$ for all $x\in A$.
\[\forall x\ A(x)\Rightarrow xRx\]This means that if two of the same elements are compared successfully then the relation is reflexive.
As example of a relation that is non-reflexive is $<$ as the left must be different to the right.
Symmetric
When $xRy$ implies $yRx$ for all $x,y\in A$:
\[\forall x,y\ xRy\Rightarrow yRx\]This is similar to Facebook friends. If you are friends with one person they have to be your friend too.
An example that is non-symmetric is $\leq$ as they are not necessarily comparable.
Antisymmetric
When $xRy$ and $yRx$ imply $x=y$ for all $x,y\in A$:
\[\forall x,y\ xRy\text{ and } yRx\Rightarrow y = x\]This means that if you can swap the elements and the relation still holds true then the elements must be equal. This is the same as the $\leq$ relation.
The $L$ relation from before doesn’t satisfy this property as two different words with the same length are not the same.
Transitive
When $xRy$ and $yRz$ imply $xRz$ for all $x,y,z\in A$:
\[\forall x,y,z\ xRy\text{ and }yRz\Rightarrow xRz\]This is the same as the ordering example from before. Thus the relationship $<$ satisfies this property.
Examples
Which of the following define a relation that is reflexive, symmetric, antisymmetric of transitive?
- $x$ divides $y$ on the set $\Bbb{Z^+}$ of positive integers.
- This relations is reflexive, antisymmetric and transitive.
- $x\neq y$ on the set $\Bbb{Z}$ of integers.
- This relations is symmetric and transitive.
- $x$ has the same age as $y$ on the set of people.
- This relations is reflexive, symmetric and transitive.