Question about relating cardinalities

Question

Assume $\left |A \right | > \left |B\right |$ and $\left |C \right | > \left |D\right |$. Define $E=\{(x,y):x\in A ,y\in C\}$ and $F=\{(x,y):x\in B ,y\in D\}$. Is $\left |E \right | > \left |F\right |$? My gut feeling tells me that it is, but I don't know how to prove it.

Answer 1

Do we know the size of $E$ and $F$? If we do, then the problem is solved. Now the question boils down to being able to find the sizes of the product of two sets. For any two sets $A$, $B$, we define the cartesian product of $A$ and $B$, written as $A \times B$, as:

$$ A \times B \equiv \{ (a, b) : \forall a \in A, ~ \forall b \in B \} $$

If we know $|A \times B$|, we are done, because $E = A \times C$, $F = B \times D$.

Calculating $|A \times B|$:

See that for every $a \in A$, we have a copy of the entire set $B$. So, if we consider, for example $A = \{ a_1, a_2 \}$, $C = \{ c_1, c_2, c_3 \}$, we will have $E = A \times C = \{ (a_1, c_1), (a_1, c_2), (a_2, c_1), (a_2, c_2), (a_3, c_1), (a_3, c_2) \}$ which has $|A| \times |C| = 3 \times 2 = 6$ elements.

In general, $|A| \times |B|$ will have $|A| \times |B|$ elements.

Comparing |E| and |F|

1. $|A| > |B|$, $|C| >|D|$ (given).
2. $E = A \times B$ (by definition of set cartesian product)
3. $F = C \times D$ (by definition of set cartesian product)
4. $|E| = |A \times C| = |A| \times |C|$ (by observation above) 6.. $|F| = |B \times D| = |B| \times |D|$ (by observation above)
5. Since $|A| > |B|$ and $|C| > |D|$, we have $|A| \times |C| > |B| \times |D|$ (by property of multiplication and greater than)

Hence, to wrap up, we have that $|E| = |A| \times |C| > |B| \times |D| = |F|$. So, $|E| > |F|$.