5.6: La codificación es representable

Última actualización
Guardar como PDF

Page ID: 113559

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

Una parte básica de nuestro mecanismo de codificación será la capacidad de codificar secuencias finitas de números como un solo número. Un número\(c\) va a ser un código para una secuencia de números\(\left( k_1, k_2, \ldots, k_n \right)\) si y solo si

\[c = \langle k_1, k_2, \ldots, k_n \rangle = 2^{k_1+1} 3^{k_2+1} \cdots p_n^{k_n+1},\]

donde\(p_n\) está el número primo\(n\) th.

Chafia: Ten cuidado con la notación aquí. La secuencia de números está encerrada entre paréntesis, mientras que el\(\langle \cdot \rangle\) denota la función de codificación introducida de nuevo en el Capítulo 4.

Mostramos ahora que\(N\) es lo suficientemente fuerte como para reconocer los números de código. En otras palabras, queremos establecer

proposición 5.6.1.

La colección de números que son códigos para secuencias finitas es un conjunto representable.

prueba

Es fácil escribir una\(\Delta\) -definición para el conjunto de números de código:

\(Codenumber \left( c \right) =\)

\[Divides \left( SS0, c \right) \land \left( \forall z < c \right) \left( \forall y < z \right) \\ \left[ \left( Prime \left( z \right) \land Divides \left( z, c \right) \land Primepair \left( y, z \right) \right) \rightarrow Divides \left( y, c \right) \right].\]

Observe que\(Codenumber \left( c \right)\) es una fórmula con una variable libre,\(c\). Si lo miras detenidamente, todo lo que dice la fórmula es que\(c\) es divisible por\(2\) y si alguna prima se divide\(c\), también lo hacen todos los primos anteriores. Dado que la definición anterior es una\(\Delta\) -definición, Corolario 5.3.15 nos dice que el conjunto\(CODENUMBER\) es un conjunto representable.

Como\(CODENUMBER\) es representable y\(Codenumber\) es una\(\Delta\) -fórmula, ahora sabemos (por ejemplo) que

\[N \vdash Codenumber \left( \overline{18} \right)\]

\[N \vdash \neg Codenumber \left( \overline{45} \right).\]

Ahora, supongamos que queríamos tomar un número de código\(c\), y decodificarlo. Para encontrar el tercer elemento de la secuencia de números codificados por\(c\), necesitamos encontrar el exponente del tercer número primo. Así,\(N\) para poder probar declaraciones sobre la secuencia codificada por un número, se\(N\) necesitará poder reconocer la función que toma\(i\) y la asigna al número\(i^\text{th}\) primo,\(p_i\). Demostrar que esta función\(p\) es representable es nuestro próximo objetivo principal.

proposición 5.6.2.

La función\(p\) que enumera los primos es una función representable.

prueba

Comenzamos construyendo una medida de los primos. Un número\(a\) estará en el conjunto\(YARDSTICK\) si y sólo si\(a\) es de la forma\(2^1 3^2 5^3 \cdots p_i^i\) para algunos\(i\). Entonces los primeros elementos del conjunto son\(\{ 2, 18, 2250, 5402250, \ldots \}\).

\(Yardstick \left( a \right) =\)

\[Codenumber \left( a \right) \land \\ Divides \left( SS0, a \right) \land \neg Divides \left( SSSS0, a \right) \land \\ \left( \forall y < a \right) \left( \forall z < a \right) \left( \forall k < a \right) \\ \left[ \left( Divides \left( z, a \right) \land Primepair \left( y, z \right) \right) \rightarrow \\ \: \: \: \: \: \left( Divides \left( y^k, a \right) \leftrightarrow Divides \left( z^{Sk}, a \right) \right) \right].\]

Si desentrañamos esto, todo lo que tenemos es que 2 divide\(a\), 4 no divide\(a\), y si\(z\) es un número primo tal que\(z\) divide\(a\), entonces el poder de\(z\) que entra\(a\) es uno más que el poder del primo anterior que entra\(a\).

Ahora es relativamente fácil proporcionar una\(\Delta\) -definición de la función\(p\):

\(IthPrime \left( i, y \right) =\)

\[Prime \left( y \right) \land \\ \left( \exists a \leq \left( y^i \right)^i \right) \left[ Yardstick \left( a \right) \land Divides \left( y^1, a \right) \land \neg Divides \left( y^{Si}, a \right) \right].\]

¡Observe el límite complicado en el cuantificador! Aquí está el pensamiento detrás de ese límite: Si\(y\) es, de hecho, el\(i^\text{th}\) primo, entonces aquí hay un\(a \in YARDSTICK\) que muestra este hecho:\(a = 2^1, 3^2, \ldots y^i\). Pero entonces ciertamente\(a\) es menor o igual a\(y^i y^i, \cdots y^1 \left( i \: \text{terms} \right)\), y así\(a \leq \left( y^1 \right)^i\). Este límite es, por supuesto, mucho más grande que\(a\) (siendo la única excepción cuándo\(i = 1\) y\(y = 2\)), pero sólo nos interesará la existencia de límites, y casi no prestaremos atención a que los límites sean precisos en cualquier sentido.

Chafia: Hay un poco de tensión sobre la notación que hay que mencionar aquí. Supongamos que quisiéramos discutir el decimoséptimo número primo, que pasa a ser 59, y que se supone que\(y\) es igual a 59. La manera obvia de afirmar esto sería afirmar eso\(y = p_{17}\), pero tenderemos a usar la\(\mathcal{L}_{NT}\) fórmula explícita\(IthPrime \left( 17, y \right)\). Nuestra elección nos dará un gran incremento en la consistencia, ya que nuestras fórmulas se vuelven bastante más complicadas sobre el resto de este capítulo. Tendremos a escribir todas nuestras funciones de esta manera consistente, si no exactamente intuitiva.

Ahora podemos usar la función\(IthPrime\) para encontrar cada elemento codificado por un número:

\(IthElement \left( e, i, c \right) =\)

\[Codenumber \left( c \right) \land \left( \exists y < c \right) \left( IthPrime \left( i, y \right) \land \\ Divides \left( y^{Se}, c \right) \land \neg Divides \left( y^{SSe}, c \right) \right).\]

Así intuitivamente,\(IthElement \left( e, i, c \right)\) es cierto si\(c\) es un código y\(e\) es el número en posición\(i\) de la secuencia codificada por\(c\).

La longitud de la secuencia codificada por también\(c\) se encuentra fácilmente:

\(Length \left( c, l \right) =\)

\[Codenumber \left( c \right) \land \left( \exists y < c \right) \left[ \left( IthPrime \left( l, y \right) \land Divides \left( y, c \right) \\ \land \left( \forall z < c \right) \left[ PrimePair \left( y, z \right) \rightarrow \neg Divides \left( z, c \right) \right] \right) \right].\]

Todo lo que dice es que si el\(l^\text{th}\) primo divide\(c\) y el\(\left( l + 1 \right)^\text{st}\) primo no divide\(c\), entonces la longitud de la secuencia codificada por\(c\) es\(l\).

Ejercicios

Decidir si las siguientes afirmaciones son verdaderas o falsas como declaraciones sobre los números naturales. Justifica tus respuestas.
a)\(\left( 5, 13 \right) \in ITHPRIME\)
b) c)\(\left( 1200, 3 \right) \in LENGTH\)
\(IthElement \left( \bar{1}, \bar{2}, \overline{3630} \right)\) (¿Por qué hay esas líneas sobre los números?)