Autor Tema: Comentarios a "La Aritmética Recursiva Primitiva"

0 Usuarios y 1 Visitante están viendo este tema.

29 Julio, 2023, 05:38 pm
Respuesta #250

argentinator

  • Consultar la FIRMAPEDIA
  • Administrador
  • Mensajes: 7,797
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
Citar
Y, aunque esto pudiera definirse —que no se puede— ni aun así se podría definir un funtor ⊨α que distinga si una fórmula es verdadera o falsa, pues tampoco podríamos formalizar en ARP el "para toda valoración" que requiere la definición.

Primero que nada, aclaro que aún no he trabajado todo lo referido a la formalización de la sintaxis de ARP.

Así que comento esto sólo porque me llamó la atención.

¿Pueden formalizarse cosas como "la longitud de una fórmula", ó "el máximo índice de una variable en una fórmula"?

Luego de eso, se usaría un cuantificador acotado, y asunto resuelto: quedarían formalizadas las valoraciones.

29 Julio, 2023, 05:49 pm
Respuesta #251

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
¿Pueden formalizarse cosas como "la longitud de una fórmula", ó "el máximo índice de una variable en una fórmula"?

No sé exactamente hasta dónde has llegado en el hilo, pero hemos visto que cada número natural \( s \) se puede interpretar como una sucesión finita de números naturales, cuya longitud viene dada por el funtor \( \ell(s) \) (se trata simplemente de la formalización de lo que vimos en el hilo sobre ordinales menores que \( \epsilon_0 \)).

Las fórmulas no son más que números naturales que, vistos como sucesiones, sus términos son números de los que hemos tomado como signos del lenguaje, y cumplen la definición de fórmula. En particular, la longitud de una fórmula \( \alpha \) viene dada por el funtor \( \ell(\alpha) \), aplicable a números naturales cualesquiera, sean fórmulas o no.

Tampoco hay problema en formalizar el máximo índice de una variable en una fórmula.

Luego de eso, se usaría un cuantificador acotado, y asunto resuelto: quedarían formalizadas las valoraciones.

Si te refieres a formalizar el concepto de valoración, sí, no hay ningún problema, entendiendo que cada valoración está definida únicamente sobre un conjunto finito de variables, pero yo no hablaba de formalizar el concepto de valoración, sino formalizar "para toda valoración". El problema no es el "valoración" sino el "para toda". Hay infinitas valoraciones y no puedes meter un "para toda valoración" en medio de una definición, porque sería un cuantificador que no podrías acotar, y por ello no es expresable en el lenguaje de ARP.

De todos modos, en este mensaje hemos visto que hay problemas insoslayables para formalizar la semántica de ARP muy anteriores al problema que nos encontraríamos a la hora de definir el concepto de fórmula verdadera al no poder formalizar "para toda valoración".

30 Julio, 2023, 02:07 am
Respuesta #252

argentinator

  • Consultar la FIRMAPEDIA
  • Administrador
  • Mensajes: 7,797
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
¿Pueden formalizarse cosas como "la longitud de una fórmula", ó "el máximo índice de una variable en una fórmula"?

No sé exactamente hasta dónde has llegado en el hilo, pero hemos visto que cada número natural \( s \) se puede interpretar como una sucesión finita de números naturales, cuya longitud viene dada por el funtor \( \ell(s) \) (se trata simplemente de la formalización de lo que vimos en el hilo sobre ordinales menores que \( \epsilon_0 \)).

Las fórmulas no son más que números naturales que, vistos como sucesiones, sus términos son números de los que hemos tomado como signos del lenguaje, y cumplen la definición de fórmula. En particular, la longitud de una fórmula \( \alpha \) viene dada por el funtor \( \ell(\alpha) \), aplicable a números naturales cualesquiera, sean fórmulas o no.

Tampoco hay problema en formalizar el máximo índice de una variable en una fórmula.

Luego de eso, se usaría un cuantificador acotado, y asunto resuelto: quedarían formalizadas las valoraciones.

Si te refieres a formalizar el concepto de valoración, sí, no hay ningún problema, entendiendo que cada valoración está definida únicamente sobre un conjunto finito de variables, pero yo no hablaba de formalizar el concepto de valoración, sino formalizar "para toda valoración". El problema no es el "valoración" sino el "para toda". Hay infinitas valoraciones y no puedes meter un "para toda valoración" en medio de una definición, porque sería un cuantificador que no podrías acotar, y por ello no es expresable en el lenguaje de ARP.

De todos modos, en este mensaje hemos visto que hay problemas insoslayables para formalizar la semántica de ARP muy anteriores al problema que nos encontraríamos a la hora de definir el concepto de fórmula verdadera al no poder formalizar "para toda valoración".

Me confundí, dije una estupidez.
No tendría que haber posteado nada.
Por un momento creí que bastaba considerar valoraciones acotadas,
pero es que aún éstas son infinitas. mmmm.


31 Julio, 2023, 12:17 pm
Respuesta #253

Eparoh

  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 983
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Hola.

No he podido mirar el último mensaje con detenimiento (y no creo que pueda hacerlo hoy :-\), pero al leerlo un poco por encima y ver que se utilizaban los funtores que se definieron para numerar los funtores, me han surgido un par de dudas rápidas.

La primera es que aquí

Enumeración de funtores Es interesante observar que podemos enumerar los funtores de \( \mathcal L_{\rm arp} \). Para ello observamos que si \( f\in \mbox{Fun}({\color{blue}\mathcal L_{\rm arp}}) \), entonces \( {\color{blue}\kappa}({\color{blue}S} ,f) \) es otro funtor del mismo rango, pero mayor como número natural. Esto nos permite definir los funtores

\( \mbox{SF}(f)= \mu g\leq {\color{blue}\kappa}({\color{blue} S}, f)(g\in \mbox{Fun}({\color{blue}\mathcal L_{\rm arp}})\land f<g), \)

\( \mbox{SFR}(f)=\mu g\leq {\color{blue}\kappa}({\color{blue} S}, f)(g\in \mbox{Fun}({\color{blue}\mathcal L_{\rm arp}}) \land \mbox{rang}(g)=\mbox{rang}(f)\land f<g).
 \)

que calculan el menor funtor mayor que uno dado, y el menor funtor del mismo rango mayor que uno dado. A su vez:

\( f_0 = {\color{blue}S},\qquad f_{k+1} = \mbox{SF}(f_k), \)

\( f^n_0 =\mu g\leq p^n_1(g\in \mbox{Fun}({\color{blue}\mathcal L_{\rm arp}})\land \mbox{rang}(g)=n),\qquad f^n_{k+1} = \mbox{SFR}(f^n_k),
 \)

de modo que

\( f_k\in \mbox{Fun}({\color{blue}\mathcal L_{\rm arp}}),\qquad  f_k^n\in  \mbox{Fun}({\color{blue}\mathcal L_{\rm arp}})\land \mbox{rang}(f^n_k)=n,
 \)

\( k<k'\rightarrow f_k<f_{k'}\land f^n_k<f^n_{k'}, \)
(de donde se sigue por inducción que \( k\leq f_k \), \( k\leq f^n_k \)), y a su vez

\( f_k \) y \( f_k^n \) son, respectivamente, un funtor monádico y otro diádico de ARP, pero en la antepenúltima línea se establece que también son funtores de \( {\color{blue}\mathcal L_{\rm arp}} \) y, además, \( f_k^n \) es de rango \( n \). Aquí, lo que estamos queriendo decir es para cada \( k \) se tiene que \( f_k \) es un funtor de \( {\color{blue}\mathcal L_{\rm arp}} \), ¿no?

Aunque claro, como ese "para todo" no se puede expresar en ARP, es lo que me está confundiendo un poco. Lo que quiero decir es que, si llamamos \( h \) al funtor monádico de ARP \( f_k \) (es decir, \( h \) será una cadena de signos de ARP que empezará por \( \rho \) al haberse definido por recursión, etc.), entonces no se cumple que \( h \in \mbox{Fun}({\color{blue}\mathcal L_{\rm arp}}) \), ¿no?

Lo que (creo que) sabemos, con esta notación, es que los términos \( g(0), g(1), g(2), \cdots \) si pertenecen todos a \( \mbox{Fun}({\color{blue}\mathcal L_{\rm arp}}) \) y, además, como la \( k \) es un parámetro de \( g \) esto si se puede probar por inducción en ARP y esto es lo que me está haciendo un lío ahora mismo :(

Estoy seguro que es una tontería que no veo por haberme encabezonado en ver algo como no debería, pero llevo desde ayer por la tarde que leí el hilo por encima pensándolo y no lo veo.

Por otra parte, aquí:

Supongamos que existiera el funtor \( \phi \). Entonces podríamos definir un funtor monádico mediante

\( f(k) = \phi(f^1_k,\left<k\right>)+1. \)

Nota En el argumento anterior subyace el hecho siguiente: si enumeramos todas las funciones monádicas recursivas primitivas, \( f_0^1, f_1^1, f_2^1, \ldots \) la función dada por \( f(k) = f^1_k(k)+1 \) puede calcularla un ordenador, pero no es recursiva primitiva, pues entonces sería una de las \( f_k \), y entonces \( f_k(k) = f(k) = f_k(k)+1 \), lo cual es imposible.

En la primera cita con \( f^1_k \) haces referencia al funtor de los del mensaje anterior (bueno, realmente sería al funtor monádico definido por el término \( g(k,1) \) siendo \( g \equiv f^n_k \), ¿verdad?), sobre los que he planteado la duda anterior. Pero, con la notación del segundo caso te refieres a funciones recursivas primitivas, metamatemáticamente, no a funtores de ARP aunque sea la misma notación, ¿no?

Un saludo.

31 Julio, 2023, 03:24 pm
Respuesta #254

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
No he podido mirar el último mensaje con detenimiento (y no creo que pueda hacerlo hoy :-\),

No hay ninguna prisa.

Enumeración de funtores Es interesante observar que podemos enumerar los funtores de \( \mathcal L_{\rm arp} \). Para ello observamos que si \( f\in \mbox{Fun}({\color{blue}\mathcal L_{\rm arp}}) \), entonces \( {\color{blue}\kappa}({\color{blue}S} ,f) \) es otro funtor del mismo rango, pero mayor como número natural. Esto nos permite definir los funtores

\( \mbox{SF}(f)= \mu g\leq {\color{blue}\kappa}({\color{blue} S}, f)(g\in \mbox{Fun}({\color{blue}\mathcal L_{\rm arp}})\land f<g), \)

\( \mbox{SFR}(f)=\mu g\leq {\color{blue}\kappa}({\color{blue} S}, f)(g\in \mbox{Fun}({\color{blue}\mathcal L_{\rm arp}}) \land \mbox{rang}(g)=\mbox{rang}(f)\land f<g).
 \)

que calculan el menor funtor mayor que uno dado, y el menor funtor del mismo rango mayor que uno dado. A su vez:

\( f_0 = {\color{blue}S},\qquad f_{k+1} = \mbox{SF}(f_k), \)

\( f^n_0 =\mu g\leq p^n_1(g\in \mbox{Fun}({\color{blue}\mathcal L_{\rm arp}})\land \mbox{rang}(g)=n),\qquad f^n_{k+1} = \mbox{SFR}(f^n_k),
 \)

de modo que

\( f_k\in \mbox{Fun}({\color{blue}\mathcal L_{\rm arp}}),\qquad  f_k^n\in  \mbox{Fun}({\color{blue}\mathcal L_{\rm arp}})\land \mbox{rang}(f^n_k)=n,
 \)

\( k<k'\rightarrow f_k<f_{k'}\land f^n_k<f^n_{k'}, \)
(de donde se sigue por inducción que \( k\leq f_k \), \( k\leq f^n_k \)), y a su vez

\( f_k \) y \( f_k^n \) son, respectivamente, un funtor monádico y otro diádico de ARP, pero en la antepenúltima línea se establece que también son funtores de \( {\color{blue}\mathcal L_{\rm arp}} \) y, además, \( f_k^n \) es de rango \( n \). Aquí, lo que estamos queriendo decir es para cada \( k \) se tiene que \( f_k \) es un funtor de \( {\color{blue}\mathcal L_{\rm arp}} \), ¿no?

Con precisión:

\( f \) (no \( f_k \)) es un funtor monádico de \( \mathcal L_{\rm arp} \). Y en ARP se demuestra que \( f_k\in \mbox{Fun}({\color{blue}\mathcal L_{\rm arp}}) \). Esto es un teorema en el que, como en todo teorema, esa variable \( k \) libre se interpreta como que eso vale para todo \( k \). Pero no hay ningún "para todo". Simplemente, la fórmula

\( f_k\in \mbox{Fun}({\color{blue}\mathcal L_{\rm arp}}) \),

con su variable libre \( k \), es un teorema de ARP.

Aunque claro, como ese "para todo" no se puede expresar en ARP, es lo que me está confundiendo un poco.

No sé si es esto lo que te lía: esa \( k \) es una variable, no un numeral o algo así.

Lo que quiero decir es que, si llamamos \( h \) al funtor monádico de ARP \( f_k \)

Aquí algo no cuadra. El funtor monádico es \( f \). La notación \( f_k\equiv f(k)\equiv fk \) es el término que resulta de poner la variable \( k \) después del funtor \( f \) para formar un término de \( \mathcal L_{\rm arp} \).

Entonces, no sé si estás llamando \( h \) a lo que ya tiene un nombre y se llama \( f \), en cuyo caso esto:

(es decir, \( h \) será una cadena de signos de ARP que empezará por \( \rho \) al haberse definido por recursión, etc.), entonces no se cumple que \( h \in \mbox{Fun}({\color{blue}\mathcal L_{\rm arp}}) \), ¿no?

no es que no se cumpla, sino que no tiene sentido. Delante de un \( \in \) tienes que poner un término, nunca un funtor. Es como si escribes \( +\in  \mbox{Fun}({\color{blue}\mathcal L_{\rm arp}}) \) eso es un disparate. Lo que sí que tendría sentido es \( {\color{blue}+}\in  \mbox{Fun}({\color{blue}\mathcal L_{\rm arp}}) \), e igualmente podrías escribir  \( {\color{blue}h}\in  \mbox{Fun}({\color{blue}\mathcal L_{\rm arp}}) \) y sería un teorema.

Pero si realmente quieres decir \( h\equiv f_k \) (que me parece que no es eso) entonces sí que sería un teorema \( h\in  \mbox{Fun}({\color{blue}\mathcal L_{\rm arp}}) \).

Lo que (creo que) sabemos, con esta notación, es que los términos \( g(0), g(1), g(2), \cdots \) si pertenecen todos a \( \mbox{Fun}({\color{blue}\mathcal L_{\rm arp}}) \)

¿Esas ges son lo que habías llamado h? En realidad lo natural sería llamarlo \( f \). Tienes un (único) funtor monádico \( f \), de modo que, si tomas una variable \( k \), puedes formar el término \( f_k\equiv f(k)\equiv fk \), y es un teorema que \( f_k\in \mbox{Fun}({\color{blue}\mathcal L_{\rm arp}}) \), lo que a su vez implica que \( f_0\in \mbox{Fun}({\color{blue}\mathcal L_{\rm arp}}) \), \( f_1\in \mbox{Fun}({\color{blue}\mathcal L_{\rm arp}}) \), etc.

y, además, como la \( k \) es un parámetro de \( g \) esto si se puede probar por inducción en ARP y esto es lo que me está haciendo un lío ahora mismo :(

No sé qué quieres decir con "parámetro". Lo que tenemos es que \( f_k \) es un término normal y corriente, formado por un funtor monádico \( f \) seguido de una variable \( k \). Probar \( f_k\in \mbox{Fun}({\color{blue}\mathcal L_{\rm arp}}) \) por inducción supone probar

\( f_0\in \mbox{Fun}({\color{blue}\mathcal L_{\rm arp}}) \),

lo cual se cumple porque \( f_0={\color{blue}S}\in \mbox{Fun}({\color{blue}\mathcal L_{\rm arp}}) \), y luego, supuesto \( f_k\in \mbox{Fun}({\color{blue}\mathcal L_{\rm arp}}) \), hay que probar que

\( f_{k+1} = \mbox{SF}(f_k)\in \mbox{Fun}({\color{blue}\mathcal L_{\rm arp}}) \),

y esto es cierto, porque el funtor SF asigna un funtor a cada funtor.

Estoy seguro que es una tontería que no veo por haberme encabezonado en ver algo como no debería, pero llevo desde ayer por la tarde que leí el hilo por encima pensándolo y no lo veo.

Pues no estoy seguro de qué es exactamente lo que te confunde, pero tengo la impresión de que estás interpretando \( f_k \) de forma extraña. A ver si con lo que te he dicho lo ves ya o, si no, removiendo la sopa acabará saliendo a flote la confusión.

Por otra parte, aquí:

Supongamos que existiera el funtor \( \phi \). Entonces podríamos definir un funtor monádico mediante

\( f(k) = \phi(f^1_k,\left<k\right>)+1. \)

Nota En el argumento anterior subyace el hecho siguiente: si enumeramos todas las funciones monádicas recursivas primitivas, \( f_0^1, f_1^1, f_2^1, \ldots \) la función dada por \( f(k) = f^1_k(k)+1 \) puede calcularla un ordenador, pero no es recursiva primitiva, pues entonces sería una de las \( f_k \), y entonces \( f_k(k) = f(k) = f_k(k)+1 \), lo cual es imposible.

En la primera cita con \( f^1_k \) haces referencia al funtor de los del mensaje anterior (bueno, realmente sería al funtor monádico definido por el término \( g(k,1) \) siendo \( g \equiv f^n_k \), ¿verdad?), sobre los que he planteado la duda anterior.

Aquí tenemos una pequeña ambigüedad, y es que hay dos funtores que se llaman \( f \), sólo que se distinguen por el contexto, porque uno es monádico y el otro diádico. Ahora estamos hablando del segundo, que se llama \( f \), como digo (pero no es el mismo del que hemos hablado antes), y \( f_k^n\equiv f(k, n)\equiv f k n \) es el término que se forma con el funtor diádico y dos variables. Tenemos que en ARP se demuestra \( n\geq 1\rightarrow f^n_k\in \mbox{Fun}({\color{blue}\mathcal L_{\rm arp}}) \) (me doy cuenta ahora de que falta esa hipótesis en el hilo), luego en particular \( f^1_k\in \mbox{Fun}({\color{blue}\mathcal L_{\rm arp}}) \)

Pero, con la notación del segundo caso te refieres a funciones recursivas primitivas, metamatemáticamente, no a funtores de ARP aunque sea la misma notación, ¿no?

Pues eso es delicado. En principio el argumento sólo requiere que numeremos las funciones monádicas recursivas primitivas admitiendo que la enumeración tenga repeticiones, y eso es una suerte, porque es mucho más fácil enumerar las funciones recursivas primitivas con repeticiones que enumerarlas sin repeticiones.

Si admitimos repeticiones, basta enumerar los funtores monádicos de \( \mathcal L_{\rm arp} \), y precisamente hemos visto cómo hacerlo. Si los identificamos con números naturales, es decir, si identificamos cada funtor \( g \) con el número denotado por el funtor \( g \), entonces basta enumerarlos en orden creciente, y la función que los enumera es recursiva primitiva, Si llamamos \( H = F(f) \) a la función diádica denotada por el funtor diádico que enumera los funtores según su rango, entonces la función \( h(k) = H(k,1) \) enumera los funtores monádicos. Si llamamos \( f^1_k \) a la función recursiva primitiva denotada por el funtor \( h(k) \), tenemos una enumeración de las funciones recursivas primitivas con repeticiones, porque dos funtores pueden denotar la misma función.

Eliminar las repeticiones no es fácil, porque no es fácil determinar si dos funciones recursivas primitivas definidas de forma distinta son o no la misma función.

01 Agosto, 2023, 11:03 am
Respuesta #255

Eparoh

  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 983
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Hola.

Pues, efectivamente me estaba encabezonando con no ver las cosas como tocan y he tenido un lapsus de los gordos :banghead:

A pesar de que ya en su día comenté esto:

Teorema Si \( t(x_1,\ldots, x_n) \) es un término cuyas variables están todas entre \( x_1,\ldots, x_n \), entonces existe un funtor \( n \)-ádico \( f_t \) tal que

\( \mathop{\vdash}\limits_{\rm ARP} f_t(x_1,\ldots, x_n)=t(x_1,\ldots, x_n). \)

Demostración
Razonamos por inducción sobre la longitud de \( t \). Si \( t\equiv 0 \), basta tomar\(  f_0 \equiv \kappa(c, p^n_1) \), pues la definición de \( f_0 \) es:

\( f_0(x_1,\ldots, x_n) = c(p\color{red}_1^n\color{black}(x_1,\ldots, x_n)), \)

y por otro lado, la definición de \( c \) es \( c(x) = 0 \), luego aplicando \( S_1 \) obtenemos

\( c(p\color{red}_1^n\color{black}(x_1,\ldots, x_n))=0, \)

y, finalmente, la regla \( T \) nos da la igualdad

\( f_0(x_1,\ldots, x_n) = 0. \)

Si \( t\equiv x_i \), basta tomar \( f_t\equiv p^n_i \). La alternativa es que \( t \equiv f(t_1,\ldots, t_m) \), para cierto funtor \( f \) y ciertos términos \( t_i \) para los que, por hipótesis de inducción, existen funtores \( f_{t_i} \) tales que

\( \mathop{\vdash}\limits_{\rm ARP}f_{t_i}(x_1,\ldots, x_n) = t_i(x_1,\ldots, x_n). \)

Basta tomar \( f_t \equiv \kappa(f, f_{t_1},\ldots, f_{t_m}) \), pues la definición de \( f_t \) es

\( f_t(x_1,\ldots, x_n) = f(f_{t_1}(x_1,\ldots, x_n), \ldots, f_{t_m}(x_1,\ldots, x_n)). \)

Si llamamos \( \bar t_i \equiv f_{t_i}(x_1, \ldots, x_n) \), tenemos \( f_t(x_1,\ldots, x_n) = f(\bar t_1,\ldots, \bar t_n) \), así como \( \bar t_i = t_i \), luego aplicando \( S_2 \) sucesivamente obtenemos

\( \color{blue}f(\bar t_1,\ldots, \bar t_n) = f(t_1,\bar t_2,\ldots, \bar t_n), \)

\( \color{blue}f(t_1,\bar t_2,\ldots, \bar t_n) = f(t_1, t_2, \bar t_3, \ldots, \bar t_n), \)

etc., y la regla \( T \) nos da

\( \color{blue}f_t(x_1,\ldots, x_n) = f(t_1, \ldots, t_n) \equiv t. \)
[cerrar]

Pequeñas erratas con \( p_1^n \) dentro del spoiler.

En el enunciado del teorema, entiendo que se está haciendo un abuso de notación y donde pone \( f_t(x_1, \cdots, x_n) \) se refiere al término \( f_tx_1 \cdots x_n \), mientras que con \( t(x_1, \cdots, x_n) \) se refiere únicamente al término \( t \), pero haciendo referencia a que todas sus variables están entre las dadas, ¿no?

Ahora, más de un mes después, me olvido de lo aprendido e interpreto (sin excusa ni lógica ninguna) que \( f_k \) o \( f^n_k \) son los funtores en sí, y no los términos \( fk \) y \( fkn \) (donde el funtor \( f \) realmente es diferente en cada caso, sí).

Vamos, un lapsus mental enorme, pero todo ya claro como siempre.

Al resto de la respuesta contesto ahora después cuando termine de leer el último mensaje del hilo principal.

Un saludo.

01 Agosto, 2023, 02:12 pm
Respuesta #256

Eparoh

  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 983
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Hola de nuevo.

Pues eso es delicado. En principio el argumento sólo requiere que numeremos las funciones monádicas recursivas primitivas admitiendo que la enumeración tenga repeticiones, y eso es una suerte, porque es mucho más fácil enumerar las funciones recursivas primitivas con repeticiones que enumerarlas sin repeticiones.

Si admitimos repeticiones, basta enumerar los funtores monádicos de \( \mathcal L_{\rm arp} \), y precisamente hemos visto cómo hacerlo. Si los identificamos con números naturales, es decir, si identificamos cada funtor \( g \) con el número denotado por el funtor \( g \), entonces basta enumerarlos en orden creciente, y la función que los enumera es recursiva primitiva, Si llamamos \( H = F(f) \) a la función diádica denotada por el funtor diádico que enumera los funtores según su rango, entonces la función \( h(k) = H(k,1) \) enumera los funtores monádicos. Si llamamos \( f^1_k \) a la función recursiva primitiva denotada por el funtor \( h(k) \), tenemos una enumeración de las funciones recursivas primitivas con repeticiones, porque dos funtores pueden denotar la misma función.

Eliminar las repeticiones no es fácil, porque no es fácil determinar si dos funciones recursivas primitivas definidas de forma distinta son o no la misma función.

Vale, a ver si lo he entendido bien.

Lo que comentas al principio es básicamente la construcción de los dos funtores en la parte que titulaste "Enumeración de funtores", y lo que ocurre entonces es que si consideramos el funtor monádico \( h \) definido por el término \( f^1_k \), entonces la función recursiva primitiva \( H=F(h) \) denotada por \( h \) nos da la enumeración (con repetición) buscada.

Esto es más o menos lo que comentabas, ¿no?

Ahora, las erratas, dudas y comentarios del último mensaje:

Teorema Existe un funtor diádico \( \phi \) tal que las afirmaciones siguientes son teoremas de ARP:

  • \( \phi({\color{blue}S}, s) = s_{\color{red} \cancel 0}+1 \).

  • \( \phi({\color{blue}c}, s)=0 \).

  • \( 1\leq k\leq n\rightarrow \phi(p^n_k, s) = s_{k\dot- 1} \).

  • \( h\in \mbox{Fun}({\color{blue}\mathcal L_{\rm arp}})\land \mbox{rang}(h)=m\land \ell(g)=m\land \forall i<m(g_i\in \mbox{Fun}({\color{blue}\mathcal L_{\rm arp}})\land \mbox{rang}(g_i)=n)\land \ell(s)=n\rightarrow \phi({\color{blue}\kappa}(h, g_1,\ldots, g_n), s)=\phi(h,\prod\limits_{i<m}\left<\phi(g_i,s)\right>) \),
    donde el producto indica la concatenación de sucesiones.

  • \( g, h\in \mbox{Fun}({\color{blue}\mathcal L_{\rm arp}})\land \mbox{rang}(g) = n\land \mbox{rang}(h)=n+2\land \ell(s)=n\rightarrow \phi({\color{blue}\rho}(g, h), s\frown \left<0\right>)=\phi(g, s)\land  \)

    \( \phi({\color{blue}\rho}(g, h),s\frown \left<k+1\right>)=\phi(h, s\frown \left<k\right>\frown \left<\phi({\color{blue}\rho}(g, h),s\frown\left<k\right>)\right>) \)

Relajando el formalismo por caridad cristiana, este "teorema" afirma que el funtor \( \phi \) cumple (bajo las hipótesis obvias en cada caso):

  • \( \phi({\color{blue}S},n) = n+1 \).

  • \( \phi({\color{blue}c}, n) = 0 \).

  • \( \phi(p^n_k, \left<m_1,\ldots, m_n\right>) = m_{\color{red}k} \).

  • \( \phi({\color{blue}\kappa}(h, g_1,\ldots, g_m), \left<s_1,\ldots, s_n\right>) =\phi(h,\left<\phi(g_1,\left<s_1,\ldots, s_n\right>),\ldots,\phi(g_m,\left<s_1,\ldots, s_n\right>) \right>){\color{red} \cancel ,} \).

  • \( \phi({\color{blue}\rho}(g, h),\left<s_1,\ldots, s_n, 0\right>) = \phi(g, \left<s_1,\ldots, s_n\right>) {\color{red} \wedge}
    \phi({\color{blue}\rho}(g, h),\left<s_1,\ldots, s_n,k+1\right>) = \phi(h,\left<s_1,\ldots, s_n,k, \phi({\color{blue}\rho}(g, h),\left<s_1,\ldots, s_n,k\right>)\right>) \).

Sin embargo el "teorema" anterior es falso. Vamos a demostrar que no existe tal funtor \( \phi \). El lector que crea que debería poder definirse un funtor \( \phi \) que cumpla las condiciones indicadas debería tratar de dar una definición detallada formalizable en ARP, y si la encuentra, entonces es que no ha acabado de entender qué hace falta para que una construcción sea formalizable en ARP.

Realmente lo que se demuestra no es en sí que no exista un funtor que no cumpla el "Teorema", sino que no existe ningún funtor que cumpla esto:

Citar
Si \( f \) es un funtor \( n \)-ádico, \( k_1,\ldots, k_n \) son números naturales y \( \bar k_i \) es el numeral correspondiente a \( k_i \), entonces

\( \mathop\vdash\limits_{\rm ARP}\phi({\color{blue}f},\left<\bar k_1,\ldots, \bar k_n\right>)=\overline{F(f)(k_1,\ldots, k_n)}, \)

donde \( F(f) \) es la función denotada por el funtor \( f \).

¿Verdad?

Por otro lado, es fácil programar un ordenador para que si le damos como entrada un funtor \( n \)-ádico \( f \) de ARP y una \( n \)-tupla \( \left<k_1,\ldots, k_n\right> \) nos dé como respuesta \( F(f)(k_1,\ldots, k_n) \). En otras palabras, la función diádica \( F(f, s) \) que, cuando \( f \), visto como sucesión de números naturales, corresponde a un funtor \( n \)-ádico de \( {\color{blue}\mathcal L_{\rm arp}} \) y \( s \) es una sucesión de longitud \( n \) ,calcula

\( F(f, s) = f(s_0,\ldots, s_{n-1}) \)

(y para otros argumentos toma el valor \( 0 \)) la puede calcular un ordenador, pero no es recursiva primitiva.

No entiendo del todo bien esto en relación con el párrafo anterior. La última función \( F \) que das, ¿qué calcula exactamente? Porque no entiendo que significa \( f(s_0,\ldots, s_{n-1}) \) si es \( f \) un funtor de \( {\color{blue}\mathcal L_{\rm arp}} \), ya que los \( s_i \) no tienen porque ser términos de \( {\color{blue}\mathcal L_{\rm arp}} \), ¿no?

Igual de nuevo me estoy armando un lío con una tontería, pero no veo clara ni la notación, ni tampoco la relación entre las dos oraciones de este párrafo.
 
Puesto que \( \mu u\leq {\color{blue} f}{\color{red} \cancel \mid} {\color{blue} f} = f^1_u \) es un término sin variables, podemos considerar el número \( k \) que denota, de modo que, según el teorema final de la respuesta #7, se cumple que

\( \mathop\vdash\limits_{\rm ARP}\bar k = \mu u\leq {\color{blue} f}{\color{red} \cancel \mid} {\color{blue} f} = f^1_u, \)

Nota En el argumento anterior subyace el hecho siguiente: si enumeramos todas las funciones monádicas recursivas primitivas, \( f_0^1, f_1^1, f_2^1, \ldots \) la función dada por \( f(k) = f^1_k(k)+1 \) puede calcularla un ordenador, pero no es recursiva primitiva, pues entonces sería una de las \( f_{\color{green}j}^{\color{red}1} \), y entonces \( f_{\color{green}j}^{\color{red}1}({\color{green} j}) = f({\color{green} j}) = f_{\color{green}j}^{\color{red}1}({\color{green} j})+1 \), lo cual es imposible.

En verde he cambiado las últimas "\( k \)" por "\( j \)", porque me parece más claro así para no confundir la variable de la \( f \) con el subíndice que le correspondería si fuera una función recursiva primitiva. A mi me parece más claro así, pero se que no es incorrecto como está.

Más precisamente, no puede suceder que \( \psi \) cumpla, en particular, que, si \( t \) es un término metamatemático sin variables, entonces

\( \mathop\vdash\limits_{\rm ARP}\psi({\color{orange} t}, 0) = \overline{N(t)}, \)

donde \( N(t) \) es el número natural denotado por \( t \).

En lo que he marcado en naranja, falta ponerlo en azul.

A su vez, esto implica que no es posible definir un funtor diádico \( \vDash \alpha[v] \) tal que si \( \alpha\in \mbox{Form}({\color{blue}\mathcal L_{\rm arp}}) \) y \( v \) es una valoración definida sobre las variables que aparecen en \( \alpha \), entonces \( \vDash \alpha[v] \) tome el valor \( 1 \) o \( 0 \) según si \( \alpha \) es satisfecha o no respecto de la valoración \( v \).

¿Aquí lo que se pretende decir no es más bien algo como esto?

Citar
A su vez, esto implica que no es posible definir un funtor diádico \( \vDash \alpha[v] \) tal que si \( \alpha \) es una fórmula de ARP y \( v \) es una valoración definida sobre las variables que aparecen en \( \alpha \), entonces \( \vDash {\color{blue}\alpha}[{\color{green} v}] \) (donde \( {\color{green} v} \) es la formalización de la valoración \( v \)) tome el valor \( 1 \) o \( 0 \) según si \( \alpha \) es satisfecha o no respecto de la valoración \( v \).

Y, de todas forma, no veo del todo claro como se obtiene esto de lo anterior. Veo claro que, al menos, no se puede hacer de forma directa, porque ya hemos visto que no se puede formalizar el número natural que denota un término respecto de una valoración, pero no veo porque no podría conseguirse de alguna otra forma (la cual no soy capaz de imaginarme) sin pasar por formalizar la denotación de términos.

Un saludo.

PD: Supongo que al hilo le quedan ya solo un par de mensajes más (terminar de formalizar la sintaxis de ARP y el último mensaje que comentaste sobre como podría extenderse ARP a una teoría de primer orden), ¿no?

01 Agosto, 2023, 11:45 pm
Respuesta #257

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Pues eso es delicado. En principio el argumento sólo requiere que numeremos las funciones monádicas recursivas primitivas admitiendo que la enumeración tenga repeticiones, y eso es una suerte, porque es mucho más fácil enumerar las funciones recursivas primitivas con repeticiones que enumerarlas sin repeticiones.

Si admitimos repeticiones, basta enumerar los funtores monádicos de \( \mathcal L_{\rm arp} \), y precisamente hemos visto cómo hacerlo. Si los identificamos con números naturales, es decir, si identificamos cada funtor \( g \) con el número denotado por el funtor \( g \), entonces basta enumerarlos en orden creciente, y la función que los enumera es recursiva primitiva, Si llamamos \( H = F(f) \) a la función diádica denotada por el funtor diádico que enumera los funtores según su rango, entonces la función \( h(k) = H(k,1) \) enumera los funtores monádicos. Si llamamos \( f^1_k \) a la función recursiva primitiva denotada por el funtor \( h(k) \), tenemos una enumeración de las funciones recursivas primitivas con repeticiones, porque dos funtores pueden denotar la misma función.

Eliminar las repeticiones no es fácil, porque no es fácil determinar si dos funciones recursivas primitivas definidas de forma distinta son o no la misma función.

Vale, a ver si lo he entendido bien.

Lo que comentas al principio es básicamente la construcción de los dos funtores en la parte que titulaste "Enumeración de funtores", y lo que ocurre entonces es que si consideramos el funtor monádico \( h \) definido por el término \( f^1_k \), entonces la función recursiva primitiva \( H=F(h) \) denotada por \( h \) nos da la enumeración (con repetición) buscada.

Esto es más o menos lo que comentabas, ¿no?

La idea es ésa, pero, puestos a ser puristas, la situación es muy sutil. Es verdad que el término \( f^1_{\bar k} \) (donde \( \bar k \) es el numeral asociado a \( k \)) "es" un funtor en el sentido de que se demuestra en ARP que \( f^1_{\bar k}\in \mbox{Fun}({\color{\blue}\mathcal L_{\rm arp}}) \), pero en realidad no es un funtor. Es un término que denota un cierto número natural, digamos \( N \). Lo que pasa es que \( N \) no es cualquier número, sino que existe un funtor de verdad, digamos, \( h \), tal que si interpretas sus signos como los números 0, 1, 2, 3, 4, 5  y a \( h \) como una sucesión de números, entonces esa sucesión es \( N \).

Ahora, las erratas, dudas y comentarios del último mensaje:

 ::)

Teorema Existe un funtor diádico \( \phi \) tal que las afirmaciones siguientes son teoremas de ARP:

  • \( \phi({\color{blue}S}, s) = s_{\color{red} \cancel 0}+1 \).

¡Te va a reñir argentinator!  Estas confundiendo un número con la sucesión de longitud 1 que consta de ese número. Yo reivindico esa confusión, pero justo aquí, en el terreno formal, no le podemos discutir nada. El funtor fantasma \( \Phi \) actúa sobre un funtor y una sucesión de números naturales. Si tiene longitud 1, su único término es \( s_0 \).

Sin embargo el "teorema" anterior es falso. Vamos a demostrar que no existe tal funtor \( \phi \). El lector que crea que debería poder definirse un funtor \( \phi \) que cumpla las condiciones indicadas debería tratar de dar una definición detallada formalizable en ARP, y si la encuentra, entonces es que no ha acabado de entender qué hace falta para que una construcción sea formalizable en ARP.

Realmente lo que se demuestra no es en sí que no exista un funtor que no cumpla el "Teorema", sino que no existe ningún funtor que cumpla esto:

Citar
Si \( f \) es un funtor \( n \)-ádico, \( k_1,\ldots, k_n \) son números naturales y \( \bar k_i \) es el numeral correspondiente a \( k_i \), entonces

\( \mathop\vdash\limits_{\rm ARP}\phi({\color{blue}f},\left<\bar k_1,\ldots, \bar k_n\right>)=\overline{F(f)(k_1,\ldots, k_n)}, \)

donde \( F(f) \) es la función denotada por el funtor \( f \).

¿Verdad?

Sí, si un funtor cumpliera el "teorema", cumpliría eso.

Por otro lado, es fácil programar un ordenador para que si le damos como entrada un funtor \( n \)-ádico \( f \) de ARP y una \( n \)-tupla \( \left<k_1,\ldots, k_n\right> \) nos dé como respuesta \( F(f)(k_1,\ldots, k_n) \). En otras palabras, la función diádica \( F(f, s) \) que, cuando \( f \), visto como sucesión de números naturales, corresponde a un funtor \( n \)-ádico de \( {\color{blue}\mathcal L_{\rm arp}} \) y \( s \) es una sucesión de longitud \( n \) ,calcula

\( F(f, s) = f(s_0,\ldots, s_{n-1}) \)

(y para otros argumentos toma el valor \( 0 \)) la puede calcular un ordenador, pero no es recursiva primitiva.

No entiendo del todo bien esto en relación con el párrafo anterior. La última función \( F \) que das, ¿qué calcula exactamente? Porque no entiendo que significa \( f(s_0,\ldots, s_{n-1}) \) si es \( f \) un funtor de \( {\color{blue}\mathcal L_{\rm arp}} \), ya que los \( s_i \) no tienen porque ser términos de \( {\color{blue}\mathcal L_{\rm arp}} \), ¿no?

Igual de nuevo me estoy armando un lío con una tontería, pero no veo clara ni la notación,

Esta vez es culpa mía. Me faltaba una F y entonces resulta que F son dos cosas, así que mejor de esta forma:
Citar
En otras palabras, la función diádica \( H(f, s) \) que, cuando \( f \), visto como sucesión de números naturales, corresponde a un funtor \( n \)-ádico de \( {\color{blue}\mathcal L_{\rm arp}} \) y \( s \) es una sucesión de longitud \( n \), calcula

\( H(f, s) = F(f)(s_0,\ldots, s_{n-1}) \)

(y para otros argumentos toma el valor \( 0 \)) la puede calcular un ordenador, pero no es recursiva primitiva.
ni tampoco la relación entre las dos oraciones de este párrafo.
 
Puesto que \( \mu u\leq {\color{blue} f}{\color{blue} f} = f^1_u \) es un término sin variables, podemos considerar el número \( k \) que denota, de modo que, según el teorema final de la respuesta #7, se cumple que

\( \mathop\vdash\limits_{\rm ARP}\bar k = \mu u\leq {\color{blue} f}{\color{blue} f} = f^1_u, \)

No acabo de ver cuál es tu duda. Lo primero es un término sin variables, y por eso denota un número natural. Si tuviera variables, el número denotado dependería de la valoración con la que se calcula. Por eso \( k \) es un número en concreto y podemos considerar su numeral \( \bar k \). Pero no sé si esto te aclara algo o tu duda era otra.

A su vez, esto implica que no es posible definir un funtor diádico \( \vDash \alpha[v] \) tal que si \( \alpha\in \mbox{Form}({\color{blue}\mathcal L_{\rm arp}}) \) y \( v \) es una valoración definida sobre las variables que aparecen en \( \alpha \), entonces \( \vDash \alpha[v] \) tome el valor \( 1 \) o \( 0 \) según si \( \alpha \) es satisfecha o no respecto de la valoración \( v \).

¿Aquí lo que se pretende decir no es más bien algo como esto?

Citar
A su vez, esto implica que no es posible definir un funtor diádico \( \vDash \alpha[v] \) tal que si \( \alpha \) es una fórmula de ARP y \( v \) es una valoración definida sobre las variables que aparecen en \( \alpha \), entonces \( \vDash {\color{blue}\alpha}[{\color{green} v}] \) (donde \( {\color{green} v} \) es la formalización de la valoración \( v \)) tome el valor \( 1 \) o \( 0 \) según si \( \alpha \) es satisfecha o no respecto de la valoración \( v \).

Lo he puesto como propones, porque es más fácil así, pero lo que quería expresar es que no es posible definir un funtor que al actuar sobre fórmulas \( \alpha\in \mbox{Form}({\color{blue}\mathcal L_{\rm arp}}) \) y valoraciones \( v \) el valor \( \vDash \alpha[v]\equiv F(\alpha, v) \) sea un \( 0 \) o un \( 1 \) de forma que podamos decir que esto formaliza la definición de "satisfacción", en el  sentido de que si \( \alpha \) es una fórmula de ARP, entonces \( \vDash {\color{blue}\alpha}[{\color{blue}v}] = 1 \) se cumpla si y sólo si \( \alpha \) es satisfecha respecto a \( v \)

Y, de todas forma, no veo del todo claro como se obtiene esto de lo anterior. Veo claro que, al menos, no se puede hacer de forma directa, porque ya hemos visto que no se puede formalizar el número natural que denota un término respecto de una valoración, pero no veo porque no podría conseguirse de alguna otra forma (la cual no soy capaz de imaginarme) sin pasar por formalizar la denotación de términos.

Vale, te iba a responder que en tal caso, podrías calcular \( N(t)[v] \) como el mínimo número natural \( n \) que cumple \( \vdash x = t[v_x^n] \), pero no está claro que eso fuera formalizable, porque no tenemos una cota para \( n \). He cambiado la redacción para rebajar la afirmación al hecho de que no podemos hacer con la semántica lo mismo que estamos haciendo con la sintáxis: formalizarla mecánicamente en ARP sin más que seguir las definiciones informales al pie de la letra.

PD: Supongo que al hilo le quedan ya solo un par de mensajes más (terminar de formalizar la sintaxis de ARP y el último mensaje que comentaste sobre como podría extenderse ARP a una teoría de primer orden), ¿no?

Sí, eso es.

02 Agosto, 2023, 09:46 am
Respuesta #258

Eparoh

  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 983
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Hola.

La idea es ésa, pero, puestos a ser puristas, la situación es muy sutil. Es verdad que el término \( f^1_{\bar k} \) (donde \( \bar k \) es el numeral asociado a \( k \)) "es" un funtor en el sentido de que se demuestra en ARP que \( f^1_{\bar k}\in \mbox{Fun}({\color{\blue}\mathcal L_{\rm arp}}) \), pero en realidad no es un funtor. Es un término que denota un cierto número natural, digamos \( N \). Lo que pasa es que \( N \) no es cualquier número, sino que existe un funtor de verdad, digamos, \( h \), tal que si interpretas sus signos como los números 0, 1, 2, 3, 4, 5  y a \( h \) como una sucesión de números, entonces esa sucesión es \( N \).

Entiendo, ¿pero podrías entonces describir exactamente como podríamos llegar a la enumeración de las funciones monádicas recursivas primitivas?

Lo que entiendo es esto:
  • Podemos enumerar los funtores monádicos de \( {\color{blue}\mathcal L_{\rm arp}} \) (no es más que la enumeración \( f^1_0, f^1_1, f^1_2, \cdots \) donde cada término es el dado por el funtor \( f \) del mensaje anterior).
  • Dado \( g \) un funtor monádico cualquiera de ARP, se tiene que \( \color{blue} g \) es un funtor monádico de \( {\color{blue}\mathcal L_{\rm arp}} \) y, por tanto,es alguno de los \( f^1_j \).
  • Si tuvieramos una enumeración, \( g_0, g_1, g_2, \cdots \), de los funtores monádicos de ARP entonces una enumeración (con posibles repeticiones) de las funciones monádicas recursivas primitivas es \( F(g_0), F(g_1), F(g_2), \cdots \). Efectivamente, aunque en el hilo no lo hemos demostrado, veo claro que dada una función \( n \)-ádica recursiva primitiva \( G \) existe un funtor de ARP (que no tiene porque ser único) \( g \) de rango \( n \) tal que \( F(g)=G \), por lo tanto como en la lista \( g_0, g_1, g_2, \cdots \) aparecen todos los funtores monádicos, en la lista \( F(g_0), F(g_1), F(g_2), \cdots \) deben aparecer todas las funciones monádicas recursivas primitivas.

El paso que no veo claro es como pasar de la enumeración de los funtores monádicos de \( {\color{blue}\mathcal L_{\rm arp}} \) a una enumeración de los funtores monádicos de ARP.

Teorema Existe un funtor diádico \( \phi \) tal que las afirmaciones siguientes son teoremas de ARP:

  • \( \phi({\color{blue}S}, s) = s_{\color{red} \cancel 0}+1 \).

¡Te va a reñir argentinator!  Estas confundiendo un número con la sucesión de longitud 1 que consta de ese número. Yo reivindico esa confusión, pero justo aquí, en el terreno formal, no le podemos discutir nada. El funtor fantasma \( \Phi \) actúa sobre un funtor y una sucesión de números naturales. Si tiene longitud 1, su único término es \( s_0 \).

¡Ah, vale! Me lio un poco el párrafo siguiente, donde entonces es igual mejor poner esto, ¿no?

Relajando el formalismo por caridad cristiana, este "teorema" afirma que el funtor \( \phi \) cumple (bajo las hipótesis obvias en cada caso):

  • \( \phi({\color{blue}S},{\color{red} \langle}n{\color{red} \rangle}) = n+1 \).

  • \( \phi({\color{blue}c}, {\color{red} \langle}n{\color{red} \rangle}) = 0 \).
[...]



ni tampoco la relación entre las dos oraciones de este párrafo.
 
Puesto que \( \mu u\leq {\color{blue} f}{\color{blue} f} = f^1_u \) es un término sin variables, podemos considerar el número \( k \) que denota, de modo que, según el teorema final de la respuesta #7, se cumple que

\( \mathop\vdash\limits_{\rm ARP}\bar k = \mu u\leq {\color{blue} f}{\color{blue} f} = f^1_u, \)

No acabo de ver cuál es tu duda. Lo primero es un término sin variables, y por eso denota un número natural. Si tuviera variables, el número denotado dependería de la valoración con la que se calcula. Por eso \( k \) es un número en concreto y podemos considerar su numeral \( \bar k \). Pero no sé si esto te aclara algo o tu duda era otra.

¡No! Que mal me expresé ahí :-[

Me refería a las dos oraciones del párrafo anterior, de lo que estaba preguntando donde comentas que faltaba una "\( F \)". De ese párrafo que ahora citas era simplemente la pequeña errata que había, no ninguna duda.

Esta vez es culpa mía. Me faltaba una F y entonces resulta que F son dos cosas, así que mejor de esta forma:
Citar
En otras palabras, la función diádica \( H(f, s) \) que, cuando \( f \), visto como sucesión de números naturales, corresponde a un funtor \( n \)-ádico de \( {\color{blue}\mathcal L_{\rm arp}} \) y \( s \) es una sucesión de longitud \( n \), calcula

\( H(f, s) = F(f)(s_0,\ldots, s_{n-1}) \)

(y para otros argumentos toma el valor \( 0 \)) la puede calcular un ordenador, pero no es recursiva primitiva.

Vale, ahora le veo algo más de sentido, pero sigo sin tenerlo claro. Estas diciendo que \( f \) es un funtor de \( {\color{blue}\mathcal L_{\rm arp}} \), pero luego consideras \( F(f) \) como la función recursiva denotada por \( f \) y esto no me cuadra siendo un funtor de \( {\color{blue}\mathcal L_{\rm arp}} \) y no de ARP.

Me espero mejor a que aclaremos la notación y entienda bien que quieres decir para exponer la otra duda que quedó pendiente en el mensaje anterior por el lío que hice al parecer que hacía referencia a la siguiente cita en lugar de a la que tocaba.

Y, de todas forma, no veo del todo claro como se obtiene esto de lo anterior. Veo claro que, al menos, no se puede hacer de forma directa, porque ya hemos visto que no se puede formalizar el número natural que denota un término respecto de una valoración, pero no veo porque no podría conseguirse de alguna otra forma (la cual no soy capaz de imaginarme) sin pasar por formalizar la denotación de términos.

Vale, te iba a responder que en tal caso, podrías calcular \( N(t)[v] \) como el mínimo número natural \( n \) que cumple \( \vdash x = t[v_x^n] \), pero no está claro que eso fuera formalizable, porque no tenemos una cota para \( n \). He cambiado la redacción para rebajar la afirmación al hecho de que no podemos hacer con la semántica lo mismo que estamos haciendo con la sintáxis: formalizarla mecánicamente en ARP sin más que seguir las definiciones informales al pie de la letra.

Entiendo. Pero, aun así, supongo que por razones más complejas que las que podemos ver con lo que sabemos, es igualmente imposible obtener el funtor diádico que formalice la definición de "satisfacción" en las condiciones que ya se han mencionado, ¿no?

Un saludo.

PD: Me he dado cuenta de otra errata que se me pasó (¡sacrilegio!) revisando el hilo para responder a este mensaje:

A partir de las definiciones precedentes (y suprimiendo precisiones técnicas), es fácil ver que todo funtor \( f\in \mbox{Fun}({\color{blue}\mathcal L_{\rm arp}}) \) se encuentra en uno de los casos siguientes:

  • \( f = {\color{blue} S} \) (en cuyo caso \( f \) es un funtor monádico),

  • \( f = {\color{orange} c} \) (en cuyo caso \( f \) es un funtor monádico),

  • \( f = p^n_k \), para ciertos índices \( 1\leq k\leq n \) (y entonces \( f \) es un funtor \( n \)-ádico),

  • \( f = {\color{blue}\kappa}(h, g_0,\ldots, g_{m\dot-1}) \), donde \( h \) es un funtor \( m \)-ádico y los \( g_i \) forman una sucesión de funtores \( n \)-ádicos (y entonces \( f \) es un funtor \( n \)-ádico),

  • \( f = {\color{blue}\rho}(g, h) \), donde \( g \) es un funtor \( n \)-ádico y \( h \) es un funtor \( n+2 \)-ádico (y entonces \( f \) es un funtor \( n+1 \)-ádico).

La \( c \) que marco en naranja debería ser una \( c \) azul, pero en el hilo aparece una \( s \) azul.

02 Agosto, 2023, 11:28 am
Respuesta #259

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
La idea es ésa, pero, puestos a ser puristas, la situación es muy sutil. Es verdad que el término \( f^1_{\bar k} \) (donde \( \bar k \) es el numeral asociado a \( k \)) "es" un funtor en el sentido de que se demuestra en ARP que \( f^1_{\bar k}\in \mbox{Fun}({\color{\blue}\mathcal L_{\rm arp}}) \), pero en realidad no es un funtor. Es un término que denota un cierto número natural, digamos \( N \). Lo que pasa es que \( N \) no es cualquier número, sino que existe un funtor de verdad, digamos, \( h \), tal que si interpretas sus signos como los números 0, 1, 2, 3, 4, 5  y a \( h \) como una sucesión de números, entonces esa sucesión es \( N \).

Entiendo, ¿pero podrías entonces describir exactamente como podríamos llegar a la enumeración de las funciones monádicas recursivas primitivas?

Lo que entiendo es esto:
  • Podemos enumerar los funtores monádicos de \( {\color{blue}\mathcal L_{\rm arp}} \) (no es más que la enumeración \( f^1_0, f^1_1, f^1_2, \cdots \) donde cada término es el dado por el funtor \( f \) del mensaje anterior).
  • Dado \( g \) un funtor monádico cualquiera de ARP, se tiene que \( \color{blue} g \) es un funtor monádico de \( {\color{blue}\mathcal L_{\rm arp}} \) y, por tanto,es alguno de los \( f^1_j \).
  • Si tuvieramos una enumeración, \( g_0, g_1, g_2, \cdots \), de los funtores monádicos de ARP entonces una enumeración (con posibles repeticiones) de las funciones monádicas recursivas primitivas es \( F(g_0), F(g_1), F(g_2), \cdots \). Efectivamente, aunque en el hilo no lo hemos demostrado, veo claro que dada una función \( n \)-ádica recursiva primitiva \( G \) existe un funtor de ARP (que no tiene porque ser único) \( g \) de rango \( n \) tal que \( F(g)=G \), por lo tanto como en la lista \( g_0, g_1, g_2, \cdots \) aparecen todos los funtores monádicos, en la lista \( F(g_0), F(g_1), F(g_2), \cdots \) deben aparecer todas las funciones monádicas recursivas primitivas.

El paso que no veo claro es como pasar de la enumeración de los funtores monádicos de \( {\color{blue}\mathcal L_{\rm arp}} \) a una enumeración de los funtores monádicos de ARP.

Estamos mareando la perdiz (y cuando digo "estamos", quiero decir que tú la estás mareando, y yo también). Es todo mucho más sencillo y directo. Sólo hay que tener presente que los teoremas de ARP no son meras cadenas de signos, sino que tienen un significado muy concreto. Por ejemplo, si demostramos en ARP que

\( x^3+y^3 = z^3\rightarrow xyz = 0 \),

cosa que es posible, cualquiera que vea la demostración debería convencerse inmediatamente de que la ecuación \( x^3+y^3=z^3 \) no tiene soluciones naturales no nulas, porque eso es lo que significa el teorema en cuestión.

Análogamente, en ARP hemos demostrado que el funtor monádico \( f^1 \) definido por

\( f^1(k) = f^1_k \)

enumera los funtores monádicos de \( \mathcal L_{\rm arp} \) y ahora sólo tenemos que preguntarnos: ¿y eso qué significa? Si es un teorema de ARP, es que es verdadero, pero ¿qué significa?

Para responder a esa pregunta debemos recordar que hemos formalizado ARP identificando sus signos con los números del 0 al 7, con lo que cada funtor de \( \mathcal L_{\rm arp} \) se identifica con una sucesión finita de números del 0 al 5 y, por consiguiente, con un número natural.

Quiero decir, que, por ejemplo, el funtor \( p^1_1 \) (de \( \mathcal L_{\rm arp} \), no su formalización) es la sucesión \( pS0S0 \), que podemos identificar con la sucesión \( 2, 1, 0, 1, 0 \), que a su vez podemos identificar con el número natural \( \left<2, 1, 0, 1, 0\right>_\infty = 170\,378\,236\,901 \).

Así pues, podemos identificar cada funtor monádico de ARP con un número natural, y una enumeración de los funtores monádicos de \( \mathcal L_{\rm arp} \) consiste simplemente en enumerarlos de menor a mayor. El hecho de que en ARP hayamos construido el funtor monádico \( f^1 \) significa simplemente que la función \( H=F(f^1) \) enumera todos los funtores monádicos de \( \mathcal L_{\rm arp} \), es decir, que si \( H(0) = 2 \), con eso estamos diciendo que el primer funtor monádico de \( \mathcal L_{\rm arp} \) es el funtor que, como número natural, es el número \( 2 \), es decir, el funtor \( S \), mientras que \( H(1) \) es el número natural que, como funtor de \( \mathcal L_{\rm arp} \) es el segundo funtor en orden creciente, etc.

Más precisamente, lo que hemos probado al demostrar esto en ARP es que la función \( H \), por ser la función denotada por un funtor, es recursiva primitiva. Hemos probado que la función que a cada número natural \( k \) le asigna el número natural \( H(k) \) que, visto como sucesión finita de números naturales es el \( k \)-ésimo funtor monádico de \( \mathcal L_{\rm arp} \), es recursiva primitiva.

La enumeración, en la práctica (en el sentido de que es una forma de hacerlo, no necesariamente el más eficiente, ni mucho menos) es: sabemos que \( H(0) = 2 \). Si ya hemos calculado \( H(k)=m \):

1) Calculamos el funtor \( g \) correspondiente a \( m \) (es decir, calculamos la sucesión de números naturales que se identifica con \( m \)).

2) Le anteponemos \( p_1^1 = \left<2, 1, 0, 1, 0\right> \) a esa sucesión, con lo que obtenemos el número \( M \) correspondiente a un funtor mayor que \( m \).

3) Examinamos todos los números entre \( m+1 \) y \( M \) viendo cuáles se corresponden con funtores y nos quedamos con el menor de ellos, que será \( H(k+1) \).

Así, si llamamos \( \bar f_k^1 \) al funtor de \( \mathcal L_{\rm arp} \) que, visto como número natural, es igual a \( H(k) \), tenemos una enumeración de todos los funtores monádicos de \( \mathcal L_{\rm arp} \), de modo que en ARP se demuestra que \( {\color{blue}f^1_k} = f^1_{\bar k} \), donde \( \bar k \) es el numeral de \( k \).

A su vez, la sucesión \( F(\bar f^1_k) \) es una enumeración (con repeticiones) de las funciones monádicas recursivas primitivas.

¡Ah, vale! Me lio un poco el párrafo siguiente, donde entonces es igual mejor poner esto, ¿no?

Relajando el formalismo por caridad cristiana, este "teorema" afirma que el funtor \( \phi \) cumple (bajo las hipótesis obvias en cada caso):

  • \( \phi({\color{blue}S},{\color{red} \langle}n{\color{red} \rangle}) = n+1 \).

  • \( \phi({\color{blue}c}, {\color{red} \langle}n{\color{red} \rangle}) = 0 \).
[...]

¡Chivato! Ahora me reñirá a mí argentinator, porque ahí estaba feo haber puesto \( n \) en vez de \( \left<n\right> \).

Esta vez es culpa mía. Me faltaba una F y entonces resulta que F son dos cosas, así que mejor de esta forma:
Citar
En otras palabras, la función diádica \( H(f, s) \) que, cuando \( f \), visto como sucesión de números naturales, corresponde a un funtor \( n \)-ádico de \( {\color{blue}\mathcal L_{\rm arp}} \) y \( s \) es una sucesión de longitud \( n \), calcula

\( H(f, s) = F(f)(s_0,\ldots, s_{n-1}) \)

(y para otros argumentos toma el valor \( 0 \)) la puede calcular un ordenador, pero no es recursiva primitiva.

Vale, ahora le veo algo más de sentido, pero sigo sin tenerlo claro. Estas diciendo que \( f \) es un funtor de \( {\color{blue}\mathcal L_{\rm arp}} \), pero luego consideras \( F(f) \) como la función recursiva denotada por \( f \) y esto no me cuadra siendo un funtor de \( {\color{blue}\mathcal L_{\rm arp}} \) y no de ARP.

Ahí estaba yo mareando la perdiz, y al final puse en azul un \( \mathcal L_{\rm arp} \) que no debería haber estado en azul. En realidad es lo mismo que he dicho más arriba, pero ahora para funtores no necesariamente monádicos:

Tenemos el funtor monádico \( f \) que enumera todos los funtores de \( \mathcal L_{\rm arp} \), y entonces, simplemente interpretando lo que significa el teorema que dice que ese funtor enumera todos los funtores, vemos que la función monádica recursiva primitiva \( H = F(f) \) enumera todos los funtores de \( \mathcal L{\rm arp} \), en el sentido de que \( H(7) \) es el séptimo número natural (en orden creciente) que, visto como sucesión de números naturales e identificando \( 0 \) con el signo \( 0 \), \( 1 \) con el signo \( S \), etc., resulta ser un funtor de \( \mathcal L_{\rm arp} \) (en negro).

Me espero mejor a que aclaremos la notación y entienda bien que quieres decir para exponer la otra duda que quedó pendiente en el mensaje anterior por el lío que hice al parecer que hacía referencia a la siguiente cita en lugar de a la que tocaba.

He modificado un poco la frase en el hilo. La relación por la que preguntas es que si fuera recursiva primitiva la función \( H \) que a cada funtor \( n \)-ádco \( f \) (identificado con un número natural) y a cada \( n \)-tupla \( s \) de números naturales (identificada con otro número natural) les hace corresponder \( H(f, s) = F(f)(s) \), entonces habría un funtor \( \Phi \) tal que \( F(\Phi) = H \) y ese funtor \( \Phi \) cumpliría el "teorema".

Decías más arriba que no hemos demostrado que a cada función recursiva primitiva le corresponde un funtor. He mirado la respuesta #3 y, efectivamente, no lo dice explícitamente, más allá de la declaración de intenciones: "Ahora vamos a darle un nombre en \( \mathcal L_{\rm arp} \) a cada función recursiva primitiva", pero es obvio que de la definición de función recursiva primitiva se sigue que toda función es denotada por un funtor.

Entiendo. Pero, aun así, supongo que por razones más complejas que las que podemos ver con lo que sabemos, es igualmente imposible obtener el funtor diádico que formalice la definición de "satisfacción" en las condiciones que ya se han mencionado, ¿no?

Existe el teorema de Tarski, que afirma que en una teoría aritmética de primer orden razonable capaz de formalizar su propia sintaxis no se puede definir una fórmula \( \vDash \alpha \) que se interprete en un modelo \( M \) como que la fórmula \( \alpha \) es verdadera en dicho modelo. El argumento de fondo es que entonces se podría construir una fórmula que fuera equivalente a que ella misma es falsa.

Esto no se aplica directamente a ARP, porque no es una teoría de primer orden, pero, aunque no me he puesto a comprobar los detalles, sospecho que todo vale igualmente.