[Math] Distinct elements in the Union and Intersection of A and B

combinatoricselementary-number-theoryprobabilityproblem solving

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.

Best Answer

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.