# All Sets have bijection with cartesian products of Subsets?

I was doodling around with some math today, trying to find "representations" for sets as cartesian products of their proper subsets. For example:

$\mathbb{N}\leftrightarrow 2\mathbb{N}\times\{0,1\}$

$\mathbb{Z}\leftrightarrow 2\mathbb{Z}\times\{0,1\}$

$\mathbb{R}\leftrightarrow \mathbb{Z}\times[0,1)$

I'm thinking most ways to do this have to do with abstract algebra, using quotient structures times the respective substructure. But I was wondering given an arbitrary non-empty set $A$ and ignoring trivial cases like $|A|=1$, does there always exist a bijection with some $B\times C$ where $B$ and $C$ are proper non-empty subsets of $A$?

• Under the axiom of choice, any infinite set $A$ is in bijection with $2A$ and $A\times A$, so yes. – Andrés E. Caicedo Jul 12 '14 at 5:05

No. If $X$ and $Y$ are finite then $|X\times Y|=|X|\cdot|Y|$.

Take $A$ to be any finite set with a prime number of elements, then it cannot be expressed as the product of two proper subsets.

In the case of an infinite set, then answer is positive - at least assuming the axiom of choice - because every infinite set satisfies $|A|=|A\times A|$, so one can easily cook such proper subsets.

Finally, you should recall that infinite sets usually don't have a natural structure like that of $\Bbb R$ and $\Bbb Z$ so that you can think about them as algebraic structure. Sets are... well, sets.

• Hi Asaf, pretty sure the trivial cases mentioned in the last paragraph are precisely the $A$ with prime number size. – Andrés E. Caicedo Jul 12 '14 at 5:06
• (And the obvious question now, whether choice is needed. Do we have "prime" Dedekind finite numbers?) – Andrés E. Caicedo Jul 12 '14 at 5:07
• @Andres: Well, $|A|=1$ is one trivial case, $|A|=2$ is a whole different trivial case. (In the former there are no proper subsets which are non-empty; in the latter it is because of $2$ is prime.) So I disagree. – Asaf Karagila Jul 12 '14 at 5:07
• @Andres: Of course, in recent MO threads, Noah S pointed a wonderful second paper by Sageev that shows that from an inaccessible we get that all Dedekind-finite sets are comparable; and also that if all Dedekind-finite sets are comparable, then they form a model of arithmetic. – Asaf Karagila Jul 12 '14 at 5:09
• Thanks guys. Some of this is way over my head, but I get the answer for infinite sets. – Robearz Jul 12 '14 at 5:14