Given $X = \{1, 2, 3, 4\}$. Define a relation $\mathbf{R}$ over $P(X)$ as follows: For two elements $A,B ∈ P(X)$, $A \mathrel{\mathbf{R}} B$ if $|A| ≡ |B| \pmod{3}$.

(a) Demonstrate that the previous relation is an equivalence relation.

(b) Determine the cardinality of every equivalence class.

I have found how many classes in there which is the trivial part of the question as it is modulo $3$ then we have three classes $C_0$, $C_1$, $C_2$.

But I am not able to demonstrate that the previous relation is an equivalence relation or the cardinality of the equivalence classes.

Sorry for being inefficient even tho the question might be easy.



You have to show the following.

  • Reflexive, $\forall A \in P(X), ARA$.
  • Symmetric, $ARB \implies BRA$.
  • Transitive, $ARB \land BRC \implies A RC$

In particular, transitivity is simply $|A|\equiv |B| \pmod{3}$ and $|B|\equiv |C| \pmod{3}$, then we have $|A| \equiv |C| \pmod{3}$.

Try to write out what they mean and you should be able to use the property of modulo arithmetic to see why it is an equivalence relation.

As for how many members each equivalence class has. Try to answer the following question.

  • How many subsets have exactly $1$ or $4$ elements.
  • How many subsets have exactly $2$ elements.
  • How many subsets have exactly $0$ or $3$ elements.
  • $\begingroup$ For the transitivity it is clear, but still the second part of how many subsets I can't recognize how many subsets it is the thing that I can't work on I know it is simple but I don't know how to approach it. $\endgroup$ – CptPackage Jul 14 '18 at 14:28
  • $\begingroup$ To construct a subset of $i$ element, out of the $4$ elements, you have to choose $i$ elements. Hence there are $4$ choose $i = \binom{4}{i}=\frac{4!}{i!(4-i)!}$ such subsets. Using this property, can you determine how many subset has $0$ elements? what about $1$ element and so on? $\endgroup$ – Siong Thye Goh Jul 14 '18 at 14:34
  • $\begingroup$ There are $3$ equivalence class, but the question is how many subsets are there in those equivalence classes. For example $C_0$ consists of subsets with either $0$ elements or $3$ elements, $C_0=\{ \emptyset, \{1,2,3\}, \{1,2,4\}, \{ 1,3,4\}, \{2,3,4\} \}$. Note that $0 \equiv 3 \pmod{3}$. What is the cardinality of $C_0$? $\endgroup$ – Siong Thye Goh Jul 14 '18 at 14:41
  • $\begingroup$ Alright, I can only use the binomial coefficient and it will work but I want to ask something. So C0 is the class containing the empty element, and all the possible combinations of 3 elements as 0 mod 3 = 0 and 3 mod 3 = 0 so it will be the same equivalence class, but for C1 it will the combination of the subsets of 1 element each right? Like C1={{1},{2},{3},{4}} but it will have the cardinality of 4 not 5 which is wrong. And C2 will be C2={{1,2},{1,3},{1,4},{2,3},{2,4},{3,4}} right? So can you please explain to me this small part? Sorry, I know I have been exhausting enough. $\endgroup$ – CptPackage Jul 14 '18 at 14:49
  • $\begingroup$ $C_1$ is the class containing subsets of $1$ element and $4$ elements since $1 \equiv 4 \pmod{3}$, so $|C_1|=5$. You have listed $C_2$ correctly. Without listing it, the computation is just $\binom{4}{2}=6$. Don't worry about how long you ask the question, just make sure you are learning. ;) $\endgroup$ – Siong Thye Goh Jul 14 '18 at 14:55

(a) Reflexive: $|A|\equiv|A|$. Symmetric: $|A|\equiv|B|\implies|B|\equiv|A|$. Transitive: if $|A|\equiv|B|\equiv|C|$, integers $m,\,n$ exist with $|A|=|B|+3m=|C|+3m+3n$.

(b) There are $1,\,4,\,6,\,4,\,1$ subsets of sizes $0,\,\cdots,\,4$. One equivalence class is for cardinalities $0$ and $3$, and is of size $1+4=5$; another covers $1$ and $4$, and again there are $5$ elements; the last is just the size-$2$ case, with the remaining $6$ elements.

  • $\begingroup$ Alright I can get it with the first answer, but the second one isn't very clear for me can you please simplify it more if possible? $\endgroup$ – CptPackage Jul 14 '18 at 14:25
  • $\begingroup$ @CptPackage Which part needs simplifying? Counting subsets by size with a row of Pascal's triangle, or grouping subset sizes modulo $3$? $\endgroup$ – J.G. Jul 14 '18 at 14:50
  • $\begingroup$ Grouping subsets, Mr.Siong Thye Goh showed me that we can get the results using the binomial coefficient which I didn't know about so sorry for being an ignorant. But can you please show me the combination of the subsets in the equivalence classes? Like C1={{1},{2},{3},{4}}.. $\endgroup$ – CptPackage Jul 14 '18 at 14:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.