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

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

20 Julio, 2023, 10:17 am
Respuesta #220

Eparoh

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

Tienes razón con las correcciones, pero en realidad el error era otro: es que el caso que quería poner como ejemplo era \( D<0, d>0 \) (el mismo que en la primera parte de la demostración), y las cuentas que has rectificado son las correctas para ese caso. Lo he dejado con el caso \( D<0, d>0 \) porque es más representativo.

Ah claro, tiene más sentido ::)

Pero, aún así, aquí si sigue habiendo esta errata, ¿no?

\( c^*(D, d) = \cases{\phantom-c(|D|, |d|)&si $D\geq 0$, $d>0$ o $D<0$, $d{\color{red}<}0$, $r(|D|, |d|)=0$,\cr
-c(|D|, |d|)&si $D\geq 0$, $d<0$ o $D<0$, $d{\color{red}>}0$, $r(|D|, |d|)=0$,\cr -c(|D|,|d|)-1&si $D<0$, $d>0$, $r(|D|, |d|)>0$, \cr
\phantom- c(|D|, |d|)+1&si $D<0$, $d<0$, $r(|D|, |d|)>0$,}
 \)

Porque si \( z \) es un número entero, entonces \( z = [a, b] \), para cierto par de números naturales \( a, b \), pero eso significa que \( z \) es el mínimo \( z = \left<u, v\right>_\infty \), con \( (u, v)\,R\, (a, b) \), pero entonces \( u = z_0, v = z_1 \), y así \( z = \left<z_0, z_1\right> \) y \( [z_0, z_1] = [a, b] = z \), luego se cumple \( \exists ab<z\, z = [a, b] \) tomando \( a = z_0, b = z_1 \).

En realidad, podría haber definido más fácilmente \( z \in \mathbb Z\equiv z = [z_0, z_1] \).

Vale, todo claro. Me había liado por utilizar \( a,b \), con lo que me has comentado efectivamente es fácil ver que cualquier natural de la forma \( [c,d] \) es un entero bajo dicha definición que es justo lo que quería comprobar.

Si sólo quieres sucesiones finitas de números enteros:

\( \forall i<\ell(p)\, p_i\in \mathbb Z \)       8^)

Pero en realidad tienes que pedir que el coeficiente director sea no nulo, porque las sucesiones \( \left<1, 2, 3\right>_\infty \) y \( \left<1, 2, 3, 0, 0\right>_\infty \) deben definir el mismo polinomio \( 1+2x+3x^2 \), así que la definición correcta es:

\( p\in \mathbb Z[x]\equiv \forall i<\ell(p)\, p_i\in \mathbb Z\land (p = 0\lor (\ell(p)>0\land p_{\ell(p)\dot{-}1}\neq 0)) \).

Vale, vale, es más sencillo de lo que pensaba. Sin embargo, he intentado definir la suma y el producto y me he atascado porque no veo como se pueden definir sucesiones de longitud variable con los términos que uno quiera.

Por ejemplo, para la suma había pensado algo como definir el funtor

\( F(p,q,i)=\left\{ \begin{array}{lcl} p_i+q_i & \text{si} & i < \min\{\ell(p), \ell(q)\}\\
p_i & \text{si} & \min\{\ell(p), \ell(q)\} \leq i < \max\{\ell(p), \ell(q)\} \wedge \max\{\ell(p), \ell(q)\}=\ell(p) \\
q_i & \text{si} & \min\{\ell(p), \ell(q)\} \leq i < \max\{\ell(p), \ell(q)\} \wedge \max\{\ell(p), \ell(q)\}=\ell(q) \\
0 & \text{si} & \max\{\ell(p), \ell(q)\} \leq i
\end{array} \right. \)

y luego definir algo como

\( p+q=\langle F(p,q,0), \cdots, F(p,q,\max\{\ell(p), \ell(q)\} \dot{-}1) \rangle_\infty \)

Pero esta última definición no es correcta pues el miembro de la derecha no es un término fijo, sino que varía dependiendo de la longitud de \( p \) y \( q \). ¿Cómo podemos definir entonces la suma y el producto de polinomios?

No hace falta que hagas una nueva respuesta al hilo con esto si no quieres. Con saber como se pueden definir estas dos operaciones y ver un poco como se puede trabajar con sucesiones de longitud variable dentro de ARP me sobra.

Un saludo.



Justo antes de publicar el mensaje se me ha ocurrido una idea, pero me parece tan rebuscada (y no se si es correcta) que aún así, me gustaría saber como lo harías tú (porque para el producto, siguiendo este camino lo veo chungo...). Y bueno, ya puestos, si es correcto lo que he hecho aunque sea un "monstruo".

Se me ha ocurrido que podría definir el término

\( T(p,q) \equiv \{F(i,p,q) \mid i \in I_{\max\{\ell(p), \ell(q)\}}\} \)

para poder definir entonces la función \( f(p,q): I_{\max\{\ell(p), \ell(q)\}} \longrightarrow T(p,q) \) dada por

\( f(p,q) \equiv \{\langle i, F(p,q,i)  \rangle_\infty \mid i \in I_{\max\{\ell(p), \ell(q)\}} \} \)

y, finalmente, definir el funtor

\( p+q=H\left(T(p,q),I_{\max\{\ell(p), \ell(q)\}}\right)(f(p,q)) \)

PD: Mirando bien el hilo para tratar de no meter la pata con lo que he escrito me he dado cuenta de esta errata:

Diremos que \( f \) es una aplicación de un conjunto \( x \) en un conjunto \( y \) si cumple:

\( f: x\longrightarrow y\equiv f\subset x\times y\land \forall u\in {\color{red} x}\exists! v\in y\,\left<u,v\right>_\infty\in f. \)

EDITO

Me he dado cuenta leyendo lo último que has añadido a la respuesta #17 de dos cosas:

1. Has utilizado la misma notación para el funtor que defines al comenzar el añadido y para el que ya definiste en su momento justo antes del teorema de recursión completa y creo que esto puede ser un buen lío. Me espero a que corrijas esto para seguir leyendo, porque también tengo dudas sobre la demostración y prefiero esperar a que la notación esté aclarada.

2. Con dicha definición que se dio justo antes del teorema de recursión completa me he dado cuenta de que con mi primer intento si se podría definir
\( p+q=F|_{\max\{\ell(p), \ell(q)\}}(p,q) \)
¿Verdad?

20 Julio, 2023, 03:48 pm
Respuesta #221

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Pero, aún así, aquí si sigue habiendo esta errata, ¿no?

\( c^*(D, d) = \cases{\phantom-c(|D|, |d|)&si $D\geq 0$, $d>0$ o $D<0$, $d{\color{red}<}0$, $r(|D|, |d|)=0$,\cr
-c(|D|, |d|)&si $D\geq 0$, $d<0$ o $D<0$, $d{\color{red}>}0$, $r(|D|, |d|)=0$,\cr -c(|D|,|d|)-1&si $D<0$, $d>0$, $r(|D|, |d|)>0$, \cr
\phantom- c(|D|, |d|)+1&si $D<0$, $d<0$, $r(|D|, |d|)>0$,}
 \)

Vaya, se me pasó. Me sabe mal que, encima del tiempo que gastas detectando erratas, tengas que pasar más tiempo comprobando que te hago caso.

¿Cómo podemos definir entonces la suma y el producto de polinomios?

No hace falta que hagas una nueva respuesta al hilo con esto si no quieres. Con saber como se pueden definir estas dos operaciones y ver un poco como se puede trabajar con sucesiones de longitud variable dentro de ARP me sobra.

Ante todo, este tipo de problemas requiere una mentalidad positiva: uno tiene que pensar que si no hay inconveniente en explicarle a alguien qué tiene que hacer para sumar dos sucesiones \( \left<2, 3, 0, 2\right>_\infty+\left<0, 1, 0, 2, 7\right>_\infty \) o para multiplicarlas pensando que son polinomios, de modo que sólo es hacer un cálculo que no tiene ninguna complicación con posibles infinitos, entonces eso se tiene que poder formalizar en ARP. La pregunta no es si se puede, sino cómo hacerlo de la forma más elegante posible, porque "muy a lo bruto" se tiene que poder seguro. De hecho, salvo por que has pasado por alto un detalle, tú mismo has definido correctamente la suma que querías definir.

Pongo aquí una forma posible, sin perjuicio de que a alguien se le ocurra algo más fácil, que es esencialmente lo mismo que has hecho tú, pero en términos que valen tanto para la suma como para el producto.

En primer lugar definimos las sucesiones nulas (donde el \( 0 \) en los miembros derechos es siempre el número entero \( 0 \)):

\( 0_0 = 0,\qquad 0_{n+1} = 0_n\frown \left<0\right>_\infty \)

Ahora definimos \( n(s) = \mu i\leq \ell(s)(s = s|_i\frown 0_{\ell(s)\dot - i}) \), que nos da el máximo índice a partir del cual la sucesión \( s \) tiene todo ceros (enteros) que será \( \ell(s) \) si \( s \) no acaba en una sucesión de ceros enteros.

Así podemos definir \( R(s) = s|_{n(s)} \), de modo que

\( R(s) = 0 \lor (\ell(R(s))>0 \land s = R(s)\frown 0_{\ell(s)\dot- \ell(R(s))}\land R(s)_{\ell(R(s))\dot -1}\neq 0) \)

Así, \( \forall n i<\ell(s)\, s_i\in \mathbb Z\rightarrow R(s)\in \mathbb Z[x]. \)

En resumen: si tenemos una sucesión finita \( s \) de enteros, el funtor \( R \) le quita los ceros finales.

Por otro lado, podemos definir el coeficiente \( i \)-ésimo de un polinomio como

\( C_i(p) = \cases{p_i&si $i<\ell(p)$,\cr 0&si $i\geq \ell(p)$.} \)

Así podemos definir la suma de dos polinomios definiendo primero el funtor: \( S(p, q, i) = C_i(p)+C_i(q) \) y entonces

\( p + q = R(S(p, q)|_{\max\{\ell(p), \ell(q))\}}) \).

Para el producto consideramos

\( P(p, q,i) = \sum\limits_{j\leq i}C_j(p)\cdot C_{i\dot- j}(q) \),

donde el sumatorio es el que acabo de definir en la respuesta #19 partiendo de la suma de números enteros, y así

\( p\cdot q = R(P(p, q)|_{\ell(p)+\ell(q)}) \).

2. Con dicha definición que se dio justo antes del teorema de recursión completa me he dado cuenta de que con mi primer intento si se podría definir
\( p+q=F|_{\max\{\ell(p), \ell(q)\}}(p,q) \)
¿Verdad?

Sí, enunciado así es esencialmente lo mismo que he hecho yo, salvo que te falta aplicar el funtor \( R \) para eliminar los posibles ceros que surjan de las posibles cancelaciones de coeficientes.

1. Has utilizado la misma notación para el funtor que defines al comenzar el añadido y para el que ya definiste en su momento justo antes del teorema de recursión completa y creo que esto puede ser un buen lío. Me espero a que corrijas esto para seguir leyendo, porque también tengo dudas sobre la demostración y prefiero esperar a que la notación esté aclarada.

He cambiado la notación, pero en realidad no era algo grave. La moraleja del teorema de recursión que he añadido es que podemos definir un funtor \( F \) sobre una sucesión finita \( s \) supuesto que ya está definido sobre las subsucesiones de \( \mbox{Sub}(s) \). En la práctica no será necesario escribir nunca la definición en términos de \( F|_{\rm {Sub}(s)} \), sino que simplemente, al definir \( F(s) \) podremos usar \( F(t) \) para cualquier \( t\in \mbox{Sub}(s) \) que nos interese. Veremos muchos ejemplos de esto en el próximo mensaje del hilo. Y, aun si escribiéramos, \( F|_{\rm {Sub}(s)} \), el contexto dejaría claro que nos referimos a la última definición y no a la primera.

20 Julio, 2023, 04:16 pm
Respuesta #222

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
He añadido al final de la respuesta #17 un teorema de recursión que me hará falta para formalizar ARP en ARP.

Ah, pero eso sólo puede ser obra del Maligno.  >:D

Sí, creo que fue Gödel el primero que empezó a hacer cosas así.

El caso es que creo que esto responde en parte una de tus dudas existenciales: siempre te has planteado qué hay que suponer para construir una teoría axiomática que permita trabajar formalmente en matemáticas. Pues bien, si nos restringimos a la parte sintáctica (es decir, sin meternos en modelos, verdad, etc.) en ARP puedes formalizar la construcción de ARP e igualmente la de ZFC, luego la respuesta a tu pregunta existencial es esa: si quieres definir ZFC (sin usar, obviamente, ZFC) lo único que necesitas aceptar que es intuitivamente válido es lo necesario para construir informalmente ARP, que a su vez no es nada que no sea formalizable en ARP, es decir, que sólo necesitas aceptar que son intuitivamente ciertos los axiomas y las reglas de inferencia de ARP.

Otra cosa es si además quieres convencerte de que la lógica de ZFC es semánticamente completa, es decir, todo lo relacionado con el teorema de completitud de Gödel: que una teoría es consistente si y sólo si tiene un modelo, etc. Para eso hace falta un poquito más que ARP, pero no es trivial que baste un poquito más que ARP. Más precisamente, para probar el teorema de completitud (en su versión para modelos numerables) hay que trabajar en una teoría aritmética de segundo orden suponiendo lo que se llama "lema de König débil", pero puede probarse que dicha teoría es consistente si y sólo si lo es ARP, así que no es mucho suponer.

Estoy hablando de la teoría llamada WKL\( _0 \), descrita, por ejemplo aquí:

https://en.wikipedia.org/wiki/Reverse_mathematics

20 Julio, 2023, 05:53 pm
Respuesta #223

argentinator

  • Consultar la FIRMAPEDIA
  • Administrador
  • Mensajes: 7,797
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
He añadido al final de la respuesta #17 un teorema de recursión que me hará falta para formalizar ARP en ARP.

Ah, pero eso sólo puede ser obra del Maligno.  >:D

Sí, creo que fue Gödel el primero que empezó a hacer cosas así.

El caso es que creo que esto responde en parte una de tus dudas existenciales: siempre te has planteado qué hay que suponer para construir una teoría axiomática que permita trabajar formalmente en matemáticas. Pues bien, si nos restringimos a la parte sintáctica (es decir, sin meternos en modelos, verdad, etc.) en ARP puedes formalizar la construcción de ARP e igualmente la de ZFC, luego la respuesta a tu pregunta existencial es esa: si quieres definir ZFC (sin usar, obviamente, ZFC) lo único que necesitas aceptar que es intuitivamente válido es lo necesario para construir informalmente ARP, que a su vez no es nada que no sea formalizable en ARP, es decir, que sólo necesitas aceptar que son intuitivamente ciertos los axiomas y las reglas de inferencia de ARP.

Otra cosa es si además quieres convencerte de que la lógica de ZFC es semánticamente completa, es decir, todo lo relacionado con el teorema de completitud de Gödel: que una teoría es consistente si y sólo si tiene un modelo, etc. Para eso hace falta un poquito más que ARP, pero no es trivial que baste un poquito más que ARP. Más precisamente, para probar el teorema de completitud (en su versión para modelos numerables) hay que trabajar en una teoría aritmética de segundo orden suponiendo lo que se llama "lema de König débil", pero puede probarse que dicha teoría es consistente si y sólo si lo es ARP, así que no es mucho suponer.

Estoy hablando de la teoría llamada WKL\( _0 \), descrita, por ejemplo aquí:

https://en.wikipedia.org/wiki/Reverse_mathematics

La cuestión es que ARP es su propia metateoría.
Ya no se sabe qué fue primero, si el huevo o la gallina.

Tendría que haber anticipado un final maléfico como éste.


20 Julio, 2023, 09:37 pm
Respuesta #224

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
La cuestión es que ARP es su propia metateoría.
Ya no se sabe qué fue primero, si el huevo o la gallina.

Tendría que haber anticipado un final maléfico como éste.

 ::)    Tendrías que ir a un maestro zen para que te ayude a mirar en tu interior y descubrir qué necesitas realmente para ser feliz.

Buscabas saber precisamente qué necesitas para fundamentar la matemática: tienes ante ti una respuesta (al menos para la parte sintáctica) y ahora te asaltan preocupaciones darwinistas.

Bueno, mejor discutir esto cuando hayamos visto la formalización de ARP.


22 Julio, 2023, 12:12 pm
Respuesta #225

Eparoh

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

De la Respuesta #19 está todo claro y no he visto ninguna errata, así que pongo primero las erratas y pequeños comentarios sobre el añadido a la respuesta #17, y luego paso a exponer algunas dudas sobre la misma y sobre lo último que me has comentado de los polinomios.

ERRATAS

Así \( \mbox{Sub}(s) \) está formado por las subsucesiones propias \( t \) de \( s \), en el sentido de que \( s = x\frown\ t\frown\ y \), para ciertos \( x, y \).

La propia \( s \) no forma parte de \( \mbox{Sub}(s) \), ¿no?

Teorema Si \( G \) es un funtor de rango \( n+2 \), existe un funtor \( F \) de rango \( n+1 \) tal que

\( F(x_1, \ldots, x_n, s) = G(x_1, \ldots, x_n, s, [F]|_{\rm Sub(s)}(x_1,\ldots, x_n)). \)

En otros términos: podemos definir un funtor especificando el valor de \( F(x_1, \ldots, x_n, s) \) supuesto definido \( F(x_1, \ldots, x_n, t) \) para todo \( t\in \mbox{Sub}(s) \).

Demostración

[...]

Sea
\( S_k = \{{\color{red} s}\in \bigcup\limits_{i\leq k}S_i(I_k)\mid L(s)\leq k\}, \)

[...]

[cerrar]

DUDAS

Ahora, mi primera duda es respecto a la demostración del nuevo teorema de recursión. No es que tenga ninguna duda en sí sobre que haces en la demostración ni que vea nada erróneo, pero (ya me conoces) he intentado demostrarla usando formalmente el teorema de recursión completa que diste en la Respuesta #14, es decir, he modificado tu prueba para definir explícitamente la función \( G \) que aparece en dicho teorema (la cual he llamado \( T \)) y me gustaría saber si lo que he hecho es correcto:

Nueva demostración sin utilizar recursión completa

Spoiler
Sea \( L(s) = \sum\limits_{i<\ell(s)}(s_i+1) \). Así es claro que

\( t\in \mbox{Sub}(s)\rightarrow L(t)<L(s). \)

Sea

\( S_k = \left\{s\in \bigcup\limits_{i\leq k}S_i(I_k)\mid L(s)\leq k\right\}, \)

de modo que \( s\in S_k\leftrightarrow L(s)\leq k \).

Por el Teorema de definición de funtores mediante términos sabemos que existe un funtor \( H \) de rango \( n+2 \) que cumple (abreviamos \( \bar{x} \equiv x_1, \cdots, x_n \)):

\(
\begin{align*}
H(\bar x, s,0) & =G(\bar{x},0 ,0)\\
H(\bar x, s,k+1) & =G\left(\bar x, s, \left\{ \left\langle u, H(\bar x, u, k) \right\rangle_\infty \mid u \in \mbox{Sub}(s) \right\} \right)
\end{align*}
 \)

Observemos ahora que se cumple
\( s \in S_k \rightarrow H(\bar{x},s,k+1)=H(\bar{x},s,k). \qquad (1) \)

Demostración
Veamoslo por inducción en \( k \).

Si \( k=0 \) entonces \( S_0=\{0\} \), con lo que si \( s \in S_0 \) entonces claramente es \( s=0 \) y

\( H(\bar x, s, 1) = G(\bar x, s, \{\langle u,H(\bar x, u, 0) \rangle_\infty \mid u \in \text{Sub}(0)\}) =G(\bar x, 0 ,0) = H(\bar x, s, 0) \)

Supongamos pues que es cierto para \( k \) y sea \( s \in S_{k+1} \). Tenemos entonces que

\( H(\bar x, s, k+2) = G\left(\bar{x},s, \left\{ \left\langle u, H(\bar x, u, k+1) \right\rangle_\infty \mid u \in \mbox{Sub}(s) \right\} \right) \)

Ahora bien, observemos que si \( u \in \mbox{Sub}(s) \) entonces \( u \in S_k \) pues \( L(u) < L(s) \leq k+1 \) (la segunda desigualdad se da por ser \( s \in S_{k+1} \)), con lo que por hipótesis de inducción se tiene que

\( H(\bar x, u, k+1) = H(\bar x, u, k), \)

y con ello obtenemos que

\(
\begin{align*}
H(\bar x, s, k+2) & = G\left(\bar{x},s, \left\{ \left\langle u, H(\bar x, u, k+1) \right\rangle_\infty \mid u \in \mbox{Sub}(s) \right\} \right) =\\
 & = G\left(\bar{x},s, \left\{ \left\langle u, H(\bar x, u, k) \right\rangle_\infty \mid u \in \mbox{Sub}(s) \right\} \right) =\\
 & = H(\bar x, s, k+1). \quad \blacksquare
\end{align*}
 \)
[cerrar]

Además, también se cumple

\( L(s) \leq k \rightarrow H(\bar{x},s,k)=H(\bar{x},s,L(s)). \qquad (2) \)

Demostración
Veamoslo por inducción en \( k \).

Si \( k=0 \) entonces \( L(s)=0 \) y el resultado es trivialmente cierto.

Supogamos pues que es cierto para \( k \) y sea \( s \) tal que \( L(s) \leq k+1 \).

Si \( L(s)=k+1 \) la igualdad es trivialmente cierta, con lo que supongamos que \( L(s) \leq k \). En este caso, por hipótesis de inducción tenemos que

\( H(\bar x, s, k) = H(\bar x, s, L(s)), \)

y como \( s \in S_k \) (por ser \( L(s) \leq k \)) por \( (1) \) tenemos que

\( H(\bar x, s, k+1)=H(\bar x, s, k), \)

con lo que juntando las dos igualdades concluimos la inducción. \( \quad \blacksquare \)
[cerrar]

Definiendo ahora

\( F(\bar x, s) = H(\bar x, s, L(s)) \)

obtenemos que \( F \) es el funtor buscado.

Efectivamente, si \( s=0 \) entonces

\( F(\bar x, s)=H(\bar x, 0,0) = G( \bar x, 0 ,0) = G \left ( \bar x, s, [F]|_{\rm{Sub}(s)}(\bar x) \right). \)

Por otra parte, si \( s \neq 0 \) entonces \( L(s)>0 \) y

\( F(\bar x, s) =H(\bar x, s,L(s)) = G\left(\bar{x},s, \left\{ \left\langle u, H(\bar x, u, L(s) \dot{-}1) \right\rangle_\infty \mid u \in \mbox{Sub}(s) \right\} \right), \)

pero si \( u \in \mbox{Sub}(s) \) entonces \( L(u) < L(s) \), es decir, \( L(u) \leq L(s) \dot{-} 1 \), con lo que por \( (2) \) es

\( H(\bar x, u, L(s) \dot{-}1) = H(\bar x, u, L(u)) \)

y así

\( \begin{align*}
F(\bar x, s) &  = G\left(\bar{x},s, \left\{ \left\langle u, H(\bar x, u, L(s) \dot{-}1) \right\rangle_\infty \mid u \in \mbox{Sub}(s) \right\} \right) = \\
 & = G\left(\bar{x},s, \left\{ \left\langle u, H(\bar x, u, L(u)) \right\rangle_\infty \mid u \in \mbox{Sub}(s) \right\} \right) =\\
 & = G\left(\bar{x},s, \left\{ \left\langle u, F(\bar x, u) \right\rangle_\infty \mid u \in \mbox{Sub}(s) \right\} \right) = G\left(\bar{x},s, [F]|_{\rm{Sub}(s)}(\bar x) \right) \quad \blacksquare
\end{align*} \)
[cerrar]

Demostración  anterior con recursión completa

Spoiler
Sea \( L(s) = \sum\limits_{i<\ell(s)}(s_i+1) \). Así es claro que

\( t\in \mbox{Sub}(s)\rightarrow L(t)<L(s). \)

Sea

\( S_k = \left\{s\in \bigcup\limits_{i\leq k}S_i(I_k)\mid L(s)\leq k\right\}, \)

de modo que \( s\in S_k\leftrightarrow L(s)\leq k \).

Consideremos ahora el funtor de rango \( n+3 \) (donde abreviamos \( \bar{x} \equiv x_1, \cdots, x_n \))


\( T(\bar{x}, s, k, q)=\left\{ \begin{array}{lcc}
G(\bar{x},0 ,0) & \text{si} & {\color{green} k}=0 \\\\
G\left( \bar{x}, s, \left\{ \left\langle u, S_s^u \left(p_{\ell(q) \dot{-} 1}(q)\right) \right\rangle_\infty \mid u \in \mbox{Sub}(s) \right\} \right) & \text{si} & {\color{green} k} \neq 0 \end{array} \right. \)


y por el Teorema de Recursión Completa sabemos que existe un funtor \( H \) de rango \( n+2 \) tal que

\( H(\bar{x},s,k)=T\left(\bar{x},s,k, H|_{k}(\bar{x}, s) \right). \)

Observemos ahora que se cumple
\( s \in S_k \rightarrow H(\bar{x},s,k+1)=H(\bar{x},s,k). \qquad (1) \)

Demostración
Veamoslo por inducción en \( k \).

Si \( k=0 \) entonces \( S_0=\{0\} \), con lo que si \( s \in S_0 \) entonces claramente es \( s=0 \) y

\( \color{green}\begin{align*}
H(\bar x, s, 1) & = T\left(\bar{x},0,1, H|_{1}(\bar{x}, 0) \right) = G(\bar x, s, \{\langle u,H(\bar x, u, 0) \rangle_\infty \mid u \in \mbox{Sub}(0)\})=\\
 & =G(\bar x, 0 ,0) = T\left(\bar{x},0,0, H|_{0}(\bar{x}, 0) \right) = H(\bar x, s, 0)
\end{align*} \)

Supongamos pues que es cierto para \( k \) y sea \( s \in S_{k+1} \) (con \( s \neq 0 \) pues dicho caso es trivial por la definición de \( T \) y \( H \)). Tenemos entonces que

\( \begin{align*}
H(\bar x, s, k+2) & = T\left(\bar{x},s,k+2, H|_{k+2}(\bar{x}, s) \right)=\\
 &= G\left(\bar{x},s, \left\{ \left\langle u, H(\bar x, u, k+1) \right\rangle_\infty \mid u \in \mbox{Sub}(s) \right\} \right)
\end{align*} \)

Ahora bien, observemos que si \( u \in \mbox{Sub}(s) \) entonces \( u \in S_k \) pues \( L(u) < L(s) \leq k+1 \) (la segunda desigualdad se da por ser \( s \in S_{k+1} \)), con lo que por hipótesis de inducción se tiene que

\( H(\bar x, u, k+1) = H(\bar x, u, k), \)

y con ello obtenemos que

\( \begin{align*}
H(\bar x, s, k+2) & = G\left(\bar{x},s, \left\{ \left\langle u, H(\bar x, u, k+1) \right\rangle_\infty \mid u \in \mbox{Sub}(s) \right\} \right) =\\
 & = G\left(\bar{x},s, \left\{ \left\langle u, H(\bar x, u, k) \right\rangle_\infty \mid u \in \mbox{Sub}(s) \right\} \right) =\\
 & = T\left(\bar{x},s,k+1, H|_{k+1}(\bar{x}, s) \right) = H(\bar x, s, k+1). \quad \blacksquare
\end{align*} \)
[cerrar]

Además, también se cumple

\( L(s) \leq k \rightarrow H(\bar{x},s,k)=H(\bar{x},s,L(s)). \qquad (2) \)

Demostración
Veamoslo por inducción en \( k \).

Si \( k=0 \) entonces \( {\color{green}L(}s{\color{green})}=0 \) y por la definición de \( T \) y \( H \) el resultado es trivialmente cierto.

Supogamos pues que es cierto para \( k \) y sea \( s \) tal que \( L(s) \leq k+1 \).

Si \( L(s)=k+1 \) la igualdad es trivialmente cierta, con lo que supongamos que \( L(s) \leq k \). En este caso, por hipótesis de inducción tenemos que

\( H(\bar x, s, k) = H(\bar x, s, L(s)), \)

y como \( s \in S_k \) (por ser \( L(s) \leq k \)) por \( (1) \) tenemos que

\( H(\bar x, s, k+1)=H(\bar x, s, k), \)

con lo que juntando las dos igualdades concluimos la inducción. \( \quad \blacksquare \)
[cerrar]

Definiendo ahora

\( F(\bar x, s) = H(\bar x, s, L(s)) \)

obtenemos que \( F \) es el funtor buscado.

Efectivamente, si \( s=0 \) entonces

\( \begin{align*}
F(\bar x, s)=H(\bar x, 0,0) = T(\bar x, 0, 0, 0) = G( \bar x, 0 ,0) = G \left ( \bar x, s, [F]|_{\rm{Sub}(s)}(\bar x) \right).
\end{align*} \)

Por otra parte, si \( s \neq 0 \) entonces \( L(s)>0 \) y

\( \begin{align*}
F(\bar x, s) & =H(\bar x, s,L(s)) = T\left(\bar x, s, L(s), H|_{L(s)}(\bar x, s)\right) =\\
 & = G\left(\bar{x},s, \left\{ \left\langle u, H(\bar x, u, L(s) \dot{-}1) \right\rangle_\infty \mid u \in \mbox{Sub}(s) \right\} \right),
\end{align*} \)

pero si \( u \in \mbox{Sub}(s) \) entonces \( L(u) < L(s) \), es decir, \( L(u) \leq L(s) \dot{-} 1 \), con lo que por \( (2) \) es

\( H(\bar x, u, L(s) \dot{-}1) = H(\bar x, u, L(u)) \)

y así

\( \begin{align*}
F(\bar x, s) &  = G\left(\bar{x},s, \left\{ \left\langle u, H(\bar x, u, L(s) \dot{-}1) \right\rangle_\infty \mid u \in \mbox{Sub}(s) \right\} \right) = \\
 & = G\left(\bar{x},s, \left\{ \left\langle u, H(\bar x, u, L(u)) \right\rangle_\infty \mid u \in \mbox{Sub}(s) \right\} \right) =\\
 & = G\left(\bar{x},s, \left\{ \left\langle u, F(\bar x, u) \right\rangle_\infty \mid u \in \mbox{Sub}(s) \right\} \right) = G\left(\bar{x},s, [F]|_{\rm{Sub}(s)}(\bar x) \right) \quad \blacksquare
\end{align*} \)
[cerrar]

Respecto a esto:

Observemos además que si dos funtores \( F_1 \) y \( F_2 \) satisfacen el teorema anterior, entonces podemos probar que

\( F_1(x_1, \ldots, x_n, s) = F_2(x_1, \ldots, x_n, s). \)

Demostración
Si suponemos que \( F_1(x_1, \ldots, x_n, s) \neq F_2(x_1, \ldots, x_n, s) \), podemos considerar

\( {\color{blue} m}_0 \equiv \mu {\color{blue} m}\leq L(s)\exists t\in S_{\color{blue} m}\ F_1(x_1, \ldots, x_n, t) \neq F_2(x_1, \ldots, x_n, t) \)

A su vez, podemos tomar

\( t_0 \equiv \mu t\in S_{{\color{blue} m}_0}\ F_1(x_1, \ldots, x_n, t) \neq F_2(x_1, \ldots, x_n, t), \)

de modo que
\( F_1(x_1, \ldots, x_n, t_0) \neq F_2(x_1, \ldots, x_n, t_0) \)
, pero si
\( L(u)<L(t_0) {\color{red} \leq} {\color{blue} m}_0 \)
, entonces \( F_1(x_1, \ldots, x_n, u) = F_2(x_1, \ldots, x_n, u) \). Como

\( u\in \mbox{Sub}(t_0)\rightarrow L(u)<L(t_0), \)

resulta que\( [F_1]|_{\rm Sub(t_0)}(x_1, \ldots, x_n)=[F_2]|_{\rm Sub(t_0)}(x_1, \ldots, x_n) \), y entonces la hipótesis sobre \( F_1 \) y \( F_2 \) nos da que \( F_1(x_1, \ldots, x_n, t_0) = F_2(x_1, \ldots x_n, t_0) \), con lo que tenemos una contradicción.
[cerrar]

Lo que he cambiado en azul (las "\( n \)" por "\( m \)"), mejor así para que no haya confusión con el rango del funtor \( F \), ¿no?

Y, lo que he cambiado en rojo, estoy seguro que es un \( \leq \) porque \( t_0 \in S_{m_0} \), por tanto, ¿el "\( = \)" era una errata o me estoy perdiendo algo que hace que se pueda afinar más y poner el "\( = \)"?

Y, por último, de esa misma línea (sea con \( \leq \) o con \( = \)) se obtiene que \( u \in S_{m_0} \), luego si fuera \( F_1(x_1, \ldots, x_n, u) \neq F_2(x_1, \ldots, x_n, u) \), tendríamos que \( t_0 <u \) (por la definición de \( t_0 \)), ¿pero por qué esto no es posible? ¿Por qué de \( L(u) < L(t_0) \) se sigue que \( u < t_0 \)? Esto último no lo veo tan claro.

Respecto a los polinomios en \( \Bbb Z \) esta todo claro, salvo que tengo en algunos puntos pequeñas dudas sobre cuando estamos utilizando el cero entero o el cero natural, así que voy a citar tus mensajes al respecto y a marcar en rojo todos los que creo que son ceros enteros (los que no los dejo sin marcar), para que me digas si estoy en lo correcto:

\( p\in \mathbb Z[x]\equiv \forall i<\ell(p)\, p_i\in \mathbb Z\land (p = 0\lor (\ell(p)>0\land p_{\ell(p)\dot{-}1}\neq {\color{red} 0})) \).

En primer lugar definimos las sucesiones nulas (donde el \( 0 \) en los miembros derechos es siempre el número entero \( 0 \)):

\( 0_0 = 0,\qquad 0_{n+1} = 0_n\frown \left<{\color{red} 0}\right>_\infty \)

Ahora definimos \( n(s) = \mu i\leq \ell(s)(s = s|_i\frown 0_{\ell(s)\dot - i}) \), que nos da el máximo índice a partir del cual la sucesión \( s \) tiene todo ceros (enteros) que será \( \ell(s) \) si \( s \) no acaba en una sucesión de ceros enteros.

Así podemos definir \( R(s) = s|_{n(s)} \), de modo que

\( R(s) = 0 \lor (\ell(R(s))>0 \land s = R(s)\frown 0_{\ell(s)\dot- \ell(R(s))}\land R(s)_{\ell(R(s))\dot -1}\neq {\color{red} 0}) \)

Así, \( \forall n i<\ell(s)\, s_i\in \mathbb Z\rightarrow R(s)\in \mathbb Z[x]. \)

En resumen: si tenemos una sucesión finita \( s \) de enteros, el funtor \( R \) le quita los ceros finales.

Por otro lado, podemos definir el coeficiente \( i \)-ésimo de un polinomio como

\( C_i(p) = \cases{p_i&si $i<\ell(p)$,\cr {\color{red} 0}&si $i\geq \ell(p)$.} \)

Así podemos definir la suma de dos polinomios definiendo primero el funtor: \( S(p, q, i) = C_i(p)+C_i(q) \) y entonces

\( p + q = R(S(p, q)|_{\max\{\ell(p), \ell(q))\}}) \).

Para el producto consideramos

\( P(p, q,i) = \sum\limits_{j\leq i}C_j(p)\cdot C_{i\dot- j}(q) \),

donde el sumatorio es el que acabo de definir en la respuesta #19 partiendo de la suma de números enteros, y así

\( p\cdot q = R(P(p, q)|_{\ell(p)+\ell(q)}) \).

Por último, en esto que le comentas a argentinator me surge una duda.

El caso es que creo que esto responde en parte una de tus dudas existenciales: siempre te has planteado qué hay que suponer para construir una teoría axiomática que permita trabajar formalmente en matemáticas. Pues bien, si nos restringimos a la parte sintáctica (es decir, sin meternos en modelos, verdad, etc.) en ARP puedes formalizar la construcción de ARP e igualmente la de ZFC, luego la respuesta a tu pregunta existencial es esa: si quieres definir ZFC (sin usar, obviamente, ZFC) lo único que necesitas aceptar que es intuitivamente válido es lo necesario para construir informalmente ARP, que a su vez no es nada que no sea formalizable en ARP, es decir, que sólo necesitas aceptar que son intuitivamente ciertos los axiomas y las reglas de inferencia de ARP.

Otra cosa es si además quieres convencerte de que la lógica de ZFC es semánticamente completa, es decir, todo lo relacionado con el teorema de completitud de Gödel: que una teoría es consistente si y sólo si tiene un modelo, etc. Para eso hace falta un poquito más que ARP, pero no es trivial que baste un poquito más que ARP. Más precisamente, para probar el teorema de completitud (en su versión para modelos numerables) hay que trabajar en una teoría aritmética de segundo orden suponiendo lo que se llama "lema de König débil", pero puede probarse que dicha teoría es consistente si y sólo si lo es ARP, así que no es mucho suponer.

Estoy hablando de la teoría llamada WKL\( _0 \), descrita, por ejemplo aquí:

https://en.wikipedia.org/wiki/Reverse_mathematics

Por lo que has comentado ya, en los siguientes mensajes veremos como formalizar ARP dentro de ARP, y aquí comentas que es también posible formalizar ZFC. Ahora bien, también comentas que no es posible definir plenamente la semántica en ARP, pero si es posible hacerlo en ZFC y acabamos de decir que ZFC es formalizable en ARP. Por tanto, entiendo que lo que no es posible es formalizar la semántica probando en ARP (cosa que en ZFC si se podría) ciertos teoremas que relacionen las definiciones dadas sobre satisfacción y verdad con aspectos formales del tipo que ya me comentaste en el hilo sobre los ordinales menores a \( \epsilon_0 \), ¿no?

Un saludo.

EDITADO
REEDITADO

22 Julio, 2023, 01:55 pm
Respuesta #226

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Así \( \mbox{Sub}(s) \) está formado por las subsucesiones propias \( t \) de \( s \), en el sentido de que \( s = x\frown\ t\frown\ y \), para ciertos \( x, y \).

La propia \( s \) no forma parte de \( \mbox{Sub}(s) \), ¿no?

En efecto. Definimos \( \mbox{Sub}(s) \) para poder definir funtores sobre \( s \) suponiéndolos definidos sobre \( \mbox{Sub}(s) \), y para eso no podemos admitir a \( s \) en \( \mbox{Sub}(s) \).

La idea es que así, por ejemplo, podemos definir cuándo una cadena de signos es un funtor supuesto que ya sepamos distinguir cuáles de sus subcadenas son funtores.

Ahora, mi primera duda es respecto a la demostración del nuevo teorema de recursión. No es que tenga ninguna duda en sí sobre que haces en la demostración ni que vea nada erróneo, pero (ya me conoces) he intentado demostrarla usando formalmente el teorema de recursión completa que diste en la Respuesta #14, es decir, he modificado tu prueba para definir explícitamente la función \( G \) que aparece en dicho teorema (la cual he llamado \( T \)) y me gustaría saber si lo que he hecho es correcto:

No me he parado a ver los detalles de tu prueba porque hay una línea que a simple vista ya no me cuadra:

\( H(\bar{x},s,k)=T\left(\bar{x},s,k, H|_{k}(\bar{x}, s) \right). \)

Si esto estuviera bien, si \( s \) cumple \( L(s) = 100 \), estarías definiendo \( H(\bar x, s, 100) \) suponiendo que ya están definidos \( H(\bar x, s, 0), \ldots, H(\bar x, s, 99) \), pero ahí no tienes información suficiente. Lo que necesitas es tener definidos \( H(\bar x, t, 99) \) para todo \( t\in \mbox{Sub}(s) \).

El funtor \( H \) de rango \( n+2 \) que defines tú no es el funtor de rango \( n+1 \) que defino yo (para empezar, tienen rangos distintos), de manera que el mío no tiene la \( s \) como argumento, sino que para cada \( k \) calcula una función con dominio \( S_k \), de modo que al suponer definido \( H(\bar x, 99) \) sabes asignar imágenes a todas las sucesiones con \( L(t)<k \).

De hecho, ahora me doy cuenta de que ni siquiera es necesario usar recursión completa. En la prueba que yo doy se define en realidad \( H_k \) a partir de \( H_{k\dot-1} \). Ahora en cuanto pueda lo cambio, que sólo se trata de modificar un par de comentarios y toda la construcción vale sin cambios.

Lo que he cambiado en azul (las "\( n \)" por "\( m \)"), mejor así para que no haya confusión con el rango del funtor \( F \), ¿no?

Pues se nota que ya has saciado tu rencor, porque eso es una errata en toda regla.

Y, lo que he cambiado en rojo, estoy seguro que es un \( \leq \) porque \( t_0 \in S_{m_0} \), por tanto, ¿el "\( = \)" era una errata o me estoy perdiendo algo que hace que se pueda afinar más y poner el "\( = \)"?

Puedes poner un \( = \). Si fuera \( m' = L(t_0)<m_0 \), entonces \( m' \) contradiría la minimalidad de \( m_0 \).

Y, por último, de esa misma línea (sea con \( \leq \) o con \( = \)) se obtiene que \( u \in S_{m_0} \), luego si fuera \( F_1(x_1, \ldots, x_n, u) \neq F_2(x_1, \ldots, x_n, u) \), tendríamos que \( t_0 <u \) (por la definición de \( t_0 \)), ¿pero por qué esto no es posible? ¿Por qué de \( L(u) < L(t_0) \) se sigue que \( u < t_0 \)? Esto último no lo veo tan claro.

Es que la minimalidad de \( t_0 \) es irrelevante, la que importa, y no tienes en cuenta, es la de \( m_0 \). Si \( m' = L(u)<L(t_0) = m_0 \), pero fuera \( F_1(\bar x, u)\neq F_2(\bar x, u) \), entonces \( u\in S_{m'} \) y \( m' \) contradiría la minimalidad de \( m \).

Respecto a los polinomios en \( \Bbb Z \) esta todo claro, salvo que tengo en algunos puntos pequeñas dudas sobre cuando estamos utilizando el cero entero o el cero natural, así que voy a citar tus mensajes al respecto y a marcar en rojo todos los que creo que son ceros enteros (los que no los dejo sin marcar), para que me digas si estoy en lo correcto:

Sí, exacto.

El caso es que creo que esto responde en parte una de tus dudas existenciales: siempre te has planteado qué hay que suponer para construir una teoría axiomática que permita trabajar formalmente en matemáticas. Pues bien, si nos restringimos a la parte sintáctica (es decir, sin meternos en modelos, verdad, etc.) en ARP puedes formalizar la construcción de ARP e igualmente la de ZFC, luego la respuesta a tu pregunta existencial es esa: si quieres definir ZFC (sin usar, obviamente, ZFC) lo único que necesitas aceptar que es intuitivamente válido es lo necesario para construir informalmente ARP, que a su vez no es nada que no sea formalizable en ARP, es decir, que sólo necesitas aceptar que son intuitivamente ciertos los axiomas y las reglas de inferencia de ARP.

Otra cosa es si además quieres convencerte de que la lógica de ZFC es semánticamente completa, es decir, todo lo relacionado con el teorema de completitud de Gödel: que una teoría es consistente si y sólo si tiene un modelo, etc. Para eso hace falta un poquito más que ARP, pero no es trivial que baste un poquito más que ARP. Más precisamente, para probar el teorema de completitud (en su versión para modelos numerables) hay que trabajar en una teoría aritmética de segundo orden suponiendo lo que se llama "lema de König débil", pero puede probarse que dicha teoría es consistente si y sólo si lo es ARP, así que no es mucho suponer.

Estoy hablando de la teoría llamada WKL\( _0 \), descrita, por ejemplo aquí:

https://en.wikipedia.org/wiki/Reverse_mathematics

Por lo que has comentado ya, en los siguientes mensajes veremos como formalizar ARP dentro de ARP, y aquí comentas que es también posible formalizar ZFC. Ahora bien, también comentas que no es posible definir plenamente la semántica en ARP, pero si es posible hacerlo en ZFC y acabamos de decir que ZFC es formalizable en ARP. Por tanto, entiendo que lo que no es posible es formalizar la semántica probando en ARP (cosa que en ZFC si se podría) ciertos teoremas que relacionen las definiciones dadas sobre satisfacción y verdad con aspectos formales del tipo que ya me comentaste en el hilo sobre los ordinales menores a \( \epsilon_0 \), ¿no?

Pues... me resulta muy difícil responderte a esto sin hacer referencia a los mensajes que faltan sobre la formalización de ARP en ARP. Creo que sería mejor discutirlo más adelante. Pero la idea básica es que el hecho de que se pueda formalizar ZFC en ARP no aporta nada a estas cosas. Por ejemplo, en ARP no se puede definir \( \aleph_1 \) y en ZFC sí, pero en ARP puedes demostrar que en ZFC se puede demostrar que \( 2^{\aleph_0}\geq \aleph_1 \). Más precisamente: en ARP puedes definir el lenguaje formal de ZFC, sus axiomas y lo que es una demostración en ZFC, y en particular puedes definir la fórmula que afirma que \( 2^{\aleph_0}\geq \aleph_1 \) (que no es más que una sucesión finita de números naturales, si identificas cada signo con un número natural) y también la sucesión finita de fórmulas que lo demuestra. Pero eso no contradice a que en ARP no se pueden definir conjuntos infinitos. La fórmula de ZFC que afirma que \( 2^{\aleph_0}\geq \aleph_1 \) es una sucesión finita de números naturales y, por lo tanto, un número natural, igual que la demostración de este teorema, por eso es posible hablar de ello en ARP.

22 Julio, 2023, 06:23 pm
Respuesta #227

Eparoh

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

No me he parado a ver los detalles de tu prueba porque hay una línea que a simple vista ya no me cuadra:

\( H(\bar{x},s,k)=T\left(\bar{x},s,k, H|_{k}(\bar{x}, s) \right). \)

Si esto estuviera bien, si \( s \) cumple \( L(s) = 100 \), estarías definiendo \( H(\bar x, s, 100) \) suponiendo que ya están definidos \( H(\bar x, s, 0), \ldots, H(\bar x, s, 99) \), pero ahí no tienes información suficiente. Lo que necesitas es tener definidos \( H(\bar x, t, 99) \) para todo \( t\in \mbox{Sub}(s) \).

Había una errata en la definición que puse de \( T \) que la arrastré al pasar lo que hice del papel al ordenador y luego se fue trasladando por algunas partes de la prueba, pero con lo que he editado (ya de paso, también he añadido una prueba que solo usa recursión simple) en el mensaje anterior, aunque es cierto que no es el mismo funtor que tu definías, creo que la prueba si es correcta, ¿no?

Y, ahora si es perfectamente saber por recursión el valor de \( H \) (llamemos \( g \equiv G(\bar x, 0, 0) \) para simplificar) teniendo en cuenta que sí conocemos \( G \):

Para el caso de recursión completa:

\(
\begin{align*}
H(\bar x, s, 0)  & = T(\bar x, s, 0, 0)=g\\
H(\bar x, s, 1)  & = T(\bar x, s, 1, \langle H(\bar x, s, 0) \rangle_\infty)=G(\bar x, s, \{\langle u, g \rangle_\infty \mid u \in \mbox{Sub}(s)\})\\
H(\bar x, s, 2)  & = T(\bar x, s, 2, \langle H(\bar x, s, 0), H(\bar x, s, 1) \rangle_\infty)=G(\bar x, s, \{\langle u, H(\bar x, u, 1) \rangle_\infty \mid u \in \mbox{Sub}(s)\})\\
 & \vdots
\end{align*}
 \)

Para el caso de recursión simple:

\(
\begin{align*}
H(\bar x, s, 0)  & = g\\
H(\bar x, s, 1)  & =G(\bar x, s, \{\langle u, g \rangle_\infty \mid u \in \mbox{Sub}(s)\})\\
H(\bar x, s, 2)  & =G(\bar x, s, \{\langle u, H(\bar x, u, 1) \rangle_\infty \mid u \in \mbox{Sub}(s)\})\\
 & \vdots
\end{align*}
 \)

Y, si no me he equivocado en nada (he vuelto a repasar la prueba y yo no veo nada raro, pero si pudieras repasarla (la de recursión simple, pues la otra es solo una versión más compleja de esta) te lo agradecería) se obtiene el funtor \( F \) deseado.

Por cierto, con la nueva construcción que has dado se obtiene que \( F(\bar x, 0)=0 \), pero debería ser igual a \( G(\bar x, 0,0) \). La definición correcta sería

\( H_0(x_1,\ldots, x_n) = \{\left<0, G(x_1, \ldots, x_n,0,0)\right>_\infty\} \)

¿No?

Pues... me resulta muy difícil responderte a esto sin hacer referencia a los mensajes que faltan sobre la formalización de ARP en ARP. Creo que sería mejor discutirlo más adelante. Pero la idea básica es que el hecho de que se pueda formalizar ZFC en ARP no aporta nada a estas cosas. Por ejemplo, en ARP no se puede definir \( \aleph_1 \) y en ZFC sí, pero en ARP puedes demostrar que en ZFC se puede demostrar que \( 2^{\aleph_0}\geq \aleph_1 \). Más precisamente: en ARP puedes definir el lenguaje formal de ZFC, sus axiomas y lo que es una demostración en ZFC, y en particular puedes definir la fórmula que afirma que \( 2^{\aleph_0}\geq \aleph_1 \) (que no es más que una sucesión finita de números naturales, si identificas cada signo con un número natural) y también la sucesión finita de fórmulas que lo demuestra. Pero eso no contradice a que en ARP no se pueden definir conjuntos infinitos. La fórmula de ZFC que afirma que \( 2^{\aleph_0}\geq \aleph_1 \) es una sucesión finita de números naturales y, por lo tanto, un número natural, igual que la demostración de este teorema, por eso es posible hablar de ello en ARP.

Vale sí, a eso es a lo que me refería. Que ARP te permite definir todo ZFC y dentro de ZFC puedes probar lo que sea que quieras probar aunque involucre conjuntos infinitos, pero eso es todo a partir de lo que se halla definido que es una demostración en ZFC, con lo que si lo vieras "desde lejos" todo como fórmulas de ARP, no aparece nada infinito ni no computable. Los infinitos los introduces llamando a ciertos naturales "infinito", pero nada más que eso.

Vamos, que ARP te da el idioma y la gramática necesarias para hablar de infinitos, pero cualquier construcción del idioma no deja de ser finita y computable.

¿Es esto a lo que te refieres, no?

Aún así, esto si me parece impresionante. Que con unas premisas metamatemáticas tan simples como las que se propusieron en los primeros mensajes pueda construirse un lenguaje formal con unos axiomas y reglas tan simples que te permita, a su vez, formalizar toda la matemática y la propia metamatemática.

Un saludo.

22 Julio, 2023, 07:06 pm
Respuesta #228

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Había una errata en la definición que puse de \( T \) que la arrastré al pasar lo que hice del papel al ordenador y luego se fue trasladando por algunas partes de la prueba, pero con lo que he editado (ya de paso, también he añadido una prueba que solo usa recursión simple) en el mensaje anterior, aunque es cierto que no es el mismo funtor que tu definías, creo que la prueba si es correcta, ¿no?

No, no es correcta. Si es necesario, me pongo a analizarla con detalle para decirte el punto exacto donde introduces algo que no es coherente, pero no debería hacer falta, porque la incoherencia salta a la vista en el mero objetivo que pretendes conseguir:

Y, ahora si es perfectamente saber por recursión el valor de \( H \) (llamemos \( g \equiv G(\bar x, 0, 0) \) para simplificar) teniendo en cuenta que sí conocemos \( G \):

Para el caso de recursión completa:

\(
\begin{align*}
H(\bar x, s, 0)  & = T(\bar x, s, 0, 0)=g\\
H(\bar x, s, 1)  & = T(\bar x, s, 1, \langle H(\bar x, s, 0) \rangle_\infty)=G(\bar x, s, \{\langle u, g \rangle_\infty \mid u \in \mbox{Sub}(s)\})\\
\color{red}H(\bar x, s, 2)  & \color{red}= T(\bar x, s, 2, \langle H(\bar x, s, 0), H(\bar x, s, 1) \rangle_\infty)=G(\bar x, s, \{\langle u, H(\bar x, u, 1) \rangle_\infty \mid u \in \mbox{Sub}(s)\})\\
 & \vdots
\end{align*}
 \)

Para el caso de recursión simple:

\(
\begin{align*}
H(\bar x, s, 0)  & = g\\
H(\bar x, s, 1)  & =G(\bar x, s, \{\langle u, g \rangle_\infty \mid u \in \mbox{Sub}(s)\})\\
\color{red}H(\bar x, s, 2)  &\color{red} =G(\bar x, s, \{\langle u, H(\bar x, u, 1) \rangle_\infty \mid u \in \mbox{Sub}(s)\})\\
 & \vdots
\end{align*}
 \)

Y, si no me he equivocado en nada (he vuelto a repasar la prueba y yo no veo nada raro, pero si pudieras repasarla (la de recursión simple, pues la otra es solo una versión más compleja de esta) te lo agradecería) se obtiene el funtor \( F \) deseado.

Piensa en la primera línea que te he marcado en rojo. En ella quieres definir \( H(\bar x, s, 2) \) en términos de un funtor \( T \) que puedes definir como más te convenga (pero que no importa cómo lo definas, que no puede funcionar) tomando como datos \( \bar x, s, 2, H(\bar x, s, 0), H(\bar x, s, 1) \). Puedes definir \( T \) como quieras, pero sin hacer referencia a \( H \) (que aún no está definido) y luego, tienes que aplicar esa definición a los datos anteriores exclusivamente. En particular, no puedes usar nada de \( H \) que no sean los dos valores \( H(\bar x, s, 0), H(\bar x, s, 1) \).

Sin embargo, en la segunda igualdad, pretendes que la aplicación de \( T \) tenga en cuenta los valores \( H(\bar x, u, 1) \), donde \( u \) varía en \( \mbox{Sub}(s) \), ¿pero de dónde sacas esa información? De acuerdo con tu construcción, sólo tienes derecho a usar \( H(\bar x, s, 0), H(\bar x, s, 1) \), y ninguno de estos dos valores es ninguno de los \( H(\bar x, u, 1) \) que te sacas de la manga.

Por eso te digo que no importa cómo definas \( T \), porque el problema es que, si aplicas \( T \) a unos datos que sólo incluyen \( H(\bar x, s, 0), H(\bar x, s, 1) \), es imposible que el resultado dependa de los valores \( H(\bar x, u, 1) \).

El problema viene de tu intento de poner \( s \) entre los argumentos de \( H \). Eso te obliga a mantener fijo \( s \) cuando defines el funtor para \( k \), cuando necesitas considerar distintos valores  \( u \) en lugar de \( s \).

En el caso de la recursión simple la incoherencia es más evidente, pues la definición por recursión usual te permite definir \( H(\bar x, s, 2) \) exclusivamente en términos de \( \bar x, s, 2, H(\bar x, s, 1) \), luego es trampa que metas de contrabando los valores de \( H(\bar x, u, 1) \) que realmente necesitas para que todo te funcione, ya que no los tienes definidos.

No sé si la confusión que tienes es ésta:

Cuando defines por recurrencia usual, no es que puedas definir \( F(x_1, \ldots, x_n, x+1) \) supuesto que ya tienes definido \( F(x_1, \ldots, x_n, x) \) para valores cualesquiera de \( x_1,\ldots, x_n \), sino que sólo puedes suponer definido \( F(x_1, \ldots, x_n, x) \) para los mismos valores fijos de \( x_1,\ldots, x_n \). Lo contrario es una "herejía finitista", pues sería definir \( F(x_1, \ldots, x_n, x+1) \) usando una cantidad infinita de información (los infinitos valores de \( F(x_1, \ldots, x_n, x) \) para las infinitas posibilidades que tienen \( x_1,\ldots, x_n \). Por el contrario, sólo tienes derecho a definir \( F(x_1, \ldots, x_n, x+1) \) usando una cantidad finita de información: los \( x+1 \) valores

\( F(x_1, \ldots, x_n, 0), F(x_1, \ldots, x_n, 1),\ldots, F(x_1, \ldots, x_n, x) \)

Piénsalo y, si todavía no te convences de que no puedes poner a \( s \) como un argumento del funtor \( H \), discutimos el problema con más detalle, entrando en tu construcción, si es necesario, pero, como te digo, el argumento en contra es general y no depende de la construcción que hagas.

Por cierto, con la nueva construcción que has dado se obtiene que \( F(\bar x, 0)=0 \), pero debería ser igual a \( G(\bar x, 0,0) \). La definición correcta sería

\( H_0(x_1,\ldots, x_n) = \{\left<0, G(x_1, \ldots, x_n,0,0)\right>_\infty\} \)

¿No?

Cierto. Ya lo he cambiado. Gracias elevadas a ya no sé cuánto.

Vale sí, a eso es a lo que me refería. Que ARP te permite definir todo ZFC y dentro de ZFC puedes probar lo que sea que quieras probar aunque involucre conjuntos infinitos, pero eso es todo a partir de lo que se halla definido que es una demostración en ZFC, con lo que si lo vieras "desde lejos" todo como fórmulas de ARP, no aparece nada infinito ni no computable. Los infinitos los introduces llamando a ciertos naturales "infinito", pero nada más que eso.

Vamos, que ARP te da el idioma y la gramática necesarias para hablar de infinitos, pero cualquier construcción del idioma no deja de ser finita y computable.

¿Es esto a lo que te refieres, no?

Sí.

Aún así, esto si me parece impresionante. Que con unas premisas metamatemáticas tan simples como las que se propusieron en los primeros mensajes pueda construirse un lenguaje formal con unos axiomas y reglas tan simples que te permita, a su vez, formalizar toda la matemática y la propia metamatemática.

Bueno, toda la metamatemática, no. Para formalizar la parte semántica (para hablar de modelos numerables) hace falta un poquito más, pero sólo un poquito más.

22 Julio, 2023, 08:53 pm
Respuesta #229

Eparoh

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

Respecto a lo del funtor \( H \) entiendo esto que me dices:

Cuando defines por recurrencia usual, no es que puedas definir \( F(x_1, \ldots, x_n, x+1) \) supuesto que ya tienes definido \( F(x_1, \ldots, x_n, x) \) para valores cualesquiera de \( x_1,\ldots, x_n \), sino que sólo puedes suponer definido \( F(x_1, \ldots, x_n, x) \) para los mismos valores fijos de \( x_1,\ldots, x_n \). Lo contrario es una "herejía finitista", pues sería definir \( F(x_1, \ldots, x_n, x+1) \) usando una cantidad infinita de información (los infinitos valores de \( F(x_1, \ldots, x_n, x) \) para las infinitas posibilidades que tienen \( x_1,\ldots, x_n \). Por el contrario, sólo tienes derecho a definir \( F(x_1, \ldots, x_n, x+1) \) usando una cantidad finita de información: los \( x+1 \) valores

\( F(x_1, \ldots, x_n, 0), F(x_1, \ldots, x_n, 1),\ldots, F(x_1, \ldots, x_n, x) \)

Pero, sigo sin ver claro una cosa de este caso en concreto.

Por ejemplo, en este caso donde está claro que la definición de \( H(\bar x, s, 1) \) es clara, podemos entonces sustituir \( s \) por cualquier otra variable, con lo que donde está el inconveniente en continuar así:

\( \begin{align*} H(\bar x, s, 0)  & = g\\ H(\bar x, s, 1)  & =G(\bar x, s, \{\langle u, g \rangle_\infty \mid u \in \mbox{Sub}(s)\})\\ \color{red}H(\bar x, s, 2)  &\color{red} =G(\bar x, s, \{\langle u, H(\bar x, u, 1) \rangle_\infty \mid u \in \mbox{Sub}(s)\}) \color{black} = G(\bar x, s, \{\langle u, G(\bar x, u, \{\langle v, g \rangle_\infty \mid v \in \mbox{Sub}(u)\}) \rangle_\infty \mid u \in \mbox{Sub}(s)\})\\  & \vdots \end{align*} \)

Donde ya la \( H \) desaparece completamente.

Formalmente, intentaba aplicar el punto 2. de este teorema

Teorema Se cumple:

  • 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

    \( f_t(x_1,\ldots, x_n)=t(x_1,\ldots, x_n). \)

  • Si \( g(x_1,\ldots, x_n) \), \( h(x_1,\ldots, x_n, x, y) \) son términos con a lo sumo las variables indicadas, existe un funtor \( n+1 \)-ádico \( f \) que cumple:

    \( f(x_1,\ldots, x_n, 0)=g(x_1,\ldots, x_n), \)

    \( f(x_1,\ldots, x_n, Sx)=h(x_1,\ldots, x_n, x, f(x_1,\ldots, x_n,x)). \)

  • Si \( t \) es un término sin variables y \( h(x,y) \) es un término con a lo sumo las variables indicadas, existe un funtor monádico \( f \) que cumple

    \( f(0)=t,\qquad f(Sx)=h(x, f(x)). \)

Donde estoy considerando:

\(
\begin{align*}
g(\bar x,s) & \equiv G(\bar x, 0, 0)\\
h(\bar x, s, k, y) & \equiv G(\bar x, s, \{\langle u, {\color{red}S_s^u}y \rangle_\infty \mid u \in \text{Sub}(s)\})
\end{align*}
 \)

Y, si no me equivoco, la variable \( u \) que aparece en el término \( h \) y que parecería contradecir la parte del teorema que dice "con a lo sumo las variables indicadas", realmente no contradice nada porque si vamos a la definición que daba el Reemplazo en ARP, dicha \( u \) no es realmente una variable del término, ¿no?

¿Dónde me estoy colando en todo esto?

Y, por otra parte, de la forma en la que defines tú el funtor \( H \), también estás utilizando de fondo este teorema de recursión, ¿no?  Por tanto, más o menos complicadas también tienen que existir estas \( g \) y \( h \) y, ¿podrían ser estas?

Por comodidad denotamos \( A(t,k)\equiv \{t \in S_{k+1} \mid L(t)=k+1\} \)

\(
\begin{align*}
g(\bar x) & \equiv \{\langle 0, G(\bar x, 0, 0) \rangle_\infty\}\\
h(\bar x, k, y) & \equiv y \cup \bigcup_{s \in A(t,k)} \left\{\langle s, G(\bar x, s, \{\langle u, y(u) \rangle_\infty | u \in \text{Sub}(s)\}) \rangle_\infty\right\}
\end{align*}
 \)

Si estos son los términos adecuados, ¿qué diferencia hay con los que yo definí anteriormente?

Y, si no son los adecuados, ¿cuáles serían?

Aún así, esto si me parece impresionante. Que con unas premisas metamatemáticas tan simples como las que se propusieron en los primeros mensajes pueda construirse un lenguaje formal con unos axiomas y reglas tan simples que te permita, a su vez, formalizar toda la matemática y la propia metamatemática.

Bueno, toda la metamatemática, no. Para formalizar la parte semántica (para hablar de modelos numerables) hace falta un poquito más, pero sólo un poquito más.

Vale aquí si que tengo una duda un poco existencial, pero que tal vez cuando continúe el hilo principal se resuelve. Aún así la pregunto ya.

Cuando dices "formalizar la parte semántica" supongo que ahí también se incluye el poder demostrar dentro de la teoría formal cosas que relacionen las definiciones semánticas (formales) con las definiciones semánticas informales o algo por el estilo, ¿no? Porque si no es así, no entiendo como es posible que en ZFC si se pueda formalizar esta parte semántica, que dentro de ARP se pueda formalizar ZFC, pero que en ARP no se pueda formalizar la parte semántica. Entiendo entonces que debe ser por lo dicho, que con "formalizar la parte semántica" hay algo más allá de definir por recurrencia lo que significa que una formula sea satisfecha en un modelo, etc. y que implica algo más relacionado con la capacidad demostrativa de la propia teoría.

Pero igual me estoy haciendo ya un buen lío y es mejor dejar la discusión para más adelante ::)

Un saludo.

EDITADO: Se me olvidó poner la sustitución