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?

  • 1
    $\begingroup$ 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$. $\endgroup$ – Henning Makholm Mar 30 '14 at 12:53
  • $\begingroup$ Do you mean Cantor's pairing function: $$f(n,m)=\frac{(n+m)(n+m+1)}2+n$$ $\endgroup$ – Asaf Karagila Mar 30 '14 at 12:53
  • $\begingroup$ @Henning: Note that $\approx$ symbol, rather than $=$. $\endgroup$ – Asaf Karagila Mar 30 '14 at 12:54
  • $\begingroup$ @Henning You are right that is customary, but i meant cardinal multiplication. I'll edit it. $\endgroup$ – John. p Mar 30 '14 at 12:55
  • $\begingroup$ @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) $\endgroup$ – 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.

Its inverse needs a square root and a bit of footwork, though.

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.

  • $\begingroup$ Just replace $\frac{(x+y)(x+y+1)}{2}$ with $\sum_{i=1}^{x+y} i$. Then really no division! ;-) $\endgroup$ – user642796 Mar 30 '14 at 13:00

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.