Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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 at 17:19

2 Answers 2

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$.

share|improve this answer
    
Am I missing something, or should it be $A_\omega\times A_\omega\subset A_\omega$? –  Ansgar Esztermann Apr 4 at 14:52
    
@AnsgarEsztermann Hehe. Typo, thanks for spotting it. Fixed now. –  Andres Caicedo Apr 4 at 15:01
    
I'm sorry, I don't understand why Ω={Ω} implies that Ω=Ω×Ω. –  Alex Apr 4 at 15:45
1  
@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. –  Andres Caicedo Apr 4 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$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.