Help on a set proof using propositional logic.

Question

Prove that, if $B \not\subseteq \emptyset$ and $(A \times B) \subseteq (B \times C)$, then $A \subseteq B$.

How would a formal proof of this look like using propositional logic? What relevance does $B$ not being a subset of the empty set have? Is it simply saying $B$ is not an empty set? How would I get rid of the $C$ set in my proof?

Answer 1

$B\nsubseteq\emptyset$ does indeed assert that $B$ is not empty. That is that $B$ contains something.

The importance is that $A\times\emptyset = \emptyset$ and $\emptyset\times C = \emptyset$ for any $A,C$, including those where $A\nsubseteq C$. So the implication only holds when $B$ is not empty (if at all).

Your proof should use this to begin somewhat like:

Take $B\nsubseteq\emptyset$ and $A\times B\subseteq B\times C$ as premises.

The first premise entails that there is some term $y$ where $y\in B$.

Therefore for any term $x$, where $x\in A$, then there is some $y$ where $\langle x,y\rangle\in A\times B$.

Next, the second premise entails...

And in conclusion

Therefore, for any term $x$ that $x\in A\to x\in B$.

Which is to say $A\subseteq B$, by definition of (improper) subset.

---

In Fitch Style that is: $$\def\fitch#1#2{\quad\begin{array}{|l}#1\\\hline#2\end{array}}\fitch{~~1.~B\nsubseteq \emptyset\hspace{20ex}\textsf{Premise}\\~~2.~A\times B\subseteq B\times C\hspace{10.5ex}\textsf{Premise}}{~~3.~\exists y~.y\in B\hspace{16.5ex}1,\subseteq \textsf{Elimination}\\\fitch{~~4.~[b]~b\in B\hspace{14.5ex}\textsf{Assumption (Witness)}}{\fitch{~~5.~[a]\hspace{17ex}\textsf{Assumption (Arbitrary)}}{\fitch{~~6.~a\in A\hspace{10.5ex}\textsf{Assumption}}{~~7.~a\in A\wedge b\in B\hspace{2.5ex}4,6,\wedge\textsf{Introduction}\\~~8.~\langle a, b\rangle \in A\times B\hspace{2.5ex}7,\times\textsf{Introduction}\\~~\vdots}\\~~\vdots}\\~~\vdots}\\17.~\forall x~.(x\in A\to x\in B)\hspace{6ex}3,4{-}16,\exists\textsf{Elimination}\\18.~A\subseteq B\hspace{20ex}17,\subseteq\textsf{Introduction}}$$