If $A$ and $B$ each have at least two elements, then not every element of $P(A × B)$ has the form $ A_1 \times B_1$

elementary-set-theory

The full definition is:

If $A$ and $B$ each have at least two elements, then not every element of
$P(A \times B)$ has the form $A_1 \times B_1$ for some $A_1 \in P(A)$ and $B_1 \in P(B)$.

Well In my opinion it is not difficult to understand why this is true, If I have for example $A=\{A_1,A_2\}$ and $B=\{B_1,B_2\}$ then I will have an element in $A\times B$ that is $A_1\times B_2$ that would result in $(A_1,B_2)$ and then $\{(A_1,B_2)\}\in P(A\times B)$.

But this definition is so obvious I am having trouble writing up a formal proof. Any guidance would be appreciated!

Best Answer

Let $a_1$ and $a_2$ be distinct elements of $A$ and let $b_1$ and $b_2$ be distinct elements of $B$. Then $C := \{(a_1,b_1), (a_2,b_1), (a_1,b_2)\} \in P(A \times B)$. To see that it is not of the form $A_1 \times B_1$, note that if that were the case, then:

  1. $A_1$ must contain both $a_1$ and $a_2$ (else we miss either $(a_1,b_1)$ or $(a_2,b_1)$ from the product).
  2. $B_1$ must contain both $b_1$ and $b_2$ (else we miss either $(a_1,b_1)$ or $(a_1,b_2)$ from the product).
  3. Thus, $A_1 \times B_1$ must contain $(a_2, b_2)$, which $C$ does not.

Thus, $C$ cannot be such a product, and we win.

Related Question