By using a Venn diagram we can see almost immediately that the cardinality of the members of the equality is in fact the same, however the exercise asks me to prove it formally and there is where my problem lies.

I have though on making a bijection to prove it, I just don't see how I can do it when I am not given any more information in the statement, can someone guide me to what I have to do?

Thanks a lot.

  • $\begingroup$ To formalize the argument "each part of the Venn diagram except the intersection is cancelled, and the intersection cancels except for one term": You could write $|A| = |A \cap B \cap C| + |A \cap B^c \cap C| + |A \cap B \cap C^c| + |A \cap B^c \cap C^c|$ and similarly $|A \cap B| = |A\cap B\cap C| + |A\cap B\cap C^c|$. $\endgroup$ – Daniel Schepler Nov 21 '18 at 22:44

HINT: First prove that $|A\cup B|=|A|+|B|-|A\cap B|$, and then use this and the fact that $\cup$ and $\cap$ are associative to prove the formula for $|A\cup B\cup C|$.

  • $\begingroup$ Okay, but my question is, how do I formally prove that that equality does in fact have the same cardinality, I know I have to be able to map every element, but do I just take an arbitrary x? I don't know how many elements they have, or if they are even countable. $\endgroup$ – tuesday1234 Nov 21 '18 at 22:41
  • $\begingroup$ @tuesday1234 It still counts as a formal proof if you prove the "lemma" that I suggested and arrive at the answer through simple algebraic manipulations. What exactly is the problem? $\endgroup$ – Frpzzd Nov 21 '18 at 22:43
  • $\begingroup$ you are right, now I get it, thanks a lot for the help!! $\endgroup$ – tuesday1234 Nov 22 '18 at 6:16

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.