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 A₁, A₂... A_k, be k subsets (not empty) of A.

What is the cardinality of P(A₁)∪P(A₂)∪...∪P(A_k) ? - 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.

 

[jambaugh]

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?

 

[Office_Shredder]

If you just start with two:
$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...

 

[Office_Shredder]

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?

 

[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...
Thanks anyway for your concern.

 

[Xavier Labouze]

It seems I can't change the question any more...

 

[pbuk]

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?

 

[Xavier Labouze]

The question is : is it the best (the fatest) way to compute theses unions ? How to prove it ?

 

[Office_Shredder]

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.

 

[Office_Shredder]

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)

 

[Office_Shredder]

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$

 

[jambaugh]

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]

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...) .

 

[Office_Shredder]

If you have a in $A_1$ only, and b in $A_1$ and $A_2$, does the set {a,b} ever get counted by the algorithm? I missed not understand it because it seems like it doesn't.

 

[Xavier Labouze]

@Office_Shredder is right. The algorithm does not work, it misses a lot of subsets of $A_1$. An idea may be is to count all subsets only included in $P(A_1)$ , i.e. $P(C_1) X [P(D_1)- \emptyset]$ (they are $2^{|A_1|}-2^{|C_1|}$) and to continue... that is to say, replace $2^{|D_1|}$ in the algorithm by $2^{|A_1|}-2^{|C_1|}$... What do you think ?

 

[Xavier Labouze]

No it doesn't work either : by removing all $2^{|C_1|}$ subsets of $A_1$, it is as if all the $C_1$ elements form a proper subset in another subset than $A_1$ which is not sure...

 

[jambaugh]

Oops! You (y'all) are correct. Hmmm... If instead, I take $2^{|A_1|}-2^{|D_1|}$ ... no that won't work either. That would exclude sets such as $\{a,b\}\subseteq D_1$ but where $a$ and $b$ do not both appear in any of the subsequent sets. Dang... let me think on it further.