Subset of Cartesian Product not necessarily Cartesian Product of Subsets

Theorem

Let $A$ and $B$ be sets.

Let $A$ and $B$ both have at least two distinct elements.

Then there exists $W \subseteq A \times B$ such that $W$ is not the cartesian product of a subset of $A$ and a subset of $B$.

Proof

Let $a \in A, b \in A, c \in B, d \in B$ be arbitrary elements of $A$ and $B$.

Let:

$W = \set {\tuple {a, c}, \tuple {a, d}, \tuple {b, d} }$

Then $W \subseteq A \times B$.

Suppose $W = X \times Y$ such that $X \subseteq A, Y \subseteq B$.

Then $a, b \in X$ and $c, d \in Y$.

But $X \times Y$ also contains $\tuple {b, c}$ which is not in $W$.

Hence the result.

$\blacksquare$

Sources

• 1975: Bert Mendelson: Introduction to Topology (3rd ed.) ... (previous) ... (next): Chapter $1$: Theory of Sets: $\S 5$: Products of Sets: Exercise $3$