Cardinality of equivalence classes in a set

Question

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.

Answer 1

Guide:

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.

Answer 2

(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.