Welcome to our community

Be a part of something great, join today!

Cartesian Product - Proof

Yankel

Active member
Jan 27, 2012
398
Dear all,

I am trying to prove a simple thing, that if AxA = BxB then A=B.

The intuition is clear to me. If a pair (x,y) belongs to AxA it means that x is in A and y is in A. If a pair (x,y) belongs to BxB it means that x is in B and y is in B. If the sets of all pairs are equal, it means that every x in A is also in B and vice versa.

How do I prove it formally ?

Thank you !
 

Opalg

MHB Oldtimer
Staff member
Feb 7, 2012
2,679
Dear all,

I am trying to prove a simple thing, that if AxA = BxB then A=B.

The intuition is clear to me. If a pair (x,y) belongs to AxA it means that x is in A and y is in A. If a pair (x,y) belongs to BxB it means that x is in B and y is in B. If the sets of all pairs are equal, it means that every x in A is also in B and vice versa.

How do I prove it formally ?

Thank you !
This may not be as simple as you think. To start with, what do you mean by saying that two sets are equal? I think that the only way to make sense of that is to interpret "A=B" to mean that A and B have the same cardinality.

If a set $A$ is finite then its cardinality is just the number of elements it contains, denoted by $|A|$. If $|A| = m$ then $|A\times A| = m^2.$ So if $|B| = n$ and $|A\times A| = |B\times B|$ then $m^2 = n^2$, from which it follows that $m=n$. This proves that if "$A\times A = B\times B$" then "$A=B$" in the case of finite sets.

For infinite sets the situation is more complicated. There is a theorem of Zermelo that if $A$ is an infinite set then $|A\times A| = |A|$. From that it follows immediately that if $|A\times A| = |B\times B|$ then $|A| = |B|$. However, the proof of Zermelo's theorem requires the Axiom of Choice. In models of set theory that do not satisfy this axiom, it may be that your result does not hold.
 

HallsofIvy

Well-known member
MHB Math Helper
Jan 29, 2012
1,151
Opalg said "
I think that the only way to make sense of that is to interpret "A=B" to mean that A and B have the same
cardinality
."

I disagree. To say that sets A and B are equal means "[tex]x\in A[/tex] if and only if [tex]x\in B[/tex]". If two sets are equal they have the same cardinality but the converse is not true. The sets A= {1, 2, 3} and B= {a, b, c} have the same cardinality but are not equal.
 

Opalg

MHB Oldtimer
Staff member
Feb 7, 2012
2,679
Opalg said "
I think that the only way to make sense of that is to interpret "A=B" to mean that A and B have the same
cardinality
."

I disagree. To say that sets A and B are equal means "[tex]x\in A[/tex] if and only if [tex]x\in B[/tex]". If two sets are equal they have the same cardinality but the converse is not true. The sets A= {1, 2, 3} and B= {a, b, c} have the same cardinality but are not equal.
In that case, the result becomes trivially true. If $A\times A$ and $B\times B$ are just two different names for the same set, then the diagonal elements of $A\times A$ (those of the form $(a,a):a\in A$) are duplicates of the elements of $A$. The same holds for the diagonal elements of $B\times B$. If those diagonals are the same, it follows that the elements of $A$ are the same as the elements of $B$, so $A=B$.
 

HallsofIvy

Well-known member
MHB Math Helper
Jan 29, 2012
1,151
Yes, it is. Saying that "A= B", where A and B are sets, means that if x is in A then it is also in B and if y is in B then it is also in A.

If x is a member of A. then (x, x) is in AxA= BxB so x is in B. If y is a member of B then (y, y) is in BxB= AxA so y is in A. Therefore A= B.

It is trivial but that is the question asked.
 

Olinguito

Well-known member
Apr 22, 2018
251
I am trying to prove a simple thing, that if AxA = BxB then A=B.

The intuition is clear to me. If a pair (x,y) belongs to AxA it means that x is in A and y is in A. If a pair (x,y) belongs to BxB it means that x is in B and y is in B. If the sets of all pairs are equal, it means that every x in A is also in B and vice versa.

How do I prove it formally ?

Thank you !
Let $a\in A$. Then $(a,a)\in A\times A$. Since we’re assuming $A\times A=B\times B$, this means $(a,a)\in B\times B$ and thus $a\in B$. Therefore $A\subseteq B$. The same argument with $A$ and $B$ interchanged shows that $B\subseteq A$. Hence $A=B$.