Cartesian product and union

1,310

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

Share:
1,310

Related videos on Youtube

Igor
Author by

Igor

Updated on August 01, 2022

Comments

  • Igor
    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.