# How do i prove $\omega\times\omega\approx \omega$, **not using prime decomposition nor division**?

Yet there are many ways to prove this, i remember that i saw a proof in a text which proves this without using any decomposition nor division. (I remember the name of the text is "Set theory - Pinter", but i lost this text long time ago and i'm home now)

How do i prove this not using decomposition nor division?

• If you write $\omega$ instead of $\aleph_0$, you're indicating that you want to view it as an ordinal rather than a cardinal, and with ordinal multiplication $\omega\times\omega\neq \omega$. – Henning Makholm Mar 30 '14 at 12:53
• Do you mean Cantor's pairing function: $$f(n,m)=\frac{(n+m)(n+m+1)}2+n$$ – Asaf Karagila Mar 30 '14 at 12:53
• @Henning: Note that $\approx$ symbol, rather than $=$. – Asaf Karagila Mar 30 '14 at 12:54
• @Henning You are right that is customary, but i meant cardinal multiplication. I'll edit it. – John. p Mar 30 '14 at 12:55
• @Asaf No. I remember there is a proof in the text not using division. (Since $n$ is finite, ordinal or cardinal multiplications are identical here. No ambiguity) – John. p Mar 30 '14 at 12:58

The standard "Cantor zig-zag" bijection $\mathbb N\times\mathbb N\to\mathbb N$ is something like $$f(x,y) = x+\frac{(x+y)(x+y+1)}{2}$$ No division (except for a halving) or factoring used here.
If you want to avoid the halving but can accept a definition by cases, how about $$g(x,y) = \begin{cases}x^2+y & \text{if }x>y \\ y^2 + 2y - x & \text{if }y\ge x\end{cases}$$
Even more alternatively, consider the injections $$h(x) = (x,x) \qquad\qquad k(x,y) = 10^{2x}+10^{2y+1}$$ and appeal to the Cantor-Bernstein-Schröder theorem.
• Just replace $\frac{(x+y)(x+y+1)}{2}$ with $\sum_{i=1}^{x+y} i$. Then really no division! ;-) – user642796 Mar 30 '14 at 13:00