A pairing function is a one-to-one mapping from $N^2$ into $N$; for example the Cantor pairing function is given by:
$$J(x,y) = \frac{(x+y)(x+y+1)}{2} + 1$$
Another one is: $f(x,y)=2^x(2y+1)$.
They can be easily generalized to encode $n$-tuples (points in a $n$-dimensional space) ($J(x_1,x_2,...,x_n) = J(x_1,J(x_2,...,J(x_{n-1},x_n)))$).
Are there generalizations for an infinite dimension space? I.e. functions that are bijections between (integer) points in an infinite dimension space and $N$ ?
We take $\mathbb{N}$ to include $0$. Minor modification will take care of things if we define $\mathbb{N}$ to start at $1$.
Consider the set $S$ of all sequences $(a_0,a_1,a_2,\dots)$ of natural numbers that are $0$ from some point on. Let $\psi$ be the mapping that takes the sequence $(a_0,a_1,\dots)$ to $\left(\prod_0^\infty p_i^{a_i}\right)-1$, where $p_i$ is the $i$-th prime. Then $\psi$ is a bijection from $S$ to $\mathbb{N}$.
After nesting the $2^x(2y+1)-1$ pairing function into its linear variable some finite number of times, the final linear component will have to be 0 eventually for any finite starting integer. I think this arbitrary-dimensional tupling function based on that pairing function might be an example of what you are talking about:
Tuple(x1,x2,...,xn)=(2^(n-1))*((2^sum(xj,j=1:n))-sum(2^(-k+sum(xj,j=k+1:n)),k=1:n-1))-1
$$\operatorname{Tuple} (x_1, x_2, \ldots, x_n) = 2^{n-1} \times \left( \left(2^{\sum_{j=1}^n x_j}\right) -\sum_{k=1}^{n-1} 2^{-k+\sum_{j=k+1}^n x_j} \right)-1$$
as
Tuple(x1,x2,...,xn) = Tuple(0,0,0,...,x1,x2,...,xn) = Tuple(x1,x2,...,xn)
$$\operatorname{Tuple} (x_1, x_2, \ldots, x_n) = \operatorname{Tuple} (0, 0, 0, \ldots, x_1, x_2, \ldots, x_n) = \operatorname{Tuple} (x_1, x_2, \ldots, x_n)$$
I hope this is helpful and correct, and I’m curious to know applications for this type of thing. I found your question researching this, and a similar function which can be nested into its linear variable in (almost) the same way:
P(x,y)=(y+1)*Fib(x+3)+floor(y/phi)*Fib(x+2)-2
$$P(x,y) = (y+1) \operatorname{Fib} (x+3) +\lfloor y/\phi \rfloor \operatorname{Fib} (x+2) -2$$
where Fib(n) is the nth Fibonacci number, and phi is the golden ratio (1+sqrt(5))/2.
It is harder to write down the expression of the nested version, but it is easy to program, and easy to find a quick algorithm to unpair a given integer repeatedly until its linear component is 0.
This function is tricky to turn continuous while maintaining its values on the integers, whereas the first function is already set up to be continuous.
I’d love to know a use for some of this!
