Relations and Equivalence Relations: Properties and Classes

Describing Connections Between Elements

"Is less than", "is a factor of", "has the same birthday as" and "lives in the same state as" are all ways of connecting objects in pairs. In mathematics such a connection is called a relation. Relations are central to set theory, discrete mathematics, databases and computer science. This tutorial defines relations on a set, explains the reflexive, symmetric, antisymmetric and transitive properties, shows how equivalence relations split a set into equivalence classes, and introduces partial orders, with worked examples of the kind set in first-year university courses (MTH 101/111 and discrete mathematics).

What Is a Relation?

A relation R from a set A to a set B is any subset of the Cartesian product A × B, the set of all ordered pairs (a, b) with a in A and b in B. If (a, b) is in R we write a R b and say "a is related to b". A relation from A to itself is called a relation on A.

Example 1. Let A = {1, 2, 3, 4} and define a R b if a divides b. Then

R = {(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 4), (3, 3), (4, 4)}.

A relation can be shown as a set of pairs, as an arrow diagram (a directed graph with an arrow from a to b when a R b), or as a matrix of 0s and 1s.

The Four Key Properties

For a relation R on a set A:

Reflexive: every element is related to itself: a R a for all a in A.
Symmetric: if a R b then b R a.
Antisymmetric: if a R b and b R a, then a = b. (Two different elements are never related in both directions.)
Transitive: if a R b and b R c, then a R c.

To show a property holds, you must prove it for all elements. To show it fails, one counterexample is enough.

Testing the Properties: Worked Examples

Example 2. "Divides" on {1, 2, 3, 4} (from Example 1).

Reflexive: yes, every number divides itself.
Symmetric: no. 1 divides 2, but 2 does not divide 1.
Antisymmetric: yes. If a divides b and b divides a (for positive integers), then a = b.
Transitive: yes. If a divides b and b divides c, then a divides c.

Example 3. "Is less than" (<) on the integers.

Reflexive: no, 3 < 3 is false.
Symmetric: no, 2 < 5 but not 5 < 2.
Antisymmetric: yes, vacuously: a < b and b < a can never both be true, so the condition is never broken.
Transitive: yes.

Example 4. On the set of people, a R b if "a is a friend of b" (assuming friendship is mutual and nobody counts as their own friend).

Not reflexive; symmetric; not transitive, because your friend's friend need not be your friend.

Example 5. On A = {1, 2, 3}, let R = {(1, 1), (2, 2), (3, 3), (1, 2), (2, 1), (2, 3), (3, 2)}.

Reflexive: yes, (1, 1), (2, 2) and (3, 3) are all present.
Symmetric: yes, every pair appears with its reverse.
Transitive: no. (1, 2) and (2, 3) are in R, but (1, 3) is not.

Equivalence Relations

A relation that is reflexive, symmetric and transitive is an equivalence relation. It captures the idea of "being the same in some respect".

Familiar equivalence relations:

Equality, =, on any set.
"Has the same birthday as" on a set of people.
"Is similar to" on the set of triangles.
"Is congruent modulo n to" on the integers: a ≡ b (mod n) if n divides a − b.
"Is parallel to or the same as" on the set of lines in a plane.

Example 6. Prove that congruence modulo 3 is an equivalence relation on the integers.

Reflexive: a − a = 0 = 3 × 0, so 3 divides a − a and a ≡ a.
Symmetric: if 3 divides a − b, say a − b = 3k, then b − a = 3(−k), so 3 divides b − a.
Transitive: if a − b = 3k and b − c = 3m, then a − c = (a − b) + (b − c) = 3(k + m), so a ≡ c.

All three hold, so it is an equivalence relation.

Equivalence Classes and Partitions

For an equivalence relation on A, the equivalence class of an element a is the set of everything related to a:

[a] = {x in A : x R a}.

The key theorem: the equivalence classes form a partition of A. Every element belongs to exactly one class, and any two classes are either identical or completely separate. Conversely, every partition of a set defines an equivalence relation ("is in the same part as").

Example 7. For congruence modulo 3 on the integers, there are exactly three classes:

[0] = {…, −6, −3, 0, 3, 6, …}, numbers leaving remainder 0;
[1] = {…, −5, −2, 1, 4, 7, …}, remainder 1;
[2] = {…, −4, −1, 2, 5, 8, …}, remainder 2.

Every integer is in exactly one of these. The set of classes {[0], [1], [2]} is written ℤ₃ and is the basis of modular arithmetic.

Example 8. On A = {1, 2, 3, 4, 5, 6}, define a R b if a and b have the same remainder when divided by 2. The classes are {1, 3, 5} and {2, 4, 6}: the odd and even numbers.

Example 9. On the set of ordered pairs of integers (a, b) with b ≠ 0, define (a, b) R (c, d) if ad = bc. This is an equivalence relation, and the class of (1, 2) is {(1, 2), (2, 4), (−3, −6), …}, all the fraction representations of one half. In fact, this is how rational numbers are formally constructed: each rational number is an equivalence class of pairs.

Partial Orders

A relation that is reflexive, antisymmetric and transitive is a partial order. It describes ranking or containment rather than sameness.

"≤" on the real numbers (a total order, because any two numbers can be compared).
"Divides" on the positive integers. It is only partial: 2 and 3 cannot be compared, since neither divides the other.
"Is a subset of" (⊆) on the set of all subsets of a set.

Partial orders are drawn as Hasse diagrams and are used to schedule tasks, where "task a must come before task b".

Relations in Computing

A table in a relational database is literally a relation: a set of tuples.
Equivalence classes appear in the union–find data structure, which keeps track of which items are "connected".
Transitive closure (adding every pair needed to make a relation transitive) answers reachability questions, such as which cities can be reached from which by any sequence of flights.

Summary

A relation on A is a set of ordered pairs from A × A.
The key properties are reflexive, symmetric, antisymmetric and transitive; a single counterexample disproves one.
An equivalence relation is reflexive, symmetric and transitive, and its equivalence classes partition the set.
A partial order is reflexive, antisymmetric and transitive.
Congruence modulo n is the classic equivalence relation, with n classes given by the remainders.