# Cardinality of Unions of Powersets

Xavier Labouze
TL;DR Summary
Given A, a set (note P(A) its powerset) and A1, A2... Ak, k subsets of A. What is the cardinality of P(A1)∪P(A2)∪...∪P(Ak) ?
Mentor note: In this thread I (Mark44) have edited "cardinal" to "cardinality." In English, we talk about the "cardinality of a set," not the "cardinal of the set."
Given A a set of n elements - note |A| its cardinal and P(A) its powerset. Let A1, A2... Ak, be k subsets (not empty) of A.

What is the cardinality of P(A1)∪P(A2)∪...∪P(Ak) ? - Is there a formula or a rapid algorithm to compute it ? (I don't see how to compute it in polynomial time when the subsets are not pairwise disjoint...)

Thank you.

Last edited by a moderator:

Gold Member
Hmmm...
The pertinent question here is, I believe, "What is the intersection of the power sets of two sets in terms of their intersection?"

Next, consider how to make the problem recursive. Relate the first set to the problem applied to the remaining sets.

BTW Is this a homework or assignment?

Xavier Labouze
Tks. No it is not a homework. I really wonder if it exists an algorithm running in polynomial time in ##n## (the cardinality of ##A##) - About your comment : ##P(A) \cap P(B) = P(A \cap B)## but ##\overline{P(A)} \ne P(\overline{A})## so how to deal with it?

Last edited by a moderator:
Staff Emeritus
Gold Member
##P(A_1) \cup P(A_2)##.

You know the cardinality of ##P(A_1)##. What elements of ##P(A_2)## are not contained in ##P(A_1)##, and how many are there?

Xavier Labouze
Right, ##|P(A_1) \cup P(A_2)|=|P(A_1)|+|P(A_2)|-|P(A_1 \cap A_2)|## but I don't see how to continue...

Staff Emeritus
Gold Member
Now suppose you have three. If ##B\in P(A_1)\cup P(A_2)\cup P(A_3)##. Then B is a subset of one of the ##A_i##s, which gives us ##|P(A_1)|+|P(A_2)|+|P(A_3)|##. But if B is a subset of any pair of them we overcounted it, so we have to subtract ##|P(A_1\cap A_2)| + |P(A_1\cap A_3)| + |P(A_2 \cap A_3)|##. But if it was a subset of all three of them, we added it three times and subtracted it three times, so we need to add back in ##|P(A_1 \cap A_2 \cap A_3)|##.

Are you starting to see a pattern?

pbuk
Xavier Labouze
I must have written the question wrong. I am a teacher not a student and I wonder if counting the cardinality of unions of powersets can be computed in polynomial time (or is it #NP-Complete ?). If you have the answer please give it to me.
I should certainly change the question in this way...

Last edited by a moderator:
Xavier Labouze
It seems I can't change the question any more...

Homework Helper
Gold Member
I wonder if counting the cardinality of unions of powersets can be computed in polynomial time...

Right, ##|P(A_1) \cup P(A_2)|=|P(A_1)|+|P(A_2)|-|P(A_1 \cap A_2)|##
So for 2 subsets you had to calculate 3 cardinalities.
Now suppose you have three. If ##B\in P(A_1)\cup P(A_2)\cup P(A_3)##. Then B is a subset of one of the ##A_i##s, which gives us ##|P(A_1)|+|P(A_2)|+|P(A_3)|##. But if B is a subset of any pair of them we overcounted it, so we have to subtract ##|P(A_1\cap A_2)| + |P(A_1\cap A_3)| + |P(A_2 \cap A_3)|##. But if it was a subset of all three of them, we added it three times and subtracted it three times, so we need to add back in ##|P(A_1 \cap A_2 \cap A_3)|##.
For 3 subsets, 7 cardinalities.
Are you starting to see a pattern?

Last edited by a moderator:
Xavier Labouze
The question is : is it the best (the fatest) way to compute theses unions ? How to prove it ?

Staff Emeritus
Gold Member
Well, to give a maybe useless extension to your original claim that you can only do it if they are pairwise disjoint - if they are l-wise disjoint for any fixed l, this gives you a polynomial time algorithm for computing the cardinality.

I think the problem at the start was you asked if there was a formula or a rapid algorithm, and I thought well yes, there is a very simple formula. It wasn't clear to me that you already knew about it, sorry.

When you say you want a polynomial time algorithm, in what parts exactly? For example if the size of A is fixed, you can just ignore all the trickiness and write down all the unique elements of the power sets.

Xavier Labouze
Well, to give a maybe useless extension to your original claim that you can only do it if they are pairwise disjoint - if they are l-wise disjoint for any fixed l, this gives you a polynomial time algorithm for computing the cardinality.

I think the problem at the start was you asked if there was a formula or a rapid algorithm, and I thought well yes, there is a very simple formula. It wasn't clear to me that you already knew about it, sorry.
Thank you, my question was written wrong - my first question on this forum, my bad.

Staff Emeritus
Gold Member
I edited this into my post above but you replied during it so posting it again:

When you say you want a polynomial time algorithm, in what parts exactly? For example if the size of A is fixed, you can just ignore all the trickiness and write down all the unique elements of the power sets.

Xavier Labouze
I edited this into my post above but you replied during it so posting it again:

When you say you want a polynomial time algorithm, in what parts exactly? For example if the size of A is fixed, you can just ignore all the trickiness and write down all the unique elements of the power sets.
A polytime algorithm in ##n=|A|##
(Nice quote BTW)

Staff Emeritus
Gold Member
In that case just using the formula works. I assume you want it to be polynomial in k as well?

Xavier Labouze
In that case just using the formula works. I assume you want it to be polynomial in k as well?
No - With ##k## bounded by a polynom in ##n##

Last edited:
Gold Member
Here's my algorithm.
Define Function:
Take ##A_1## and partition it into ##C_1 = \bigcup_{k=2}^n A_1\cap A_k##, and ##D_1 = A_1 - C_1##.
Return ##2^{|D_1|}##+Function applied to remainder of the list.

How does that look? If the sets are of size on the order of M then the intersection of a pair should take ##O(M^2)##?
So the whole process should take ##O(M^2 n^2)## steps. (That is if my algorithm is correct.)

Xavier Labouze
Xavier Labouze
Here's my algorithm.
Define Function:
Take ##A_1## and partition it into ##C_1 = \bigcup_{k=2}^n A_1\cap A_k##, and ##D_1 = A_1 - C_1##.
Return ##2^{|D_1|}##+Function applied to remainder of the list.

How does that look? If the sets are of size on the order of M then the intersection of a pair should take ##O(M^2)##?
So the whole process should take ##O(M^2 n^2)## steps. (That is if my algorithm is correct.)
It looks good - but it doesn't work (see the comment below...) .

Last edited:
Staff Emeritus