Is there a formula that relates the number of atoms of a boolean algebra to the number of different unions/intersections of some generating elements?
Consider the boolean sub-algebra $A$ generated by $n$ elements $a_1,a_2,...a_n$ (in any boolean algebra or a power set if you prefer). When these elements are algebraically independent (as elements of an $\mathbb{F}_2$ algebra), then:
- there are exactly $2^n$ atoms (this is the linear dimension of $A$)
- all $2^n$ unions ($\bigcup_{i\in I} a_i$ where $I\subseteq\{1,2,...,n\}$) are different
- all $2^n$ intersections ($\bigcap_{i\in I} a_i$ where $I\subseteq\{1,2,...,n\}$) are different
Now, when the generating elements are not algebraically independent, there are fewer atoms. Is there a formula or whatever that relates the number of different unions or intersections to the number of atoms? Or is there at least way to understand the problem more clearly?
I'm going to focus on intersections since the problem for unions is essentially the same.
Generally, the number of atoms is smaller than the number of intersections. The linear combinations of intersections are the polynomials in $a_1$,$a_2$,...$a_n$, thus they cover exactly $A$. This means that the linear span of the intersections is $A$. Since the (linear) dimension of $A$ is the number of atoms, the number of intersection is at least the number of atoms.
$$\text{atoms}\leq\text{intersections}$$
However, even if the reciprocal inequality is true in the independent case (both are $2^n$), it is not always true. Here is a simple and extreme example:
$$X=\{1,2,...,n\} \\ \forall i\in X\quad a_i=X\setminus\{i\}$$
There are $n$ atoms (singletons) but $2^n$ intersections (all parts of $X$).
So all we can say is:
$$\text{atoms}\leq\text{intersections}\leq \min(2^n,2^\text{atoms})$$
The same holds for unions simply reasoning on $\overline{a_1}, \overline{a_2},...,\overline{a_n}$ :
$$\text{atoms}\leq\text{unions}\leq \min(2^n,2^\text{atoms})$$