1
$\begingroup$

Denote the Cartesian product with $\times$, and let $X^c$ be the complement of $X$.

Let $X$ be contained in $A$ and $Y$ is contained in $B$. Prove: $(X \times Y)^c= (A \times Y^c) \cup (X^c \times B)$ Generalize this theorem if $X$ is contained in $A$ and $Y$ is contained in $B$, and $Z$ is contained in $C$.

  • 1
    I added TeX and switched to a slightly more common notation. Regarding $X^c$, you should probably give a universal set. That is, some set in which all this thing occurs, or does $X^c=A\setminus X$? Complements are taken relatively to a certain set, and $Y\setminus X$ is not as "the" complement of $X$.2011-10-29

1 Answers 1

4

If $c \in (X \times Y)^c$, then $c \in A \times B$ and $c\notin X \times Y$. It means that:
it is not true that: $c[1] \in X$ and $c[2] \in Y$,
which means (de Morgan's laws):
$c[1] \notin X$ or $c[2] \notin Y$,
so we have the inclusion: $(X \times Y)^c \subseteq (A \times Y^c) \cup (X^c \times B)$ (the first element of the sum is built of all such $c$ that $c[2] \notin Y$ and the second of all such $c$ that $c[1] \notin X$).

Now let's assume that $c \in (A \times Y^c) \cup (X^c \times B)$. That implies the same thing as we said before: $c[1] \notin X$ or $c[2] \notin Y$ or equivalently: it is not true that: $c[1] \in X$ and $c[2] \in Y$. It means that $c \notin X \times Y$, so $c \in (X \times Y)^c$. $\square$

EDIT: the above proof is an implementation of a general approach presented by @user9176. However it may be possible in that case to work with equivalence (iff) instead of implication and prove equality in one go. But traditional approach always requires less careful thinking ;)
@AsafKaragila made a very good remark, but I think that you mean that the universes are $A$, $B$ and $A \times B$ respectively, right?

EDIT2: Generalisation is a homework.

P.S. It is very helpful to draw $A$ and $B$ as ortogonal intervals, and think about $A \times B$ as a rectangle. Then it is easy to see where $X \times Y$ and its complement are. When you have $A, B, C$, you just imagine a cuboid instead of a rectangle.