4
$\begingroup$

I was wondering, in ZFC, if a set can ever equal to the cross product of two of its subsets. Or, more generally, the cross product of one of its subsets with any other set. (Exclude trivial examples like $\phi=\phi \times \phi$.)

So for example $\{a,b\}=\{a\} \times \mathbb{N}$ or $\mathbb{N}=\mathbb{Z} \times \{0,1\}$ are impossible. I want to write a proof that it's always impossible.

It feels like this can be proven using the Axiom of Foundation... or does someone have a counterexample?

$\endgroup$
3
  • $\begingroup$ Hm, why $\phi = \phi \times \phi$? What is $\phi$? Did you mean $\varnothing \times \varnothing = \varnothing$? $\endgroup$ – Artur Riazanov Jan 25 '18 at 15:46
  • $\begingroup$ The answer will invariably depend on how you code ordered pairs and Cartesian products. $\endgroup$ – Asaf Karagila♦ Jan 25 '18 at 16:05
  • $\begingroup$ (Just to explain why, let me point out the following. We code the ordered pair $(x,y)$ as follows, if $x$ and $y$ are both finite ordinals, then $(x,y)$ is the finite ordinal equals to $2^x(2y+1)-1$; otherwise $(x,y)=\{\{x\},\{x,y\}\}$ as usual. Now it follows that $\omega=\omega\times\omega$ since $(x,y)\mapsto 2^x(2y+1)-1$ is a bijection between $\omega\times\omega$ and $\omega$. But as Ross' answer shows, assuming we talk about the standard Kuratowski definition, the answer is indeed negative. $\endgroup$ – Asaf Karagila♦ Jan 25 '18 at 16:16
4
$\begingroup$

Define the rank of a set as the number of layers of braces down to its deepest buried $\emptyset$, so $\operatorname{rank}(\emptyset)=0,$ $\operatorname{rank}(\{\emptyset\})=1,$ and so on. It is an ordinal, and can be infinite, since for instance $\operatorname{rank}(\omega)=\omega,\operatorname{rank}(\{\omega\})=\omega+1$, etc. The rank of an ordered pair (assuming you use the usual Kuratowski definition) is $2$ more than the maximum rank of its components using ordinal addition. Take one of the members of your set of minimum rank. It cannot be the ordered pair of two members of the set.

$\endgroup$
1
  • $\begingroup$ It may be worth pointing out that, on the other hand, it is possible to have nontrivial sets $X$ with $X\times X\subseteq X$. $\endgroup$ – Andrés E. Caicedo Jan 25 '18 at 16:13
1
$\begingroup$

Ross's answer shows that you can't have such a set if you use the usual Kuratowski representation of ordered pairs.

On the other hand, you could use Quine's "type-level" definition of ordered pairs. With this definition we have, $(\varnothing,\varnothing)=\varnothing$, and so $X=\{\varnothing\}$ satisfies $X=X\times X$.

In fact, with Quine pairs every set whatsoever is an ordered pair, so you can get an infinity of examples by defining $$ f(S) = S \cup (S\times S) \cup \{x\mid \exists y: (x,y)\in S \lor (y,x)\in S\} $$ Then for any set $A$, $X=\bigcup_{n\in\mathbb N} f^n(A)$ is a solution to $X=X\times X$ that contains $A$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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