# Cardinality of Unions of Powersets

• I
• Xavier Labouze
In summary: I apologize.In summary, the conversation discusses the cardinality of the union of power sets and whether it can be computed in polynomial time. The formula for calculating the cardinality is given as |P(A1)∪P(A2)|=|P(A1)|+|P(A2)|-|P(A1∩A2)|, and it is extended to calculating the cardinality of unions of l-wise disjoint subsets in polynomial time. The question is raised about whether this is the most efficient way to compute the cardinality and how to prove it. There is also a discussion about the simplicity of the formula and a clarification that the original question was written incorrectly.
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:
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?

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:
##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?

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

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
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:
It seems I can't change the question any more...

Xavier Labouze said:
I wonder if counting the cardinality of unions of powersets can be computed in polynomial time...

Xavier Labouze said:
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.
Office_Shredder said:
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.
Office_Shredder said:
Are you starting to see a pattern?

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

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.

Office_Shredder said:
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.

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.

Office_Shredder said:
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)

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

Office_Shredder said:
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:
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
jambaugh said:
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:
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.

@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 ?

Last edited:
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...

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.

## 1. What is the definition of "Cardinality of Unions of Powersets"?

The cardinality of unions of powersets refers to the number of elements in the combined sets of all possible subsets of a given set. In other words, it is the total number of unique elements that can be created by taking the power set of a set and then taking the union of all those subsets.

## 2. How is the cardinality of unions of powersets calculated?

The cardinality of unions of powersets can be calculated using the formula 2^n, where n is the number of elements in the original set. This formula is based on the fact that for every element in the original set, there are 2 possible options - either including it or not including it in a given subset. Therefore, the total number of possible subsets is 2^n.

## 3. Can the cardinality of unions of powersets be infinite?

Yes, the cardinality of unions of powersets can be infinite. This is because there are sets with an infinite number of elements, such as the set of all real numbers. In these cases, the power set will also have an infinite number of elements, and the union of all those subsets will also have an infinite number of elements.

## 4. How is the cardinality of unions of powersets related to the cardinality of the original set?

The cardinality of unions of powersets is related to the cardinality of the original set by the formula 2^n, where n is the number of elements in the original set. This means that the cardinality of unions of powersets will always be greater than or equal to the cardinality of the original set.

## 5. What is the significance of the cardinality of unions of powersets in mathematics?

The cardinality of unions of powersets has various applications in mathematics, particularly in set theory and combinatorics. It allows for the calculation of the total number of possible subsets of a set, which can be useful in solving problems involving combinations and permutations. It also helps in understanding the relationships between different sets and their subsets.

• Set Theory, Logic, Probability, Statistics
Replies
5
Views
1K
• Calculus
Replies
1
Views
1K
• Set Theory, Logic, Probability, Statistics
Replies
8
Views
2K
• Set Theory, Logic, Probability, Statistics
Replies
14
Views
4K
• Set Theory, Logic, Probability, Statistics
Replies
1
Views
2K
• General Math
Replies
1
Views
1K
• Set Theory, Logic, Probability, Statistics
Replies
24
Views
2K
• General Math
Replies
8
Views
3K
• Math Proof Training and Practice
Replies
80
Views
4K
• General Math
Replies
1
Views
10K