Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

For example I have sets


for some reason I can't do |AUBUC|, only what i can do is calculate |A|, |B|, |C|.

How do I do to calculate |AUBUC| in this situation? is there any algorithm?

share|improve this question

closed as too localized by Yemon Choi, Tom Leinster, Felipe Voloch, Asaf Karagila, quid Aug 22 '12 at 11:34

This question is unlikely to help any future visitors; it is only relevant to a small geographic area, a specific moment in time, or an extraordinarily narrow situation that is not generally applicable to the worldwide audience of the internet. For help making this question more broadly applicable, visit the help center. If this question can be reworded to fit the rules in the help center, please edit the question.

I am not sure whether this question better fits MO, or MSE. –  Ilya Aug 22 '12 at 9:44
Without further information, you can't do it. –  Yemon Choi Aug 22 '12 at 10:24
Mark, your question isn't a good fit for this site. You'd be better off trying one of the other math sites listed in the FAQ. Good luck. –  Tom Leinster Aug 22 '12 at 10:42
thanks all, Actually it is computer-science relative question –  mark Aug 23 '12 at 3:00
This is an enumerative combinatorics question, even if it originates in computer science. (Many enumerative combinatorics do arise in computer science.) To learn more about this sort of thing, I'd suggest reading an enumerative combinatorics textbook. –  Patricia Hersh Aug 23 '12 at 12:47

2 Answers 2

To extend the last sentence of Ilya's reply have a look in Wikipedia for the inclusion-exclusion principle which accounts for the size of the intersections by the formula

$$ \left| A \cup B \cup C \right | = \left| A \right| + \left| B \right| + \left| C \right| - \left| A \cap B\right| - \left| B \cap C \right| - \left| A \cap C \right| + \left| A \cap B \cap C\right|. $$

There is an obvious generalisation to an alternating sum over the cardinalities of all the $k$-fold intersections in the case of $n$ sets. Of course if you don't know the cardinalities of the intersections this is not so useful!

share|improve this answer
yes, I agree with you, the info is not enough so that it's nearly impossible to calculate the result. –  mark Aug 23 '12 at 3:02
@Michael: Sorry I couldn't resist correcting "principal" to "principle". –  Mark Grant Aug 23 '12 at 17:48
@Mark. Ah thanks for fixing that. Too many principal bundles in my past perhaps ? –  Michael Murray Aug 24 '12 at 10:09
@Michael: Better that than a lack of principles! –  Mark Grant Aug 24 '12 at 20:43

I do not know, how much is it related to set-theory, but from the measure-theoretical point of view, $|A| = \mu(A)$ where $\mu$ is a counting measure, i.e. the one which assigns the unit weight to each element of the set. In general, if you have a finite number of sets $A_1,\dots,A_n$ then $$ \mu(A_1\cup\dots\cup A_n)\leq\sum\limits_{i=1}^n\mu( A_i) $$ which is quite a trivial fact in your case. The strict inequality only holds when the sets are not disjoint, i.e. $A_i\cap A_j$ is not empty for some $i\neq j$. In that case, you have also to account for how many element are in the intersection - and to be able to compute $\mu(A_1\cap A_2)$, $\mu(A_1\cap A_2\cap A_3)$ etc.

share|improve this answer

Not the answer you're looking for? Browse other questions tagged or ask your own question.