Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
1  
Usually to prove equality of two sets, you use double inclusion: pick $(x,y) \in (X \times Y)^c$, explain what this means and show that $(x,y) \in (A \times Y^c) \cup (X^c \times B)$. Then pick $(x,y) \in (A \times Y^c) \cup (X^c \times B)$ and try to prove$(x,y) \in (X \times Y)^c$. –  N. S. Oct 29 '11 at 20:25
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$. –  Asaf Karagila Oct 29 '11 at 20:25
add comment

1 Answer

up vote 4 down vote accepted

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.