Discrete Math · Undergraduate

Relations, Equivalence Relations and Partial Orders

Quick answer

A relation on a set A is any set of ordered pairs from A × A, written a ~ b when the pair (a, b) is in it. Four properties sort relations: reflexive, symmetric, antisymmetric and transitive. A relation with the first, second and fourth is an equivalence relation, and its equivalence classes split the set into non-overlapping parts, as congruence mod 3 splits the integers into three classes. A relation that is reflexive, antisymmetric and transitive is a partial order, like ≤ or "divides".

What you'll learn

  • Test a relation for reflexivity, symmetry, antisymmetry and transitivity
  • Recognize equivalence relations and partial orders
  • Find the equivalence classes of an equivalence relation
  • Pass between partitions and equivalence relations

Relations as sets of pairs

A relation on a set AA is any collection RR of ordered pairs from A×AA \times A. When (a,b)∈R(a, b) \in R we write a∼ba \sim b. “Is less than”, “divides”, “has the same remainder mod 33” and “was born in the same month” are all relations.

Four properties sort them. For all aa, bb, cc in AA:

PropertyMeaning
reflexivea∼aa \sim a
symmetrica∼ba \sim b gives b∼ab \sim a
antisymmetrica∼ba \sim b and b∼ab \sim a force a=ba = b
transitivea∼ba \sim b and b∼cb \sim c give a∼ca \sim c

An equivalence relation is reflexive, symmetric and transitive: it says two things are “the same” in some respect. A partial order is reflexive, antisymmetric and transitive: it ranks things, though some pairs may not be comparable.

Why equivalence classes never overlap

The equivalence class of aa is [a]={x:x∼a}[a] = \{x : x \sim a\}. Suppose two classes [a][a] and [b][b] share an element cc. Then c∼ac \sim a and c∼bc \sim b. By symmetry a∼ca \sim c, and by transitivity a∼ba \sim b. Now anything related to aa is related to bb, and the reverse, so [a]=[b][a] = [b]. Two classes are either the same class or have nothing in common. By reflexivity every element lies in its own class, so the classes split AA into non-overlapping parts, a partition. The reverse holds too: any partition defines an equivalence relation, “in the same part”.

Congruence mod 3 on 0 to 8 Nine vertices labeled 0 through 8, in three clusters. The cluster 0, 3, 6 is joined in a triangle in one color, the cluster 1, 4, 7 in a second color, and the cluster 2, 5, 8 in a third. No edges join different clusters: the three equivalence classes. 0 3 6 1 4 7 2 5 8
Congruence mod 3 on 0 to 8

Worked examples

Common mistakes

Practice problems

  1. Is ”a−ba - b is even” an equivalence relation on the integers? If so, name its classes.

    Answer

    Yes; the classes are the even and the odd integers.

    Full solution

    It is congruence mod 22: reflexive, symmetric and transitive, with two remainder classes.

  2. On {1,2}\{1, 2\}, which properties does R={(1,1),(2,2),(1,2)}R = \{(1,1), (2,2), (1,2)\} have?

    Answer

    Reflexive, antisymmetric and transitive, so a partial order; not symmetric

    Full solution

    (1,2)(1,2) is in RR but (2,1)(2,1) is not, so it is not symmetric. Every chain closes up: 1∼2∼21 \sim 2 \sim 2 gives 1∼21 \sim 2, which is present.

  3. Is ≤\le on the integers a partial order?

    Answer

    Yes

    Full solution

    a≤aa \le a; a≤ba \le b and b≤ab \le a force a=ba = b; a≤b≤ca \le b \le c gives a≤ca \le c.

  4. How many equivalence classes does congruence mod 44 have on the integers?

    Answer

    44

    Full solution

    One for each remainder 00, 11, 22, 33.

  5. How many relations are there on a set with 22 elements?

    Answer

    1616

    Full solution

    A×AA \times A has 44 pairs, and each is in or out: 242^4.

  6. List the pairs of the equivalence relation on {1,2,3,4}\{1, 2, 3, 4\} whose classes are {1,3}\{1, 3\} and {2,4}\{2, 4\}.

    Answer

    (1,1),(3,3),(1,3),(3,1),(2,2),(4,4),(2,4),(4,2)(1,1), (3,3), (1,3), (3,1), (2,2), (4,4), (2,4), (4,2)

    Full solution

    Two elements are related exactly when they lie in the same part.

  7. How many equivalence relations are there on {a,b,c}\{a, b, c\}?

    Answer

    55

    Full solution

    Count partitions: {a,b,c}\{a, b, c\}; three ways to put one element alone and pair the other two; and three singletons. 1+3+1=51 + 3 + 1 = 5.

  8. A student says “is a sibling of” (not counting yourself) is transitive. Test the claim.

    Answer

    It fails: Ann is a sibling of Ben and Ben of Ann, but Ann is not her own sibling.

    Full solution

    Transitivity with a∼ba \sim b and b∼ab \sim a would demand a∼aa \sim a, which this relation excludes.

Frequently asked questions

What is a relation on a set?

Any set R of ordered pairs (a, b) with a and b in the set. We write a ~ b, or a R b, when (a, b) is in R.

What makes a relation an equivalence relation?

It is reflexive (a ~ a), symmetric (a ~ b gives b ~ a) and transitive (a ~ b and b ~ c give a ~ c).

What is an equivalence class?

The set [a] of everything related to a. Two classes are either identical or share no elements, so the classes split the set into parts.

What is a partial order?

A relation that is reflexive, antisymmetric (a ~ b and b ~ a force a = b) and transitive, such as ≤ on numbers or ⊆ on sets.

How many equivalence relations does a 3-element set have?

Five, one for each way to split the set into parts: all together, all apart, or one of three ways to pair two elements.

What to learn next