Confused with problem: How many different expressions can be formed from set variables, and operators union and intersection

80 Views Asked by At

This is problem 11, page 4, A. Shen's Basic set theory:

How many different expressions can be formed from set variables, and operators union and intersection. (Variables and operations can be used more than once. Two expressions are considered identical if they assume the same value for each set of values of the variables involved.)

(For $n = 2$ and $n = 3$ this problem is easy to solve; however, no general formula for any $n$ is known. This problem is also called “counting monotone Boolean functions in n variables”.)

For the case $n=2$, I could only get 4 "expressions" $A, B, A \cap B,A\cup B$. But, the author said that this problem is actually number of monotone Boolean functions of n variables, A000372. That is, for $n=2$, the result would be 6.


I edited because after reading comment by @GerryMyerson, it rises my new confusion.

The problem 11 is actually an extension of problem 10, which by some hints from the internet I could prove, and by testing with particular values of $n$ which lead to correct result.

Problem 10. How many different expressions can be formed from set variables $A$ and $B$ by using union, intersection and set difference? (Variables and operations can be used more than once. Two expressions are considered identical if they assume the same value for each set of values of the variables involved.) Solve the same problem for three sets and for n sets. (Answer in the general case: $2^{2^{n}-1}$.)

Such as for $n=2$, the 8 available expression could be: $A\setminus A, A, B, A\cup B, A\cap B, \left(A\cup B\right)\setminus\left(A\cap B\right), A\setminus B, B\setminus A$.

If apply comment by @GerryMyerson, the result would not be 8, for $n=2$. Do you think so?