Return to Question

Note. Because the 2-element Boolean algebra $\mathbf2$ is isomorphic to the powerset algebra on a singleton $V$, we can use the set-theoretic notations $\emptyset, V, \cup, \cap, C, \subseteq$ instead of normally used in $\mathbf2$ the notations $0,1,+,.,',\leq$.

Let $B$ be a power set Boolean algebra.

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$.

It is well known, that 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 $\emptyset$ or $V$ and calculating the result, using the obvious rules: $\emptyset \cup \emptyset = \emptyset$, $\emptyset \cup V = V$, $V \cup \emptyset = V$, $V \cup V = V$ and so on for $\cap, C, \subseteq$.

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

Note that this method also works for some unquantified formulas containing also some propositional connectives - in addition, after calculating all set terms in $P$ we should check that the resulting formula(not containing variables) is true. 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$?

Note 1. Early I posted a related question Set-theoretic tautologies. But the answer did not contain any concrete references to the literature. So I posted this, more precisely formulated question, hoping to receive a concrete reference to the literature. In any case, I am thankful to François G. Dorais and Emil Jeřábek for their answers.

Note 2. Because the 2-element Boolean algebra $\mathbf2$ is isomorphic to the powerset algebra on a singleton $V$, we can use the set-theoretic notations $\emptyset, V, \cup, \cap, C, \subseteq$ instead of normally used in $\mathbf2$ the notations $0,1,+,.,',\leq$.

Let $B$ be a power set Boolean algebra.

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$.

It is well known, that 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 $\emptyset$ or $V$ and calculating the result, using the obvious rules: $\emptyset \cup \emptyset = \emptyset$, $\emptyset \cup V = V$, $V \cup \emptyset = V$, $V \cup V = V$ and so on for $\cap, C, \subseteq$.

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

Note that this method also works for some unquantified formulas containing also some propositional connectives - in addition, after calculating all set terms in $P$ we should check that the resulting formula(not containing variables) is true. 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$?

Note. Because the 2-element Boolean algebra $\mathbf2$ is isomorphic to the powerset algebra on a singleton $V$, we can use the set-theoretic notations $\emptyset, V, \cup, \cap, C, \subseteq$ instead of normally used in $\mathbf2$ the notations $0,1,+,.,',\leq$.

Let $B$ be a power set Boolean algebra.

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$.

It is well known, that 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 $\emptyset or V$ and calculating the result, using the obvious rules: $\emptyset \cup \emptyset = \emptyset$, $\emptyset \cup V = V$, $V \cup \emptyset = V$, $V \cup V = V$ and so on for $\cap, C, \subseteq$.

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

Note that this method also works for some unquantified formulas containing also some propositional connectives - in addition, after calculating all set terms in $P$ we should check that the resulting formula(not containing variables) is true. 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$?

Note. Because the 2-element Boolean algebra $\mathbf2$ is isomorphic to the powerset algebra on a singleton $V$, we can use the set-theoretic notations $\emptyset, V, \cup, \cap, C, \subseteq$ instead of normally used in $\mathbf2$ the notations $0,1,+,.,',\leq$.

Let $B$ be a power set Boolean algebra.

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$.

It is well known, that 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 $\emptyset$ or $V$ and calculating the result, using the obvious rules: $\emptyset \cup \emptyset = \emptyset$, $\emptyset \cup V = V$, $V \cup \emptyset = V$, $V \cup V = V$ and so on for $\cap, C, \subseteq$.

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

Note that this method also works for some unquantified formulas containing also some propositional connectives - in addition, after calculating all set terms in $P$ we should check that the resulting formula(not containing variables) is true. 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$?