Can we convert this statement about sets into a statement of propositional logic?

495 Views Asked by At

A question was just asked here about proving

$$A⊆(B∪C)⟺A\setminus C⊆B.$$

We can prove this statement directly, using the concepts of first-order logic.

"Suppose $x \in A \setminus C$ and that $A⊆(B∪C).$ We will show $x \in B$..."

etc.

Instead of doing that, is there a way to leverage the connection between Boolean algebras and Propositional Logic to transform the statement of interest into a statement in the language of Propositional Logic?

If so, we can probably prove the new statement using more elementary means.

1

There are 1 best solutions below

3
On BEST ANSWER

Yes we can. In fact, it is rather nice to see how these things play out.

We replace the sets $A,B,C$ with the predicates $\sf A,B,C$, where $\sf A$ is to be thought of as "$\in A$". Accordingly, we need to adjust the statement to prove to:

$$(\sf A \implies (B \lor C))\iff ((A \land \neg C) \implies B)$$

which is essentially not but applying the correspondence between PropLog and Boolean algebras, after restricting to the Boolean subalgebra of $\mathcal P(U)$ (where $U$ is the universe of discourse for the original statement) determined by $A,B,C$.

We can now solve this using truth tables, more properly known as truth valuations. It is here that the connection with the first-order case becomes apparent.

For suppose we had a valuation $x$, with according truth values $x({\sf A}),x({\sf B})$ and $x({\sf C})$. Now simply think of $x({\sf A})$ as $x \in A$.

So we see that the first-order reasoning in this case can be argued to actually be zeroth-order reasoning in disguise: we just prefer to call our truth valuations (arbitrary) elements.