On the set of all integers, define
is an equivalence relation, so it cuts into equivalence classes. Exactly one of the four statements below is false. Which one?
Confirming your payment
Competency-Based Questions (CBQ) · Question 43 of 80
On the set of all integers, define
is an equivalence relation, so it cuts into equivalence classes. Exactly one of the four statements below is false. Which one?
(A) for every , so is the set of all multiples of
(B) , because and divides
(C) , and yet
(D) is an infinite set, so must have infinitely many distinct classes
Option (D) is correct — that is, (D) is the false statement.
Explanation: The key move is to separate two different kinds of "how many". Each class here is an infinite set, but there are only finitely many classes.
Where the classes come from. Divide any integer by . The remainder can only be , or , so
for some integer . Two integers are related exactly when their remainders match, because is a multiple of precisely then. So there are exactly three classes:
| Class | Its members | A typical member |
|---|---|---|

They are disjoint and they exhaust . No integer can leave two different remainders on division by , so no integer lies in two of the classes: . And every integer leaves some remainder, so every integer lies in one of them: . This is exactly what " partitions " means.
So (D) is false. Three classes, not infinitely many. What is infinite is the size of each class, not the number of classes. The number of classes is decided by the possible remainders on division by , and there are only three of those.
Why the true statements are true:
| Option | Why it is true |
|---|---|
| (A) | is a multiple of for every integer , so every multiple of is related to ; and nothing else is, since a non-multiple leaves remainder or . Hence , one single class. |
| (B) | , so divides and therefore . Related elements always have the same class, so . Watch the sign: , and the remainder is , not . |
| (C) | Shown above. Both halves matter: disjoint means no overlap, and the union being all of means nothing is left over. |