"Is less than," "divides," "is a sibling of," "has the same remainder as": each of these relates some pairs of things and not others. Using Cartesian products, a relation becomes a set of ordered pairs, and four properties sort relations into the families that matter most.
Key idea
A relation $R$ on a set $A$ is a subset of $A \times A$; we write $a\,R\,b$ when $(a, b) \in R$. $R$ is reflexive if $a\,R\,a$ for every $a \in A$; symmetric if $a\,R\,b$ implies $b\,R\,a$; antisymmetric if $a\,R\,b$ and $b\,R\,a$ together imply $a = b$; transitive if $a\,R\,b$ and $b\,R\,c$ imply $a\,R\,c$.
Why it works
Each property is easy to see in a picture where every pair $(a, b)$ is an arrow from $a$ to $b$. Reflexive: a loop at every point (in the matrix, $1$'s all down the diagonal). Symmetric: every arrow has a return arrow (the matrix equals its transpose). Antisymmetric: no two different points have arrows both ways. Transitive: every two-step route $a \to b \to c$ has the shortcut $a \to c$. Each property is a "for all" statement, so one missing pair is enough to break it.
| Relation | R | S | A | T |
|---|---|---|---|---|
| $a = b$ (any set) | yes | yes | yes | yes |
| $a \le b$ on $\mathbb{Z}$ | yes | no | yes | yes |
| $a < b$ on $\mathbb{Z}$ | no | no | yes | yes |
| $a \mid b$ on $\mathbb{Z}^{+}$ | yes | no | yes | yes |
| $a \equiv b \pmod{3}$ | yes | yes | no | yes |
| $\lvert a - b \rvert \le 1$ on $\mathbb{Z}$ | yes | yes | no | no |
Worked examples
Worked example: Checking all four properties
On $A = \{1, 2, 3\}$, let $R = \{(1, 1), (1, 2), (2, 1), (2, 2), (3, 3)\}$. Which properties does $R$ have?
- Reflexive: $(1, 1)$, $(2, 2)$, $(3, 3)$ are all present. Yes.
- Symmetric: the only non-loop pairs are $(1, 2)$ and $(2, 1)$, each the reverse of the other. Yes.
- Antisymmetric: $1\,R\,2$ and $2\,R\,1$ with $1 \ne 2$. No.
- Transitive: check every route. $1 \to 2 \to 1$ needs $(1, 1)$: present. $2 \to 1 \to 2$ needs $(2, 2)$: present. Every other route uses a loop. Yes.
Answer: Reflexive, symmetric and transitive; not antisymmetric
Worked example: "Divides" on a small set
On $\{1, 2, 3, 4, 5, 6\}$, let $a\,R\,b$ mean $a \mid b$. Which properties hold?
- Reflexive: $a \mid a$ always. Yes.
- Symmetric: $2 \mid 4$ but $4 \nmid 2$. No.
- Antisymmetric: if $a \mid b$ and $b \mid a$ for positive integers, then $a \le b$ and $b \le a$, so $a = b$. Yes.
- Transitive: $a \mid b$ and $b \mid c$ give $a \mid c$ (proved in the direct-proof lesson). Yes.
Answer: Reflexive, antisymmetric, transitive; not symmetric
Worked example: Counting relations
How many relations are there on a set with $3$ elements?
- A relation is any subset of $A \times A$, which has $3 \cdot 3 = 9$ pairs.
- Each pair is in or out: $2^{9} = 512$ relations.
Answer: $512$
Common mistake
Reading "antisymmetric" as "not symmetric." They are different ideas. Equality is both symmetric and antisymmetric. The relation $\{(1, 2), (2, 1), (2, 3)\}$ is neither: $(2, 3)$ has no return arrow, and $1$ and $2$ point at each other. Check: antisymmetric only forbids two-way arrows between different points; it says nothing about one-way arrows or loops.