Relations

Videos (~30 minutes)

Relations Between Two Sets: Definition + First Examples (6:39)
Relations and their Inverses (2:49)
Reflexive, Symmetric, and Transitive Relations on a Set (6:54)
Equivalence Relations: Reflexive, Symmetric, and Transitive (4:36)
You need to check EVERY spot for reflexivity, symmetry, and transitivity (3:40)

Reading (~40 minutes)

Book of Proof, 11.2-11.4

Warmup (~40 minutes)

Problem 1

Part A

Recall that we write \(x \equiv y \pmod{p}\) for integers \(x\), \(y\), and \(p\) if there exists an integer \(c\) such that \((x-y) = cp\). For example, \(16 \equiv 2 \pmod{7}\) because \((16 - 2) = 2\times 7\).

Write a complete, careful proof that, for any \(p\), the relation \(\;\equiv \pmod {p}\) is an equivalence relation.

Part B

List all the equivalence classes of the relation \(\equiv \pmod{3}\). You can use either set-builder or roster notation.

Problem 2

Let \(A = \{a, b, c, d, e\}\). Suppose that \(R\) is an equivalence relation on \(A\). Suppose further that \(R\) has two equivalence classes, and that \(aRd\), \(bRc\), and \(eRd\). Fully describe \(R\) by either writing it as a set or drawing it.