Equivalence relations and partitions - Discrete Math

1. 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$?
   Answer: $h(x) = x^{20} + 2x^{10} + 3$ because of Fermat's Little Theorem reducing exponents 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.
2. 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:
   Answer: $\{\{1\}, \{2, 6\}, \{3\}, \{4\}, \{5\}\}$ 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.
3. 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?
   Answer: The partition has exactly 2 equivalence classes: $\{1, 3, 5\}$ and $\{2, 4, 6\}$ 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.
4. 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?
   Answer: Each equivalence class $[x]$ contains exactly one rational number in the interval $[0,1)$ and is countably infinite 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)$).
5. 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?
   Answer: $\rho$ is an equivalence relation, and polynomials $x^2 + 2x + 3$ and $-x^2 + 4x + 3$ are in the same equivalence class $\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.
6. 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$?
   Answer: Each equivalence class contains all strings that reduce to the same substring when all '01' patterns are removed 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.
7. 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?
   Answer: $S$ is not an equivalence relation because it lacks transitivity $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.
8. 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?
   Answer: 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 $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.
9. 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?
   Answer: The equivalence class is infinite and represents all ordered pairs equivalent to the fraction $\frac{6}{9} = \frac{2}{3}$ When you encounter equivalence relations defined on ordered pairs, think about what mathematical structure they're creating. This relation $(a,b) R (c,d)$ if $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.
10. 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$?
    Answer: 12 ordered pairs, representing the new connections between former classes $A_1$ and $A_3$ 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$ or $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.
11. 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?
    Answer: Either $2 \sim 8$ and $3 \sim 6$, or $2 \sim 6$ and $3 \sim 8$, with 8 and 6 in different blocks 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.
12. 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?
    Answer: The equivalence class is $\{(x, y) \in \mathbb{R}^2 : x - y = -3\}$, which represents a line with slope 1 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.
13. 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?
    Answer: $R$ is not an equivalence relation because it fails to be reflexive on all elements of $S$ For $R$ to be reflexive, we need $aRa$ for all $a \in S$, which means $a + a \equiv 1 \pmod{3}$ or $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.
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$?
    Answer: $W$ is not an equivalence relation because it fails transitivity when elements satisfy different conditions 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.

Start this quiz