Relations: properties, equivalence relations and partial orders

Relations are a generalization of functions. In a function every input had exactly one output; in a relation an element can be related to nothing or to many things. This week is a final exam topic. The question types expected on the exam: checking the four properties of a given relation, “Prove that $R$ is an equivalence relation”, writing equivalence classes, drawing a Hasse diagram and counting relations.

Golden rules:

1. “For every” properties (reflexive) are broken by a single missing pair, and “if … then” properties (symmetric, transitive) are broken by a single counterexample.
2. Antisymmetric does not mean “not symmetric”. Both can be true at the same time or false at the same time.
3. Equivalence = reflexive + symmetric + transitive. Partial order = reflexive + antisymmetric + transitive.
4. For the composite $S\circ R$: first $R$, then $S$.

Definitions

A binary relation from $A$ to $B$ is any subset of $A\times B$. Instead of $(a,b)\in R$ we write $a\,R\,b$. A relation from $A$ to $A$ is called a “relation on $A$”.

Intuition: let $A$ be students and $B$ be courses. ”$a$ takes course $b$” is a relation. A student may take no courses or five courses. Every function is a relation; the converse is not true.

If $|A| = n$ there are $|A\times A| = n^2$ pairs, and each is either in the relation or not. So there are $2^{n^2}$ relations on $A$.

The four properties

Let $R$ be a relation on $A$.

Example 1. $\le$ on $\{1,2,3,4\}$: every $a\le a$ (reflexive). $1\le 2$ but $2\not\le 1$ (not symmetric). If $a\le b$ and $b \le a$ then $a = b$ (antisymmetric). If $a\le b\le c$ then $a \le c$ (transitive).

Example 2. $R = \{(1,1),(1,2),(2,1)\}$ on $\{1,2,3\}$:

reflexive?      (2,2) missing              -> NO
symmetric?      (1,2) and (2,1) both present  -> YES
antisymmetric?  (1,2),(2,1) present but 1 != 2  -> NO
transitive?     (2,1),(1,2) present, (2,2) missing   -> NO

PITFALL · Skipping the case $a = c$ in the transitivity check. In Example 2, $(2,1)$ and $(1,2)$ require $(2,2)$. Most students look only at chains of “three distinct elements” and miss this.

TIP · the empty condition. For “if … then” properties, if the premise is never satisfied, the property is automatically true. The empty relation is symmetric, antisymmetric and transitive (but not reflexive if $A$ is nonempty).

Counting relations

$|A| = n$. There are $n$ pairs on the diagonal and $n^2 - n$ off the diagonal; the off-diagonal pairs are grouped into matchings $\{a,b\}$, and there are $\frac{n(n-1)}{2}$ matchings.

The logic: in symmetric the diagonal pairs are free ($2^n$), and each matching is “both or neither” ($2$ choices). In antisymmetric there are 3 choices for each matching: only $(a,b)$, only $(b,a)$, neither.

Composites and powers of relations

If $R$: $A\to B$ and $S$: $B \to C$, then

$S\circ R = \{(a,c) : \exists b\ \big((a,b)\in R \wedge (b,c)\in S\big)\}.$

Like function composition: go first with $R$, then continue with $S$. Powers: $R^1 = R$, $R^{n+1} = R^n \circ R$. An important theorem: $R$ is transitive $\iff$ $R^n \subseteq R$ for every $n\ge 1$.

Transitive closure $R^*$: the smallest transitive relation containing $R$. Think of it as a directed graph: if there is a path from $a$ to $b$, then $(a,b)\in R^*$. With matrices, $M_{R^*} = M_R \vee M_R^{[2]} \vee \dots \vee M_R^{[n]}$; in practice the Warshall algorithm is used.

Equivalence relations

A relation that is reflexive, symmetric and transitive is called an equivalence relation. Intuition: a “sameness” relation like “plays on the same team”, “gives the same remainder”, “born in the same year”.

The equivalence class of $a$: $[a]_R = \{s : (a,s)\in R\}$.

Basic theorem: equivalence classes are either identical or disjoint, and their union is $A$. So they form a partition. Conversely, every partition defines an equivalence relation (“being in the same block”). That is why the number of equivalence relations on an $n$-element set equals the number of partitions (the Bell number): 5 for $n = 3$, 15 for $n = 4$.

The most classic example: congruence modulo $m$. $a \equiv b \pmod m$ if and only if $m \mid a - b$. There are $m$ classes: $[0], [1], \dots, [m-1]$.

A fully written proof

Claim. Let $m > 1$ be an integer. The relation $R = \{(a,b) : a \equiv b \pmod m\}$ on $\mathbb{Z}$ is an equivalence relation.

Proof. Reflexive. For every integer $a$, $a - a = 0 = m\cdot 0$, so $m \mid a - a$ and $a\,R\,a$. Symmetric. Suppose $a\,R\,b$. Then $a - b = mk$ for some integer $k$. Hence $b - a = m(-k)$, and $-k$ is an integer, so $b\,R\,a$. Transitive. Suppose $a\,R\,b$ and $b\,R\,c$. Then $a - b = mk$ and $b - c = ml$ for some integers $k, l$. Adding, $a - c = m(k + l)$, so $m \mid a - c$ and $a\,R\,c$. Since $R$ is reflexive, symmetric and transitive, it is an equivalence relation. $\blacksquare$

In plain words: write each property under a separate heading, write the definition ($a - b = mk$) out explicitly, and at the end add a closing sentence that mentions all three. Instructors give marks per property.

Partial orders

A relation that is reflexive, antisymmetric and transitive is called a partial order; the pair $(S, \preccurlyeq)$ is called a poset. Examples: $\le$ on numbers, $\mid$ on positive integers, $\subseteq$ on sets.

It is “partial” because two elements need not be comparable: $2 \nmid 3$ and $3\nmid 2$. If every pair is comparable it is called a total order.

Hasse diagram

A short way to draw a poset. From the directed graph remove three things:

1. the diagonal loops (already known from reflexivity),
2. the edges that come from transitivity (the edge $a$-$c$ if $a \preccurlyeq b \preccurlyeq c$),
3. the arrow directions (the smaller is drawn lower).

Only the cover pairs remain: $a \prec b$ with no element in between.

Example. The divisors of 18, $\{1,2,3,6,9,18\}$, with divisibility:

level 3:             18
                    /  \
level 2:           6    9
                  / \  /
level 1:         2   3
                  \ /
level 0:           1
edges: 1-2, 1-3, 2-6, 3-6, 3-9, 6-18, 9-18   (7 edges)

Terms: maximal (nothing above it), minimal (nothing below it), greatest/least element (greater/smaller than everyone, must be unique), upper bound (greater than or equal to everything in a subset), least upper bound (the smallest of the upper bounds). For divisibility, lub = lcm, glb = gcd.

n-ary relations (briefly)

A subset of $A_1\times A_2\times\dots\times A_n$ is called an n-ary relation. A database table is exactly this: each row is an $n$-tuple, each column is a field. Selection filters rows, projection removes columns, join matches two tables on common fields. On the final it comes at most as one definition question.

Common mistakes