Equivalence Relations

Return to Course Outline

Previous Lecture

Anything You Want to Talk About?

The last day to grade anything for this course is May 20.

Problem Set 11

The last problem set of the semester (problem set 11) is now officially ready for you to start.

It should be finished by next Wednesday (May 5) and graded by the following Wednesday (May 12).

See the handout for more information.

Equivalence Relations

From section 7.2 in the textbook and this discussion of equivalence relations.

Examples

Can you think of some reasonably “real world” examples of equivalence relations?

Books and the movies based on them? This might be a little hard to make an equivalence relation from, because the domain and range seem to be different sets (books for one and movies for the other), but symmetry and transitivity require that domain and range are the same set.

But how about a “same series” (of books, movies, etc.) relation as a variation?

• Reflexive: Is book a in the same series as itself? Yes.
• Symmetric: If book a is in the same series as b, is b in the same series as a? Yes.
• Transitive: If a is in the same series as b and b in same series as c, is a in the same series as c? Yes.

So this is a good example of an equivalence relation.

For other examples, consider relations between the cards in a deck: “same suit,” “same color,” “same number,” etc. are all equivalence relations.

At any particular moment in some games, some cards might be face up and others face down, giving rise to a “same state” relation, i.e., a is in the same state as b if a and b are both face up or both face down. This is also an equivalence relation.

Interestingly, the similar relation “different states” is not an equivalence relation, because it’s not reflexive (a is not in a different state from itself) nor transitive (if a is in a different state from b and b in a different state from c, then a and c are in the same state — assuming the only states are “face up” and “face down” — not different states).

Proofs

Define the relation ~ on integers by n ~ m if and only if n - m is divisible by 3, i.e., n - m = 3k for some integer k.

How would you prove that ~ is an equivalence relation (if it is)?

We first guessed that it is an equivalence relation. Then we wrote out the proof formally in LaTeX. You can find the LaTeX source and PDF files on Canvas.

The key thing such a proof has to do is prove that the relation is reflexive, symmetric, and transitive.

Each of those parts is a separate argument, typically referencing the definition of the relation.

Next

Any equivalence relation on some set A divides A into “equivalence classes,” i.e., subsets whose elements are all equivalent to each other.

Please read section 7.3 in the textbook.

Please also contribute to this equivalence classes discussion.

Next Lecture