Probando el Cantor Función de sincronización Bijective

Question

¿Cómo podría usted probar el Cantor Función de sincronización bijective? Sólo sé cómo probar un bijection mostrando (1) Si $f(x) = f(y)$, $x=y$ y (2) existe una $x$ tal que $f(x) = y$

¿Cómo podría usted demostrar que para una función como la de Cantor función de sincronización?

Answer 1

Se puede hacer exactamente como lo sugieren: mediante la demostración de (1) que si $\pi(m,n)=\pi(p,q)$,$\langle m,n\rangle=\langle p,q\rangle$, y (2) que para cada una de las $m\in\mathbb{N}$ hay un par de $\langle p,q\rangle\in\mathbb{N}\times\mathbb{N}$ tal que $\pi(p,q)=m$ donde $$\pi:\mathbb{N}\times\mathbb{N}\to\mathbb{N}:\langle m,n\rangle\mapsto \frac12(m+n)(m+n+1)+n$$ (donde yo estoy usando la versión de la vinculación de la función dada en el artículo de la Wikipedia que usted cita).

(1) Supongamos que $\pi(m,n)=\pi(p,q)$, es decir, que $$\frac12(m+n)(m+n+1)+n=\frac12(p+q)(p+q+1)+q\;.\tag{1}$$ The first step is to show that $m+n=p+q$, so suppose not. We may as well assume that $m+n<p+q$. For convenience let $a=m+n$ and $d=(p+q)-un$, so that $(1)$ becomes $$\frac{a(a+1)}2+n=\frac{(a+d)(a+d+1)}2+q\;.$$

Entonces $$\begin{align*} n-q&=\frac{(a+d)(a+d+1)}2-\frac{a(a+1)}2\\ &=ad+\frac{d(d+1)}2\\ &\ge a+1\;, \end{align*}$$

por lo $n>a+q\ge a=m+n\ge n$, lo cual es absurdo. Por lo tanto, $m+n=p+q$, e $(1)$ implica inmediatamente que $n=q$ y por lo tanto también es $m=p$. Este establece que $\pi$ es inyectiva.

(2) Este es exactamente el cálculo dado aquí. El artículo no es demostrar (1) de forma explícita, porque en el proceso de forma exclusiva la reconstrucción de $\langle x,y\rangle$ $z=\pi(x,y)$ implícitamente muestra (1).

Answer 2

Reclamo: $f: (m,n) \mapsto n + \frac12 (m+n)(m+n+1)$ es bijective.

Prueba: Es suficiente para demostrar que $f$ es invertible, porque si hay una función inversa $g$ luego de inyectividad y surjectivity tanto sigue directamente de $f \circ g = \mathrm{id}$.

Para invertir $f$ presentamos las siguientes variables: $$ z = f(m,n) = n + \frac12 (m+n)(m+n+1)$$

$$ w = m + n$$

de modo que $z = n + \frac{w^2 + w}{2}$. Siguiente se introduce también $$ t = \frac{w^2 + w}{2}$$

No está claro para mí cómo nos dimos cuenta de lo que vamos a introducir. Pero después se introduce $t$ $w$ es claro que $n = z -t$ $m = w-n$ donde $z$ es conocido, así que si podemos escribir $w$ $t$ como funciones de $z$ hemos terminado.

Nos observador que de $t = \frac{w^2 + w}{2}$ obtenemos $w^2 + w - 2t = 0$ a partir de la cual obtenemos $w = \frac{-1 \pm \sqrt{1 + 8t}}{2} $ y desde $w \in \mathbb N$ es evidente que sólo el $$w = \frac{-1 + \sqrt{1 + 8t}}{2}$$ es una solución. Ahora tenemos $w$ como una función de la $t$. A partir de esto podemos llegar a nuestra meta de escribir $w$ como una función de la $z$. Para este fin, se introduce $h(t) = w = \frac{-1 + \sqrt{1 + 8t}}{2}$ y observar que $h$ es estrictamente creciente en a$\mathbb R_{\geq 0}$$h^{-1}(\omega) = t = \frac{w^2 + w}{2}$.

También, $t \leq t + n < t + w + 1$ que es el mismo que $\frac{w^2 + w}{2} \leq z < \frac{(w+1)^2 + (w+1)}{2}$. Que es el mismo que $$ h^{-1}(w) \leq z < h^{-1}(w+1)$$

De la que podemos obtener $$ w \leq h(z) < w+1$$

que es el mismo que $$ w \leq \frac{-1 + \sqrt{1 + 8z}}{2} < w + 1$$ Ahora estamos casi allí. Sabemos que $w \in \mathbb N$ por lo tanto $$ w = \left \lfloor \frac{-1 + \sqrt{1 + 8z}}{2} \right \rfloor$$

Ahora tenemos $w$ como una función de la $z$ que es lo que queríamos. De esto podemos obtener $n$ $m$ (como funciones de $z$).