Note: Do not confuse binary operations (+, x, -, …) with relations. Recall the definition for a relation as:
A relation R on a set A is a subset R ⊆ A × A. We often abbreviate the statement (x, y) ∈ R as xRy.
For instance, the binary operation “x” has a numeric value: Yet a mathematical relation, for example “<“, has a True/False value: are both False expressions.
We want to look at some properties of relations. We will look at three properties for relation expressions:
Suppose A is a set with relation R, then
- Relation R is Reflexive if
- Relation R is Symmetric if
- Relation R is Transitive if
The first property tells us that if every element, x, in set A is related to itself, then the relation R acting on the set A is termed “reflective.”
The second property tells us that if “x is related to y” from set A implies that “y is also related to x,” then R is termed “symmetric.”
Lastly, if “x is related to y” and “y is related to z” implies that “x is also related to z,” then the relation R is termed “transitive.”
Let’s look at the following examples: with relation Then:
In other words is reflexive since every number in set A is equal to itself (i.e. are all true expressions)
In other words is not symmetric since we can find some numbers in A such that does not imply . For example, doesn’t imply
In other words is transitive. We can take any three numbers (x, y and z) from set A: whenever holds true, it implies . For instance, implies
Consider the next example: Here and R is the following relation on A: We want to check whether R is reflexive, symmetric or transitive.
- This relation is not reflexive. We know this because R doesn’t have the elements (e, e) so we cannot conclude that every element in A is related to itself under the relation R. Note however, that elements b, c and d are related to themselves since we have (b, b), (c, c) and (d, d) in R.
- The relation R is symmetric. We can see this because whenever we have xRy, it follows that yRx holds true as well (where x and y are any elements from set A). Unlike the reflexive property, we do not need the relation to hold FOR ALL elements in A. Rather, the condition for symmetry is that WHENEVER some relation holds in A, the reverse should also be implied. In other words: (b, c) implies (c, b); (b, d) implies (d, b) and finally (c, d) implies (d, c). We can also write: bRc and cRb; bRd and dRb; dRc and cRd.
- The relation R is also transitive. As with symmetry, the transitive property need not hold FOR ALL elements in A. Showing the transitive property will take a bit more work… For example: (d, b) and (b, c) implies (d, c). Similarly, (b, d) and (d, d) implies (b, d). We can do this for all the other pairs, too. In summary, (x, y) and (y, z) implies (x, z) where x, y and z are elements in A.
- So the relation R is symmetric and transitive.
Sometimes relations are simultaneously reflexive, symmetric and transitive. In such cases we call the relation an Equivalence Relation.