Skip to main content
5 of 11
edited tags
Asaf Karagila
  • 41.8k
  • 9
  • 143
  • 298

Formulas that are valid simultaneously in a power set Boolean algebra $B$ and the 2-element Boolean algebra $\mathbf2$

Let $B$ be a power set Boolean algebra with more than 2 elements.

Let $P$ be an unquantified formula constructed using variables and the symbols $\emptyset, V$ (the universe), $\cup, \cap, C, \subseteq, =$ (union, intersection, complement, inclusion, equality, respectively) such as, for example, $A \subseteq A \cup X$.

Clearly, such a formula is valid in $B$ iff it is valid in the 2-element Boolean algebra $\mathbf2$.

So instead of proving $P$ in $B$, we can check that $P$ is true in $\mathbf2$ - by checking $2^n$ possible cases ($n$ is the number of variables in $P$) substituting instead of each variable 0 or 1 and calculating the result.

If the result is 1 in all cases then $P$ is true in $\mathbf2$ and, therefore, in $B$.

Note that this method also works for some unquantified formulas containing in addition some propositional connectives, For example, $A \subseteq B \rightarrow A \cup X \subseteq B \cup X$ is true in $\mathbf2$ and $B$.

But there are some formulas(for example, $X \subseteq Y \lor Y \subseteq X$) that are valid in $\mathbf2$ but not in $B$.

So my question is:

What is the widest class of unquantified formulas in $B$ containing variables, the above set-theoretic symbols and propositional connectives, which are valid simultaneously in $\mathbf2$ and in $B$?