Properties of Relations

A binary relation $$R$$ defined on a set $$A$$ may have the following properties:

• Reflexivity
• Irreflexivity
• Symmetry
• Antisymmetry
• Asymmetry
• Transitivity

Next we will discuss these properties in more detail.

Reflexive Relation

A binary relation $$R$$ is called reflexive if and only if $$\forall a \in A,$$ $$aRa.$$ So, a relation $$R$$ is reflexive if it relates every element of $$A$$ to itself.

Examples of reflexive relations:

1. The relation $$\ge$$ ("is greater than or equal to") on the set of real numbers.
2. Similarity of triangles.
3. The relation $${R = \left\{ {\left( {1,1} \right),\left( {1,2} \right),}\right.}$$ $${\left.{\kern-2pt\left( {2,2} \right),\left( {3,3} \right),\left( {3,1} \right)} \right\}}$$ on the set $$A = \left\{ {1,2,3} \right\}.$$

Reflexive relations are always represented by a matrix that has $$1$$ on the main diagonal. The digraph of a reflexive relation has a loop from each node to itself.

Irreflexive Relation

A binary relation $$R$$ on a set $$A$$ is called irreflexive if $$aRa$$ does not hold for any $$a \in A.$$ This means that there is no element in $$R$$ which is related to itself.

Examples of irreflexive relations:

1. The relation $$\lt$$ ("is less than") on the set of real numbers.
2. Relation of one person being son of another person.
3. The relation $${R = \left\{ {\left( {1,2} \right),\left( {2,1} \right),}\right.}$$ $${\left.{\kern-2pt\left( {1,3} \right),\left( {2,3} \right),\left( {3,1} \right)} \right\}}$$ on the set $$A = \left\{ {1,2,3} \right\}.$$

The matrix of an irreflexive relation has all $$0'\text{s}$$ on its main diagonal. The directed graph for the relation has no loops.

Symmetric Relation

A binary relation $$R$$ on a set $$A$$ is called symmetric if for all $$a,b \in A$$ it holds that if $$aRb$$ then $$bRa.$$ In other words, the relative order of the components in an ordered pair does not matter - if a binary relation contains an $$\left( {a,b} \right)$$ element, it will also include the symmetric element $$\left( {b,a} \right).$$

Examples of symmetric relations:

1. The relation $$=$$ ("is equal to") on the set of real numbers.
2. The relation "is perpendicular to" on the set of straight lines in a plane.
3. The relation $${R = \left\{ {\left( {1,1} \right),\left( {1,2} \right),}\right.}$$ $${\left.{\kern-2pt\left( {2,1} \right),\left( {1,3} \right),\left( {3,1} \right)} \right\}}$$ on the set $$A = \left\{ {1,2,3} \right\}.$$

For a symmetric relation, the logical matrix $$M$$ is symmetric about the main diagonal. The transpose of the matrix $$M^T$$ is always equal to the original matrix $$M.$$ In a digraph of a symmetric relation, for every edge between distinct nodes, there is an edge in the opposite direction.

Antisymmetric Relation

A binary relation $$R$$ on a set $$A$$ is said to be antisymmetric if there is no pair of distinct elements of $$A$$ each of which is related by $$R$$ to the other. So, an antisymmetric relation $$R$$ can include both ordered pairs $$\left( {a,b} \right)$$ and $$\left( {b,a} \right)$$ if and only if $$a = b.$$

Examples of antisymmetric relations:

1. The relation $$\ge$$ ("is greater than or equal to") on the set of real numbers.
2. The subset relation $$\subseteq$$ on a power set.
3. The relation $${R = \left\{ {\left( {1,1} \right),\left( {2,1} \right),}\right.}$$ $${\left.{\kern-2pt\left( {2,3} \right),\left( {3,1} \right),\left( {3,3} \right)} \right\}}$$ on the set $$A = \left\{ {1,2,3} \right\}.$$

In a matrix $$M = \left[ {{a_{ij}}} \right]$$ representing an antisymmetric relation $$R,$$ all elements symmetric about the main diagonal are not equal to each other: $${a_{ij}} \ne {a_{ji}}$$ for $$i \ne j.$$ The digraph of an antisymmetric relation may have loops, however connections between two distinct vertices can only go one way.

Asymmetric Relation

An asymmetric binary relation is similar to antisymmetric relation. The difference is that an asymmetric relation $$R$$ never has both elements $$aRb$$ and $$bRa$$ even if $$a = b.$$

Every asymmetric relation is also antisymmetric. The converse is not true. If an antisymmetric relation contains an element of kind $$\left( {a,a} \right),$$ it cannot be asymmetric. Thus, a binary relation $$R$$ is asymmetric if and only if it is both antisymmetric and irreflexive.

Examples of asymmetric relations:

1. The relation $$\gt$$ ("is greater than") on the set of real numbers.
2. The family relation "is father of".
3. The relation $$R = \left\{ {\left( {2,1} \right),\left( {2,3} \right),\left( {3,1} \right)} \right\}$$ on the set $$A = \left\{ {1,2,3} \right\}.$$

The matrix for an asymmetric relation is not symmetric with respect to the main diagonal and contains no diagonal elements. The digraph of an asymmetric relation must have no loops and no edges between distinct vertices in both directions.

Transitive Relation

A binary relation $$R$$ on a set $$A$$ is called transitive if for all $$a,b,c \in A$$ it holds that if $$aRb$$ and $$bRc,$$ then $$aRc.$$

This condition must hold for all triples $$a,b,c$$ in the set. If there exists some triple $$a,b,c \in A$$ such that $$\left( {a,b} \right) \in R$$ and $$\left( {b,c} \right) \in R,$$ but $$\left( {a,c} \right) \notin R,$$ then the relation $$R$$ is not transitive.

Examples of transitive relations:

1. The relation $$\gt$$ ("is greater than") on the set of real numbers.
2. The relation "is parallel to" on the set of straight lines.
3. The relation $${R = \left\{ {\left( {1,2} \right),\left( {1,3} \right),}\right.}$$ $${\left.{\kern-2pt\left( {2,2} \right),\left( {2,3} \right),\left( {3,3} \right)} \right\}}$$ on the set $$A = \left\{ {1,2,3} \right\}.$$

In a matrix $$M = \left[ {{a_{ij}}} \right]$$ of a transitive relation $$R,$$ for each pair of $$\left({i,j}\right)-$$ and $$\left({j,k}\right)-$$entries with value $$1$$ there exists the $$\left({i,k}\right)-$$entry with value $$1.$$ The presence of $$1'\text{s}$$ on the main diagonal does not violate transitivity.

See solved problems on Page 2.