Prove by contradiction that given any four sets A B C and D

Prove by contradiction that given any four sets A, B, C, and D, if the Cartesian products A × B and C × D are disjoint, then either A and C are disjoint, or B and D are disjoint.

Solution

Any sets A, B, C, and D, if the Cartesian product of A and B is disjoint with the Cartesian product of C and D, then either A and C are disjoint or B and D are disjoint:

( A×B C×D = ) ( AC = BD = )

on the basis of denition (Cartesian product) If A and B are sets, the Cartesian product of A and B is the set A × B = {(a, b):(a A) and (b B)}.

The following points are worth special attention: The Cartesian product of two sets
is a set, and the elements of that set are ordered pairs. In each ordered pair, the rst
component is an element of A, and the second component is an element of B.
Example (Cartesian product) If A = {{1, 2}, {3}} and B = {(a, b), (c, d)}, then
A × B = {({1, 2}, (a, b)), ({1, 2}, (c, d)), ({3}, (a, b)), ({3}, (c, d))}.

Disjoint Sets : Two sets A and B are said to be disjoint sets, if there is no common element in
A and B.

If A and B are disjoint A B =
the sets A and B have no elements in common .

A Cartesian product is defined as follows: A X B = { (a,b) | a Î A Ù b Î B }

This is a set of ordered pairs, hence the order here matters.

If we want the size of the Cartesian Product of two sets, we can get it as follows:

|A X B| = |A|x|B|.

One way to see that this is the case is to list out all the elements in a Cartesian product in a table. Label all the rows with elements from the set A, and all the columns with the elements from the set B. Each cell in this table will contain an unique element of the Cartesian product of A and B. Furthermore, each element of the Cartesian product can be found on the table. Thus, the total number of elements in the Cartesian product is the total number of cells in the table, |A|x|B|.

Here is a problem involving cartesian products:

If A Í C and B Í D, then A x B Í C x D.

We must show that if (x,y) Î A x B, then (x,y) Î C x D.

Consider an element (x,y) Î A x B.

By definition of a cartesian product, we must have that xÎA and yÎB.

Using our given subset information, we can deduce that xÎC and yÎD.

Finally, considering the definition of a cartesian product, we have that (x,y) Î C x D, as desired.

So , let proof that Any sets A, B, C, and D, if the Cartesian product of A and B is disjoint with the Cartesian product of C and D, then either A and C are disjoint or B and D are disjoint:

(A×BC×D=)(AC=BD=)

Let ACAC and BDBD. So ,

xAC,  yBDxAC,  yBD

So

(x,y)A×B,  (x,y)C×D(x,y)A×B,  (x,y)C×D

But

(A×B)(C×D)=

So putting all together we\'ve proved

(A×B)(C×D)=AC=BD=

The Cartesian products A × B and C × D are disjoint, then either A and C are disjoint, or B and D are disjoint.