Cómo expresar "b es una potencia de 10" - Teoría tipográfica de números en Gödel Escher Bach

Question

El libro Gödel, Escher, Bach (GEB) de Douglas R. Hofstadter introduce un sistema formal denominado "Teoría Tipográfica de Números" (TNT). Esencialmente lógica de predicados de primer orden sobre el universo de los números naturales, con suma y multiplicación pero sin exponenciación. Los números se codifican utilizando el cero y el función sucesora $S$ .

En un ejercicio, explícitamente descrito como difícil, se pide formalizar la condición de que un número dado es una potencia de $10$ . Mi solución parece demasiado simple, y el GEB ha sido mi primera introducción al TNT, por lo que dudo que haya acertado con este problema. Por supuesto, debido a mi posición en la curva de aprendizaje, creo que el efecto Dunning-Kruger me limita a la hora de darme cuenta de mi propio fallo en esta solución. ¿Puede alguien decirme cómo es que esto está mal, o si de alguna manera es milagrosamente correcto?

$d$ es una potencia de $10$ si:

$$\exists! a: \exists! b: \exists c: \exists d: (((a = SS0) \land (b = SSSSS0)) \land (((a \cdot c) \cdot (b \cdot c)) = d)) \\ $$

Answer 1

cómo se expresa "b es una potencia de 10".

Dado que Rory ya ha abordado los problemas que plantea tu planteamiento, yo abordaré la cuestión de encontrar una solución diferente. En mi primer intento de hacerlo, he cometido un error, así que reescribo completamente mi respuesta. Ahora está inspirada en esta entrada por Anders Kaseorg, aunque la redacción es mía.

Todos los poderes a la vez

El principal problema es que no se puede escribir simplemente una definición recursiva. No puedes hacer que la fórmula se construya sobre sí misma. Una forma de resolverlo es hablar de todas las potencias de diez, al menos hasta el número dado, simultáneamente. A falta de conjuntos, tenemos que representar esto como un solo número. Todavía no podemos hacer el desplazamiento de dígitos en base 10, pero puede expresar potencias de diez en alguna base prima.

Un poco de nomenclatura por adelantado. Utilizaré $a$ para denotar la variable libre, la entrada, la cosa para la que queremos comprobar el predicado. $p$ será un número primo utilizado como base numérica, $t$ la base- $p$ número utilizado para codificar nuestras potencias de diez. $d$ será a menudo un dígito o elemento de ese conjunto de potencias de diez.

Para facilitar la comprensión, definiré las abreviaturas de las unidades semánticas. Pero ten en cuenta que cada una de esas abreviaturas sólo se basa en las que he definido antes, no en sí misma ni en las que vengan después. Por lo tanto, se podrían ampliar las abreviaturas nivel por nivel para volver a la notación estricta de TNT. Lo haré hacia el final de este post.

Paso a paso

esPrimo(p)

¿Cuándo un número es primo? Si él mismo no es menor que $2$ y no el producto de dos enteros mayores o iguales que $2$ . (Escribo $\neg$ en lugar de $\sim$ para la negación).

$$\text{isPrime}(p):=\;\;\langle\exists i:p=\textsf{SS}i\;\wedge\;\neg\;\exists j:\exists k:p=\textsf{SS}j\cdot\textsf{SS}k\rangle$$

primePower(p, q)

Para escribir operaciones con dígitos en una base $p$ número, tendremos que hablar de potencias de $p$ . ¿Cuándo se $q$ un poder de $p$ ? Si $q$ es distinto de cero y no contiene otros factores primos. (Prefiero escribir implicación como $\rightarrow$ no $\supset$ .)

\begin{align*} \text{primePower}(p,q):=\;\;&\Bigl\langle\neg\;q=\textsf 0\;\wedge\\&\forall g:\forall h:\big\langle q=\textsf{SS}g\cdot\textsf{SS}h\;\rightarrow\;\langle\neg\;\text{isPrime}(\textsf{SS}g)\;\vee\;\textsf{SS}g=p\rangle\big\rangle\Bigr\rangle \end{align*}

digitOf(p, t, d)

¿Cuándo es $d$ un dígito de una base- $p$ número $t$ ? Si $t=(e\cdot p+d)\cdot p^k+f$ para algunos $e,f,k$ con $d<p$ y $f<p^k$ .

\begin{align*} \text{digitOf}(p,t,d):=\;\;&\exists e:\exists f:\exists q:\big\langle \langle\exists c:p=d+\textsf{S}c\;\wedge\;\exists c:q=f+\textsf{S}c\rangle\;\wedge\\&\langle t=(e\cdot p+d)\cdot q+f\;\wedge\;\text{primePower}(p,q)\rangle\big\rangle\end{align*}

contiene(p, t, d)

Teniendo base $p$ Los números representan conjuntos es una idea hermosa, pero hay que tener cuidado con los ceros: cada contiene un número infinito de ceros a la izquierda. Pero no queremos ceros en nuestro conjunto de potencias de diez, así que podemos excluir los ceros.

$$\text{contains}(p, t, d):=\;\;\langle\neg\;d=0\;\wedge\;\text{digitOf}(p, t, d)\rangle$$

potenciasDeDiez(p, t)

Ahora podemos empezar a hablar de potencias de diez. ¿Cuándo una base $p$ número $t$ describir un número suficiente de potencias de diez? Originalmente empezaría diciendo que debe contener $1=10^0$ y para cada $d$ debe contener $10\cdot d$ y ningún otro número excepto éstos. Pero al final cuantificaremos este número como $\exists t$ Así que todos los requisitos sobre lo que debe contener puede evitarse. Lo único importante es anotar lo que debe no contener, es decir, expresar que no debe contener más que potencias de diez. Por cada número que contenga, debe haber una potencia menor de diez que también contenga, con el uno como excepción obvia.

\begin{align*} \text{powersOfTen}(p,t):=\;\;&\forall d:\Big\langle\text{contains}(p,t,d)\;\rightarrow\;\big\langle d=\textsf{S0}\;\vee\\&\exists b:\langle d=\textsf{SSSSSSSSSS0}\cdot b\;\wedge\;\text{contains}(p,t,b)\rangle\big\rangle\Big\rangle \end{align*}

potenciaDeDiez(a)

¿Cuándo un número es una potencia de diez? Si está contenido en el número de potencias de diez, para algún primo adecuado $p$ .

\begin{align*} \text{powerOfTen}(a):=\;\;&\exists p:\bigl\langle\text{isPrime}(p)\;\wedge\\& \exists t:\langle\text{powersOfTen}(p,t)\;\wedge\;\text{contains}(p,t,a)\rangle\bigr\rangle\end{align*}

No requerimos $p>a$ pero la cuantificación existencial de $t$ se encarga de eso. Del mismo modo, en ningún momento hicimos ninguna declaración sobre el orden de los dígitos dentro de $t$ . Cualquier orden es válido, y las repeticiones también están bien.

La formulación no está optimizada para ser breve. En su lugar, he intentado que cada definición capte una idea matemática de la forma más precisa posible, aunque eso signifique abarcar casos extremos que son irrelevantes para la aplicación en cuestión. Por ejemplo, si en la $\text{digitOf}$ formulación que había escrito $\textsf Sq$ para $p^k$ en lugar de $q$ entonces el caso de $q=0$ en $\text{primePower}$ sería irrelevante.

Todos juntos

Si lo unes todo, obtienes la siguiente expresión bastante ilegible:

$$ \exists p:\langle \\ \langle\exists i:p=\textsf{SS}i\;\wedge\;\neg\;\exists j:\exists k:p=\textsf{SS}j\cdot\textsf{SS}k\rangle \\ \;\wedge\;\exists t:\langle \forall d:\langle \\ \langle\neg\;d=0\;\wedge\; \\ \exists e:\exists f:\exists q:\langle\langle\exists c:p=d+\textsf Sc\;\wedge\;\exists c:q=f+\textsf Sc\rangle\;\wedge\;\langle t=(e\cdot p+d)\cdot q+f\;\wedge\; \\ \langle\neg\;q=\textsf 0\;\wedge\;\forall g:\forall h:\langle q=\textsf{SS}g\cdot\textsf{SS}h\;\rightarrow\;\langle\neg\; \\ \langle\exists i:\textsf{SS}g=\textsf{SS}i\;\wedge\;\neg\;\exists j:\exists k:\textsf{SS}g=\textsf{SS}j\cdot\textsf{SS}k\rangle \\ \;\vee\;\textsf{SS}g=p\rangle\rangle\rangle \rangle\rangle \rangle \\ \;\rightarrow\;\langle d=\textsf{S0}\;\vee\;\exists b:\langle d=\textsf{SSSSSSSSSS0}\cdot b\;\wedge\; \\ \langle\neg\;b=0\;\wedge\; \\ \exists e:\exists f:\exists q:\langle\langle\exists c:p=b+\textsf Sc\;\wedge\;\exists c:q=f+\textsf Sc\rangle\;\wedge\;\langle t=(e\cdot p+b)\cdot q+f\;\wedge\; \\ \langle\neg\;q=\textsf 0\;\wedge\;\forall g:\forall h:\langle q=\textsf{SS}g\cdot\textsf{SS}h\;\rightarrow\;\langle\neg\; \\ \langle\exists i:\textsf{SS}g=\textsf{SS}i\;\wedge\;\neg\;\exists j:\exists k:\textsf{SS}g=\textsf{SS}j\cdot\textsf{SS}k\rangle \\ \;\vee\;\textsf{SS}g=p\rangle\rangle\rangle \rangle\rangle \rangle \rangle\rangle\rangle \\ \;\wedge\; \langle\neg\;a=0\;\wedge\; \\ \exists e:\exists f:\exists q:\langle\langle\exists c:p=a+\textsf Sc\;\wedge\;\exists c:q=f+\textsf Sc\rangle\;\wedge\;\langle t=(e\cdot p+a)\cdot q+f\;\wedge\; \\ \langle\neg\;q=\textsf 0\;\wedge\;\forall g:\forall h:\langle q=\textsf{SS}g\cdot\textsf{SS}h\;\rightarrow\;\langle\neg\; \\ \langle\exists i:\textsf{SS}g=\textsf{SS}i\;\wedge\;\neg\;\exists j:\exists k:\textsf{SS}g=\textsf{SS}j\cdot\textsf{SS}k\rangle \\ \;\vee\;\textsf{SS}g=p\rangle\rangle\rangle \rangle\rangle \rangle \rangle\rangle $$

Si se fija bien, podrá reconocer tres bloques similares, correspondientes a los tres $\text{contains}$ instancias. Eso podría ayudarte a orientarte.

Alternativas

Lo anterior es un posible formulación, pero hay muchas otras. El post de Anders Kaseorg formulado $\text{primePower}$ no en términos de "todo factor primo debe ser igual a $p$ "sino que "cada factor debe ser divisible por $p$ ". En la forma ampliada esto es ciertamente más corto, pero como mi formulación es la que primero se me ocurrió, la mantendré tal cual.

En lugar de escribir $t$ como configure de todas las potencias de diez, también se podría hacer una secuencia de tales poderes. En ese caso dirías que cada par de dígitos subsiguientes tiene una potencia de diez entre ellos. Pero como seguimos necesitando el $\text{contains}$ para comprobar si $a$ está contenido, trabajar exclusivamente en platós simplifica las cosas.

¿Cómo se define la exponenciación en la aritmética de Peano? es una variante más general de esta cuestión. Las respuestas allí no utilizan base- $p$ números, sino los Teorema chino del resto para expresar una secuencia en un solo número. La gran ventaja es que el índice de la secuencia es sólo un factor de algún producto en las fórmulas que lo acompañan. En mi enfoque, es el exponente del primo, así que necesito predicados extra para formular eso. Así que la indexación es más fácil con el teorema chino del resto. Por otro lado, ver cómo se almacenan los datos en el número es más difícil. Incluso si racionalmente estás perfectamente convencido de que el teorema funciona como se anuncia, sigo pensando que es más difícil establecer una especie de comprensión visceral de cómo el único número (o más bien par de números, en mi caso $t$ y $p$ ) representa una secuencia. Esa es la razón por la que prefiero la base $p$ cifras. Sin embargo, su enfoque es más adecuado si no sólo desea establecer que $a$ es una potencia de diez, sino también caracterizar el exponente, como comprobar si $a=10^b$ para $a,b$ dadas como variables libres. El uso de una secuencia con una indexación sencilla resulta rentable en esta configuración.

Otra herramienta común para representar secuencias como números individuales es mediante el uso de un función de emparejamiento para denotar la secuencia. El primer elemento del par sería un elemento de la lista, el segundo el resto de la lista excepto ese primer elemento. Pero se trata de una estructura de datos recursiva, y ya hemos tenido bastantes problemas para expresar los conceptos recursivos más simples, así que yo no seguiría ese enfoque aquí. Lo mismo ocurre con la idea de representar un conjunto escribiendo tantos números primos distintos como elementos tenga el conjunto, y utilizando los elementos del conjunto como exponentes de los números primos. Para descifrar esto, no sólo hay que reconocer las potencias de los números primos, sino también identificar el exponente. Una vez que puedes expresar estas cosas, la respuesta a este problema es una aplicación bastante trivial.

Answer 2

Las abreviaturas deben deletrearse, ya que no son universales. Supongo que te refieres a la "Teoría Tipográfica de los Números" del libro "Gödel, Escher, Bach" de Douglas R. Hofstadter.

Su afirmación TNT es errónea. En primer lugar, usted quiere que su fórmula sea sobre $d$ pero tú ataste $d$ en un cuantificador de existencia. Por lo tanto, elimine el $\exists d:$ para obtener una declaración sobre $d$ .

Además, su fórmula sólo dice que $a=2$ , $b=5$ , $c$ es un número natural, y la ecuación básicamente dice $d=10c^2$ .

También trabajé un poco en este problema cuando leí (la primera mitad de) Gödel, Escher, Bach, y la respuesta será mucho más complicada de lo que has expuesto aquí. Tuve algunas ideas pero nunca terminé la respuesta: demasiado tiempo implicado. Ni siquiera llegué a la segunda mitad del libro.

AÑADIDO

Si no recuerdo mal, pude obtener una afirmación para "b es una potencia de 2" diciendo algo como "2 es el único divisor primo de b", y de forma similar para "b es una potencia de 5". Entonces podría decir "b es una potencia de 2 por una potencia de 5", pero nunca encontré la forma de asegurar que los exponentes de 2 y de 5 fueran iguales.

Answer 3

Paso 1: Podemos codificar cualquier secuencia finita en unos pocos números

Cualquier secuencia finita $a_0,a_2,\ldots,a_n$ de números (naturales) puede codificarse como un predicado $$\begin{align}P(x,k,\alpha,\beta,n)&\iff x\text{ is the $k$th term of thes given equence $a_0,\ldots,a_n$}\\&\iff k\le n\land x=\alpha\bmod{((k+1)\beta+1)}\\&\iff\exists t\colon n=k+t\land \exists t\colon \alpha\cdot x+t\cdot S(\beta\cdot Sk)\land \exists t\colon x+t=\beta\cdot Sk\end{align}$$ donde la existencia de $\alpha,\beta$ está garantizado por el Teorema Chino del Resto. Todo lo que necesitamos es que los números $\beta+1,2\beta+1,\ldots,(n+1)\beta+1$ son coprimos y $>a_k$ que puede conseguirse dejando que $\beta$ un múltiplo de $(n+1)!$ .

Exemple : $\alpha=1981297324554360860$ , $\beta=2016$ puede utilizarse para codificar (cualquier seqmento inicial de) la secuencia $1,10,100,1000,10000,7101,6944,15819,\ldots$ especialmente, los primeros términos coinciden con las primeras potencias de diez.

Paso 2: Podemos hablar de secuencias recursivas utilizando secuencias finitas

Supongamos que definimos una secuencia por su término inicial $a_0$ y una recursión $a_n=f(a_{n-1})$ (donde podemos expresar $f$ en TNT). Entonces podemos codificar la propiedad $x$ es igual a $a_n$ como $$\begin{align}R(x,n)\iff\exists \alpha\exists\beta\colon &\quad P(a_0,0,\alpha,\beta,n)\\&\land P(x,n,\alpha,\beta,n)\\&\land\forall k\forall y\colon\bigl(( k<n\land P(y,k,\alpha,\beta,n))\to P(f(y),Sk,\alpha,\beta,n)\bigr)\\ \end{align}$$

Exemple : Si $f(y)=10\cdot y$ y $a_0=1$ entonces los números $\alpha,\beta$ del ejemplo anterior hacen que la afirmación $R(10000,4)$ cierto.

Paso 3: Podemos codificar " $b$ es una potencia de $10$ "

Esto es sólo $$\exists n\colon R(b,n) $$ donde $R$ se define como en el paso 2 utilizando $f(y)=10y$ y $a_0=1$ .

Ejercicio: Reconoce los métodos de los dos pasos que acabamos de describir a continuación:

n:a:c:d:e: p:q:r:s:t: f:g: S(a-SSc)=(b+(d-S(Sc-Sn)) (b+e)=(Sc-Sn) ¬S(p+r)=n ¬S(a-SSc)=(q+(s-S(Sc-Sp)) ¬(q+t)=(Sc-Sp) S(a-SSc)=((SSSSSSSS0-q)+(f-S(Sc-SSp))) ((SSSSSSSS0-q)+g)=(Sc-SSp)