# Cartesian Product

• Feb 4th 2010, 03:44 AM
KSM08
Axiom of Foundation and Cartesian Product
Can anyone help with this question:

Use the Axiom of Foundation to show that if A is a non-empty set, then A is not equal to A × A.
[Hint: consider the set a = A ∪ (∪A)]?

Many thanks.
• Feb 9th 2010, 09:24 AM
Mimi89
See here: Axiomatic set theory - Google Books (Suppes, Axiomatic Set Theory, Theorem 107). There you get that A=0, which contradicts it being non-empty.

Hope this helps!
• Feb 9th 2010, 11:31 AM
MoeBlee
I'll give you a proof but I'll ask "WHY?" for certain details you should be able to supply as an easy exercise. If you can't answer the "WHY?"s, then you need to review your introductory set theory and/or logic material.

'x/\y' will stand for binary intersection.

Proof by contradiction: Suppose A not empty and A = AxA.

A not empty, so any m in A is in AxA (WHY?).
So, if m in A, then there is a j and k such that j in A and k in A and m = {{j} {j k}} (WHY?).
A not empty, perforce AuUA not empty (WHY?).
No m in AuUA is empty (WHY?).
Since AuUA not empty, by the axiom of regularity, there is an m such that m in AuUA and m/\(AuUA) empty. And m not empty, since, as we observed, no member of AuUA is empty.
Suppose m in A.
So m subset of UA (WHY?).
So, since m not empty, we have m/\UA not empty (WHY?), which contradicts m/\(AuUA) empty (WHY?).
So m not in A.
So m in UA (WHY?).
So there is a j and k such that j in A and k in A and m = {j} or m = {j k} (WHY?).
So m/\A not empty (WHY?), which contradicts m/\(AuUA) is empty (WHY?).
So we are done (WHY?).