Construction and properties of pairing functions

[13/77%]

Show

LaTeX

Show LaTeX

Problem 8.243 from Pólya G., Szegő G. "Problems and Theorems in Analysis" [PóSz98]More problems in Section 1 "Lattice Points in Two and Three Dimensions"

(1)(2)

The lattice points in the closed first quadrant are enumerable. I.e. there exist functions $f(x,y)$ defined for ordered pairs of non-negative integers $x,y$ that combine the following two properties:

(1)

The values assumed by $f(x,y)$ form the set of numbers $1,2,3,4,5,\ldots$ .

(2)

The function $f(x,y)$ takes different values at distinct points; i.e. if $x,y,x',y'$ are integers, $x\geq 0$ , $y\geq 0$ , $x'\geq 0$ , $y'\geq 0$ , $(x-x')^2+(y-y')^2>0$ , then $f(x,y)\neq f(x',y')$ .

There even exist rational entire functions $f(x,y)$ that enumerate the lattice points, i.e. that have the properties (1) (2). An example is the function

f(x,y) = \tfrac 12(x^2+2xy+y^2+3x+y+2) = \binom {x+y+1}{2}+x+1

and the function arising from it by interchanging $x$ and $y$ [the lattice points are counted successively on the line segments

x+y=0, \quad x+y=1, \quad x+y=2, \quad \ldots , \quad x\geq 0, \quad y\geq 0 .

Let $f(x,y)$ be a rational entire function of degree $m$

f(x,y) = \varphi _0(x,y)+\varphi _1(x,y)+\cdots +\varphi _m(x,y) ,

where $\varphi_\mu (x,y)$ denotes a rational entire homogeneous function of degree $\mu$ . If $f(x,y)$ enumerates the lattice points, then clearly $\varphi_m(x,y)\geq 0$ for $x\geq 0$ , $y\geq 0$ . If $\varphi_m(x,y)>0$ for $x\geq 0$ , $y\geq 0$ , $x+y>0$ and $f(x,y)$ enumerates the lattice points, then the degree of $f(x,y)$ is

m=2 .

[The number of lattice points contained inside the contour line $f(x,y)=\text{const.}$ is related to the enclosed area.]]

Problem 299 from Дехтярь М.И., Дудаков С.М., Карлов Б.Н., Карлов М.И. "Лекции по дискретной математике" [ДДК+21a]More problems in Chapter 19 "Partial Recursive Functions"

(a)(b)(c)

Suppose that all pairs $(x, y)$ of natural numbers are ordered by increasing sum $x+y$ , and pairs with the same sum are ordered by increasing coordinate $x$ . This order looks as follows:

\begin{aligned} (0,0),(0,1),(1,0),(0,2) & ,(1,1),(2,0), \ldots \\ & \ldots ,(0, x+y),(1, x+y-1), \ldots ,(x, y), \ldots ,(x+y, 0), \ldots \end{aligned}

Let $\langle x, y\rangle$ be the number of the pair $(x, y)$ in this order (we take the pair $(0,0)$ to have number 0). Then the function $\langle \cdot ,\cdot \rangle$ enumerates all pairs of natural numbers bijectively.

(a)

Prove that $\langle x, y\rangle =\frac{(x+y)(x+y+1)}{2}+x$ .

(b)

Find the inverse functions $\left\rangle_{1}\right.$ and $\left\rangle_{2}\right.$ such that the equalities $\langle \langle x, y\rangle \rangle_{1}=x,\langle \langle x, y\rangle \rangle_{2}=y$ hold, and hence $\left\langle \langle z\rangle_{1},\langle z\rangle_{2}\right\rangle =z$ .

(c)

Show that all these functions are general recursive.

Problem 300 from Дехтярь М.И., Дудаков С.М., Карлов Б.Н., Карлов М.И. "Лекции по дискретной математике" [ДДК+21a]More problems in Chapter 19 "Partial Recursive Functions"

Show that the function $F(x)$ from Problem 281 on page 381 is general recursive. Hint. First show that the function $g(x)=\langle F(x), F(x+1)\rangle$ is general recursive.

Problem 578 from Дехтярь М.И., Дудаков С.М., Карлов М.И., Карлов Б.Н. "Задачник по дискретной математике" [ДДК+21b]More problems in Chapter 23 "Partial Recursive Functions"

(a)(b)(c)

Suppose that all pairs $(x, y)$ of natural numbers are ordered by increasing sum $x+y$ , and pairs with the same sum — by increasing coordinate $x$ . This order looks like this:

\begin{aligned} & (0,0),(0,1),(1,0),(0,2),(1,1),(2,0), \ldots \\ & \quad \ldots ,(0, x+y),(1, x+y-1), \ldots ,(x, y), \ldots ,(x+y, 0), \ldots \end{aligned}

Let $\langle x, y\rangle$ be the number of the pair $(x, y)$ in this order (we take the pair (0,0) to have number 0). Then the function $\langle ,\rangle$ numbers all pairs of natural numbers in a one-to-one fashion.

(a)

Prove that $\langle x, y\rangle =\frac{(x+y)(x+y+1)}{2}+x$ .

(b)

Find the inverse functions $\langle \rangle_{1}$ and $\langle \rangle_{2}$ such that the equalities $\langle \langle x, y\rangle \rangle_{1}=x,\langle \langle x, y\rangle \rangle_{2}=y$ hold, and consequently $\langle \langle z\rangle_{1},\langle z\rangle_{2}\rangle =z$ .

(c)

Show that all these functions are general recursive.

Problem 580 from Дехтярь М.И., Дудаков С.М., Карлов М.И., Карлов Б.Н. "Задачник по дискретной математике" [ДДК+21b]More problems in Chapter 23 "Partial Recursive Functions"

Another function that allows one to number pairs of natural numbers looks like this: $c(x, y)=2^{x}(2 y+1)-1$ . Prove that $c$ itself and the inverse functions $c_{1}$ and $c_{2}$ to it (that is, $c_{1}(c(x, y))=x$ and $c_{2}(c(x, y))=y$ ) are general recursive. $\circledast$

Problem 581 from Дехтярь М.И., Дудаков С.М., Карлов М.И., Карлов Б.Н. "Задачник по дискретной математике" [ДДК+21b]More problems in Chapter 23 "Partial Recursive Functions"

(a)(b)(c)

Given a one-to-one numbering of pairs $k$ (for example, from Problems 578 or 580), one can inductively number ordered $n$ -tuples of arbitrary length:

\begin{aligned} K() & =0 \\ K\left(x_{1}, \ldots , x_{n}, x_{n+1}\right) & =k\left(k\left(k_{1}\left(K\left(x_{1}, \ldots , x_{n}\right)\right), x_{n+1}\right), n+1\right) \end{aligned}

(a)

Prove that the function $K$ is one-to-one.

(b)

Prove that the functions $K^{(n)}\left(x_{1}, \ldots , x_{n}\right)$ are general recursive.

(c)

Prove that the inverse function $K^{\prime }$ to $K$ is also general recursive: $\circledast$

K^{\prime }\left(K\left(x_{0}, \ldots , x_{n}\right), m\right)= \begin{cases} x_{m}, & \text{ for } m \leqslant n, \\ 0, & \text{ otherwise. }\end{cases}

Problem 582 from Дехтярь М.И., Дудаков С.М., Карлов М.И., Карлов Б.Н. "Задачник по дискретной математике" [ДДК+21b]More problems in Chapter 23 "Partial Recursive Functions"

(a)(b)(c)

Yet another way of coding finite sequences of natural numbers uses binary notation: the sequence $\left(n_{0}, n_{1}, \ldots , n_{k}\right)$ is coded by the binary number $1^{n_{k}} 01^{n_{k-1}} 0 \ldots 01^{n_{1}} 01^{n_{0}}$ (sequences that arise from one another by adding or removing trailing zeros are not distinguished).

(a)

Find the codes of the sequences $(2,3,0,1)$ and $(0,0,2,1,2)$ .

(b)

Determine of which sequences the numbers 169 and 19783 are codes.

(c)

Prove that the function $k(x, y)$ is general recursive. Here $x$ is the code of a sequence, $y$ is the index of an element, and the value of the function equals that element. $\circledast$

Problem 4.7.1 from Du D., Ko K. "Problem Solving in Automata, Languages, and Complexity" [DuKo01]More problems in Section 4.7 "Pairing Functions and Gödel Numberings"

(a)(b)

Show that the following functions are pairing functions.

(a)

$f_{1}(n, m)=2^{n}(2 m+1)-1$ .

(b)

$f_{2}(n, m)=\max (n, m)^{2}+m+g(m, n)$ , where $g(m, n)=n$ if $m \geq n$ , and $g(m, n)=0$ if $n>m$ .

Problem 4.7.3 from Du D., Ko K. "Problem Solving in Automata, Languages, and Complexity" [DuKo01]More problems in Section 4.7 "Pairing Functions and Gödel Numberings"

Let $n_{1}, n_{2}, \ldots , n_{k}$ are $k$ nonnegative integers. Prove that if $1 \leq i_{1}< i_{2}<\cdots <i_{\ell } \leq k$ , then $\left[n_{i_{1}}, n_{i_{2}}, \ldots , n_{i_{\ell }}\right] \leq \left[n_{1}, n_{2}, \ldots , n_{k}\right]$ .

Example 4.32 from Du D., Ko K. "Problem Solving in Automata, Languages, and Complexity" [DuKo01]More problems in Section 4.7 "Pairing Functions and Gödel Numberings"

Show that the function $\pi : \mathbf{N}^{2} \rightarrow \mathbf{N}$ , defined by

\pi (i, j)=\frac{(i+j)(i+j+1)}{2}+j,

is a pairing function.

Example 4.41 from Du D., Ko K. "Problem Solving in Automata, Languages, and Complexity" [DuKo01]More problems in Section 4.8 "Partial Recursive Functions"

(a)(b)

Suppose

(a)

$\Sigma =\left\{ 1,2, \ldots , 8,9, X\right\}$ with the ordering $1 \prec 2 \prec \cdots \prec 8 \prec 9 \prec X$ .

(b)

$\Sigma =\left\{ 0,1\right\}$ and $0 \prec 1$ .

Investigate $\iota (n)$ .

Problem III.1.15 from Lavrov I.A., Maksimova L.L. "Задачи по теории множеств, математической логике и теории алгоритмов" [LaMa02]More problems in Chapter III.1 "Partial Recursive Functions"

How can all partial recursive functions be obtained from one-place partial recursive functions and the functions $c^{n}(x_{1}, \ldots , x_{n})$ ?

Problem III.4.1 from Lavrov I.A., Maksimova L.L. "Задачи по теории множеств, математической логике и теории алгоритмов" [LaMa02]More problems in Chapter III.4 "Kleene and Post Numberings"

Prove that:

(a)

$[x,y]$ is a bijection between $\mathbb {N}^{2}$ and $\mathbb {N}$ ;

(b)

$[x_{1}, \ldots , x_{n}]$ is a bijection between $\mathbb {N}^{n}$ and $\mathbb {N}$ ;

(c)

$[[x]_{1}^{2}, [x]_{2}^{2}] = x$ , $[[x,y]]_{1}^{2} = x$ , $[[x,y]]_{2}^{2} = y$ ;

(d)

$[[x]_{1}^{n}, \ldots , [x]_{n}^{n}] = x$ , $[[x_{1}, \ldots , x_{n}]]_{i}^{n} = x_{i}$ ;

(e)

$[x_{1}, \ldots , x_{m}, x_{m+1}, \ldots , x_{n}] = [[x_{1}, \ldots , x_{m}], x_{m+1}, \ldots , x_{n}]$ ;

(f)

$c(x_{0}, c(x_{1}, x_{2})) = [c(x_{0}, x_{1}), x_{2}]$ .

References

[PóSz98] Pólya G., Szegő G. Problems and Theorems in Analysis. Springer, 1998.

[ДДК+21a] Дехтярь М.И., Дудаков С.М., Карлов Б.Н., Карлов М.И. Лекции по дискретной математике. 3-е изд., Тверской государственный университет, 2021.

[ДДК+21b] Дехтярь М.И., Дудаков С.М., Карлов М.И., Карлов Б.Н. Задачник по дискретной математике. 2-е изд., Тверской государственный университет, 2021.

[DuKo01] Du D., Ko K. Problem Solving in Automata, Languages, and Complexity. John Wiley & Sons, 2001.

[LaMa02] Lavrov I.A., Maksimova L.L. Задачи по теории множеств, математической логике и теории алгоритмов. 5-е изд., Физматлит, 2002.