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

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

02 Agosto, 2023, 02:04 pm
Respuesta #260

Eparoh

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

Se han resuelto varias dudas, pero surgen nuevas ::)

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 \).

Aquí supongo que estás "traduciendo" la definición de \( \text{SFR} \) y, si es así, ¿lo que le anteponemos no es \( {\color{blue} \kappa S}=\langle 4,1 \rangle \)?

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 \).

Esto de aquí (a parte de que supongo que al final faltan barras sobre la \( f \)), no lo entiendo del todo bien. ¿El funtor que defines no es, precisamente, el funtor \( f^1 \) que has definido al principio?

Si no es así, me estoy perdiendo algo porque no veo cual es la definición formal de dicho funtor :-\

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 \( H(f, s) \) que, cuando el número \( f \), visto como sucesión de números naturales, corresponde a un funtor \( n \)-ádico de \( \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 (si lo fuera, un funtor \( \Phi \) que la denotara cumpliría el "teorema" anterior).

Vale, ahora con las aclaraciones hechas aquí y los cambios lo veo claro todo, salvo un par de detalles.

El primero es que, formalmente, como se demuestra que este funtor \( \Phi \) cumple el "teorema" o, para lo que nos importa, que cumple que si \( f \) es un funtor \( n \)-ádico, \( k_1, \cdots ,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)}. \)

Supongo que esta segunda se probará por inducción en la longitud de \( f \), pero no veo claro como formalizarlo.

Por ejemplo, el primer paso sería probarlo cuando \( f \equiv S \) y debemos demostrar entonces que

\( \mathop\vdash\limits_{\rm ARP}\Phi({\color{blue} S},\left<\bar k \right>)=\overline{F(S)(k)} = \overline{k+1}. \)

Por lo que pongo más abajo, es claro que esto es semánticamente cierto, ¿pero como se prueba que es realmente un teorema de ARP?

Y, el ver que cumple el teorema, supongo que se prueba cada uno de los 5 puntos por separado, pero tampoco veo claro como demostrar que cada uno de los puntos es un teorema de ARP.

Por ejemplo, para el primer punto debemos demostrar que

\( \mathop\vdash\limits_{\rm ARP} \Phi({\color{blue} S}, s) = s_0+1 \)

y no veo nada claro como hacer esto.

Tengo claro que debe ser verdad (bueno, verdad si en el punto 1 añadimos que la longitud de \( s \) es \( 1 \), ¿no?), porque tenemos que si es \( s=\langle s_0 \rangle \) entonces

\( F(\Phi)(N({\color{blue} S}), N(s))=H((N({\color{blue} S}), N(s))=H(2,N(s)) = F(S)(N(s_0))=N(s_0)+1 \)

Pero, esto no prueba formalmente lo que se busca, solo nos indica que es cierto, ¿pero como sabemos que es demostrable en ARP?

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.

Entendido.

Un saludo.

02 Agosto, 2023, 03:07 pm
Respuesta #261

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Hola.

Se han resuelto varias dudas, pero surgen nuevas ::)

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 \).

Aquí supongo que estás "traduciendo" la definición de \( \text{SFR} \) y, si es así, ¿lo que le anteponemos no es \( {\color{blue} \kappa S}=\langle 4,1 \rangle \)?

Sí, me he rayado. Como estaba hablando de \( p^1_1 \), he puesto \( p^1_1 \), pero tenía que haber puesto lo que dices. Tambien serviría \( \kappa p^1_1 \), pero sería complicarlo para nada.

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 \).

Esto de aquí (a parte de que supongo que al final faltan barras sobre la \( f \)), no lo entiendo del todo bien. ¿El funtor que defines no es, precisamente, el funtor \( f^1 \) que has definido al principio?

Si no es así, me estoy perdiendo algo porque no veo cual es la definición formal de dicho funtor :-\

No, por raro que parezca, ahí lo he escrito todo como toca y no falta ninguna barra. Lo que digo ahí es: toma un número natural \( k \) cualquiera, calcula \( m = H(k) \), que es otro número natural, pero no uno cualquiera, sino uno que, cuando lo interpretas como sucesión de números naturales (e identificas los signos de \( \mathcal L_{\rm arp} \) con números naturales) resulta ser un funtor monádico de \( \mathcal L_{\rm arp} \). Llama \( f^1_k \) a ese funtor. No estóy definiendo ningún funtor. Estoy leyendo el número \( m \) como un funtor y a ese funtor lo llamo \( f^1_k \). A su vez, puedes considerar el numeral \( f^1_k \), del que podemos probar en ARP \( {\color{blue}f^1_k}\in \mbox{Fun}({\color{blue}\mathcal L_{\rm arp}}) \). Y lo que digo es que en ARP se puede probar que \( {\color{blue}f^1_k} = f^1_{\bar k} \), donde, a la derecha, \( f^1 \) es el funtor monádico definido al principio.

Repito lo que decía en el mensaje anterior: Si quieres enumerar los funtores monádicos de \( \mathcal L_{\rm arp} \). El proceso es:

1) Definimos \( f^1_0 = S \) (o, si prefieres ver a \( S \) como el número \( 1 \), pues \( f^1_0 = 1 \)).

2) Supuesto definido \( f^1_k \), lo interpretamos como una sucesión de números naturales, que a su vez se interpreta como un número natural \( m \), y vamos estudiando los números naturales \( m+1 \), \( m+2 \), etc. hasta encontrar un número \( M \) que, visto como sucesión finita, corresponda a un funtor monádico de \( \mathcal L_{\rm arp} \), y a ese funtor lo llamamos \( f^1_{k+1} \).

Con esto no estoy definiendo un funtor \( f^1 \), sino directamente la enumeración de los funtores monádicos que me pedías, pero lo cierto es que, teniendo en cuenta que la búsqueda de \( M \) en 2) está acotada por el valor de \( \kappa S f^1_k \) como número natural, lo cierto es que la función \( k\mapsto f^1_k \) es una función monádica recursiva primitiva, que no es sino la función denotada por el funtor \( f^1 \) definido en ARP como \( f^1(k) = f(k, 1) \), donde \( f \) es a su vez el funtor diádico construido en el hilo que enumera los funtores de \( \mathcal L_{\rm arp} \).

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 \( H(f, s) \) que, cuando el número \( f \), visto como sucesión de números naturales, corresponde a un funtor \( n \)-ádico de \( \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 (si lo fuera, un funtor \( \Phi \) que la denotara cumpliría el "teorema" anterior).

Vale, ahora con las aclaraciones hechas aquí y los cambios lo veo claro todo, salvo un par de detalles.

El primero es que, formalmente, como se demuestra que este funtor \( \Phi \) cumple el "teorema" o, para lo que nos importa, que cumple que si \( f \) es un funtor \( n \)-ádico, \( k_1, \cdots ,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)}. \)

Supongo que esta segunda se probará por inducción en la longitud de \( f \), pero no veo claro como formalizarlo.

En primer lugar, el "para lo que nos importa" es esencial. He cambiado la redacción en el hilo para dejar claro que eso es lo que pasaría, que el funtor \( \phi \) cumpliría esto y no puede ser.

No hace falta ninguna inducción. Ten en cuenta el último teorema de la respuesta #7. Lo que hay que probar es una igualdad \( t_1=t_2 \) entre dos términos sin variables. Si pruebas que es verdadera, entonces es demostrable en ARP, porque si es verdadera es que ambos términos denotan un mismo número natural \( d \), y el teorema que te digo afirma que en ARP puedes demostrar que \( t_1 = N_d \) y que \( t_2=N_d \), luego también puedes demostrar que \( t_1 = t_2 \).

Ahora bien, que la igualdad es verdadera es justo lo que significa que \( \phi \) denote la función \( H \).

Y, el ver que cumple el teorema, supongo que se prueba cada uno de los 5 puntos por separado, pero tampoco veo claro como demostrar que cada uno de los puntos es un teorema de ARP.

No, eso sería pedir demasiado. Lo dije mal. Lo que se puede probar es que el funtor \( \phi \) cumpliría la condición que ahora he llamado (*) en el hilo, la misma que has puesto tu aquí como la que realmente importa.

02 Agosto, 2023, 05:11 pm
Respuesta #262

Eparoh

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

Creo que ahora ya he entendido todo completamente, pero tengo que insistir en esto:

Así, si llamamos \( \color{orange}\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}{\color{orange}\bar f}^1_k} = f^1_{\bar k} \), donde \( \bar k \) es el numeral de \( k \).

Aquí, en el primer mensaje donde trataste de explicarme las cosas, llamaste al funtor que denota el número natural \( H(k) \) como \( \bar f_k^1 \), con una barrita sobre la \( f \). Entonces, lo que yo antes decía (y ahora que ya he entendido todo bien, me reafirmo en ello), es que en este caso faltaba la barrita azul sobre la \( f \) en la fórmula \( {\color{blue}f^1_k} = f^1_{\bar k} \) (la que yo he añadido ahora poniéndolo en naranja), ¿no?

Un saludo.

02 Agosto, 2023, 05:15 pm
Respuesta #263

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Hola.

Creo que ahora ya he entendido todo completamente, pero tengo que insistir en esto:

Así, si llamamos \( \color{orange}\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}{\color{orange}\bar f}^1_k} = f^1_{\bar k} \), donde \( \bar k \) es el numeral de \( k \).

Aquí, en el primer mensaje donde trataste de explicarme las cosas, llamaste al funtor que denota el número natural \( H(k) \) como \( \bar f_k^1 \), con una barrita sobre la \( f \). Entonces, lo que yo antes decía (y ahora que ya he entendido todo bien, me reafirmo en ello), es que en este caso faltaba la barrita azul sobre la \( f \) en la fórmula \( {\color{blue}f^1_k} = f^1_{\bar k} \) (la que yo he añadido ahora poniéndolo en naranja), ¿no?

Un saludo.

Ah, no me acordaba de esa barra (era una notación "local" improvisada en el momento). Sí, yo ahora había llamado a ese funtor \( f^1_k \), pero si lo llamamos \( \bar f^1_k \), entonces falta la barra, cierto.

02 Agosto, 2023, 08:10 pm
Respuesta #264

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Acabo de descubrir un error en la prueba del tercer spoiler de la respuesta #17. Es posible que el mismo error se repita en otros sitios, pero la solución es siempre la misma.

Se trata de la prueba en ARP de que \( x\cap y = \emptyset\rightarrow |x\cup y| = |x|+|y| \).

La prueba estaba planteada como una inducción sobre \( n = |y| \), de modo que se probaba por inducción sobre \( n \) la fórmula

\( |y| = n \land x\cap y =\emptyset \rightarrow |x\cup y| = |x|+|y|. \)

y luego se sustituía \( n = |y| \), ¡¡pero eso está mal!!  :banghead:

Un matemático ve bien la prueba que había dado porque es correcta en cualquier teoría "normal", porque probar eso por inducción sobre \( n \) es en realidad lo mismo que probar por inducción sobre \( n \) la fórmula

\( \forall y(|y| = n \land x\cap y =\emptyset \rightarrow |x\cup y| = |x|+|y|). \)

y así, lo que hacemos es suponer que esto vale para \( n \) con lo que tenemos la hipótesis de inducción para todo conjunto \( y \) de cardinal \( n \), y al suponer un conjunto \( y \) de cardinal \( n+1 \), se le quita un elemento, para obtener otro conjunto \( y' \) de cardinal \( n \) y a ése se le aplica la hipótesis de inducción. Eso es correcto en ZF, o en AP o casi en cualquier sitio, ¡pero no en ARP!

En ARP no podemos poner ese \( \forall y \), por lo que si tomamos meramente como hipótesis de inducción

\( |y| = n \land x\cap y =\emptyset \rightarrow |x\cup y| = |x|+|y|. \)

y luego partimos de un \( y \) que cumpla \( |y| = n+1 \), a partir del cual construimos un \( y' \) tal que \( |y'| = n \) ¡no podemos aplicar la hipótesis de inducción!

Para ello tendríamos que sustituir \( y \) por \( y' \) en la hipótesis de inducción, pero estamos aplicando el teorema de deducción: suponemos \( \alpha(n) \) para probar \( \alpha(n+1) \), y desde el momento en que suponemos \( \alpha(n) \) está prohibido sustituir variables que estén en \( \alpha(n) \). En particular, ¡no podemos sustituir \( y \) por \( y' \).

En general, si suponemos una hipótesis de inducción y tiene parámetros, como aquí son \( x, y \) ¡no podemos sustituirlos por nada! ¡los parámetros son constantes en todo el razonamiento inductivo!

Pero eso tiene una solución muy simple, porque no necesitamos la hipótesis de inducción para todos los conjuntos de cardinal \( n \) (que son infinitos, luego estamos cometiendo una herejía finitista), sino únicamente para los subconjuntos de \( y \) de cardinal \( n \), que son un número finito. Técnicamente eso significa que hay que probar por inducción sobre \( n \) la fórmula

\( \forall y'\in \mathcal P y\ (|y'| = n \land x\cap y' =\emptyset \rightarrow |x\cup y'| = |x|+|y'|. \)

Una vez demostrado esto, ya podemos sustituir lo que queramos, y hacemos \( n = |y| \) y luego eliminamos el cuantificador haciendo \( y' = y \), y ya tenemos la fórmula que queríamos.

De este modo, cuando suponemos que \( y'\in \mathcal Py \) cumple \( |y'| = n+1 \) y luego pasamos a un \( y''\subset y' \) con \( |y''| = n \), tenemos que \( y''\in \mathcal Py \), por lo que le podemos aplicar la hipótesis de inducción sin problemas.

Como ya digo, es posible que haya otros casos parecidos. Si encuentro alguno ya lo avisaré.

02 Agosto, 2023, 09:28 pm
Respuesta #265

Eparoh

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

Acabo de descubrir un error en la prueba del tercer spoiler de la respuesta #17. Es posible que el mismo error se repita en otros sitios, pero la solución es siempre la misma.

Vaya... Pues es verdad y tampoco me di cuenta al leerlo porque ya había bajado las defensas formalistas ::)

Yo estoy seguro de haber utilizado el argumento al menos una vez más, pero es posible que fuera en alguna demostración que hubieras dejado a cargo del lector. Mañana buscaré por algunas palabras clave en lo que tengo escrito y si encuentro algo lo pongo por aquí.

Por cierto, un comentario respecto a lo que has añadido en el hilo principal con esta corrección.

Aquí has escrito lo siguiente:

Una vez demostrado esto, ya podemos sustituir lo que queramos, y hacemos \( n = |y| \) y luego eliminamos el cuantificador haciendo \( y' = y \), y ya tenemos la fórmula que queríamos.

Pero en el hilo principal has puesto:

Lo correcto es probar por inducción

\( \forall y'\in \mathcal P y(|y'| = n \land x\cap y' =\emptyset \rightarrow |x\cup y'| = |x|+|y'|. \)

y luego sustituir \( y' = y, n = |y| \).

Y da la impresión de que digas que se utiliza dos veces \( S_1 \), una sustituyendo \( y' \) por \( y \), y otra sustituyendo \( n \) por \( |y| \), cuando en el primer caso realmente te refieres a una eliminación del generalizador, porque la \( y' \) no es ni siquiera una variable en la fórmula dada.

Me refiero a que igual sería mejor escribir esa frase más parecido a como lo has hecho en este hilo.

Un saludo.

02 Agosto, 2023, 11:19 pm
Respuesta #266

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Me refiero a que igual sería mejor escribir esa frase más parecido a como lo has hecho en este hilo.

Ya lo he cambiado.

03 Agosto, 2023, 03:11 pm
Respuesta #267

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Acabo de añadir una demostración mucho más simple del resultado del que hablábamos en los últimos mensajes.

04 Agosto, 2023, 12:01 pm
Respuesta #268

Eparoh

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

Acabo de añadir una demostración mucho más simple del resultado del que hablábamos en los últimos mensajes.

Ciertamente es mucho más sencilla y elegante, pero creo que hay un par de pequeñas erratas:

Razonamos por inducción completa sobre \( y \), es decir, suponemos que la igualdad es cierta para todo \( y'<y \) y vamos a probarla para \( y \). Si \( y = 0 \) es trivial, pues
\( |x\cup y| = |x| = |x|+0 = |x|+|y| \).

Si \( y\neq 0 \), podemos tomar \( v\in y \) y definir \( y' = y\setminus\{v\} \), de modo que \( x\cap y' = \emptyset \), \( y'\subsetneq y \), luego \( y'< y \). Podemos aplicar la hipótesis de inducción, que nos da que \( |x\cup y'| = |x|+|y'| \).

Ahora observamos que una biyección \( f: {\color{red} I_{|y'|}}\longrightarrow y' \) se extiende a otra biyección \( f':{\color{red} I_{|y'|+1}}\longrightarrow y \) sin más que definir \( f'(|y'|) = v \), con lo que \( |y| = |y'|+1 \), y esto vale siempre que a un conjunto se le quita uno de sus elementos, luego, puesto que \( x\cup y' = (x\cup y)\setminus\{v\} \), también \( |x\cup y| = |x\cup y'|+1 = |x|+|y'|+1 = |x|+|y| \).

Y, otra duda. En la prueba se utiliza que si \( x \subset y \), entonces \( x \leq y \). Teniendo en cuenta informalmente lo que significa la pertenencia en ARP esto está claro, pero para demostrarlo formalmente he necesitado "trabajar un poco" y me gustaría saber si lo que he hecho es correcto y, si me he complicado o no la vida.

En primer lugar, he demostrado lo siguiente: \( j>n_d(x) \rightarrow x_j[d]=0. \)

Para ello, he utilizado esto que vimos en la demostración de la existencia y unicidad de los desarrollos decimales:

En particular, para \( k=\ell(s)\dot{-} 1 \) tenemos que

\( \forall i< \ell(s)\,(s_{(d)})_i[d]=s_i. \)

Donde \( s \) era cualquier sucesión no nula y tal que \( \forall i<\ell(s)\, s_i<d \).

Sin más, si es \( j>n_d(x) \) y consideramos la sucesión \( s \) de longitud \( j+1 \) tal que

\( s_i= \left\{ \begin{array}{lcl}
x_i[d] & \text{si} & i \leq n_d(x) \\
0 & \text{si} & n_d(x) < i \leq j
\end{array} \right. \)

entonces \( s \) es un desarrollo decimal de \( x \), luego podemos aplicar el resultado obteniendo en particular que \( (s_{(d)})_j[d] = s_j \). Como además \( x=s_{(d)} \) concluimos que

\( x_j[d] = (s_{(d)})_j[d] = s_j=0. \)

Ahora, si \( x \subset y \), entonces se tiene que \( x_i[2]=1 \rightarrow y_i[2]=1 \). En particular, \( y_{n_2(x)}[2]=1 \). Esto junto a lo demostrado anteriormente muestra que \( n_2(x) \leq n_2(y) \) y así obtenemos que

\( x\displaystyle=\sum_{i \leq n_2(x)} x_i[2] \cdot 2^i \leq \sum_{i \leq n_2(x)} y_i[2] \cdot 2^i \leq \sum_{i \leq n_2(y)} y_i[2] \cdot 2^i = y. \)

Voy a ponerme ahora a mirar el último mensaje, a ver si vuelvo a adelantarme :laugh:

Un saludo.

04 Agosto, 2023, 12:51 pm
Respuesta #269

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Y, otra duda. En la prueba se utiliza que si \( x \subset y \), entonces \( x \leq y \). Teniendo en cuenta informalmente lo que significa la pertenencia en ARP esto está claro, pero para demostrarlo formalmente he necesitado "trabajar un poco" y me gustaría saber si lo que he hecho es correcto y, si me he complicado o no la vida.

En el hilo hemos visto que

\( x=x^*_n[d]\cdot d^{n+1}+\sum\limits_{i\leq n}x_i[d]\cdot d^i. \)

y a continuación se razona que \( x^*_x[d]=0 \), pero en realidad el argumento prueba que si \( n\geq x \), entonces \( x^*_n[d]=0 \) (simplemente porque \( x<d^{x+1}\leq d^{n+1} \)), luego

\( x=\sum\limits_{i\leq n}x_i[d]\cdot d^i. \)

Es un desarrollo decimal válido para todo \( n\geq x \) y, por definición de \( n_d(x) \), que es simplemente el mínimo para el que vale esto, resulta que tienes este desarrollo decimal para cada \( n\geq n_d(x) \).

Teniendo esto en cuenta, para probar que \( x\subset y\rightarrow x\leq y \) basta tener en cuenta (suponiendo \( x\neq 0 \), pues en caso contrario la conclusión es obvia) y llamando \( n \) al máximo de \( n_2(x) \) y \( n_2(y) \), que

\( x = \sum\limits_{i\leq n}x_i[2]\cdot 2^i\leq \sum\limits_{i\leq n}y_i[2]\cdot 2^i=y \),

pues la inclusión hace que si \( x_i[2]=1 \), entonces \( i\in x \), luego \( i\in y \), luego \( y_i[2]=1 \), luego siempre \( x_i[2]\leq y_i[2] \).

Voy a ponerme ahora a mirar el último mensaje, a ver si vuelvo a adelantarme :laugh:

Como diría Fernando Revilla: yo disparé antes.