# Cantor's Diagonalization Process(CDP) and North-east to South-west Diagonalization Process(NSDP)

While looking at the function $$f:\mathbb{N}\rightarrow \mathbb{N} \times \mathbb{N}$$, I accidentally made an inversion in my labelling for $$f(x)$$

What I mean is, we go with a zig-zag path in CDP(either $$f(2)=(1,2)$$ or $$f(2)=(2,1)$$, I am going with the former), but while writing the value for each of the members of $$\mathbb{N}$$, I went in the north-east(NE) to south-west(SW) manner.

Elaboration:

$$(1,1),\ (1,2),\ (1,3),\ ...\\ (2,1),\ (2,2),\ (2,3),\ ... \\ (3,1),\ (3,2),\ (3,3),\ ... \\ .\\ .\\ .\\$$ $$\big($$Also, regardless of CDP or NSDP, we can observe below, that the last element in each row $$n(n\geq2)$$ is of the form $${n+1 \choose 2} \ \big( 3={2+1 \choose 2}$$, $$6={3+1 \choose 2}$$, $$10={4+1 \choose 2}\big)\big)$$

In CDP we have:

$$f(1)=(1,1)$$

$$f(2)=(1,2), \ f(3)=(2,1)$$ ($$\leftarrow$$ NE to SW)

$$f(4)=(3,1), \ f(5)=(2,2),\ f(6)=(1,3)$$ ($$\rightarrow$$ SW to NE)

$$f(7)=(1,4),\ f(8)=(2,3),\ f(9)=(3,2)\ f(10)=(4,1)$$ ($$\leftarrow$$ NE to SW)

$$f(11)=(5,1),\ f(12)=(4,2),\ f(13)=(3,3), \ f(14)=(2,4),\ f(15)=(1,5)$$ ($$\rightarrow$$ SW to NE)

...

But, I did:

$$f(1)=(1,1)$$

$$f(2)=(1,2), \ f(3)=(2,1)$$ ($$\leftarrow$$ NE to SW)

$$f(4)=(1,3), \ f(5)=(2,2),\ f(6)=(3,1)$$ ($$\leftarrow$$ NE to SW)

$$f(7)=(1,4),\ f(8)=(2,3),\ f(9)=(3,2)\ f(10)=(4,1)$$ ($$\leftarrow$$ NE to SW)

$$f(11)=(1,5),\ f(12)=(2,4),\ f(13)=(3,3), \ f(14)=(4,2),\ f(15)=(5,1)$$ ($$\leftarrow$$ NE to SW)

...

Now, in doing so I saw a pattern: Take the first column. Let's label the set of the domains' elements in the first column.

$$\begin{array}\{X_1&:=\{1,2,4,7,11,16,22,29,37,...\} \\ &=\{x_1,x_2,x_3,x_4,x_5,x_6,x_7,x_8,x_9,...\}\\ \end{array}$$

and for the range:

$$\begin{array}\{Y_1&:=\{(1,1),(1,2),(1,3),(1,4),(1,5),(1,6),(1,7),(1,8),(1,9),...\} \\ &=\{(1,y_1),(1,y_2),(1,y_3,(1,y_4),(1,y_5),(1,y_6),(1,y_7),(1,y_8),(1,y_9),...\}\\ \end{array}$$ We can see that the first co-ordinate is constant, and the second one increases at a linear pace.

Moreover, $$x_i+y_i=x_{i+1}$$ Also, if we observe the $$x_r's$$, $$x_r=\frac{(r-1)(r)}{2}+1, \ \forall r \in \mathbb{N}$$

In case of the second column:

$$\begin{array}\{X_2&:=\{3,5,8,12,17,23,30,38,47,...\} \\ &=\{x_1,x_2,x_3,x_4,x_5,x_6,x_7,x_8,x_9,...\}\\ \end{array}$$

$$\begin{array}\{Y_2&:=\{(2,1),(2,2),(2,3),(2,4),(2,5),(2,6),(2,7),(2,8),(2,9),...\} \\ &=\{(2,y_1),(2,y_2),(2,y_3,(2,y_4),(2,y_5),(2,y_6),(2,y_7),(2,y_8),(2,y_9),...\}\\ \end{array}$$

Observing the $$x_s's$$, $$x_s=\frac{(s)(s+1)}{2}+2, \ \forall s \in \mathbb{N}$$

In case of the third column:

$$\begin{array}\{X_3&:=\{6,9,13,18,24,31,39,48,58,...\} \\ &=\{x_1,x_2,x_3,x_4,x_5,x_6,x_7,x_8,x_9,...\}\\ \end{array}$$

$$\begin{array}\{Y_3&:=\{(3,1),(3,2),(3,3),(3,4),(3,5),(3,6),(3,7),(3,8),(3,9),...\} \\ &=\{(3,y_1),(3,y_2),(3,y_3,(3,y_4),(3,y_5),(3,y_6),(3,y_7),(3,y_8),(3,y_9),...\}\\ \end{array}$$

Observing the $$x_p's$$, $$x_p=\frac{(p+1)(p+2)}{2}+3, \ \forall p \in \mathbb{N}$$

By the first principle of mathematical induction, we have for the $$n^{th}$$ column: for sets $$X_n,Y_n$$:

$$\big(x_q=\frac{(q+(n-1))(q+(n-2))}{2}+n, \forall q \in \mathbb{N} \big)\forall n \in \mathbb{N}$$

Thus, in general, the function looks like $$f(x)=(\alpha,\beta)$$, where $$x=\frac{(\beta+(\alpha-1))(\beta+(\alpha-2))}{2}+\alpha$$.

Hence there is a dependence of at least two variables that we know of, on x.

Now, my question is:

(A) In NSDP, can I make a proper explicit form of the function?(I just know $$x$$ drives $$\alpha,\beta$$, but I am unable to arbitrarily locate the value, other than knowing the column type slection, which is good while dealing with one column at a time, but in a general manner, I am not able to make the function's definition explicit.)

(B) In CDP, how do I proceed with the logic used in NSDP, or is there a better way out? (I know that the last element of each row $$n$$ is of the form $${n+1 \choose 2}$$ and the sum of co-ordinates of each elements is equal in case of each row(eg: 1+3=2+2=3+1).)

• I think the inverse triangular number function will be useful. If $T = \mathrm{Tri}(n) := \sum_{i=1}^n{i} = \frac{n(n+1)}{2} = \frac{1}{2} n^2 + \frac{1}{2} n$, then $\mathrm{Tri}^{-1}(T) = \sqrt{2T + \frac{1}{4}} - \frac{1}{2}$. It can be seen that $\alpha(x) + \beta(x) = \left\lceil \mathrm{Tri}^{-1}(x) \right\rceil + 1$. This should allow you to begin finding a closed form. Jan 30 at 11:53

(A) Proceeding from my above comment:

Let us define the triangular number function as

$$\mathrm{Tri}(n) := \sum_{i=1}^n{i}=\frac{n(n+1)}{2}$$

The inverse of this function is

$$\mathrm{Tri}^{-1}(x) = \sqrt{2x+\frac{1}{4}}-\frac{1}{2}$$

We can observe that $$\alpha(x) + \beta(x) = \left\lceil \mathrm{Tri}^{-1}(x) \right\rceil + 1$$.

From this, we can further proceed to the explicit form of the functions:

$$\alpha(x) = \left\lceil \mathrm{Tri}^{-1}(x) \right\rceil - \mathrm{Tri}\left(\left\lceil \mathrm{Tri}^{-1}(x) \right\rceil\right) + x$$ $$\beta(x) = 1 + \mathrm{Tri}\left(\left\lceil \mathrm{Tri}^{-1}(x) \right\rceil\right) - x$$

(B) For the CDP, we can define

$$\alpha'(x) = \begin{cases}\alpha(x), &\text{if}\left\lceil \mathrm{Tri}^{-1}(x) \right\rceil \text{is even.} \\ \beta(x), &\text{if}\left\lceil \mathrm{Tri}^{-1}(x) \right\rceil \text{is odd.}\end{cases}$$

$$\beta'(x) = \begin{cases}\beta(x), &\text{if}\left\lceil \mathrm{Tri}^{-1}(x) \right\rceil \text{is even.} \\ \alpha(x), &\text{if}\left\lceil \mathrm{Tri}^{-1}(x) \right\rceil \text{is odd.}\end{cases}$$

• I understood the procedure you gave in comment, but can you explain taking ceiling function of $Tri^{-1}(x)$ and onwards. I am unable to understand this part. Jan 30 at 12:53
• @Apointinspace Essentially for $\alpha(x)$ we're counting from $1$ to $\left\lceil\mathrm{Tri}(x)\right\rceil$ while at the same time we count backwards from $\left\lceil\mathrm{Tri}(x)\right\rceil$ to $1$ for $\beta(x)$. $x - \mathrm{Tri}\left(\left\lceil \mathrm{Tri}^{-1}(x) \right\rceil\right)$ is just a "correction factor" so that our counting begins from $1$ or $\mathrm{Tri}^{-1}(x)$ as the case may be. My answer to part (B) then just switches the $\alpha$ and $\beta$ coordinates each diagonal to mimic the snaking nature of the CDP. Try it out! It may be inelegant, but it works. Jan 30 at 15:24
• I see the formation now. It makes perfect sense, so taking the ceiling value of the inverse triangular function of $x$, gives us the row number. And the correction function you introduced did accurately mark the values of $\alpha(x)$ and $\beta(x)$, and the alternate row flips done in case of CDP is elegant :) Thanks for this proof! Jan 30 at 16:03