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

Equivalence Classes: Everything Equivalent to y

IKey Formulas

Formula	Meaning
$[y] = \{ x \in A \mid x \sim y \}$	the equivalence class of $y$ , for an equivalence relation $\sim$ on $A$
$[y]_\sim,\ \ R[y],\ \ [y]_R$	the same class, naming the relation when more than one is in use
$[y] \subseteq A$ , $\ y \in A$	a class is a subset; the element that names it is an element
$[0], [1], \ldots, [n-1]$	the $n$ distinct congruence classes modulo $n$ , one per remainder

Key Insight: Every element names a class, but many names give the same class: $[7] = [10] = [-2] = [1]$ for congruence modulo $3$ .

IIThe Integers in $n$ Panels

Congruence modulo $n$ cuts the integers into $n$ congruence classes, one for each remainder.

Modulus n 3 Element y 7

IIIWhich Class Modulo 4?

Each integer lies in exactly one of $[0]$ , $[1]$ , $[2]$ , $[3]$ for congruence modulo $4$ .

IVQuiz Questions

Problem 1 · A Roster Modulo 4

For congruence modulo $4$ on $\mathbb{Z}$ , which roster is the class $[3]$ ?

✅ Correct! Start at

3

and step by

4

in both directions.

❌ Not quite.

-3 = 4(-1) + 1

lies in

[1]

; mirroring the positive entries does not keep the remainder.

❌ Not quite. That is

[0]

for congruence modulo

3

; here the step is

4

❌ Not quite. The class also contains negative integers, for instance

-1 = 4(-1) + 3

Show solution

$x \in [3]$ exactly when $x \equiv 3 \pmod 4$ , that is, $x = 3 + 4k$ for some integer $k$ . Taking $k = -3, -2, -1, 0, 1, 2$ gives

[3] = \{\ldots, -9, -5, -1, 3, 7, 11, \ldots\}.

Check a negative entry: $-1 = 4(-1) + 3$ , remainder $3$ .

Problem 2 · Element or Subset?

For congruence modulo $2$ on $\mathbb{Z}$ , which statement is true?

✅ Correct! The class

[1]

is the set of odd integers: a subset of

\mathbb{Z}

that contains

1

❌ Not quite.

[1]

is a set of integers and

1

is an integer; a set is never equal to one of its elements here.

❌ Not quite.

[1]

is not an integer; it is a subset of

\mathbb{Z}

❌ Not quite.

[1]

is the odd integers and

[0]

the even integers; they are disjoint.

Show solution

$[1] = \{ x \in \mathbb{Z} \mid x \equiv 1 \pmod 2 \} = \{\ldots, -3, -1, 1, 3, 5, \ldots\}$ , the odd integers. It is a subset of $\mathbb{Z}$ , and $1 \equiv 1 \pmod 2$ (reflexivity) puts $1$ in it. It is not an integer, not equal to $1$ , and shares no element with $[0]$ , the even integers.

Problem 3 · A Class on a Finite Set

On $A = \{1, 2, 3, 4, 5, 6\}$ define $x \mathrel{R} y$ when $\lceil x/2 \rceil = \lceil y/2 \rceil$ . This is an equivalence relation. Find $[4]_R$ .

✅ Correct!

\lceil 4/2 \rceil = 2

, and the only elements with

\lceil x/2 \rceil = 2

are

3

and

4

❌ Not quite.

4 \in [4]_R

, but so is every

x

with

\lceil x/2 \rceil = 2

❌ Not quite.

\lceil 5/2 \rceil = 3 \ne 2

, so

5

is not related to

4

❌ Not quite. That groups by parity; compute

\lceil x/2 \rceil

instead.

Show solution

The values of $\lceil x/2 \rceil$ for $x = 1, \ldots, 6$ are $1, 1, 2, 2, 3, 3$ . Since $\lceil 4/2 \rceil = 2$ ,

[4]_R = \{ x \in A \mid \lceil x/2 \rceil = 2 \} = \{3, 4\}.

$R$ has three classes, $\{1, 2\}$ , $\{3, 4\}$ and $\{5, 6\}$ ; six elements give six names but only three classes.

Problem 4 · Congruence Modulo 7

Consider congruence modulo $7$ on $\mathbb{Z}$ .

How many distinct congruence classes are there?

Which class contains $-23$ ?

✅ Correct! Seven remainders give seven classes, and

-23 = 7(-4) + 5

❌ Count the remainders. Dividing by

7

leaves

0, 1, \ldots, 6

: one class for each.

❌ Check the remainder. The multiple of

7

just below

-23

-28

Show solution

Each integer is congruent modulo $7$ to exactly one of $0, 1, \ldots, 6$ , so the distinct classes are $[0], [1], \ldots, [6]$ : seven of them. Infinitely many integers name classes, but $[k] = [r]$ whenever $r$ is the remainder of $k$ .

-23 = 7(-4) + 5,

so $-23 \equiv 5 \pmod 7$ and $-23 \in [5]$ . (Negating $23 = 7 \cdot 3 + 2$ would give $-2$ , which is not a remainder.)

Solved: 0 / 4

Equivalence Classes: Everything Equivalent to y

IKey Formulas

IIThe Integers in nnn Panels

IIIWhich Class Modulo 4?

IVQuiz Questions

IIThe Integers in $n$ Panels