Mathematical-Reasoning · Unit 28 · Video 1 · Interactive Practice

Sorting a Set: The Classes of an Equivalence Relation

IKey Formulas

Formula	Meaning
$R[y] = \{ x \in A \mid x \mathrel{R} y \}$	everything related to $y$ : read it off the arrows into $y$
$x \in R[y] \iff x \mathrel{R} y \iff (x, y) \in R$	the membership test; $x$ on the left, $y$ on the right
reflexive $+$ symmetric $+$ transitive	an equivalence relation: any two sets $R[y]$ are equal or disjoint

Key Insight: For the equivalence relation $R$ on $A = \{1, 2, 3, 4, 5\}$ the five sets are only two, $\{1, 2, 5\}$ and $\{3, 4\}$ ; for $S$ they are five different sets, and some overlap without being equal.

IIReading $R[y]$ off the Arrows

$R[y]$ collects the starting points of the arrows that end at $y$ , the loop at $y$ included.

Relation Element y 1

IIIEqual, Disjoint, or Overlapping?

Column $y$ of the pair grid is the set $R[y]$ ; the right grid compares every two of these sets.

💡 Challenge: starting from $R$ , remove as few pairs as possible so that two of the sets overlap without being equal.

IVQuiz Questions

Problem 1 · Build One Set

Let $A = \{1, 2, 3, 4\}$ and let $T = \{(1,1), (2,2), (3,3), (4,4), (1,3), (3,1), (2,4), (4,2)\}$ . Find $T[3] = \{ x \in A \mid x \mathrel{T} 3 \}$ .

✅ Correct! The pairs with

3

in second place are

(1, 3)

and

(3, 3)

, so

T[3] = \{1, 3\}

❌ Not quite. The loop

(3, 3)

puts

3

T[3]

, but

(1, 3) \in T

puts

1

there too.

❌ Not quite.

\{2, 4\}

T[2]

and

T[4]

; neither

2

nor

4

is related to

3

❌ Not quite. Keep only the

x

with

(x, 3) \in T

Show solution

By definition $x \in T[3]$ exactly when $(x, 3) \in T$ . Scanning the list for pairs whose second entry is $3$ gives $(3, 3)$ and $(1, 3)$ and nothing else. So

T[3] = \{1, 3\}.

(In the same way $T[1] = \{1, 3\}$ and $T[2] = T[4] = \{2, 4\}$ : two different sets, which are disjoint.)

Problem 2 · The Order Matters

Let $B = \{1, 2, 3\}$ and let $U = \{(1,2), (1,3), (2,2)\}$ . Find $U[1] = \{ x \in B \mid x \mathrel{U} 1 \}$ .

✅ Correct! No pair in

U

has

1

in second place, so nothing is related to

1

❌ That reads the arrows the wrong way.

1 \mathrel{U} 2

and

1 \mathrel{U} 3

are arrows out of

1

;

U[1]

needs arrows into

1

❌ Not quite.

U

is not reflexive:

(1, 1) \notin U

, so

1 \notin U[1]

❌ Not quite. Look for pairs of the form

(x, 1)

Show solution

$x \in U[1]$ exactly when $(x, 1) \in U$ . The second entries of the pairs in $U$ are $2$ , $3$ and $2$ ; none is $1$ . Hence $U[1] = \emptyset$ .

The pairs $(1, 2)$ and $(1, 3)$ say $1 \mathrel{U} 2$ and $1 \mathrel{U} 3$ : they put $1$ into $U[2]$ and $U[3]$ , not anything into $U[1]$ . Indeed $U[2] = \{1, 2\}$ and $U[3] = \{1\}$ .

Problem 3 · Neither Equal nor Disjoint

For the relation $S$ of the video, $S[1] = \emptyset$ , $S[2] = \{1, 2\}$ , $S[3] = \{2, 3, 4\}$ , $S[4] = \{1, 3, 4\}$ and $S[5] = \{5\}$ . Which pair of sets is neither equal nor disjoint?

✅ Correct!

S[2] \cap S[4] = \{1\} \ne \emptyset

, yet

S[2] \ne S[4]

❌ Not quite.

S[5] = \{5\}

shares no element with

S[2]

S[3]

S[4]

: those pairs are disjoint.

❌ Not quite. The empty set meets nothing, so

S[1] \cap S[4] = \emptyset

: disjoint.

❌ Not quite. Compute each intersection.

Show solution

Compute the intersections:

$S[2] \cap S[4] = \{1, 2\} \cap \{1, 3, 4\} = \{1\}$ , and $\{1, 2\} \ne \{1, 3, 4\}$ : neither equal nor disjoint.
$S[2] \cap S[5] = \emptyset$ and $S[3] \cap S[5] = \emptyset$ : disjoint.
$S[1] \cap S[4] = \emptyset \cap S[4] = \emptyset$ : disjoint.

So the answer is $S[2]$ and $S[4]$ . (The pairs $S[2], S[3]$ and $S[3], S[4]$ overlap in the same way.)

Problem 4 · How Many Different Sets?

On $A = \{1, 2, 3, 4, 5, 6\}$ define $x \mathrel{E} y$ when $x + y$ is even. $E$ is an equivalence relation. How many different sets are there among $E[1], E[2], \ldots, E[6]$ ?

✅ Correct!

x + y

is even exactly when

x

and

y

have the same parity, giving

\{1, 3, 5\}

and

\{2, 4, 6\}

❌ Not quite.

1 + 2 = 3

is odd, so

(1, 2) \notin E

and the sets cannot all be the same.

❌ Not quite. Six elements give six names, but different names can give the same set:

E[1] = E[3]

❌ Not quite. When is

x + y

even?

Show solution

$x + y$ is even exactly when $x$ and $y$ are both odd or both even. So

E[1] = E[3] = E[5] = \{1, 3, 5\}, \qquad E[2] = E[4] = E[6] = \{2, 4, 6\}.

There are $2$ different sets, and they are disjoint, as the sets of an equivalence relation must be.

Solved: 0 / 4

Sorting a Set: The Classes of an Equivalence Relation

IKey Formulas

IIReading R[y]R[y]R[y] off the Arrows

IIIEqual, Disjoint, or Overlapping?

IVQuiz Questions

IIReading $R[y]$ off the Arrows