Equivalence Relations

Return to Course Outline

Previous Lecture

Questions?

Equivalence Relations

Section 7.2.

The Idea

Find an example of an equivalence relation on Henry VIII’s relatives (see https://www.britroyals.com/tudortree.asp)

“Sibling” (including half-siblings, works for the people in the actual family tree, but if the tree had been slightly different it wouldn’t) or “same mother,” “same father.”

The key thing to check in deciding whether a relation is an equivalence relation is that it is reflexive, symmetric, and transitive.

Proofs

Define relation ~ on the reals as x ~ y if and only if x² = y². Prove that ~ is an equivalence relation.

The heart of the proof is showing that ~ is reflexive, symmetric, and transitive. Here are two versions of the proof, with their LaTeX source here.

This proof is typical of many proofs that relations are equivalence relations, particularly showing that the relation is reflexive, symmetric, and transitive. Also, like this one, many proofs about relations that are defined in terms of two things being equal come down to the fact that equality is reflexive, symmetric, and transitive.

Key Points

Equivalence relations are reflexive (x relates to x), symmetric (if x relates to y then y relates x), and transitive (if x relates to y and y relates to z then x relates to z).

Prove a relation is an equivalence relation by proving each of the 3 properties.

Next

Notice how the ~ relation above divides the real numbers into sets of equivalent numbers, e.g., {2,-2}, {1,-1}, etc. 0 goes in a set by itself, {0}. No number is ever in more than one set, and every number is in one.

Equivalence classes and partitions.

Read section 7.3.

Next Lecture