Discrete Math Quiz: Equivalence Relations And Partitions

14 questions · exam conditions

0:00

Equivalence Relations And PartitionsQuestion 1 of 14

Let $W$ be the relation on $\{1,2,3,4,5,6,7,8,9\}$ where $aWb$ if and only if $a$ and $b$ have the same remainder when divided by 3, OR both $a$ and $b$ are greater than 6. Which of the following best describes the partition induced by $W$ ?

W

is not an equivalence relation because it fails transitivity when elements satisfy different conditions

The partition has 3 classes:

\{1,4,7\}

\{2,5,8\}

, and

\{3,6,9\}

based solely on remainders mod 3

The partition has 2 classes:

\{1,2,3,4,5,6\}

and

\{7,8,9\}

based on the threshold condition

The partition has 2 classes:

\{1,2,3,4,5,6\}

(remainder condition) and

\{7,8,9\}

(threshold condition only)

← Back to quizzes

Discrete Math Quiz

Discrete Math Quiz: Equivalence Relations And Partitions

Practice Equivalence Relations And Partitions in Discrete Math with focused quiz questions that help you check what you know, review explanations, and build confidence with test-style prompts.

What this quiz covers

This quiz focuses on Equivalence Relations And Partitions, giving you a quick way to practice the rules, question types, and explanations that matter most for Discrete Math.

How to use this quiz

Try each quiz question before looking at the correct answer. Use the explanations to review missed ideas, then come back to similar questions until the pattern feels familiar.

All questions

Question 1

$W$ is not an equivalence relation because it fails transitivity when elements satisfy different conditions (correct answer)
The partition has 3 classes: $\{1,4,7\}$ , $\{2,5,8\}$ , and $\{3,6,9\}$ based solely on remainders mod 3
The partition has 2 classes: $\{1,2,3,4,5,6\}$ and $\{7,8,9\}$ based on the threshold condition
The partition has 2 classes: $\{1,2,3,4,5,6\}$ (remainder condition) and $\{7,8,9\}$ (threshold condition only)

Explanation: Consider

1W7

(both have remainder 1 mod 3),

7W8

(both > 6), but

1 \not W 8

since 1 and 8 have different remainders mod 3 and 1 is not > 6. This violates transitivity. The relation combines two different conditions with OR, creating a situation where transitivity fails. Choices B and C incorrectly assume the relation is an equivalence relation and attempt to describe its partition. Choice D makes the same error while misunderstanding how the conditions interact.

Question 2

Consider the relation $\rho$ on the set $\mathbb{Q}$ of rational numbers defined by $a\rho b$ if and only if $a - b$ is an integer. Let $[x]$ denote the equivalence class of $x$ under $\rho$ . Which statement about the structure of these equivalence classes is correct?

Each equivalence class $[x]$ contains exactly one rational number in the interval $[0,1)$
Every equivalence class has the same cardinality as $\mathbb{Z}$ and is countably infinite
The set of all equivalence classes has the same cardinality as $\mathbb{R}$ and is uncountable
Each equivalence class $[x]$ contains exactly one rational number in the interval $[0,1)$ and is countably infinite (correct answer)

Explanation: Two rationals

a

and

b

are equivalent iff

a - b \in \mathbb{Z}

, i.e., they have the same fractional part. Each equivalence class

[x]

consists of all rationals of the form

\{x\} + n

where

\{x\}

is the fractional part of

x

and

n \in \mathbb{Z}

. This means each class contains exactly one representative in

[0,1)

and is countably infinite (in bijection with

\mathbb{Z}

). Choice A misses that classes are infinite. Choice B misses the unique representative property. Choice C incorrectly describes the cardinality of the quotient set (there are only countably many rationals in

[0,1)

Question 3

A computer science student defines relation $V$ on the set of all finite binary strings where $sVt$ if and only if string $s$ can be obtained from string $t$ by any sequence of the following operations: (1) inserting '01' anywhere in the string, (2) deleting '01' from anywhere in the string. Which statement correctly characterizes the equivalence classes of $V$ ?

Each equivalence class contains all strings with the same number of '1' bits
Each equivalence class contains all strings with the same length modulo 2
Each equivalence class contains all strings that reduce to the same substring when all '01' patterns are removed (correct answer)
Each equivalence class contains all strings with the same number of '01' substrings

Explanation: Since we can insert or delete '01' freely, two strings are equivalent iff they have the same 'reduced form' after removing all possible '01' substrings. For example, '1101' reduces to '11' (removing one '01'), and any string equivalent to '1101' must also reduce to '11'. Choice A is wrong because '11' and '101' have the same number of 1s but different reduced forms ('11' vs '1'). Choice B is wrong because length changes arbitrarily with '01' operations. Choice D is wrong because the number of '01' substrings changes during the operations.

Question 4

Let $\mathcal{P} = \{A_1, A_2, A_3, A_4\}$ be a partition of a set $X$ with $|A_1| = 3$ , $|A_2| = 5$ , $|A_3| = 2$ , and $|A_4| = 4$ . If we define a new relation $T$ on $X$ by merging $A_1$ and $A_3$ into a single equivalence class while keeping $A_2$ and $A_4$ separate, how many ordered pairs are in the symmetric difference of the original equivalence relation and $T$ ?

12 ordered pairs, representing the new connections between former classes $A_1$ and $A_3$ (correct answer)
24 ordered pairs, accounting for both directions of the new equivalences created
36 ordered pairs, including all bidirectional relationships in the merged class
48 ordered pairs, representing the total change in the equivalence structure

Explanation: The original equivalence relation has pairs within each

A_i

. Relation

T

merges

A_1

and

A_3

, so it has all pairs from the original relation plus new pairs

(a,b)

where

a \in A_1, b \in A_3

a \in A_3, b \in A_1

. The symmetric difference contains only these new pairs:

|A_1| \times |A_3| + |A_3| \times |A_1| = 3 \times 2 + 2 \times 3 = 12

. Choice B incorrectly doubles this count. Choice C miscalculates by including existing internal pairs. Choice D overestimates the total structural change.

Question 5

Consider the equivalence relation $\equiv$ on $\mathbb{Z}$ defined by $a \equiv b$ if and only if $a^2 - b^2$ is divisible by 8. Which of the following correctly describes the equivalence classes of this relation?

Four equivalence classes: $[0], [1], [2], [3]$ where $[k] = \{n \in \mathbb{Z} : n \equiv k \pmod{4}\}$
Four equivalence classes where $0 \equiv 4$ , $1 \equiv 3 \equiv 5 \equiv 7$ , $2 \equiv 6$ , with distinct classes $\{[0], [1], [2]\}$ based on squares modulo 8 (correct answer)
Two equivalence classes: even integers and odd integers
Eight equivalence classes corresponding to residues modulo 8

Explanation:

a \equiv b

iff

8 | (a^2 - b^2)

. Computing squares modulo 8:

0^2 \equiv 0, 1^2 \equiv 1, 2^2 \equiv 4, 3^2 \equiv 1, 4^2 \equiv 0, 5^2 \equiv 1, 6^2 \equiv 4, 7^2 \equiv 1 \pmod{8}

. Elements with the same square modulo 8 are equivalent. This gives equivalence classes:

\{0, 4\}

(squares

\equiv 0

\{1, 3, 5, 7\}

(squares

\equiv 1

\{2, 6\}

(squares

\equiv 4

). There are 3 distinct equivalence classes, not 4. Choice A incorrectly uses modulo 4. Choice C oversimplifies to parity. Choice D incorrectly suggests 8 classes.

Question 6

Let $S = \{1, 2, 3, 4, 5, 6, 7, 8, 9\}$ and suppose $\mathcal{P} = \{A_1, A_2, A_3\}$ is a partition of $S$ where each $A_i$ has exactly 3 elements. If we know that $1 \sim 4 \sim 7$ , $2 \sim 5$ , and $3 \sim 9$ under the equivalence relation corresponding to $\mathcal{P}$ , what additional relationship must be true?

Either $2 \sim 8$ or $3 \sim 6$ or $6 \sim 8$ , but not multiple relationships simultaneously
Exactly two of the following: $2 \sim 8$ , $3 \sim 6$ , $6 \sim 8$
All three relationships $2 \sim 8$ , $3 \sim 6$ , and $6 \sim 8$ must hold
Either $2 \sim 8$ and $3 \sim 6$ , or $2 \sim 6$ and $3 \sim 8$ , with 8 and 6 in different blocks (correct answer)

Explanation: We have

A_1 = \{1, 4, 7\}

(complete). The remaining elements

\{2, 3, 5, 6, 8, 9\}

must be split into two blocks of size 3 each. We know

2 \sim 5

and

3 \sim 9

. Each of these pairs needs one more element to complete their respective blocks. The remaining elements are 6 and 8. So either: (i)

\{2, 5, 6\}

and

\{3, 8, 9\}

, giving us

2 \sim 6

and

3 \sim 8

, or (ii)

\{2, 5, 8\}

and

\{3, 6, 9\}

, giving us

2 \sim 8

and

3 \sim 6

. In both cases, 6 and 8 are in different blocks. Choices A, B, and C incorrectly suggest that 6 and 8 could be in the same block or that multiple simultaneous relationships are impossible.

Question 7

Consider the set $P$ of all polynomials with integer coefficients. Define relation $\gamma$ on $P$ by $p(x) \gamma q(x)$ if and only if $p(n) \equiv q(n) \pmod{5}$ for all integers $n$ . Which polynomial is in the same equivalence class as $f(x) = x^4 + 2x^2 + 3$ ?

$g(x) = x^4 + 7x^2 + 8$ because coefficients are congruent modulo 5
$h(x) = x^{20} + 2x^{10} + 3$ because of Fermat's Little Theorem reducing exponents (correct answer)
$k(x) = x^8 + 2x^4 + 3$ because higher powers cycle modulo 5 by periodicity
$m(x) = 6x^4 + 12x^2 + 13$ because all coefficients differ by multiples of 5

Explanation: By Fermat's Little Theorem, for any integer

n

and prime

p = 5

, we have

n^5 \equiv n \pmod{5}

. For any integer

n

, this gives us

n^{20} = (n^5)^4 \equiv n^4 \pmod{5}

and

n^{10} = (n^5)^2 \equiv n^2 \pmod{5}

. Therefore,

h(n) = n^{20} + 2n^{10} + 3 \equiv n^4 + 2n^2 + 3 = f(n) \pmod{5}

for all integers

n

. Choice A fails because having congruent coefficients mod 5 is not sufficient—we need the polynomial values to be congruent for all integer inputs. Choices C and D can be verified to fail by checking specific values.

Question 8

Define relation $T$ on $\mathbb{R}^2$ by $(a,b) T (c,d)$ if and only if $a + d = b + c$ . If $T$ is an equivalence relation, which of the following statements about the equivalence class containing $(2, 5)$ is true?

The equivalence class is $\{(x, y) \in \mathbb{R}^2 : x - y = -3\}$ , which represents a line with slope 1 (correct answer)
The equivalence class is $\{(x, y) \in \mathbb{R}^2 : x + y = 7\}$ , which represents a line with slope -1
The equivalence class is $\{(x, y) \in \mathbb{R}^2 : y - x = 3\}$ , which represents a line with slope 1
The equivalence class is $\{(x, y) \in \mathbb{R}^2 : |x - y| = 3\}$ , which represents two parallel lines

Explanation: For

(x,y)

to be equivalent to

(2,5)

, we need

2 + y = 5 + x

, which simplifies to

x - y = 2 - 5 = -3

. This gives the line

y = x + 3

, which has slope 1. Choice A correctly identifies this condition and slope. Choice B incorrectly uses

x + y = 7

(slope -1) which would come from

2 + y = 5 - x

. Choice C has the right slope but wrong equation (

y - x = 3

means

x - y = -3

, which is correct, but the way it's written suggests

y = x + 3

). Choice D incorrectly uses absolute value, giving two lines instead of one.

Question 9

Let $P_1 = \{\{1, 3\}, \{2, 4, 6\}, \{5\}\}$ and $P_2 = \{\{1\}, \{2, 6\}, \{3, 5\}, \{4\}\}$ be two partitions of the set $\{1, 2, 3, 4, 5, 6\}$ . The partition that corresponds to the equivalence relation $R_1 \cap R_2$ (where $R_i$ is the equivalence relation corresponding to $P_i$ ) is:

$\{\{1\}, \{2\}, \{3\}, \{4\}, \{5\}, \{6\}\}$
$\{\{1, 3\}, \{2, 4, 6\}, \{5\}\}$
$\{\{1\}, \{2, 6\}, \{3\}, \{4\}, \{5\}\}$ (correct answer)
$\{\{1\}, \{3, 5\}, \{2, 4, 6\}\}$

Explanation: For

R_1 \cap R_2

, elements

a

and

b

are related iff they are in the same block in BOTH

P_1

AND

P_2

. Checking each pair: (1,3) are together in

P_1

but separate in

P_2

, so not related in intersection. (2,4) and (2,6) are together in

P_1

, but only (2,6) are together in

P_2

. (4,6) are together in

P_1

but separate in

P_2

. (3,5) are separate in

P_1

. Only (2,6) remain together in both partitions. All other elements are isolated. Choice A would be correct only if no pairs were together in both partitions. Choices B and D incorrectly preserve relationships that don't exist in both partitions.

Question 10

Define relation $R$ on $\mathbb{Z} \times \mathbb{Z}$ by $(a,b) R (c,d)$ if and only if $ad = bc$ . This relation partitions $\mathbb{Z} \times \mathbb{Z}$ into equivalence classes. Which statement about the equivalence class containing $(6, 9)$ is true?

The equivalence class contains exactly 4 elements from the set $\{(2,3), (4,6), (8,12), (10,15)\}$
The equivalence class contains exactly 3 elements from the set $\{(2,3), (4,6), (8,12), (10,15)\}$
The equivalence class is infinite and represents all ordered pairs equivalent to the fraction $\frac{6}{9} = \frac{2}{3}$ (correct answer)
The equivalence class is finite and contains all pairs $(a,b)$ where $\gcd(a,b) = 3$

Explanation: When you encounter equivalence relations defined on ordered pairs, think about what mathematical structure they're creating. This relation

(a,b) R (c,d)

ad = bc

is actually capturing when two fractions

\frac{a}{b}

and

\frac{c}{d}

are equal (assuming non-zero denominators). To find the equivalence class containing

(6,9)

, you need all pairs

(a,b)

such that

(6,9) R (a,b)

, meaning

6b = 9a

, or equivalently

\frac{a}{b} = \frac{6}{9} = \frac{2}{3}

. This gives you infinitely many pairs:

(2,3)

(4,6)

(6,9)

(8,12)

(10,15)

(-2,-3)

(20,30)

, and so on. Any pair where the second coordinate is

\frac{3}{2}

times the first coordinate belongs to this class. Option A claims exactly 4 elements from the given set belong to the class, but checking:

(2,3)

(4,6)

(8,12)

, and

(10,15)

all satisfy

\frac{a}{b} = \frac{2}{3}

, so all 4 are included, making this count correct but missing that the class is infinite. Option B incorrectly counts only 3 of the 4 qualifying pairs. Option D incorrectly focuses on

\gcd(a,b) = 3

. While

(6,9)

has

\gcd(6,9) = 3

, pairs like

(2,3)

with

\gcd(2,3) = 1

are also in the same equivalence class. Option C correctly identifies that the equivalence class is infinite and represents all pairs equivalent to the reduced fraction

\frac{2}{3}

. Study tip: Equivalence relations on ordered pairs often relate to fraction equality. Always check if the relation preserves some ratio or quotient.

Question 11

Let $S = \{1, 2, 3, 4, 5, 6\}$ and define relation $R$ on $S$ by $aRb$ if and only if $a + b \equiv 1 \pmod{3}$ . Which of the following statements about $R$ is true?

$R$ is an equivalence relation with equivalence classes $\{1, 4\}$ , $\{2, 5\}$ , and $\{3, 6\}$
$R$ is not an equivalence relation because it fails to be reflexive on all elements of $S$ (correct answer)
$R$ is not an equivalence relation because it fails to be symmetric for some pairs in $S$
$R$ is not an equivalence relation because it fails to be transitive for some triples in $S$

Explanation: For

R

to be reflexive, we need

aRa

for all

a \in S

, which means

a + a \equiv 1 \pmod{3}

2a \equiv 1 \pmod{3}

. Testing:

2(1) = 2 \not\equiv 1 \pmod{3}

2(2) = 4 \equiv 1 \pmod{3}

2(3) = 6 \equiv 0 \not\equiv 1 \pmod{3}

. Since

1R1

and

3R3

are false,

R

is not reflexive. Choice A gives equivalence classes for a different relation. Choice C is wrong because

R

is symmetric: if

a + b \equiv 1 \pmod{3}

, then

b + a \equiv 1 \pmod{3}

. Choice D is incorrect as transitivity issues are secondary to the reflexivity failure.

Question 12

Consider the set $X = \{a, b, c, d, e, f\}$ with partition $P = \{\{a, c\}, \{b, e, f\}, \{d\}\}$ . If we define relation $R$ on $X$ such that $xRy$ if and only if $x$ and $y$ are in the same block of $P$ , and then define a new relation $S$ on $X$ by $xSy$ if and only if $xRy$ or $x = d$ or $y = d$ , which statement about $S$ is correct?

$S$ is an equivalence relation with three equivalence classes
$S$ is an equivalence relation with two equivalence classes: $\{a, c, d\}$ and $\{b, e, f\}$
$S$ is not an equivalence relation because it lacks symmetry
$S$ is not an equivalence relation because it lacks transitivity (correct answer)

Explanation:

S

is reflexive (each element relates to itself either through

R

or the

d

condition) and symmetric (if

xSy

, then

ySx

by the same reasoning). However,

S

fails transitivity:

aSd

(since

y = d

dSb

(since

x = d

), but

a \not S b

because

a

and

b

are in different blocks of

P

and neither is

d

. Choice A is wrong about the number of classes. Choice B incorrectly assumes

S

is an equivalence relation and miscalculates the classes. Choice C is incorrect since

S

is symmetric.

Question 13

Consider the relation $\rho$ on the set of all polynomials with real coefficients defined by $p(x) \rho q(x)$ if and only if $p(0) = q(0)$ and $p(1) = q(1)$ . Which statement about $\rho$ is correct?

$\rho$ is an equivalence relation, and polynomials $x^2 + 2x + 3$ and $-x^2 + 4x + 3$ are in the same equivalence class (correct answer)
$\rho$ is an equivalence relation, but polynomials $x^2 + 2x + 3$ and $-x^2 + 4x + 3$ are in different equivalence classes
$\rho$ is not an equivalence relation because it fails transitivity for some polynomial triples
$\rho$ is not an equivalence relation because it fails reflexivity for some polynomials

Explanation:

\rho

is reflexive (

p(0) = p(0)

and

p(1) = p(1)

), symmetric (if

p(0) = q(0)

and

p(1) = q(1)

, then

q(0) = p(0)

and

q(1) = p(1)

), and transitive (if

p \rho q

and

q \rho r

, then

p(0) = r(0)

and

p(1) = r(1)

). For

p(x) = x^2 + 2x + 3

p(0) = 3

p(1) = 6

. For

q(x) = -x^2 + 4x + 3

q(0) = 3

q(1) = -1 + 4 + 3 = 6

. Since both conditions match,

p \rho q

. Choice B incorrectly claims they're in different classes. Choices C and D incorrectly claim

\rho

is not an equivalence relation.

Question 14

Let $R$ be a relation on $\{1, 2, 3, 4, 5, 6\}$ defined by $aRb$ if and only if $a^2 \equiv b^2 \pmod{4}$ . Which of the following statements about the partition induced by $R$ is correct?

The partition has exactly 2 equivalence classes: $\{1, 3, 5\}$ and $\{2, 4, 6\}$ (correct answer)
The partition has exactly 3 equivalence classes: $\{1, 5\}$ , $\{2, 6\}$ , and $\{3, 4\}$
The partition has exactly 4 equivalence classes with sizes 2, 2, 1, and 1
The partition has exactly 6 equivalence classes, each containing exactly one element

Explanation: First, we compute

a^2 \bmod 4

for each element:

1^2 \equiv 1 \pmod{4}

2^2 \equiv 0 \pmod{4}

3^2 \equiv 1 \pmod{4}

4^2 \equiv 0 \pmod{4}

5^2 \equiv 1 \pmod{4}

6^2 \equiv 0 \pmod{4}

. Elements are equivalent if their squares have the same remainder mod 4. This gives us two classes:

\{1, 3, 5\}

(remainder 1) and

\{2, 4, 6\}

(remainder 0). Choice B incorrectly separates elements with the same remainder. Choice C gives the wrong number of classes. Choice D fails to recognize that this relation creates non-trivial equivalences.