Relations

• Sets: Cartesian products, subsets, partitions, power sets.

Representations

• Set of pairs: $R = \{(1, 1), (1, 2), (2, 3)\}$.
• Zero-one matrix $M_R$: $M_R[i][j] = 1$ if $(a_i, a_j) \in R$, else 0.
• Directed graph (digraph): a vertex per element, an arc $a_i \to a_j$ per pair; a pair $(a, a)$ is a loop.

Properties of a relation on $A$

• Not reflexive is not the same as irreflexive. $\{(1, 1)\}$ on $\{1, 2\}$ is neither.
• Symmetric and antisymmetric are not opposites. The empty relation and the identity relation $\{(a, a)\}$ are both. $\{(1, 2), (2, 1), (1, 3)\}$ is neither.
• Asymmetric = antisymmetric + irreflexive. Asymmetric implies irreflexive (take $a = b$).
• The empty relation on a non-empty set is irreflexive, symmetric, antisymmetric, asymmetric and transitive, but not reflexive.

Counting relations with a property

Operations on relations

• Inverse: $R^{-1} = \{(b, a) \mid (a, b) \in R\}$; $M_{R^{-1}} = M_R^T$.
• Complement: $\overline{R} = (A \times B) - R$.
• Composition: for $R \subseteq A \times B$ and $S \subseteq B \times C$,

• Powers: $R^1 = R$, $R^{k+1} = R^k \circ R$. $(a, b) \in R^k$ if and only if there is a directed walk of length exactly $k$ from $a$ to $b$ in the digraph.
• $R$ is transitive if and only if $R^2 \subseteq R$ (equivalently $R^k \subseteq R$ for all $k \ge 1$).

Closures

WARSHALL(M, n)          // M is the n x n zero-one matrix of R
    W <- M
    for k <- 1 to n
        for i <- 1 to n
            for j <- 1 to n
                W[i][j] <- W[i][j] OR (W[i][k] AND W[k][j])
    return W            // matrix of the transitive closure

Equivalence relations and partitions

• Any two classes are either identical or disjoint: $[a] = [b]$ if and only if $a\,R\,b$.
• The distinct classes form a partition of $A$; conversely every partition of $A$ defines an equivalence relation ("in the same block"). This bijection is why the number of equivalence relations on an $n$-set equals the number of partitions, the Bell number $B_n$: $B_0, \ldots, B_6 = 1, 1, 2, 5, 15, 52, 203$.
• An equivalence relation whose partition has blocks of sizes $s_1, \ldots, s_k$ contains exactly $\sum s_i^2$ ordered pairs.

Partial orders (preview)

Example 1: classify relations

Example 2: transitive closure

Example 3: counting

Example 4: equivalence relations with a given class structure

• Intersection of two equivalence relations is an equivalence relation; their union need not be (transitivity fails). Example on $\{1, 2, 3\}$: classes $\{1, 2\}, \{3\}$ and $\{1\}, \{2, 3\}$; the union contains $(1, 2), (2, 3)$ but not $(1, 3)$.
• Unions preserve reflexivity, irreflexivity and symmetry, but not antisymmetry, asymmetry or transitivity. Intersections preserve reflexivity, irreflexivity, symmetry, antisymmetry, asymmetry and transitivity (irreflexivity, antisymmetry and asymmetry pass to every subset; reflexivity, symmetry and transitivity survive because each pair the definition requires is in both relations, so it is in the intersection: if $(a, b) \in R \cap S$ then $(b, a) \in R$ and $(b, a) \in S$, and likewise if $(a, b), (b, c) \in R \cap S$ then $(a, c)$ is in both).
• The inverse preserves all six of those properties. The complement preserves symmetry only, and it swaps reflexivity with irreflexivity. Composition of two relations preserves reflexivity only.

• $R$ is symmetric if and only if $R = R^{-1}$; antisymmetric if and only if $R \cap R^{-1} \subseteq \Delta_A$.
• A relation that is symmetric, transitive and "serial" (every element related to something) is reflexive; without the serial condition the classic false proof of "symmetric and transitive implies reflexive" fails, as $R = \emptyset$ shows.

• Property checks. Expect a relation given by pairs or by a rule on integers (for example $a\,R\,b$ if $a - b$ is even, or if $ab \ge 0$); test each property and look for a single counterexample.
• Counting relations. The counting-relations table covers the common counts. Derive them from the diagonal/off-diagonal split instead of memorising.
• Equivalence classes and partitions. Bell numbers for the total; Stirling numbers of the second kind for a fixed number of classes.
• Closures. Transitive closure equals reachability; Warshall's algorithm is $\Theta(n^3)$.
• Trap: "not reflexive" versus "irreflexive"; "antisymmetric" versus "not symmetric".
• Trap: $ab \ge 0$ on $\mathbb{Z}$ is reflexive and symmetric but not transitive ($1 \cdot 0 \ge 0$, $0 \cdot (-1) \ge 0$, but $1 \cdot (-1) < 0$).

• Sets: prerequisite. Cartesian products and partitions.
• Functions: dependent. A function is a relation with exactly one image per element.
• Partial Orders and Lattices: dependent. Reflexive, antisymmetric, transitive relations.
• Functional Dependencies: related. Attribute closure uses the same closure idea.
• Depth-First Search: related. Reachability (transitive closure) by graph search.