0
$\begingroup$

By this I mean, you could take any natural number, apply some kind of operation (arithmetic or other), and end up with two natural numbers. Then, you can apply an inverse operation on the two produced natural numbers to produce the original natural number.

I haven't been able to find any mathematical operation that consistently works, and i've been looking at more "unique" solutions.

An example: you apply the operation on the number 15, and the result is the numbers 1 and 5. Then, when applying a separate operation to 1 and 5, the result would be 15. It isn't a correct example but it's along the same idea.

$\endgroup$
  • 3
    $\begingroup$ Are you are looking for a bijection from $\mathbb N$ to $\mathbb N \times \mathbb N$? One way of doing this is the Cantor pairing function. Take a look at pairing functions on wikipedia or search this website for questions on bijections between $\mathbb N$ and $\mathbb N \times \mathbb N$. $\endgroup$ – Tom Cooney Feb 19 '13 at 19:53
10
$\begingroup$

The set of natural numbers is denoted $\mathbb N$ and the set of pairs of natural numbers is denoted $\mathbb{N \times N}$. These two sets have the same cardinality between them. What you suggest with your $15$ example is a bijection $\mathbb{N \to N \times N}$.

Given a number $a \in \mathbb N$ write it as a decimal number. Map this to $(b, c)$ where $b$ are the even digits of $a$ and $c$ are the odd (counting from the $1$'s place). So $15 \mapsto (1, 5)$, $112 \mapsto (1, 12)$, and $1000001 \mapsto (0, 1001)$.

Given a pair of numbers $(b, c)$ we map $(b, c) \mapsto a$ where $a$ is the number created by interleaving the digits of $b$ and $c$, starting with the first digit of $c$. If the numbers are not the same length we add zeros to make them so before interleaving. So $(10, 1240) = (0010, 1240) \mapsto 1021400$ and $(1, 12) \mapsto 112$.

These two operations are inverse to each other.

$\endgroup$
  • $\begingroup$ (+1): Soooooo much simpler than my answer, and I'm sure it took you much less time. /sigh/ $\endgroup$ – Cameron Buie Feb 19 '13 at 22:53
2
$\begingroup$

It seems that you're trying to find a formula that gives a bijection between $\Bbb N$ and $\Bbb N\times\Bbb N$. Such a thing is possible, but not always pretty. Let me give you as nice a setup as I can.

Note: Hereinafter, I will use the definition $\Bbb N=\{0,1,2,3,...\}$, considered as a subset of the real numbers (so that absolute value and square roots make sense). Let me know if your definition of the natural numbers doesn't include $0$, and I'll adjust my answer accordingly.


For each $n\in\Bbb N$, let "gnomon $n$" of $\Bbb N\times\Bbb N$ be the set $$G(n):=\bigl\{\langle x,y\rangle\in\Bbb N\times\Bbb N:\max\{x,y\}=n\bigr\}.$$ Note that the $G(n)$ are pairwise disjoint, non-empty sets. Also, $$\bigcup_{k=0}^nG(k)=\bigl\{\langle x,y\rangle\in\Bbb N\times\Bbb N:x\leq n,y\leq n\bigr\}$$ for any $n\in\Bbb N$. From this, it follows that $\Bbb N\times\Bbb N=\bigcup_{n\in\Bbb N}G(n)$. Moreover, noting that $G(0)$ has a single element, and that $G(n+1)$ consists of the $(n+2)^2$ elements of $\bigcup_{k=0}^{n+1}G(k)$, less the $(n+1)^2$ elements of $\bigcup_{k=0}^nG(k)$, and so $G(n+1)$ has $(n+2)^2-(n+1)^2=2n+3$ elements. Thus, each $G(n)$ has $2n+1$ elements.

For each $n,$ we define a relation $\sqsubset_n$ on $G(n)$ by $\langle w,x\rangle\sqsubset_n\langle y,z\rangle$ if and only if (i) $w<y$ or (ii) $w=y=n$ and $x>z$. Each $\sqsubset_n$ is a strict total order relation (as you can check).

We now define a relation $\sqsubset$ on $\Bbb N\times N$ by $\langle w,x\rangle\sqsubset\langle y,z\rangle$ if and only if (i) $\langle w,x\rangle\in S(m)$ and $\langle y,z\rangle\in S(n)$ for some $m<n$ or (ii) $\langle w,x\rangle,\langle y,z\rangle\in S(n)$ with $\langle w,x\rangle\sqsubset_n\langle y,z\rangle$. $\sqsubset$ is a strict total order relation (as you can check).

The idea, then, is to match up the elements of $\Bbb N$ and those of $\Bbb N\times\Bbb N$ so that the $<$-order of the elements of $\Bbb N$ agrees with the $\sqsubset$-order of the corresponding elements of $\Bbb N\times\Bbb N$. It will be simpler to start with the $\Bbb N\times\Bbb N\to\Bbb N$ map (call it $f$). We'll go slice by slice.


Starting in $S(0)$, we need $f(0,0)=0$. Now, suppose for some $n>0$ that we have finished assigning $f$-values to the members of $G(k)$ for $0\leq k< n$, so we have mapped pairs to each of the first $n^2$ natural numbers--that is, $0$ through $n^2-1$. Next, take $f(0,n)=n^2,$ and in general $f(j,n)=n^2+j$ for each $0\leq j\leq n$. Then take $f(n,n-1)=n^2+n+1$, and in general take $f(j,n)=n^2+n+(n-j)$ for $0\leq j< n$. Thus, we define the map $f:\Bbb N\times\Bbb N\to\Bbb N$.

This gets us partway to a nice formula, but having the two different general formulas when we were working in gnomon $n>0$ is a problem. We can fix it, though, by noting that $$f(j,n)=n^2+j=n^2+n+(j-n)$$ for $0\leq j\leq n,$ so that in general, $$f(x,y)=n^2+n+(x-y)$$ for $x,y\in\Bbb N$ with $\max\{x,y\}=n$. This was how we defined $f(x,y)$ for $\langle x,y\rangle\neq\langle 0,0\rangle$, and it's easy to see that it works when $x=y=0$, too. Hence, given any $x,y\in\Bbb N$, we have $$f(x,y)=\bigl(\max\{x,y\}\bigr)^2+\max\{x,y\}+(x-y).\tag{#}$$ At this point, we can use the formula $(\#)$ to check that $f(w,x)<f(y,z)$ if and only if $\langle w,x\rangle\sqsubset\langle y,z\rangle$. Since $\sqsubset$ strictly orders $\Bbb N\times\Bbb N$, it follows that $f$ is a one-to-one function. I'll leave it to you to check that it's onto, and so is a formula of the kind that (it seems) you're trying to find.

If you don't want the $\max$ notation in your formula, then observe that $$\max\{a,b\}=\frac12\left(a+b+|a-b|\right)$$ for any real $a,b$. (Why?) Then $$\begin{align}\left(\max\{x,y\}\right)^2 &= \frac14\left(x+y+|x-y|\right)^2\\ &= \frac14\left((x+y)^2+2(x+y)|x-y|+|x-y|^2\right)\\ &= \frac14\left((x+y)^2+2(x+y)|x-y|+(x-y)^2\right)\\ &= \frac14\left(2x^2+2y^2+2(x+y)|x-y|\right)\\ &= \frac12\left(x^2+y^2+(x+y)|x-y|\right),\end{align}$$ and $$\begin{align}\max\{x,y\}+(x-y) &= \frac12\left(x+y+|x-y|\right)+\frac12(2x-2y)\\ &= \frac12\left(3x-y+|x-y|\right),\end{align}$$ so our formula $(\#)$ can instead be written as $$f(x,y)=\frac12\left(x^2+y^2+3x-y+(x+y+1)|x-y|\right).\tag{##}$$


We'll define $g:\Bbb N\to\Bbb N\times\Bbb N$ in a similar fashion. We need $g(0)\mapsto\langle 0,0\rangle$.

Given $m>0$, there is some greatest $n$ such that $n^2\leq m$. We'll need to have $g(m)\in G(n+1)$ to avoid skipping any pairs. If $m-n^2<n+1$, we'll put $g(m)=\langle m-n^2,n+1\rangle$, and otherwise, we'll put $g(m)=\langle n+1,(n+1)^2-m\rangle$. Since $n^2\leq m<(n+1)^2$ by our choice of $n$, then $g(m)\in G(n)$. Again, though, we'd like a consistent formula. If $m-n^2<n+1,$ then $m-n^2\leq n,$ so $$(n+1)^2-m=2n+1-(m-n^2)\geq 2n+1-n=n+1.$$ Hence, we have $$g(m)=\bigl\langle\min\{m-n^2,n+1\},\min\{(n+1)^2-m,n+1\}\bigr\rangle,$$ where $n$ is the greatest natural number such that $n^2\leq m$.

For any real $a$, we denote by $\lfloor a\rfloor$ the greatest integer that is $\leq a$. For $a\geq0$, we necessarily have that $\lfloor a\rfloor$ is a natural number. Note that for natural numbers $m,n$, we have $n^2\leq m$ if and only if $n\leq\sqrt{m}$. For $m>0$, we defined $$g(m)=\bigl\langle\min\{m-\lfloor\sqrt{m}\rfloor^2,\lfloor\sqrt{m}\rfloor+1\},\min\{(\lfloor\sqrt{m}\rfloor+1)^2-m,\lfloor\sqrt{m}\rfloor+1\}\bigr\rangle,\tag{$*$}$$ and the definition also works for $g(0)=\langle 0,0\rangle$.

Now, for all real $a,b$ we have $$\min\{a,b\}=\frac12\left(a+b-|a-b|\right).$$ We could use this to rewrite $(*)$ without the $\min$ notation, but honestly, that just makes it worse.

It turns out that $f$ and $g$ are inverses of each other, though that's easier to see from the construction than from our final formulas.

$\endgroup$
  • 2
    $\begingroup$ Oh my goodness, I haven't read the whole thing, but why on earth would you go to that much trouble? $\endgroup$ – Tara B Feb 19 '13 at 22:53
  • 1
    $\begingroup$ I've been asking myself that same question since I posted this. $\endgroup$ – Cameron Buie Feb 19 '13 at 22:55
  • $\begingroup$ How long did it take you? You must have some horrible other task to do that you really wanted to put off. =] $\endgroup$ – Tara B Feb 19 '13 at 22:56
  • $\begingroup$ Between 2 and 3 hours. And yes, I did. ;-) $\endgroup$ – Cameron Buie Feb 20 '13 at 0:14
1
$\begingroup$

$n \mapsto (2n, 2n+1)$? Do you need the inverse to be defined on all pairs?

$\endgroup$
  • $\begingroup$ Or even $n$ to $(n,n)$. $\endgroup$ – zaarcis Feb 19 '13 at 19:43
  • $\begingroup$ I don't know how to correctly word this, but this wouldn't work because if I used (5, x) for example, 5/2 would not be a natural number. $\endgroup$ – John Feb 19 '13 at 19:45
  • $\begingroup$ Looks like you're after what Tom mentioned above as a comment. A way of uniquely assigning a number to every pair rather than assigning a pair to each number. $\endgroup$ – muzzlator Feb 19 '13 at 19:55

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.