I'm facing some difficulties with a transitivity proof to show that a relation is indeed an equivalence relation.

Let $R$ be a relation on $\mathscr{P}(\mathbb{N})$ and $P, Q \in \mathscr{P}(\mathbb{N})$. Then $(P, Q) \in R$ iff $|P\triangle Q| \in \mathbb{N}$. (Here, $0 \in \mathbb{N}$) I have managed to show the two trivial cases of reflexivity and symmetry, but I'm stuck at proving transitivity for this relation.

In my understanding only the cases where $P$ or $Q$ (but not both) are equal to $\mathbb{N}$ result in $(P, Q) \notin R$. If that is correct, $(P, Q) \in R \Longleftrightarrow (|P| \in \mathbb{N} \wedge |Q| \in \mathbb{N})\vee (P = Q)$.

Is this assumption correct? If so, I'd be able to show transitivity from there. If not, how could I go about showing transitivity?

  • $\begingroup$ Your assumption is wrong. Take $P$ to be all the evens, and take $Q$ to be all the multiples of $4$. Then the symmetric set difference is all multiples of $2$ that aren't multiples of $4$, a set which is not finite. $\endgroup$ – symplectomorphic Nov 4 '17 at 17:51
  • $\begingroup$ That makes sense, thanks. $\endgroup$ – Padarom Nov 4 '17 at 17:55

Your Answer

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

Browse other questions tagged or ask your own question.