# Cartesian Product - Proof

#### Yankel

##### Active member
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
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
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 "$$x\in A$$ if and only if $$x\in B$$". 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
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 "$$x\in A$$ if and only if $$x\in B$$". 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
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
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$.