# cartesian product $A^2 = A$, possible?

Do there exist non-empty sets $A$ such that $A\times A = A$?

$A\times A = A$ looks a little strange to me, since $A\times A$ seems somehow more complicated than $A$, hence it is unlike that they are equal, but then, I cannot think of any reason why there should not be such a (non-empty) set.

-
For the benefit of non-set-theorists (like myself): "$=$" here is set equality, not equipotence (otherwise the trivial examples of $\mathbb{N}\times\mathbb{N}\equiv\mathbb{N}$ &c apply) – sds Apr 4 '14 at 17:19

Under the usual axioms of set theory, the answer is negative. The reason is that one of these axioms, the axiom of foundation, allows us to assign to each set a rank $\alpha$ (an ordinal number) that indicates at what stage of the transfinite construction of the universe the set appeared. Ordinals have the property that any non-empty collection of them has a first element, and if a set $x$ belongs to a set $y$, then the rank of $x$ is strictly smaller than the rank of $y$ (intuitively, a set cannot be constructed until all its elements are present).

Now, if $A$ is non-empty, let $a\in A$ be an element of smallest rank. Then we cannot have $a=(b,c)$ for some $b,c\in A$, since $(b,c)=\{\{b\},\{b,c\}\}$, so both $b$ and $c$ would have to have rank smaller than the rank of $a$, contradicting its minimality. This shows that $A$ cannot be a subset of $A\times A$.

The argument works for just about any reasonable definition of ordered pair, not just the usual one.

Note, however, that the other containment $A\times A\subset A$ is possible, and can be easily arranged by a recursive construction: Start with any set $A_0$. Let $A_1=A_0\cup(A_0\times A_0)$, $A_2=A_1\cup(A_1\times A_1)$, etc. Then $A_\omega=\bigcup_n A_n$ satisfies that $A_\omega\times A_\omega\subset A_\omega$.

(In fact, in the transfinite construction of the universe of sets, for any limit stage $\alpha$ we have that $V_\alpha\times V_\alpha \subset V_\alpha$.)

On the other hand, it is consistent with the negation of the axiom of foundation that there are sets $\Omega$ such that $\Omega=\{\Omega\}$, and this implies that $\Omega=\Omega\times\Omega$.

-
Am I missing something, or should it be $A_\omega\times A_\omega\subset A_\omega$? – Ansgar Esztermann Apr 4 '14 at 14:52
@AnsgarEsztermann Hehe. Typo, thanks for spotting it. Fixed now. – Andrés E. Caicedo Apr 4 '14 at 15:01
I'm sorry, I don't understand why Ω={Ω} implies that Ω=Ω×Ω. – Alex Apr 4 '14 at 15:45
@Alex If $\Omega=\{\Omega\}$, then $\Omega\times\Omega=\{\Omega\}\times\{\Omega\}=\{(\Omega,\Omega)\}$. Now, since $(a,b)=\{\{a\},\{a,b\}\}$ and $\{c,c\}=\{c\}$ for any $a,b,c$, we have that $(\Omega,\Omega)=\{\{\Omega\},\{\Omega,\Omega\}\}=\{\{\Omega\},\{\Omega\}\}=\{\{‌​\Omega\}\}=\{\Omega\}=\Omega$. Finally, $\{(\Omega,\Omega)\}=\{\Omega\}=\Omega$ as well. – Andrés E. Caicedo Apr 4 '14 at 16:38

I assume you define $(a,b):=\{\{a\},\{a,b\}\}$; for other definitions of "ordered pair" the following proof can be adjusted. Let $A$ be a set such that $A\times A=A$. So for $x\in A$ there exist $y,z\in A$ such that $x=\{\{y\},\{y,z\}\}$. Especially, there exists a unique $y\in A$ such that $\{y\}\in x$. This defines a map $f\colon A\to A$ with $\{f(x)\}\in x$ for all $x\in A$.

Assume $A\ne 0$ and let $a\in A$ be an element. Then the sequence $a, f(a), f(f(a)), \ldots$ gives us a nonempty set $$B=\{\,f^n(a)\mid n\in\mathbb N_0\,\}\cup \{\,\{f^n(a)\}\mid n\in\mathbb N_0\,\}.$$ By the Axiom of Foundation, there exists $b\in B$ with $b\cap B=\emptyset$. But if $b=f^n(a)$ then $\{f^{n+1}(a)\}\in b\cap B$; and if $b=\{f^n(a)\}$ then $f^n(a)\in b\cap B$. Contradiction! Therefore $A=\emptyset$.

-