Cartesian product and union
If we apply the distributivity of $\times$ over $\cup$ we obtain the following conditions from the antecedent:
$$C \times B \cup A \times D \subseteq A\times B \cup C \times D$$
Now $C\times B \not\subseteq A \times B \cup C \times D$ iff both $C \setminus A$ and $B \setminus D$ are non-empty.
Similarly, $A \times D \not\subseteq A \times B \cup C \times D$ iff both $A \setminus C$ and $D \setminus B$ are non-empty.
Therefore, we conclude that:
$$C \times B \cup A \times D \subseteq A\times B \cup C \times D$$
is equivalent to:
$$\neg(C\setminus A \ne\varnothing \land B\setminus D \ne \varnothing) \land \neg(A \setminus C \ne\varnothing \land D\setminus B \ne\varnothing)$$
which, using the De Morgan's laws for negation, translates to:
$$(C\setminus A =\varnothing \lor B\setminus D = \varnothing) \land (A \setminus C = \varnothing \lor D\setminus B =\varnothing)$$
Using the equivalence of $X \setminus Y = \varnothing$ and $X \subseteq Y$, we obtain:
$$(C\subseteq A \lor B\subseteq D) \land (A \subseteq C \lor D\subseteq B)$$
and by using distributivity of $\land$ over $\lor$, we obtain the disjunction:
$$C =A \lor (C\subseteq A \land D\subseteq B) \lor (A \subseteq C \land B\subseteq D) \lor B = D$$
In conclusion, if we take $\subset$ to mean $\subsetneq$, two of these possibilities drop out, and we obtain the result. But if we take $\subset$ to mean $\subseteq$, it is false (as exhibited by Brian M. Scott).
Related videos on Youtube
Igor
Updated on August 01, 2022Comments
-
Igor over 1 year
How can we prove that $(A\cup C)\times (B \cup D) \subset (A \times B) \cup (C \times D) \Rightarrow (C \subset A ~\land ~ D \subset B) ~~ \lor ~~ (A \subset C ~ \land ~ B \subset D) $?
I've tried to prove by contradiction but didn't manage to do it. I'll be grateful for any help.