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

In summary, the homework statement is proving that 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).
  • #1
Carrie233
3
0

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)} }
 
Last edited:
Physics news on Phys.org
  • #2
Carrie233 said:

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.
 
  • #3
fresh_42 said:
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.
 
  • #4
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.
 
Last edited:
  • #5
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.
Carrie233 said:
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.
 
  • #6
Carrie233 said:

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.
 
  • #7
Mark44 said:
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
 
  • #8
Carrie233 said:
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.
 

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

1. What is the Cartesian Product of Sets?

The Cartesian Product of Sets is a mathematical operation that combines two or more sets to create a new set. It is denoted by the symbol "x" and is also known as the cross product.

2. How is the Cartesian Product of Sets calculated?

The Cartesian Product of Sets is calculated by taking all possible ordered pairs of elements from the two sets and combining them. For example, if Set A has three elements (a, b, c) and Set B has two elements (1, 2), the Cartesian Product of Sets A and B would be {(a, 1), (a, 2), (b, 1), (b, 2), (c, 1), (c, 2)}.

3. What is the cardinality of the Cartesian Product of Sets?

The cardinality, or size, of the Cartesian Product of Sets is equal to the product of the cardinalities of the individual sets. In other words, if Set A has m elements and Set B has n elements, the Cartesian Product of Sets A and B will have m x n elements.

4. What are some real-world applications of the Cartesian Product of Sets?

The Cartesian Product of Sets is commonly used in computer science and statistics to analyze data and solve problems. It can also be applied in various fields such as genetics, game theory, and social sciences.

5. What is the difference between the Cartesian Product and the Union of Sets?

The Cartesian Product of Sets combines elements from two or more sets to create a new set, while the Union of Sets combines elements from two or more sets to create a single set without any duplicate elements. In other words, the Cartesian Product creates a new set, while the Union merges existing sets.

Similar threads

  • Precalculus Mathematics Homework Help
Replies
14
Views
2K
  • Linear and Abstract Algebra
Replies
3
Views
1K
  • Precalculus Mathematics Homework Help
Replies
14
Views
2K
  • Precalculus Mathematics Homework Help
Replies
11
Views
1K
  • Programming and Computer Science
Replies
3
Views
1K
  • Introductory Physics Homework Help
Replies
2
Views
6K
  • Precalculus Mathematics Homework Help
Replies
10
Views
2K
  • Precalculus Mathematics Homework Help
Replies
4
Views
1K
  • Set Theory, Logic, Probability, Statistics
2
Replies
35
Views
996
  • Precalculus Mathematics Homework Help
Replies
9
Views
1K
Back
Top