7.2: Properties of Relations

If \(R\) is a relation from \(A\) to \(A\), then \(R\subseteq A\times A\); we say that \(R\) is a relation on \(\mathbf{A}\).

Definition

A relation \(R\) on \(A\) is said to be

• reflexive if \((a,a)\in R\,a\) for all \(a\in A\),
• irreflexive if \((a,a)\notin R\) for all \(a\in A\),
• symmetric if \((a,b)\in R \Rightarrow (b,a)\in R\) for all \(a,b\in A\),
• antisymmetric if \([(a,b)\in R\,\wedge\,(b,a)\in R] \Rightarrow a=b\) for all \(a,b\in A\),
• transitive if \([(a,b)\in R\,\wedge\,(b,c)\in R] \Rightarrow (a,c)\in R\) for all \(a,b,c\in A\).

These are important definitions, so let us repeat them using the relational notation \(a\,R\,b\):

• reflexive if \(a\,R\,a\) for all \(a\in A\),
• irreflexive if \(a\!\not\!R\,a\) (that is, \(\overline{a\,R\,a}\)) for all \(a\in A\),
• symmetric if \(a\,R\,b \Rightarrow b\,R\,a\) for all \(a,b\in A\),
• antisymmetric if \([(a\,R\,b) \wedge (b\,R\,a)] \Rightarrow a=b\) for all \(a,b\in A\),
• transitive if \([(a\,R\,b) \wedge (b\,R\,c)] \Rightarrow a\,R\,c\) for all \(a,b,c\in A\).

Remark

A relation cannot be both reflexive and irreflexive. Hence, these two properties are mutually exclusive. If it is reflexive, then it is not irreflexive. If it is irreflexive, then it cannot be reflexive. Nonetheless, it is possible for a relation to be neither reflexive nor irreflexive.

Remark

Many students find the concept of symmetry and antisymmetry confusing. Even though the name may suggest so, antisymmetry is not the opposite of symmetry. It is possible for a relation to be both symmetric and antisymmetric, and it is also possible for a relation to be both non-symmetric and non-antisymmetric. A good way to understand antisymmetry is to look at its contrapositive: \[a\neq b \Rightarrow \overline{(a,b)\in R \,\wedge\, (b,a)\in R}. \nonumber\] Thus, if two distinct elements \(a\) and \(b\) are related (not every pair of elements need to be related), then either \(a\) is related to \(b\), or \(b\) is related to \(a\), but not both. Consequently, if we find distinct elements \(a\) and \(b\) such that \((a,b)\in R\) and \((b,a)\in R\), then \(R\) is not antisymmetric.

Example \(\PageIndex{1}\label{eg:SpecRel}\)

The empty relation is the subset \(\emptyset\). It is clearly irreflexive, hence not reflexive. To check symmetry, we want to know whether \(a\,R\,b \Rightarrow b\,R\,a\) for all \(a,b\in A\). More specifically, we want to know whether \((a,b)\in \emptyset \Rightarrow (b,a)\in \emptyset\). Since \((a,b)\in\emptyset\) is always false, the implication is always true. Thus the relation is symmetric. Likewise, it is antisymmetric and transitive.

The complete relation is the entire set \(A\times A\). It is clearly reflexive, hence not irreflexive. It is also trivial that it is symmetric and transitive. It is not antisymmetric unless \(|A|=1\).

The identity relation consists of ordered pairs of the form \((a,a)\), where \(a\in A\). In other words, \(a\,R\,b\) if and only if \(a=b\). It is reflexive (hence not irreflexive), symmetric, antisymmetric, and transitive.

Example \(\PageIndex{2}\label{eg:proprelat-02}\)

Consider the relation \(R\) on the set \(A=\{1,2,3,4\}\) defined by \[R = \{(1,1),(2,3),(2,4),(3,3),(3,4)\}. \nonumber\]

Since \((2,2)\notin R\), and \((1,1)\in R\), the relation is neither reflexive nor irreflexive.

We have \((2,3)\in R\) but \((3,2)\notin R\), thus \(R\) is not symmetric.

For any \(a\neq b\), only one of the four possibilities \((a,b)\notin R\), \((b,a)\notin R\), \((a,b)\in R\), or \((b,a)\in R\) can occur, so \(R\) is antisymmetric.

By going through all the ordered pairs in \(R\), we verify that whether \((a,b)\in R\) and \((b,c)\in R\), we always have \((a,c)\in R\) as well. This shows that \(R\) is transitive.

Therefore, \(R\) is antisymmetric and transitive.

Example \(\PageIndex{3}\label{eg:proprelat-03}\)

Define the relation \(S\) on the set \(A=\{1,2,3,4\}\) according to \[S = \{(2,3),(3,2)\}. \nonumber\]

Since \((1,1),(2,2),(3,3),(4,4)\notin S\), the relation \(S\) is irreflexive, hence, it is not reflexive.

Since we have only two ordered pairs, and it is clear that whenever \((a,b)\in S\), we also have \((b,a)\in S\). Hence, \(S\) is symmetric.

We have both \((2,3)\in S\) and \((3,2)\in S\), but \(2\neq3\). Hence, \(S\) is not antisymmetric.

Since \((2,3)\in S\) and \((3,2)\in S\), but \((2,2)\notin S\), the relation \(S\) is not transitive.

We conclude that \(S\) is irreflexive and symmetric.

hands-on exercise \(\PageIndex{1}\label{he:proprelat-01}\)

Define the relation \(R\) on the set \(\mathbb{R}\) as \[a\,R\,b \,\Leftrightarrow\, a\leq b. \nonumber\] Determine whether \(R\) is reflexive, irreflexive, symmetric, antisymmetric, or transitive.

hands-on exercise \(\PageIndex{2}\label{he:proprelat-02}\)

The relation \(S\) on the set \(\mathbb{R}^*\) is defined as \[a\,S\,b \,\Leftrightarrow\, ab>0. \nonumber\] Determine whether \(S\) is reflexive, irreflexive, symmetric, antisymmetric, or transitive.

Example \(\PageIndex{4}\label{eg:geomrelat}\)

Here are two examples from geometry. Let \({\cal T}\) be the set of triangles that can be drawn on a plane. Define a relation \(S\) on \({\cal T}\) such that \((T_1,T_2)\in S\) if and only if the two triangles are similar. It is easy to check that \(S\) is reflexive, symmetric, and transitive.

Let \({\cal L}\) be the set of all the (straight) lines on a plane. Define a relation \(P\) on \({\cal L}\) according to \((L_1,L_2)\in P\) if and only if \(L_1\) and \(L_2\) are parallel lines. Again, it is obvious that \(P\) is reflexive, symmetric, and transitive.

Example \(\PageIndex{5}\label{eg:proprelat-04}\)

The relation \(T\) on \(\mathbb{R}^*\) is defined as \[a\,T\,b \,\Leftrightarrow\, \frac{a}{b}\in\mathbb{Q}. \nonumber\]

Since \(\frac{a}{a}=1\in\mathbb{Q}\), the relation \(T\) is reflexive; it follows that \(T\) is not irreflexive.

The relation \(T\) is symmetric, because if \(\frac{a}{b}\) can be written as \(\frac{m}{n}\) for some integers \(m\) and \(n\), then so is its reciprocal \(\frac{b}{a}\), because \(\frac{b}{a}=\frac{n}{m}\).

Since \(\sqrt{2}\;T\sqrt{18}\) and \(\sqrt{18}\;T\sqrt{2}\), yet \(\sqrt{2}\neq\sqrt{18}\), we conclude that \(T\) is not antisymmetric.

If \(\frac{a}{b}, \frac{b}{c}\in\mathbb{Q}\), then \(\frac{a}{b}= \frac{m}{n}\) and \(\frac{b}{c}= \frac{p}{q}\) for some nonzero integers \(m\), \(n\), \(p\), and \(q\). Then \(\frac{a}{c} = \frac{a}{b}\cdot\frac{b}{c} = \frac{mp}{nq} \in\mathbb{Q}\). Hence, \(T\) is transitive.

Therefore, the relation \(T\) is reflexive, symmetric, and transitive.

hands-on exercise \(\PageIndex{3}\label{he:proprelat-03}\)

Consider the relation \(T\) on \(\mathbb{N}\) defined by \[a\,T\,b \,\Leftrightarrow\, a\mid b. \nonumber\] Determine whether \(T\) is reflexive, irreflexive, symmetric, antisymmetric, or transitive.

hands-on exercise \(\PageIndex{4}\label{he:proprelat-04}\)

The relation \(U\) on the set \(\mathbb{Z}^*\) is defined as \[a\,U\,b \,\Leftrightarrow\, a\mid b. \nonumber\] Determine whether \(U\) is reflexive, irreflexive, symmetric, antisymmetric, or transitive.

Example \(\PageIndex{6}\label{eg:proprelat-05}\)

The relation \(U\) on \(\mathbb{Z}\) is defined as \[a\,U\,b \,\Leftrightarrow\, 5\mid(a+b). \nonumber\]

• The relation \(U\) is not reflexive, because \(5\nmid(1+1)\).
• It is not irreflexive either, because \(5\mid(10+10)\).
• If \(5\mid(a+b)\), it is obvious that \(5\mid(b+a)\) because \(a+b=b+a\). Thus, \(U\) is symmetric.
• We claim that \(U\) is not antisymmetric. For example, \(5\mid(2+3)\) and \(5\mid(3+2)\), yet \(2\neq3\).
• It is not transitive either. For instance, \(5\mid(1+4)\) and \(5\mid(4+6)\), but \(5\nmid(1+6)\).
• The relation \(U\) is symmetric.

hands-on exercise \(\PageIndex{5}\label{he:proprelat-05}\)

Determine whether the following relation \(V\) on some universal set \(\cal U\) is reflexive, irreflexive, symmetric, antisymmetric, or transitive: \[(S,T)\in V \,\Leftrightarrow\, S\subseteq T. \nonumber\]

Example \(\PageIndex{7}\label{eg:proprelat-06}\)

Consider the relation \(V\) on the set \(A=\{0,1\}\) is defined according to \[V = \{(0,0),(1,1)\}. \nonumber\]

The relation \(V\) is reflexive, because \((0,0)\in V\) and \((1,1)\in V\). Hence, it is not irreflexive.

It is clearly symmetric, because \((a,b)\in V\) always implies \((b,a)\in V\).

Indeed, whenever \((a,b)\in V\), we must also have \(a=b\), because \(V\) consists of only two ordered pairs, both of them are in the form of \((a,a)\). It follows that \(V\) is also antisymmetric.

A similar argument shows that \(V\) is transitive.

The relation is reflexive, symmetric, antisymmetric, and transitive.

hands-on exercise \(\PageIndex{6}\label{he:proprelat-06}\)

Determine whether the following relation \(W\) on a nonempty set of individuals in a community is reflexive, irreflexive, symmetric, antisymmetric, or transitive: \[a\,W\,b \,\Leftrightarrow\, \mbox{$a$ and $b$ have the same last name}. \nonumber\]

Example \(\PageIndex{8}\label{eg:proprelat-07}\)

Define the relation \(W\) on a nonempty set of individuals in a community as \[a\,W\,b \,\Leftrightarrow\, \mbox{$a$ is a child of $b$}. \nonumber\]

• Nobody can be a child of himself or herself, hence, \(W\) cannot be reflexive. Instead, it is irreflexive.
• It is obvious that \(W\) cannot be symmetric.
• It may sound weird from the definition that \(W\) is antisymmetric: \[(a \mbox{ is a child of } b) \wedge (b\mbox{ is a child of } a) \Rightarrow a=b, \label{eqn:child}\] but it is true! The reason is, if \(a\) is a child of \(b\), then \(b\) cannot be a child of \(a\). This makes conjunction \[(a \mbox{ is a child of } b) \wedge (b\mbox{ is a child of } a) \nonumber\] false, which makes the implication (\ref{eqn:child}) true.
• A similar argument holds if \(b\) is a child of \(a\), and if neither \(a\) is a child of \(b\) nor \(b\) is a child of \(a\). No matter what happens, the implication (\ref{eqn:child}) is always true. Therefore \(W\) is antisymmetric.
• It may help if we look at antisymmetry from a different angle. The contrapositive of the original definition asserts that when \(a\neq b\), three things could happen:

1. \(a\) and \(b\) are incomparable (\(\overline{a\,W\,b}\) and \(\overline{b\,W\,a}\)), that is, \(a\) and \(b\) are unrelated;

and if \(a\) and \(b\) are related, then either

1. \(a\,W\,b\) but \(\overline{b\,W\,a}\), or
2. \(b\,W\,a\) but \(\overline{a\,W\,b}\).

Using this observation, it is easy to see why \(W\) is antisymmetric.

• It is clear that \(W\) is not transitive.

The relation is irreflexive and antisymmetric.

Instead of using two rows of vertices in the digraph that represents a relation on a set \(A\), we can use just one set of vertices to represent the elements of \(A\). A directed line connects vertex \(a\) to vertex \(b\) if and only if the element \(a\) is related to the element \(b\). If \(b\) is also related to \(a\), the two vertices will be joined by two directed lines, one in each direction. If \(a\) is related to itself, there is a loop around the vertex representing \(a\). See Problem 10 in Exercises 7.1.

From the graphical representation, we determine that the relation \(R\) is

• Reflexive if there is a loop at every vertex of \(G\).
• Irreflexive if \(G\) is loopless.
• Symmetric if every pair of vertices is connected by none or exactly two directed lines in opposite directions.
• Antisymmetric if every pair of vertices is connected by none or exactly one directed line.
• Transitive if for every unidirectional path joining three vertices \(a,b,c\), in that order, there is also a directed line joining \(a\) to \(c\).

The incidence matrix \(M=(m_{ij})\) for a relation on \(A\) is a square matrix. We find that \(R\) is

• Reflexive if every entry on the main diagonal of \(M\) is 1.
• Irreflexive if every entry on the main diagonal of \(M\) is 0.
• Symmetric if \(M\) is symmetric, that is, \(m_{ij}=m_{ji}\) whenever \(i\neq j\).
• Antisymmetric if \(i\neq j\) implies that at least one of \(m_{ij}\) and \(m_{ji}\) is zero, that is, \(m_{ij} m_{ji} = 0\).
• Transitive if \((M^2)_{ij} > 0\) implies \(m_{ij}>0\) whenever \(i\neq j\).

For instance, the incidence matrix for the identity relation consists of 1s on the main diagonal, and 0s everywhere else. This is called the identity matrix. If a relation \(R\) on \(A\) is both symmetric and antisymmetric, its off-diagonal entries are all zeros, so it is a subset of the identity relation.

It is an interesting exercise to prove the test for transitivity. Apply it to Example 7.2.2 to see how it works.

Summary and Review

• A relation from a set \(A\) to itself is called a relation on \(A\).
• Given any relation \(R\) on a set \(A\), we are interested in five properties that \(R\) may or may not have.
• The relation \(R\) is said to be reflexive if every element is related to itself, that is, if \(x\,R\,x\) for every \(x\in A\).
• The relation \(R\) is said to be irreflexive if no element is related to itself, that is, if \(x\not\!\!R\,x\) for every \(x\in A\).
• The reflexive property and the irreflexive property are mutually exclusive, and it is possible for a relation to be neither reflexive nor irreflexive.
• The relation \(R\) is said to be symmetric if the relation can go in both directions, that is, if \(x\,R\,y\) implies \(y\,R\,x\) for any \(x,y\in A\).
• The relation \(R\) is said to be antisymmetric if given any two distinct elements \(x\) and \(y\), either (i) \(x\) and \(y\) are not related in any way, or (ii) if \(x\) and \(y\) are related, they can only be related in one direction.
• A compact way to define antisymmetry is: if \(x\,R\,y\) and \(y\,R\,x\), then we must have \(x=y\).
• Finally, a relation is said to be transitive if we can pass along the relation and relate two elements if they are related via a third element.
• More precisely, \(R\) is transitive if \(x\,R\,y\) and \(y\,R\,z\) implies that \(x\,R\,z\).

Exercise \(\PageIndex{1}\label{ex:proprelat-01}\)

For each relation in Problem 1 in Exercises 1.1, determine which of the five properties are satisfied.

Exercise \(\PageIndex{2}\label{ex:proprelat-02}\)

For each relation in Problem 3 in Exercises 1.1, determine which of the five properties are satisfied.

Exercise \(\PageIndex{3}\label{ex:proprelat-03}\)

For the relation in Problem 6 in Exercises 1.1, determine which of the five properties are satisfied.

Exercise \(\PageIndex{4}\label{ex:proprelat-04}\)

For the relation in Problem 7 in Exercises 1.1, determine which of the five properties are satisfied.

Exercise \(\PageIndex{5}\label{ex:proprelat-05}\)

For the relation in Problem 8 in Exercises 1.1, determine which of the five properties are satisfied.

Exercise \(\PageIndex{6}\label{ex:proprelat-06}\)

For the relation in Problem 9 in Exercises 1.1, determine which of the five properties are satisfied.

Exercise \(\PageIndex{7}\label{ex:proprelat-07}\)

Let \(S\) be a nonempty set and define the relation \(A\) on \(\wp(S)\) by \[(X,Y)\in A \Leftrightarrow X\cap Y=\emptyset. \nonumber\] It is clear that \(A\) is symmetric.

1. Explain why \(A\) is not reflexive.
2. Explain why \(A\) is not irreflexive.
3. Is \(A\) transitive?
4. Let \(S=\{a,b,c\}\). Draw the directed graph for \(A\), and find the incidence matrix that represents \(A\).

Exercise \(\PageIndex{8}\label{ex:proprelat-08}\)

For each of these relations on \(\mathbb{N}-\{1\}\), determine which of the five properties are satisfied.

1. \(A_1=\{(x,y)\mid x\) and \(y\) are relatively prime\(\}\)
2. \(A_2=\{(x,y)\mid x\) and \(y\) are not relatively prime\(\}\)

Exercise \(\PageIndex{9}\label{ex:proprelat-09}\)

For each of the following relations on \(\mathbb{N}\), determine which of the five properties are satisfied.

1. \(R_1=\{(x,y)\mid x\) divides \(y\}\)
2. \(R_2=\{(x,y)\mid x+y\) is even\(\}\)
3. \(R_3=\{(x,y)\mid xy\) is even\(\}\)

Exercise \(\PageIndex{10}\label{ex:proprelat-10}\)

For each of the following relations on \(\mathbb{N}\), determine which of the five properties are satisfied.

1. \(S_1=\{(x,y)\mid y\) divides \(x\}\)
2. \(S_2=\{(x,y)\mid x+y\) is odd\(\}\)
3. \(S_3=\{(x,y)\mid xy\) is odd\(\}\)

Exercise \(\PageIndex{11}\label{ex:proprelat-11}\)

For each of the following relations on \(\mathbb{Z}\), determine which of the five properties are satisfied.

1. \(U_1=\{(x,y)\mid x \leq y\}\)
2. \(U_2=\{(x,y)\mid x-y\) is odd}\(\}\)
3. \(U_3=\{(x,y)\mid 3\) divides \(x+2y\}\)

Exercise \(\PageIndex{12}\label{ex:proprelat-12}\)

For each of the following relations on \(\mathbb{Z}\), determine which of the five properties are satisfied.

1. \(V_1=\{(x,y)\mid xy>0\}\)
2. \(V_2=\{(x,y)\mid x-y\) is even\(\}\)
3. \(V_3=\{(x,y)\mid x\) is a multiple of \(y\}\)