Just a simple question that will help me do the programming homework:

I've got two sets and need to check if they're equal. I've already implemented intersection and union methods, now I've got to implement a method which checks if $S_1$ and $S_2$ are equal. So, instead of repeating the code, I'd like to use intersection and union methods.

Now, a math question: is $$|S_1 \cup S_2| = |S_1|$$ a sufficient condition to say two sets are equal?


No, the condition you wrote does not suffice: Not even $S_1\cup S_2=S_1$ ensures equality; it simply says that $S_2$ is a subset of $S_1$.

Now, if you know that $S_1\cup S_2=S_1\cap S_2$, do you see how to conclude equality of $S_1$ and $S_2$?

By the way, I assume you are working with finite sets? If so, then $|S_1\cup S_2|=|S_1\cap S_2|$ will suffice. This won't be enough if you want you condition to work for infinite sets as well.

  • $\begingroup$ Yes, I'm aware of the problem with the powers of infinite sets :) However, I'm working with finite sets, so I'll use the condition you've provided. Thank you. $\endgroup$ – usoban Apr 30 '11 at 14:46

No. For example let $S_2$ be the empty set, or any proper subset of $S_1$. But the idea works fine as long as you add that $S_1$ and $S_2$ have the same number of elements.

  • 1
    $\begingroup$ Provided $S_1$ and $S_2$ are finite, of course. $\endgroup$ – Zhen Lin Apr 30 '11 at 14:37
  • $\begingroup$ @Zhen Lin: Indeed. But in a programming context, that is a reasonable assumption. $\endgroup$ – André Nicolas Apr 30 '11 at 14:41

Take $S_1 = \{1,2 \}$ and $S_2 = \emptyset$. Then $|S_1 \cup S_2| = |S_1|$ but $S_1 \neq S_2$.


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.