Let $S$ be the equivalence relation defined on $\wp(\{1, 2, 3, 4\})$ defined by: $$XSY\text{ if and only if } |X|\equiv|Y|\;\mod 2$$ Write down the equivalence classes of S.

I understand that equivalence classes have relations where it is reflexive, symmetric and transitive but how are you supposed to write equivalence classes?

  • $\begingroup$ It is not the absolute value. It is the cardinality, i.e. (for finite sets) the number of its elements. $\endgroup$ Apr 30, 2019 at 7:57
  • $\begingroup$ Presumably $|X|$ means the number of elements of $X$. If $X$ is in the power set of $A$ then its elements are some (or all or none) of the elements of $A$ $\endgroup$
    – Henry
    Apr 30, 2019 at 7:58

2 Answers 2


What you're calling the "absolute value of a set" is actually referred to as its cardinality. For finite sets, which is the relevant case here, cardinality is how many elements are in the set. It gets a bit murkier with infinite sets but I won't bog you down with the details here.

So in short: you look at the power set of $\{1,2,3,4\}$, i.e. the set of subsets of that. You then define the relation $S$ on these sets, where two sets, $X,Y$ are related if their cardinalities satisfy $|X| \equiv |Y| \pmod 2$.

Equivalently, let $X$ have $n$ elements and $Y$ have $m$ elements, where $X,Y \in P(\{1,...,4\})$. Then $XSY$ if and only if $n \equiv m \pmod 2$.


In particular, there are only two equivalence classes of $S$. One is, denoted by $\overline{0}$, $$\{ \emptyset, \{1, 2\}, \{ 1, 3\}, \{1, 4\}, \{2,3\},\{2,4\},\{3,4\},\{1,2,3,4\} \}.$$ And the other one is, denoted by $\overline{1}$ $$ \{ \{1\},\{2\},\{3\},\{4\}, \{2,3,4\},\{1,3,4\},\{1,2,4\},\{1,2,3\}\}.$$

  • 1
    $\begingroup$ I do not quite understand how you got those values as the answer, what does the line above the number mean? Sorry I'm a beginner in discrete maths. $\endgroup$
    – Andrea
    Apr 30, 2019 at 8:54
  • $\begingroup$ You can see @Eevee Trainer's answer, $\overline{0}$ contains all the subsets of cardinalities 0,2 and 4, which are $0 \pmod{2}$. and $\overline{1}$ contains all the subsets of cardinalities 1 and 3, which are $1 \pmod{2}$. That's why I use the two notations, $\overline{0}$ and $\overline{1}$. $\endgroup$ Apr 30, 2019 at 8:58

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.