Why Can't All Subsets of A×B Be Expressed as Cartesian Products?

[Carrie233]

Homework Statement

Prove:

If A and B each have at least two elements, then not every element of P(A×B) has the form A1 ×B1 for some A1 ∈ P(A)and B1 ∈ P(B).

Homework Equations

The Attempt at a Solution

Suppose A = {1, 2}, B = {3, 4}.
AXB = {(1,3), (1,4), (2,3), (2,4)}
P(A) = {{1}, {2}, {1,2}, ø}；P(B) = {{3}, {4}, {3,4}, ø}
Since A1 ∈ P(A), A1 could be {1}, {2}, {1,2}, or ø; similarly, B1 could be {3}, {4}, {3,4}, or ø
P(AXB) = {{(1,3)}, {(1,4)}, {(2,3)}, {(2,4)}, {(1,3),(1,4)}, ... {(1,3), (1,4), (2,3), (2,4)} }

 

[fresh_42]

Homework Statement

If A and B each have at least two elements, then not every element of P(A×B) has the form A1 ×B1 for some A1 ∈ P(A)and B1 ∈ P(B).

Homework Equations

The Attempt at a Solution

Suppose A = {1, 2}, B = {3, 4}.
I know that {(1,3), (1,4), (2,3), (2,4)} ∈ P(AXB) cannot have the form A1 x B1, but how to prove

To show "not every element ..." it's easiest to name one of these others and prove that it is different.

 

[Carrie233]

To show "not every element ..." it's easiest to name one of these others and prove that it is different.

Actually, I don't understand why {(1,3), (1,4), (2,3), (2,4)} cannot have the form of A1xB1.
In my view, {(1,3), (1,4), (2,3), (2,4)} = {1,2} x {3,4} where {1,2} ∈ A1 and {3,4} ∈ B1.

 

[fresh_42]

I thought the $A_i$ were the elements of $A$ and the $B_i$ the elements of $B$. Thus we have $A_1\in A$ and $B_1\in B$ and $(A_1,B_1)\in A \times B\,.$ Now show that there is another element in $A\times B$ and say why.

Correction: I forgot the $P()$, sorry. Disregard this.

 

[RPinPA]

I detect some slight confusion here. If P(A) means the power set of A, then it is the set of all subsets of A. So the elements of P(A) are $\emptyset$, {1}, {2}, {1,2}.

So {(1,3), (1,4), (2,3), (2,4)}, being the complete A x B, is certainly an element of P(A x B). But it's not the only one. Any subset of {(1,3), (1,4), (2,3), (2,4)} is also an element of P(A x B).

You are misinterpreting what is being asked.

I know that {(1,3), (1,4), (2,3), (2,4)} ∈ P(AXB) cannot have the form A1 x B1,

That is not being claimed. It is not being claimed that NONE of the subsets of A x B are of the form A1 x B1. It is being claimed that NOT ALL OF THEM are. All you are asked to show is that there is one subset of this which is not of the form A1 x B1 where $A1 \in P(A)$, meaning $A1 \subseteq A$, and $B1 \in P(B)$, meaning $B1 \subseteq B$.

That set, being A x B, is of course of the form of A1 x B1. Here's another: {(1, 3), (2,3)}. That is of the form {1, 2} x {3}, and {1, 2} $\subseteq A$ and {3} $\subseteq B$. But you could easily find a counterexample subset of A x B that is not of the form A1 x B1. Try to identify some.

What you're being asked is a way to show that you can always find such a counterexample so long as A and B have at least two elements. Work out a couple more examples, and then try to find a general rule that you're using to find your counterexamples.

 

[Mark44]

Homework Statement

If A and B each have at least two elements, then not every element of P(A×B) has the form A1 ×B1 for some A1 ∈ P(A)and B1 ∈ P(B).

What does P(A) mean? Is it the power set of A? Same question for the other two uses in the above.

 

[Carrie233]

What does P(A) mean? Is it the power set of A? Same question for the other two uses in the above.

Yes, P(A) is power set of A

 

[RPinPA]

P(AXB) = {{(1,3)}, {(1,4)}, {(2,3)}, {(2,4)}, {(1,3),(1,4)}, ... {(1,3), (1,4), (2,3), (2,4)} }

Yep. And not all of those has the form of {some set} x {some set}. The subsets you chose to name in the list above all CAN be expressed that way.
{(1,3)} = {1} x {3}
{(1,4)} = {1} x {4}
{(1,3),(1,4)} = {1} x {3,4}

Maybe list some more of these collections, and in each case see if you can express it as a Cartesian product.

Some of them can't. I guarantee it. Try it. Keep going with the list. There are only 16 subsets of A x B, it's not hard to list them all.