2
$\begingroup$

We know that the rationals are countable since we can list them via zig-zagging:

$$\begin{matrix} \frac{1}{1} && \frac{1}{2} &\color{red}\to &\frac{1}{3} &&\frac{1}{4} & \color{red}\to & \frac{1}{5}\\ \color{red}\downarrow & \color{red}\nearrow && \color{red}\swarrow && \color{red}\nearrow &&\color{red}\swarrow\\ \frac{2}{1} && \frac{2}{2} && \frac{2}{3} \\ & \color{red}\swarrow && \color{red}\nearrow\\ \frac{3}{1}&&\frac{3}{2}&&& \ddots\\ \color{red}\downarrow&\color{red}\nearrow\\ \frac{4}{1} \end{matrix}$$

Now suppose we have a function $f: \mathbb N^2 \to A$ for some set $A$, where we list the outputs of the function in the same way: $$\begin{matrix} f(1,1) && f(1,2) && f(1,3) && f(1,4) && f(1,5)\\ ~\\ f(2,1) && f(2,2) && f(2,3) \\ ~\\ f(3,1) && f(3,2) &&& \ddots\\ ~\\ f(4,1) \end{matrix}$$

Is there a way to define a function $f' : \mathbb N \to A$ such the resulting sequence of outputs travels along this grid in the same way?

$$\begin{matrix} f(1,1) && f(1,2) &\color{red}\to &f(1,3) &&f(1,4)& \color{red}\to & f(1,5)\\ \color{red}\downarrow & \color{red}\nearrow && \color{red}\swarrow && \color{red}\nearrow &&\color{red}\swarrow\\ f(2,1) && f(2,2) && f(2,3) \\ & \color{red}\swarrow && \color{red}\nearrow\\ f(3,1) && f(3,2) &&& \ddots\\ \color{red}\downarrow&\color{red}\nearrow\\ f(4,1) \end{matrix}$$

That is, defining $f'$ in terms of $f$ such that

$$ f'(1) = f(1,1)\\ f'(2) = f(2,1) \\ f'(3) = f(1,2) \\ f'(4) = f(1,3) \\ f'(5) = f(2,2) \\ f'(6) = f(3,1) \\ \vdots$$

Given $n\in\mathbb N$ I need to find a way to map to the corresponding pair in $\mathbb N^2$, expressing this only in terms of $n$, but I'm not sure how to do this. I appreciate any assistance.

$\endgroup$
1
+50
$\begingroup$

Yes, certainly. In particular, the idea of "zig-zagging" is captured by defining a bijection $$g:\mathbb N\rightarrow \mathbb N^2$$ where $g(i)$ is the $i^{th}$ element in the zig-zag. Then, you are looking for the function $$f'=f\circ g.$$ That is, the function defined as $f'(x)=f(g(x))$. Essentially, you are using $g$ to determine the input to $f$, which causes it to zig-zag through the outputs as you desire. This actually gives you a bijection between the set of functions $\mathbb N^2\rightarrow A$ and the set of functions $\mathbb N\rightarrow A$.

You could write $g$ explicitly if you wanted to. For instance, if we let $T_n=\frac{n(n+1)}2=1+\ldots+n$ be the $n^{th}$ triangular number. We could express $g$ by saying, for $0\leq k \leq n$ $$g(T_n+k)=\begin{cases}(n-k,k) & \text{if }n\text{ odd}\\ (k,n-k) & \text{if }n\text{ even.} \end{cases}$$ This assumes you consider $0\in \mathbb N$, but it's easy enough to shift everything to make it work if you don't like zero being a natural number.


If we wanted to write $g$ in a single equation, we could do so. In particular, suppose we want to know $g(x)$. We can figure this out based on the previous equation. We first must write $x=T_n+k$, so must determine $n$ and $k$. In particular, $T_n=\frac{1}2(n+1/2)^2-\frac{1}8$, so we can write $n=\lfloor\sqrt{2x+1/4}-1/2\rfloor.$ Then, $k=x-T_n$. We can also write our expression as $$g(T_n+k)=\left(\left(\frac{(-1)^n+1}2\cdot n + (-1)^nk\right),\left(\frac{(-1)^{n+1}+1}2\cdot n + (-1)^{n+1}k\right)\right).$$ Then, blindly substituting everything in gives: $$g(x)=\left(\left(\frac{(-1)^{\lfloor\sqrt{2x+1/4}-1/2\rfloor}+1}2\cdot (\lfloor\sqrt{2x+1/4}-1/2\rfloor)+(-1)^{\lfloor\sqrt{2x+1/4}-1/2\rfloor}\cdot (x+1/8-\frac{1}2(\lfloor\sqrt{2x+1/4}-1/2\rfloor)^2\right),\left(\frac{(-1)^{\lfloor\sqrt{2x+1/4}-1/2\rfloor+1}+1}2\cdot (\lfloor\sqrt{2x+1/4}-1/2\rfloor)+(-1)^{\lfloor\sqrt{2x+1/4}-1/2\rfloor+1}\cdot (x+1/8-\frac{1}2(\lfloor\sqrt{2x+1/4}-1/2\rfloor)^2\right)\right).$$ However, I think it should be fairly clear why I prefer the other way of writing this function. Note that if we want $\mathbb N$ to not include zero, we have to replace every instance of $n$ in the above formula by $n-1$ and then add one to each coordinate afterwards.

$\endgroup$
  • $\begingroup$ Thanks for your reply! Is there a more explicit way of defining $g$, perhaps not in a piece-wise manner? $\endgroup$ – Luke Collins Nov 27 '17 at 20:24
  • $\begingroup$ @LukeCollins The answer to that depends on what you mean by "explicit" - I think this is the clearest way to write $g$. If, however, you want a single formula, it is certainly possible if you're okay with using the floor function and raising $(-1)$ to integer powers. (I could write this if you wish, but it wouldn't look pretty) $\endgroup$ – Milo Brandt Nov 28 '17 at 3:53
  • $\begingroup$ I'd appreciate it if you write it down! $\endgroup$ – Luke Collins Nov 28 '17 at 9:26
  • $\begingroup$ @LukeCollins I added the formula. (It doesn't fit very well on the page, but I don't think it can be shortened very much. It's rather redundant - it's much easier to calculate $n$ from $x$, then $k$ from $x$ and $n$, then use the original formula) $\endgroup$ – Milo Brandt Nov 28 '17 at 18:23
1
$\begingroup$

It is a problem of ranking i.e.

What is the point with rank $n$ ?

Ranking (a mathematical art arising from Computer Science) is the fact of putting (denumerable) sets (say $X$, seen as a set of data structures) in explicit bijection with $\mathbb{N}$. Two problems then arise for the bijection $g:\mathbb{N}\to X$ (here $X=\mathbb{N}^2$)

A) Given $P\in X$, what is the "rank" of $P$ (i.e. $n\in \mathbb{N}$ s.t. $g(n)=P$) ?

B) Given $n\in \mathbb{N}$ what is the "position of $P$" ?

If you draw your picture, you see that the visits of your zig-zag curve (starting with $\phi(0)=(0,0),\phi(1)=(1,0)$) to the $x$-axis are for $n=0,1,5,6,14,15$ then for points $(2n^2+3n,2n^2+3n+1)$. Now your pattern is clear in 4 paragraphs.

a) Visits to $x$-axis $$ \phi(2n^2+3n)=(2n,0)\ ;\ \phi(2n^2+3n+1)=(2n+1,0) $$ b) Transition $x$-axis to $y$-axis $$ \phi(2n^2+3n+1+k)=(2n+1-k,k)\ ;\ k=0\ldots 2n+1 $$ c) Visits to $y$-axis $$ \phi(2n^2+5n+2)=(0,2n+1)\ ;\ \phi(2n^2+5n+3)=(0,2n+2) $$ d) Transition $y$-axis to $x$-axis $$ \phi(2n^2+5n+3+k)=(k,2n+2-k)\ ;\ k=0\ldots 2n+2 $$ and again because your reach the $x$-axis at rank $$ 2n^2+5n+3+2n+2=2(n+1)^2+3(n+1) $$ and return to (a) section.

Now, giving a rank $N$, to know $\phi(N)$ amounts to position $N$ w.r.t. the following sectors $$ 2n^2+3n<2n^2+3n+1<\cdots <2n^2+5n+2<2n^2+5n+3<\cdots <2(n+1)^2+3(n+1) $$ The positioning can be achieved solving $2n^2+3n-N=0$ and taking the integer part, here $$ n=\lfloor\frac{-3+\sqrt{9+8N}}{4}\rfloor\ . $$

Late edit Above is just to show you in detail where the ideas came from. If you have to compactly answer to the ranking question ($B$), you can, for instance, use the piecewise description of Milo (with $T_n=\frac{n(n+1)}{2}$). Having to compute $g(N)$, you first compute $$ n=\lfloor\frac{-1+\sqrt{1+9N}}{2}\rfloor\ . $$ you then get $k=N-T_n$ and can apply the dichotomy. If you are chasing the single formula you can even have one with "commutators".

Late late edit Here is, just for the fun, my version of commutators ; first use Iverson_bracket to write $g$ and then (I use here [[??]] in order to differentiate it from maths) convert Iverson brackets as follows $$ [[k\mbox{ is odd}]]=k-2\lfloor\frac{k}{2}\rfloor\ ;\ [[k\mbox{ is even}]]=1-k+2\lfloor\frac{k}{2}\rfloor\ . $$

$\endgroup$
  • $\begingroup$ I think I understand what you are doing here. Can you clarify a bit what you did near the end? And what exactly do you mean by the term rank? $\endgroup$ – Luke Collins Nov 27 '17 at 20:28
  • $\begingroup$ I elaborated a bit the concept of "ranking". Do not hesitate to interact. $\endgroup$ – Duchamp Gérard H. E. Nov 28 '17 at 5:30
  • $\begingroup$ @LukeCollins [I think I understand what you are doing here.]--->I wanted to show you in detail where the ideas came from. $\endgroup$ – Duchamp Gérard H. E. Nov 28 '17 at 7:24
  • $\begingroup$ @LukeCollins If you find my contribution helpful do not hesitate to vote. $\endgroup$ – Duchamp Gérard H. E. Nov 30 '17 at 4:23

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.