A binary relation on a set is a subset of the set's Cartesian product with itself, and its structural properties—reflexivity, symmetry, antisymmetry, and transitivity—determine whether it forms an equivalence relation (reflexive, symmetric, transitive, inducing a partition of the set into equivalence classes) or a partial order (reflexive, antisymmetric, transitive). Discrete mathematics formalizes a partially ordered set (poset) as a directed acyclic graph free of nontrivial directed cycles, represented compactly by a Hasse diagram that omits reflexive self-loops and transitively implied edges, and distinguishes comparable from incomparable element pairs, with a total order being the special case where every pair is comparable. Topological sorting is the theorem that every finite poset admits a total order extension containing its original relation, proved by repeatedly removing a minimal element—guaranteed to exist in any finite poset via a maximum-length chain argument—and inductively ordering the remainder.
A binary relation on a set is a subset of the set's Cartesian product with itself, and its structural properties—reflexivity, symmetry, antisymmetry, and transitivity—determine whether it forms an eq…