Relations: equivalence relations and partial orders

A relation on a set \( A \) is any subset \( R \subseteq A \times A \); we write \( a\,R\,b \) when \( (a, b) \in R \). Four properties organise almost every relation you will meet. \( R \) is reflexive if \( a\,R\,a \) for all \( a \); symmetric if \( a\,R\,b \) implies \( b\,R\,a \); antisymmetric if \( a\,R\,b \) and \( b\,R\,a \) together imply \( a = b \); and transitive if \( a\,R\,b \) and \( b\,R\,c \) imply \( a\,R\,c \). On a set of \( n \) elements there are \( 2^{n^2} \) relations in all, since each of the \( n^2 \) ordered pairs is either in or out.

An equivalence relation is reflexive, symmetric and transitive: a precise version of "the same in some respect". The central example is congruence: \( a \equiv b \pmod m \) when \( m \) divides \( a - b \). The equivalence class of \( a \) is the set of everything related to it, and the classes of an equivalence relation partition the set: every element lies in exactly one class. Modulo 3 the integers split into three classes, by remainder; the example finds that \( -7 \) lies in the class of 2, since \( -7 = 3 \cdot (-3) + 2 \). Conversely, every partition defines an equivalence relation (same block), so equivalence relations on an \( n \)-element set are counted by the Bell numbers.

A partial order is reflexive, antisymmetric and transitive: a precise version of "comes before or equals". Examples are \( \le \) on numbers, \( \subseteq \) on sets, and divisibility on positive integers. It is partial because two elements may be incomparable: neither of 4 and 6 divides the other. A total order is one in which every pair is comparable. A finite partial order is drawn as a Hasse diagram: a dot per element, a line from \( a \) up to \( b \) when \( a \) is below \( b \) with nothing strictly between, and every relation implied by reflexivity and transitivity left out. A minimal element has nothing below it, a least element is below everything, and a finite partial order may have many minimal elements but at most one least element.

Picture it: an equivalence relation cuts a set into separate islands, and two elements are related exactly when they stand on the same island. A partial order stacks the elements into a layered diagram, like a family tree drawn upside down, with comparability meaning "joined by a path that only goes upwards".

Think it: equivalence relations are how mathematics builds new objects by gluing: the integers modulo \( m \), the rationals as classes of fractions, the real numbers as classes of Cauchy sequences. Partial orders are how it schedules things: a topological sort lists the elements of a finite partial order in a line compatible with every relation, which is how build systems decide what to compile first.