Types of relations

When a rela­tion is defined on a sin­gle set, we can ask use­ful ques­tions about it. Is every ele­ment related to itself? If $a$ is related to $b$, is $b$ related to $a$? If $a$ is related to $b$ and $b$ to $c$, is $a$ related to $c$? The answers sort rela­tions into types: reflex­ive, sym­met­ric, tran­si­tive, and the impor­tant com­bi­na­tions called equiv­a­lence rela­tions and par­tial orders. This les­son defines each type and tests real exam­ples.

Through­out, $R$ is a rela­tion on a non-empty set $A$, that is, a rela­tion from $A$ to $A$.

The def­i­n­i­tions#

Reflex­ive. $R$ is reflex­ive if $(a, a) \in R$ for every $a \in A$. Every ele­ment is related to itself.

Sym­met­ric. $R$ is sym­met­ric if $(a, b) \in R \implies (b, a) \in R$. Every pair comes with its reverse.

Tran­si­tive. $R$ is tran­si­tive if $(a, b) \in R$ and $(b, c) \in R \implies (a, c) \in R$. Two links in a chain imply a direct link.

Equiv­a­lence rela­tion. $R$ is an equiv­a­lence rela­tion if it is reflex­ive, sym­met­ric and tran­si­tive.

Anti­sym­met­ric. $R$ is anti­sym­met­ric if $(a, b) \in R$ and $(b, a) \in R \implies a = b$. Two dif­fer­ent ele­ments are never related both ways.

Par­tial order. $R$ is a par­tial order if it is reflex­ive, anti­sym­met­ric and tran­si­tive.

To show that a prop­erty holds, you must check it for every ele­ment or every pair. To show that it fails, one coun­terex­am­ple is enough.

Test­ing finite rela­tions#

Exam­ple 1#

Let $A = \{2, 4, 6, 8\}$ and $R = \{(2, 4), (4, 2), (4, 6), (6, 4)\}$. Which prop­er­ties does $R$ have?

Reflex­ive? $2 \in A$ but $(2, 2) \notin R$. So $R$ is not reflex­ive.

Sym­met­ric? $(2, 4) \in R$ and $(4, 2) \in R$; $(4, 6) \in R$ and $(6, 4) \in R$. Every pair has its reverse, so $R$ is sym­met­ric.

Tran­si­tive? $(2, 4) \in R$ and $(4, 2) \in R$, but $(2, 2) \notin R$. So $R$ is not tran­si­tive.

Anti­sym­met­ric? $(2, 4) \in R$ and $(4, 2) \in R$, but $2 \neq 4$. So $R$ is not anti­sym­met­ric.

Exam­ple 2#

Let $A = \{1, 2, 3\}$ and $R = \{(1, 1), (1, 3), (3, 1), (2, 2), (2, 1), (3, 3)\}$. Is $R$ reflex­ive, sym­met­ric, tran­si­tive, an equiv­a­lence rela­tion?

Reflex­ive. $(1, 1)$, $(2, 2)$ and $(3, 3)$ are all in $R$, so yes.

Sym­met­ric. $(2, 1) \in R$ but $(1, 2) \notin R$. So no.

Tran­si­tive. $(2, 1) \in R$ and $(1, 3) \in R$, but $(2, 3) \notin R$. So no.

So $R$ is reflex­ive only, and it is not an equiv­a­lence rela­tion. (Some chains do work, such as $(1, 1), (1, 3) \implies (1, 3)$, but one fail­ing chain is enough.)

Test­ing rela­tions given by a rule#

Exam­ple 3#

$S$ is a rela­tion on the set $R$ of all real num­bers, given by $(a, b) \in S \iff ab \ge 0$. Which prop­er­ties does $S$ have?

Reflex­ive. For every real $a$, $a \cdot a = a^2 \ge 0$, so $(a, a) \in S$. Yes.

Sym­met­ric. If $ab \ge 0$ then $ba \ge 0$, since $ba = ab$. Yes.

Tran­si­tive. Take $a = -1$, $b = 0$, $c = 2$. Then $ab = 0 \ge 0$ and $bc = 0 \ge 0$, so $(-1, 0) \in S$ and $(0, 2) \in S$. But $ac = -2 < 0$, so $(-1, 2) \notin S$. Not tran­si­tive.

The num­ber 0 links a neg­a­tive num­ber to a pos­i­tive one, and that breaks the chain.

Exam­ple 4#

Let $W$ be the set of words in an Eng­lish dic­tio­nary, and let $R = \{(x, y) : \text{the words } x \text{ and } y \text{ have at least one letter in common}\}$. Which prop­er­ties does $R$ have?

Reflex­ive. Every word shares all its let­ters with itself. Yes.

Sym­met­ric. If $x$ and $y$ share a let­ter, then $y$ and $x$ share it. Yes.

Tran­si­tive. "cat" and "bat" share the let­ters a and t; "bat" and "bill" share the let­ter b. But "cat" and "bill" have no let­ter in com­mon. Not tran­si­tive.

Exam­ple 5#

For real num­bers $x$ and $y$, define $xRy \iff x - y + \sqrt{2}$ is an irra­tional num­ber. Which prop­er­ties does $R$ have?

Reflex­ive. $x - x + \sqrt{2} = \sqrt{2}$, which is irra­tional. So $(x, x) \in R$ for every $x$. Yes.

Sym­met­ric. Take $x = \sqrt{2}$ and $y = 1$: $\sqrt{2} - 1 + \sqrt{2} = 2\sqrt{2} - 1$, which is irra­tional, so $(\sqrt{2}, 1) \in R$. But $1 - \sqrt{2} + \sqrt{2} = 1$, which is ratio­nal, so $(1, \sqrt{2}) \notin R$. Not sym­met­ric.

Tran­si­tive. It is tempt­ing to argue that adding two irra­tional num­bers gives an irra­tional num­ber, but that is false: $\sqrt{2}$ and $-\sqrt{2}$ are irra­tional and their sum is 0. A coun­terex­am­ple: take $x = 0$, $y = 2\sqrt{2}$, $z = \sqrt{2}$.

• $x - y + \sqrt{2} = -2\sqrt{2} + \sqrt{2} = -\sqrt{2}$, irra­tional, so $(0, 2\sqrt{2}) \in R$.
• $y - z + \sqrt{2} = 2\sqrt{2} - \sqrt{2} + \sqrt{2} = 2\sqrt{2}$, irra­tional, so $(2\sqrt{2}, \sqrt{2}) \in R$.
• $x - z + \sqrt{2} = -\sqrt{2} + \sqrt{2} = 0$, ratio­nal, so $(0, \sqrt{2}) \notin R$.

So $R$ is not tran­si­tive. It is reflex­ive, but nei­ther sym­met­ric nor tran­si­tive.

An equiv­a­lence rela­tion#

Exam­ple 6#

On the set $Z$ of inte­gers, define $aRb \iff a - b$ is divis­i­ble by 3. Show that $R$ is an equiv­a­lence rela­tion.

Reflex­ive. $a - a = 0 = 3 \times 0$, divis­i­ble by 3.

Sym­met­ric. If $a - b = 3k$, then $b - a = 3(-k)$, also divis­i­ble by 3.

Tran­si­tive. If $a - b = 3k$ and $b - c = 3m$, then adding, $a - c = 3(k + m)$, divis­i­ble by 3.

So $R$ is an equiv­a­lence rela­tion. It sorts the inte­gers into three groups accord­ing to their remain­der on divi­sion by 3: $\{\ldots, -3, 0, 3, 6, \ldots\}$, $\{\ldots, -2, 1, 4, 7, \ldots\}$ and $\{\ldots, -1, 2, 5, 8, \ldots\}$. Two inte­gers are related exactly when they are in the same group. Every equiv­a­lence rela­tion splits its set into groups in this way.

A par­tial order#

Exam­ple 7#

Show that "$a$ divides $b$" is a par­tial order on $N$.

Reflex­ive. Every $a$ divides itself.

Anti­sym­met­ric. If $a$ divides $b$ and $b$ divides $a$, then $a \le b$ and $b \le a$ (for nat­ural num­bers), so $a = b$.

Tran­si­tive. If $b = ka$ and $c = mb$, then $c = (mk)a$, so $a$ divides $c$.

It is not sym­met­ric: 2 divides 6 but 6 does not divide 2. The rela­tion $\le$ on $R$ is another par­tial order.

Prac­tice#

1. Let $A = \{1, 2, 3\}$ and $R = \{(1, 1), (2, 2), (3, 3), (1, 2), (2, 1)\}$. Show that $R$ is an equiv­a­lence rela­tion.
2. Let $A = \{1, 2, 3\}$ and $R = \{(1, 2), (2, 3), (1, 3)\}$. Which of reflex­ive, sym­met­ric, tran­si­tive, anti­sym­met­ric does $R$ have?
3. Let $A = \{1, 2, 3\}$ and $R = \{(1, 1), (2, 2), (3, 3), (1, 2), (2, 3)\}$. Which prop­er­ties does $R$ have?
4. On the set of lines in a plane, is "is per­pen­dic­u­lar to" reflex­ive, sym­met­ric, tran­si­tive?
5. On $N$, define $aRb$ if $a + b$ is even. Is $R$ an equiv­a­lence rela­tion?
6. On $R$, is the rela­tion $a < b$ reflex­ive, sym­met­ric, tran­si­tive?
7. On $R$, define $aRb$ if $|a - b| \le 1$. Which prop­er­ties does $R$ have?
8. On $Z$, define $aRb$ if $a - b$ is divis­i­ble by 5. Show that $R$ is an equiv­a­lence rela­tion, and say how many groups it splits $Z$ into.
9. Write the small­est rela­tion on $\{1, 2, 3\}$ that con­tains $(1, 2)$ and is both reflex­ive and sym­met­ric.
10. Is the void rela­tion on a non-empty set $A$ reflex­ive? Is the uni­ver­sal rela­tion $A \times A$ an equiv­a­lence rela­tion?

Answers#