Relations: Properties, Equivalence Relations & Partial Orders

Discrete Mathematics Fundamentals

Chapter 5 · Relations: Properties, Equivalence Relations & Partial Orders

Chapter 1 claimed "a database table is a relation in the mathematical sense." This chapter makes that precise — what a relation actually is formally, the four properties that classify how a relation behaves, and two especially important categories: equivalence relations (which underlie grouping and equality) and partial orders (which underlie dependency resolution).

What a Relation Actually Is

Formally, a relation R from set A to set B is a subset of the Cartesian product A × B — the set of every possible ordered pair (a, b) with a ∈ A and b ∈ B. A relation "on" a single set A is a subset of A × A. Written (a, b) ∈ R, or more commonly a R b — the same way a < b or a ≡ b are written.

A database table is exactly this — a table with columns (user_id, order_id) is a subset of all possible (user_id, order_id) pairs, selecting out exactly the ones that actually hold. A "friends" table in a social network is a relation on the set of users.

Four Key Properties

Each property is a quantified statement, following Chapter 3's own notation directly:

Property	Definition	Holds for	Fails for
Reflexive	∀a (a R a)	≤ — a ≤ a is always true	< — a < a is never true
Symmetric	∀a ∀b (a R b → b R a)	"is a sibling of"	"is a parent of"
Transitive	∀a ∀b ∀c ((a R b ∧ b R c) → a R c)	<, ≤, =	"is a friend of" — a friend of a friend isn't necessarily a friend
Antisymmetric	∀a ∀b ((a R b ∧ b R a) → a = b)	≤ — a≤b and b≤a forces a=b	"is a friend of" — mutual friendship doesn't force the two people to be the same person

"Not symmetric" and "antisymmetric" are not opposites

A relation can genuinely be neither symmetric nor antisymmetric, or — as this chapter's own first exercise shows — antisymmetric without being symmetric at all. Antisymmetric doesn't mean "never symmetric anywhere" — it only forbids a R b and b R a both holding unless a and b are the same element. The diagonal (a R a) never violates it.

Equivalence Relations — Reflexive + Symmetric + Transitive

A relation with all three of the first properties together is an equivalence relation — a formal notion of "these things count as the same" for some specific purpose. An equivalence relation splits its entire set into disjoint equivalence classes, where everything inside one class is considered equivalent to everything else in that same class.

This is exactly what GROUP BY does

"Has the same email domain as" is a genuine equivalence relation on a set of users — reflexive (everyone shares a domain with themselves), symmetric (if A shares a domain with B, B shares it with A), and transitive (if A and B share a domain, and B and C share a domain, A and C do too). The equivalence classes are exactly the groups a SQL GROUP BY email_domain would produce — each class is one specific domain's worth of users. Grouping data by a shared value is partitioning by an equivalence relation, whether or not the query was ever thought of that way.

Partial Orders — Reflexive + Antisymmetric + Transitive

Swap symmetric for antisymmetric, and a different, equally important category appears: a partial order. It describes an ordering where, unlike numbers under ≤, not every pair of elements necessarily needs to be comparable at all.

"Package A depends on package B" (or its reverse, "must be installed before") is a classic partial order — reflexive in a trivial sense, antisymmetric (if A must come before B and B must come before A, something's actually wrong — normally impossible in a valid dependency graph), and transitive (a chain of dependencies carries through). Crucially, two unrelated packages might have no dependency relationship between them at all — neither has to come before the other, which is exactly what makes it partial rather than a total order like ≤ on numbers, where any two numbers are always comparable.

Subset (⊆, Chapter 4) is another classic partial order — two arbitrary sets aren't always comparable by ⊆ either.

Hands-On Exercises

Exercise 1

On the set {1, 2, 3}, consider the relation R = {(1,1), (2,2), (3,3), (1,2)}. Determine whether R is reflexive, symmetric, transitive, and antisymmetric, justifying each answer.

📄 View solution

Exercise 2

Prove that "has the same last two digits of their employee ID" is an equivalence relation on a set of employees, by explicitly checking all three required properties. Then describe what the resulting equivalence classes would actually look like.

📄 View solution

Exercise 3

The relation "a divides b" (written a | b, meaning b is a whole-number multiple of a) is defined on the positive integers. Determine whether this is a partial order by checking reflexivity, antisymmetry, and transitivity, and give one example pair of positive integers that are not comparable under this relation (neither divides the other).

📄 View solution

Chapter 5 Quick Reference

A relation is a subset of a Cartesian product — a database table is a relation, literally
Reflexive: ∀a(a R a) — Symmetric: ∀a∀b(a R b → b R a) — Transitive: ∀a∀b∀c((a R b ∧ b R c) → a R c) — Antisymmetric: ∀a∀b((a R b ∧ b R a) → a=b)
Equivalence relation = reflexive + symmetric + transitive — partitions a set into equivalence classes, exactly what GROUP BY does
Partial order = reflexive + antisymmetric + transitive — an ordering where not every pair needs to be comparable, unlike ≤ on numbers
"Not symmetric" and "antisymmetric" are not opposites — a relation can be antisymmetric without ever being symmetric anywhere off the diagonal
Next chapter: Functions — injective, surjective, and bijective