# Distinct elements in the Union and Intersection of A and B

Take a set $$x$$ with $$10$$ distinct elements.

Rule: Everytime you have two subsets, $$A$$ and $$B,$$ you also have $$A\cup B$$ and $$A \cap B.$$ What is the maximum number of subsets you can have such that you don't have all subsets in $$P(X).$$

I know that the power set is given a nonempty set $$x,$$ the power set is the set of all subsets of $$x.$$ The union is all the elements in $$x$$ and the intersection in what $$A$$ and $$B$$ have in common in $$x.$$

I know that the $$\emptyset$$ and $$X$$ can be in P(X). My friend asked this question to me for the fun of it. I was not sure how to answer this type of question with my basic knowledge. I am not sure on what the maximum number of elements can be in P(X) given $$10$$ distinct elements in a set $$x.$$ I said let those elements be $$a,b,c,d,e,f,g,h,i,j.$$ I am not sure about this. Could I use $$2^{n-1},$$ or $$2^{2^{n-1}}$$where $$n=10$$ and distinct under the union and intersection of $$A$$ and $$B$$?

Can someone please help me with this? I was thinking about this for some time now and I still am not sure? I would like to suprise my friend with a nice proof of this.

• Why is it irrelevant that it is closed under intersections?
– col
Sep 30, 2014 at 0:04

Let $\mathcal{F} \subset \mathcal{P}(X)$ be the collection of sets in question where $X$ is a set with $n$ (in your case $10$) elements. Here $\mathcal{P}(X)$ denotes the power set of $X$. Since $\mathcal{F}$ is closed under unions, there should be an element $a \in X$ that is contained in no set in $\mathcal{F}$. This implies that $|\mathcal{F}| \leq |\mathcal{P}(X \backslash \{a\})| = 2^{n-1}$. This is achievable by taking $\mathcal{F} = \mathcal{P}(X \backslash \{a\})$.
Note that it is irrelevant that $\mathcal{F}$ is also closed under intersections.