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

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

04 Agosto, 2023, 01:27 pm
Respuesta #270

Eparoh

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

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

Esta vez sí ::)

Entiendo lo que comentas, pero en esencia es casi lo mismo que yo puse aunque por un camino un poco más corto, ¿no?

Un saludo.

04 Agosto, 2023, 01:34 pm
Respuesta #271

Carlos Ivorra

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

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

Esta vez sí ::)

Entiendo lo que comentas, pero en esencia es casi lo mismo que yo puse aunque por un camino un poco más corto, ¿no?

Sí, lo que haces está bien, claro. Entendía que me preguntabas si se podía hacer más corto.

En esencia, lo que pasa es que sería mejor enunciar la unicidad de los desarrollos decimales diciendo que \( i> n_d(x)\rightarrow x_i[d]=0 \) y que todo desarrollo decimal de \( x \) es necesariamente de la forma

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

con \( n\geq n_d(x) \), de modo que el único reducido es el correspondiente a \( n = n_d(x) \).

Todo esto está probado entre el hilo y mi mensaje anterior. Puesto que sabemos que existen los desarrollos decimales de esta forma (está probado en el hilo salvo la generalización que he hecho de tomar un \( n\geq x \) en lugar de \( n = x \) como se toma en el hilo), la unicidad probada en el hilo prueba que \( x_i(d) = 0 \) para \( i>n_d(x) \) y, sabiendo esto, la unicidad del hilo equivale a la que acabo de enunciar. Y enunciado así, la prueba de que \( x\subset y\rightarrow x\leq y \) es inmediata.

04 Agosto, 2023, 03:19 pm
Respuesta #272

Eparoh

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

Ciertamente, enunciando así el teorema de unicidad es directo. Me lo he apuntado como corolario del que vimos :P

Un saludo.

04 Agosto, 2023, 04:34 pm
Respuesta #273

Eparoh

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

Ya he leído el último mensaje y, la verdad, me genera muchas dudas.

Más técnicamente sería:

\( A_\kappa(h, g) = {\color{blue} =}\ {\color{blue} \kappa}\, h\,g\,\xi_n\,h\prod\limits_{i<\ell(g)}g_i\xi_n. \)

y para añadir esto en la fórmula \( \alpha \in \mbox{Ax} \)(ARP) hay que incluir cuantificadores

\( \exists h\in\mbox{Cad}_{\ell(\alpha)} ({\color{blue}\mathcal L_{\rm arp}})\exists mn\leq \alpha\exists g\in S_m(\mbox{Cad}_{\ell(\alpha)} ({\color{blue}\mathcal L_{\rm arp}}))
 \)
y las hipótesis

\( h\in \mbox{Fun}({\color{blue}\mathcal L_{\rm arp}})\land \mbox{rang}(h) = m\land \forall i<m(g_i\in \mbox{Fun}({\color{blue}\mathcal L_{\rm arp}})\land \mbox{rang}(g_i) = n),
 \)
pero comprimiendo toda esta información en una fórmula sólo volvemos ilegible una definición tan clara como la que dimos en su día.

¿Qué es \( \mbox{Cad}_{\ell(\alpha)} ({\color{blue}\mathcal L_{\rm arp}}) \)? Porque ese subíndice después del "Cad" no lo hemos utilizado hasta ahora. ¿Es el conjunto de todas las cadenas de signos de \( {\color{blue}\mathcal L_{\rm arp}} \) de longitud menor o igual a \( \ell(\alpha) \)? Si es así, veo que es un conjunto finito y por tanto se va a poder definir, pero no veo exactamente como podríamos acotarlo. Es decir, se que podemos definir el funtor

\( \mbox{Cad}_n ({\color{blue}\mathcal L_{\rm arp}}) = \{x < \text{COTA} \mid \ell(x) \leq n \wedge x \in \mbox{Cad}({\color{blue}\mathcal L_{\rm arp}})\} \)

Pero, ¿cuál es la cota?

Y, con lo de incluir cuantificadores y las hipótesis te refieres a que si a la primera cadena de signos con los cuantificadores la llamamos \( \zeta_1 \) y a la segunda con las hipótesis la llamamos \( \zeta_2 \), entonces lo que se debe añadir a la fórmula \( \alpha \in \mbox{Ax}({\color{blue} \text{ARP}}) \) es \( \zeta_1 (\zeta_2 \rightarrow \alpha = A_\kappa (h, g)) \), ¿no?

Dejamos a cargo del lector formalizar (si lo cree imprescindible) la definición de los axiomas de los funtores definidos por recursión. El caso es que así podemos completar la definición de una fórmula \( \alpha \in \mbox{Ax} \)(ARP) que se corresponde con la definición informal, y en particular permite probar que si \( \alpha \) es un axioma (metamatemático) de ARP, entonces

\( \mathop\vdash\limits_{\rm ARP}{\color{blue}\alpha} \in \mbox{Ax} \)(ARP).

Para que lo último sea cierto, realmente tendríamos que haber tomado como axiomas de ARP no todas las definiciones de funtores, sino algunas concretas con variables concretas, ¿no?

Quiero decir, que si tomamos como axiomas de ARP cualquier definición de funtores, tenemos entonces que \( \alpha \equiv c(x_1)=0 \) (donde \( x_1 \) es la variable de índice \( 1 \)) es un axioma de ARP, pero \( \color{blue} \alpha \) no será un axioma de ARP.

Deducciones Seguidamente, el lector debería convencerse de que no hay nada que impida formalizar en ARP la definición informal de deducción. El resultado tiene que ser una fórmula

\( \Pi\mathop{\vdash}\limits_{\rm \color{blue}ARP}^d\alpha\equiv  d_{\ell(d)\dot- 1}=\alpha\land  \forall i<\ell(d)\, (d_i\in \mbox{Form}({\color{blue}\mathcal L_{\rm arp}})\land(d_i\in \Pi\lor d_i\in \mbox{Ax} \)(ARP)\( \lor \cdots)),
 \)

donde los puntos suspensivos representan cuatro fórmulas más en la disyunción que expresan que \( d_i \) se sigue de fórmulas precedentes por una de las cuatro reglas de inferencia de ARP, pero no ganamos nada condensando dichas reglas en fórmulas de ARP. Basta observar que para formalizarlas no tenemos que hacer referencia a nada que no podamos acotar en términos de la sucesión \( d \) o de sus términos.

¿Podrías mostrar como sería, por ejemplo, la fórmula que habría que añadir para la regla \( S_1 \)?

Se que lo que habría que añadir sería algo de la forma

\( S_1(d_i) \equiv \exists k < \ell(d) \, d_i=S_x^t d_k \)

donde faltaría declarar la existencia de la variable \( x \) y el término \( t \). La variable si que veo que se puede extraer del propio \( d \) con algo de la forma

\( \exists x \, (x \in \mbox{Var}_{d_k}({\color{blue}\mathcal L_{\rm arp}})) \)

donde \( x \in \mbox{Var}_{s}({\color{blue}\mathcal L_{\rm arp}}) \) sería la formalización de que una variable está en un término \( s \) (pero claro, habría que formalizar esto). Pero, para el término \( t \) no lo veo tan claro.

Si pudieras dar aunque sea este con detalle para ya tener clara la dinámica lo agradecería mucho.

Más llanamente: no podemos definir en ARP una fórmula que diga que una fórmula es un teorema de ARP, lo cual es razonable, porque "ser un teorema" no es totalmente finitista. No hay una forma de comprobar en un número finito de pasos si una fórmula dada es un teorema o no. Mejor dicho, la única forma de hacerlo consiste en encontrar una demostración. Por eso en ARP no podemos decir "\( \alpha \) es un teorema", sino que tenemos que decir necesariamente "\( d \) es una demostración de \( \alpha \)".

Por ejemplo, si queremos enunciar en ARP las reglas de inferencia de la doble negación tenemos que formular algo del estilo de

\( {\color{blue}\lnot\lnot}\alpha\mathop\vdash\limits_{\rm \color{blue}ARP}^{f(\alpha)}\alpha \)

donde \( f \) es un funtor que, a cada fórmula \( \alpha \) le hace corresponder una deducción de \( \alpha \) a partir de \( {\color{blue}\lnot\lnot}\alpha \). Como sabemos deducir \( \alpha \) a partir de \( \lnot\lnot\alpha \), sabemos cómo definir un funtor que nos dé una deducción.

¿Podrías también poner un ejemplo de esto? De como sería dicho funtor y, ya puestos, ¿cómo se formaliza la negación?

Esta parte de formalizar una teoría dentro de ella misma es muy nueva para mi y me pierdo aun un poco.

Y otra cuestión sobre esto, para indicar la formalización de la regla de inferencia no deberíamos escribir más bien algo como

\( \mathop\vdash\limits_{\rm ARP} {\color{blue}\lnot\lnot}\alpha\mathop\vdash\limits_{\rm \color{blue}ARP}^{f(\alpha)}\alpha \)

Porque si no, simplemente estamos escribiendo una fórmula, sin más, ¿no?

Sin más que esta obligación de explicitar siempre las demostraciones de los teoremas a los que hagamos referencia, el lector debería convencerse de que nada —salvo la brevedad de la vida— le impide demostrar todos los resultados que hemos expuesto en este hilo sobre ARP que no involucren conceptos semánticos. Por ejemplo, la formalización del teorema de deducción consiste en definir funtores \( D \), \( P \), \( D' \) de modo que

\( \Pi\cup\{\alpha\}\mathop{\vdash}\limits_{\rm \color{blue}ARP}^d\beta\rightarrow \left(\Pi\cup P(d, \alpha)\mathop{\vdash}\limits_{\rm \color{blue}ARP}^{D(d, \alpha)}\alpha{\color{blue}\rightarrow} \beta\right)\land \forall \gamma\in P(d,\alpha)\!\!\! \mathop{\vdash}\limits_{\rm \color{blue}ARP}^{D'(d, \alpha, \gamma)}\!\!\!\!\gamma \)

(con todas las hipótesis y conclusiones adicionales del teorema, es decir, hay que suponer que la deducción \( d \) no usa las reglas \( S_1 \) o \( I_0 \) respecto a variables que estén en \( \alpha \) y podemos concluir que la deducción \( D(d, \alpha) \) sólo usa estas reglas respecto de variables para las que ya se usaban en \( d \)).

Podemos asegurar que existen tales funtores (sin necesidad de definirlos explícitamente) porque la demostración del teorema de deducción es totalmente constructiva: determina completamente qué teoremas \( P(d, \alpha) \) necesitamos tomar como premisas (y cuáles son sus demostraciones) y cómo construir una deducción de \( \alpha\rightarrow \beta \) a partir de una deducción de \( \beta \).

El teorema de deducción es demasiado, pero si estaría bien tener algún ejemplo de lo que mencionas (tal vez más simple que lo que te he preguntado antes)

Pero todos estos detalles son irrelevantes. Lo importante es que el lector debería convencerse de que ahora puede releer todo lo dicho en este hilo no en color rojo considerando que está leyendo teoremas de ARP, en el mismo sentido que si abre cualquier libro de álgebra o de cálculo diferencial puede entender que está leyendo teoremas de ZFC a pesar de que no vea en ninguna parte chirimbolitos lógicos y axiomas ni nada de todo eso.

Aquí, entiendo que lo que quieres decir es que cualquier teorema metamatemático de los que hayamos visto ahora podemos verlo como un teorema de ARP, ¿no? Es decir, que podríamos convertir el hilo en algo del estilo de Principia Mathematica. Simplemente, tras exponer informalmente los axiomas y reglas de inferencia de ARP, pasar a enumerar una serie de teoremas de ARP que abarcaría todo lo dicho en el hilo. ¿Es esto a lo que te referías?

La respuesta a la pregunta: ¿qué es necesario suponer para estudiar metamatemáticamente la lógica formal (sin entrar en semántica (modelos, etc.)? es: como máximo (las versiones informales de) los axiomas y reglas de inferencia de ARP, lo cual es muy poco suponer.

Con esta frase me surge una duda. Hemos formalizado ARP dentro de ARP, pero lo que tu dices aquí es que ARP te permite estudiar toda la parte formal de la lógica matemática. Es decir, afirmas que con ARP podemos formalizar, por ejemplo, el concepto de lenguaje de primer orden, de teoría axiomática, de demostración en un lenguaje de dicho tipo, etc., ¿o no lo he entendido bien?

Si es así, esto último no lo veo tan tan claro.

Como digo, esta última parte de la formalización de una teoría dentro de la propia teoría aun me cuesta bastante de entender. A ver si poco a poco voy asimilándola mejor.

Un saludo.

04 Agosto, 2023, 07:02 pm
Respuesta #274

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Ya he leído el último mensaje y, la verdad, me genera muchas dudas.

¡Cuánta paciencia tienes!

Más técnicamente sería:

\( A_\kappa(h, g) = {\color{blue} =}\ {\color{blue} \kappa}\, h\,g\,\xi_n\,h\prod\limits_{i<\ell(g)}g_i\xi_n. \)

y para añadir esto en la fórmula \( \alpha \in \mbox{Ax} \)(ARP) hay que incluir cuantificadores

\( \exists h\in\mbox{Cad}_{\ell(\alpha)} ({\color{blue}\mathcal L_{\rm arp}})\exists mn\leq \alpha\exists g\in S_m(\mbox{Cad}_{\ell(\alpha)} ({\color{blue}\mathcal L_{\rm arp}}))
 \)
y las hipótesis

\( h\in \mbox{Fun}({\color{blue}\mathcal L_{\rm arp}})\land \mbox{rang}(h) = m\land \forall i<m(g_i\in \mbox{Fun}({\color{blue}\mathcal L_{\rm arp}})\land \mbox{rang}(g_i) = n),
 \)
pero comprimiendo toda esta información en una fórmula sólo volvemos ilegible una definición tan clara como la que dimos en su día.

¿Qué es \( \mbox{Cad}_{\ell(\alpha)} ({\color{blue}\mathcal L_{\rm arp}}) \)? Porque ese subíndice después del "Cad" no lo hemos utilizado hasta ahora. ¿Es el conjunto de todas las cadenas de signos de \( {\color{blue}\mathcal L_{\rm arp}} \) de longitud menor o igual a \( \ell(\alpha) \)? Si es así, veo que es un conjunto finito y por tanto se va a poder definir, pero no veo exactamente como podríamos acotarlo. Es decir, se que podemos definir el funtor

\( \mbox{Cad}_n ({\color{blue}\mathcal L_{\rm arp}}) = \{x < \text{COTA} \mid \ell(x) \leq n \wedge x \in \mbox{Cad}({\color{blue}\mathcal L_{\rm arp}})\} \)

Pero, ¿cuál es la cota?

El efecto, \( \mbox{Cad}_{\ell(\alpha)} ({\color{blue}\mathcal L_{\rm arp}}) \) es lo que has supuesto, pero es una reliquia. En principio había usado eso para las acotaciones, hasta que añadí el apartado final de la respuesta #17, tras lo cual debería haber eliminado todos los \( \mbox{Cad}_n ({\color{blue}\mathcal L_{\rm arp}}) \), pero ahí han sobrevivido un par. Debería poner:

\( \exists h\in\mbox{Sub}(\alpha)\exists mn\leq \alpha\exists g\in S_m(\mbox{Sub}(\alpha)) \)

Ya lo he cambiado en el hilo. De todos modos, aunque no hace falta,

\( \mbox{Cad}_n ({\color{blue}\mathcal L_{\rm arp}})\equiv \bigcup\limits_{i\leq n}S_i(\{0, 1, 2, 3, 4, 5, 6, 7\}). \)

Y, con lo de incluir cuantificadores y las hipótesis te refieres a que si a la primera cadena de signos con los cuantificadores la llamamos \( \zeta_1 \) y a la segunda con las hipótesis la llamamos \( \zeta_2 \), entonces lo que se debe añadir a la fórmula \( \alpha \in \mbox{Ax}({\color{blue} \text{ARP}}) \) es \( \zeta_1 (\zeta_2 \rightarrow \alpha = A_\kappa (h, g)) \), ¿no?

Sí, pero no era mi intención entrar en esos detalles. Sólo quería señalar que para formalizar con pelos y señales, no puedes poner lo esencial y ya está, que es lo que hacemos cuando escribimos normalmente, sino que hay que poner qué suponemos que es cada cosa y poner cuantificadores a todas las variables para asegurarnos de que todos quedan acotados. Si se trata de describir la estructura de una fórmula \( \alpha \), todo lo que aparecerá estará acotado por \( \mbox{Sub}(\alpha) \) o por conjuntos \( S_n(\mbox{Sub}(\alpha)) \), donde \( n \) estará acotado por \( \ell(\alpha) \), etc.

Dejamos a cargo del lector formalizar (si lo cree imprescindible) la definición de los axiomas de los funtores definidos por recursión. El caso es que así podemos completar la definición de una fórmula \( \alpha \in \mbox{Ax} \)(ARP) que se corresponde con la definición informal, y en particular permite probar que si \( \alpha \) es un axioma (metamatemático) de ARP, entonces

\( \mathop\vdash\limits_{\rm ARP}{\color{blue}\alpha} \in \mbox{Ax} \)(ARP).

Para que lo último sea cierto, realmente tendríamos que haber tomado como axiomas de ARP no todas las definiciones de funtores, sino algunas concretas con variables concretas, ¿no?

Quiero decir, que si tomamos como axiomas de ARP cualquier definición de funtores, tenemos entonces que \( \alpha \equiv c(x_1)=0 \) (donde \( x_1 \) es la variable de índice \( 1 \)) es un axioma de ARP, pero \( \color{blue} \alpha \) no será un axioma de ARP.

Sí, en la respuesta#5 dije que no merecía la pena precisar qué variables consideramos que aparecen en las definiciones de funtores porque es irrelevante. Hay dos opciones: admitir que \( c(x)=0 \) es un axioma para cualquier variable \( x \) o tomar como axioma únicamente \( c(x_0)=0 \) y entonces las demás fórmulas \( c(x)=0 \) son teoremas. Naturalmente, hay que elegir la misma opción metamatemáticamente y en la formalización. Yo he descrito la formalización con variables concretas porque es más fácil y eso presupone que tampoco tomamo a \( c(x_2)=0 \) como axioma, pero también es posible adoptar el criterio contrario complicando un poco la definición formal. Por ejemplo, en el caso de \( A_p(k n) \), en lugar de poner un \( \xi_n \) predefinido (una sucesión fija de variables), habría que decir: "existe \( \xi\in \mbox{Sub}(\alpha) \) tal que \( \ell(\xi)=n+1 \), y par cada \( i<\ell(\xi) \) se cumple que \( \xi_i \) es una variable, y las \( \xi_i \) son distintas dos a dos...

Deducciones Seguidamente, el lector debería convencerse de que no hay nada que impida formalizar en ARP la definición informal de deducción. El resultado tiene que ser una fórmula

\( \Pi\mathop{\vdash}\limits_{\rm \color{blue}ARP}^d\alpha\equiv  d_{\ell(d)\dot- 1}=\alpha\land  \forall i<\ell(d)\, (d_i\in \mbox{Form}({\color{blue}\mathcal L_{\rm arp}})\land(d_i\in \Pi\lor d_i\in \mbox{Ax} \)(ARP)\( \lor \cdots)),
 \)

donde los puntos suspensivos representan cuatro fórmulas más en la disyunción que expresan que \( d_i \) se sigue de fórmulas precedentes por una de las cuatro reglas de inferencia de ARP, pero no ganamos nada condensando dichas reglas en fórmulas de ARP. Basta observar que para formalizarlas no tenemos que hacer referencia a nada que no podamos acotar en términos de la sucesión \( d \) o de sus términos.

¿Podrías mostrar como sería, por ejemplo, la fórmula que habría que añadir para la regla \( S_1 \)?

Se que lo que habría que añadir sería algo de la forma

\( S_1(d_i) \equiv \exists k < \ell(d) \, d_i=S_x^t d_k \)

donde faltaría declarar la existencia de la variable \( x \) y el término \( t \). La variable si que veo que se puede extraer del propio \( d \) con algo de la forma

\( \exists x \, (x \in \mbox{Var}_{d_k}({\color{blue}\mathcal L_{\rm arp}})) \)

donde \( x \in \mbox{Var}_{s}({\color{blue}\mathcal L_{\rm arp}}) \) sería la formalización de que una variable está en un término \( s \) (pero claro, habría que formalizar esto). Pero, para el término \( t \) no lo veo tan claro.

Si pudieras dar aunque sea este con detalle para ya tener clara la dinámica lo agradecería mucho.

\( S_1(\alpha, \beta)\equiv \beta = \alpha \lor \exists xt\in \mbox{Sub}(\beta)(x\in \mbox{Var}({\color{blue}\mathcal L_{\rm arp}})\land t\in \mbox{Term}({\color{blue}\mathcal L_{\rm arp}})\land \beta = S_x^t\alpha) \)

La posibilidad \( \beta = \alpha \) está para incluir el caso de aplicar \( S_1 \) respecto de una variable que no esté en la fórmula inicial, con lo que la sustitución la deja igual.

En la definición de deducción pondrás:  \( \exists j<i\, S_1(d_j, d_i) \) para indicar la posibilidad de que \( d_i \) se deduzca de \( d_j \) por \( S_1 \).

Por ejemplo, si queremos enunciar en ARP las reglas de inferencia de la doble negación tenemos que formular algo del estilo de

\( {\color{blue}\lnot\lnot}\alpha\mathop\vdash\limits_{\rm \color{blue}ARP}^{f(\alpha)}\alpha \)

donde \( f \) es un funtor que, a cada fórmula \( \alpha \) le hace corresponder una deducción de \( \alpha \) a partir de \( {\color{blue}\lnot\lnot}\alpha \). Como sabemos deducir \( \alpha \) a partir de \( \lnot\lnot\alpha \), sabemos cómo definir un funtor que nos dé una deducción.

¿Podrías también poner un ejemplo de esto? De como sería dicho funtor y, ya puestos, ¿cómo se formaliza la negación?

Esta parte de formalizar una teoría dentro de ella misma es muy nueva para mi y me pierdo aun un poco.

No sé a qué te refieres con cómo se formaliza la negación. No sé si te refieres a \( {\color{blue}\lnot}\alpha \equiv {\color{blue}\lnot}\frown \alpha \), pero me extraña.

En cuanto a definir el funtor... ocuparía varias páginas, me temo (pero eso no es problema de la formalización, sino que escribir una demostración completamente detallada de esa regla (informalmente) ocuparía lo mismo). Si por caridad me dejas poner un ejemplo más simple, vamos a verlo para el caso de la regla de simetría, que está demostrada en la respuesta #6:

\( (S)\ \ \ \begin{array}{c} t_1=t_2\\ \hline t_2=t_1 \end{array} \)

La demostración hace referencia a un teorema previo, pero detallándola entera es:

\( \begin{array}{rll} (1)&t_1=t_2&\text{Premisa}\\
(2)&p_1^1(x_0)=x_0&\text{Axioma}\\
(3)&p_1^1(t_1)=t_1&S_1, 2\\
(4)&t_1=t_1&T 3, 3\\
(5)&t_2=t_1&T, 1, 4 \end{array} \)

Esto nos lleva a definir el funtor

\( D_S(x, y) = \left<x {\color{blue}=} y, p_1^1(x_0) {\color{blue}=} x_0, p_1^1(x){\color{orange}=}x, x {\color{blue}=}x, {\color{red}\cancel{x{\color{blue}=}y}},y{\color{blue}=}x\right> \).

que nos permite demostrar el teorema

\( t_1\in \mbox{Term}({\color{blue}\mathcal L_{\rm arp}})\land t_2\in \mbox{Term}({\color{blue}\mathcal L_{\rm arp}})\rightarrow \{t_1{\color{blue}=}t_2\}\mathop\vdash\limits_{\rm \color{blue}ARP}^{D_S(t_1, t_2)}t_{\color{red}2}{\color{blue} =}t_1 \).

La demostración consiste en comprobar que \( D(t_1, t_2) \) cumple la definición de deducción.

Para definir un funtor \( D_{DN}(\alpha) \) habría que hacerlo como lo hacemos informalmente, probando primero que tal fórmula es un teorema (para lo  cual usaremos que previamente hemos probado que otras fórmulas son teoremas), etc.

Y otra cuestión sobre esto, para indicar la formalización de la regla de inferencia no deberíamos escribir más bien algo como

\( \mathop\vdash\limits_{\rm ARP} {\color{blue}\lnot\lnot}\alpha\mathop\vdash\limits_{\rm \color{blue}ARP}^{f(\alpha)}\alpha \)

Porque si no, simplemente estamos escribiendo una fórmula, sin más, ¿no?

Si quieres escribir eso, tendrás que ponerle delante un \( \alpha\in \mbox{Form}({\color{blue}\mathcal L_{\rm arp}})\rightarrow \cdots \)

Y así tienes una fórmula que es un teorema de ARP. Siempre puedes añadirle delante un \( \mathop\vdash\limits_{\rm ARP} \), claro, pero normalmente enunciamos los teoremas de ARP sin ponerles delante \( \mathop\vdash\limits_{\rm ARP} \).

Sin más que esta obligación de explicitar siempre las demostraciones de los teoremas a los que hagamos referencia, el lector debería convencerse de que nada —salvo la brevedad de la vida— le impide demostrar todos los resultados que hemos expuesto en este hilo sobre ARP que no involucren conceptos semánticos. Por ejemplo, la formalización del teorema de deducción consiste en definir funtores \( D \), \( P \), \( D' \) de modo que

\( \Pi\cup\{\alpha\}\mathop{\vdash}\limits_{\rm \color{blue}ARP}^d\beta\rightarrow \left(\Pi\cup P(d, \alpha)\mathop{\vdash}\limits_{\rm \color{blue}ARP}^{D(d, \alpha)}\alpha{\color{blue}\rightarrow} \beta\right)\land \forall \gamma\in P(d,\alpha)\!\!\! \mathop{\vdash}\limits_{\rm \color{blue}ARP}^{D'(d, \alpha, \gamma)}\!\!\!\!\gamma \)

(con todas las hipótesis y conclusiones adicionales del teorema, es decir, hay que suponer que la deducción \( d \) no usa las reglas \( S_1 \) o \( I_0 \) respecto a variables que estén en \( \alpha \) y podemos concluir que la deducción \( D(d, \alpha) \) sólo usa estas reglas respecto de variables para las que ya se usaban en \( d \)).

Podemos asegurar que existen tales funtores (sin necesidad de definirlos explícitamente) porque la demostración del teorema de deducción es totalmente constructiva: determina completamente qué teoremas \( P(d, \alpha) \) necesitamos tomar como premisas (y cuáles son sus demostraciones) y cómo construir una deducción de \( \alpha\rightarrow \beta \) a partir de una deducción de \( \beta \).

El teorema de deducción es demasiado, pero si estaría bien tener algún ejemplo de lo que mencionas (tal vez más simple que lo que te he preguntado antes)

¿Te vale el que te he puesto para la regla de simetría?

Pero no deberías quedarte con la idea de que eso de formalizar la lógica es complicadísimo. Tendríamos el mismo problema si me pidieras que te pusiera aquí una demostración de la regla de doble negación, sin partir de nada previo.

Por ejemplo, una demostración razonable de la regla de doble negación (que siga el camino que hemos seguido en el hilo) supone

1) que ya hemos demostrado antes que hay un funtor \( D \) tal que

\( \alpha\in \mbox{Form}({\color{blue}\mathcal L_{\rm arp}})\rightarrow \mathop\vdash\limits_{\rm\color{blue}ARP}^{D(\alpha)}{\color\blue\lnot\lnot}\alpha{\color{blue}\rightarrow}\alpha \)

Esto es la formalización del teorema 2 de la respuesta #9.

2)  que también hemos demostrado ya la regla del modus ponens, es decir, que hemos construido un funtor MP tal que

\( \alpha\in \mbox{Form}({\color{blue}\mathcal L_{\rm arp}})\land \beta\in \mbox{Form}({\color{blue}\mathcal L_{\rm arp}})\rightarrow \{\alpha{\color{blue}\rightarrow}\beta, \alpha\}\mathop\vdash\limits_{\rm\color{blue}ARP}^{\rm MP(\alpha, \beta)}\beta \)

A partir de ahí ya es fácil definir el funtor DN que me pides.

\( \mbox{DN}(x) = D(x)\frown \mbox{MP}({\color{blue}\lnot\lnot}\alpha{\color{blue}\rightarrow}\alpha, {\color{blue}\lnot\lnot}\alpha) \).

En efecto, este funtor, cuando lo calculas en una fórmula \( \alpha \), te calcula una demostración de \( {\color{blue}\lnot\lnot}\alpha{\color{blue}\rightarrow}\alpha \) y le pone a continuación una deducción de \( \alpha \) con premisas \( {\color{blue}\lnot\lnot}\alpha{\color{blue}\rightarrow}\alpha \) y \( {\color{blue}\lnot\lnot}\alpha \), y todo junto es una deducción de \( \alpha \) con premisa \( {\color{blue}\lnot\lnot}\alpha \).

Pero todos estos detalles son irrelevantes. Lo importante es que el lector debería convencerse de que ahora puede releer todo lo dicho en este hilo no en color rojo considerando que está leyendo teoremas de ARP, en el mismo sentido que si abre cualquier libro de álgebra o de cálculo diferencial puede entender que está leyendo teoremas de ZFC a pesar de que no vea en ninguna parte chirimbolitos lógicos y axiomas ni nada de todo eso.

Aquí, entiendo que lo que quieres decir es que cualquier teorema metamatemático de los que hayamos visto ahora podemos verlo como un teorema de ARP, ¿no? Es decir, que podríamos convertir el hilo en algo del estilo de Principia Mathematica. Simplemente, tras exponer informalmente los axiomas y reglas de inferencia de ARP, pasar a enumerar una serie de teoremas de ARP que abarcaría todo lo dicho en el hilo. ¿Es esto a lo que te referías?

Sí, pero entendiendo que eso es prácticamente inviable, como es inviable escribir cualquier teorema matemático del estilo del teorema del valor medio detallando completamente su formalización en ZF.

La respuesta a la pregunta: ¿qué es necesario suponer para estudiar metamatemáticamente la lógica formal (sin entrar en semántica (modelos, etc.)? es: como máximo (las versiones informales de) los axiomas y reglas de inferencia de ARP, lo cual es muy poco suponer.

Con esta frase me surge una duda. Hemos formalizado ARP dentro de ARP, pero lo que tu dices aquí es que ARP te permite estudiar toda la parte formal de la lógica matemática. Es decir, afirmas que con ARP podemos formalizar, por ejemplo, el concepto de lenguaje de primer orden, de teoría axiomática, de demostración en un lenguaje de dicho tipo, etc., ¿o no lo he entendido bien?

Si es así, esto último no lo veo tan tan claro.

Pues eso es exactamente lo que digo. Quizá lo que te hace desconfiar es que, cietamente, no es posible dar una definición de "lenguaje formal de primer orden" en ARP, pero, dado cualquier lenguaje formal de primer orden, como el de la aritmética de Peano, o el de la teoría de conjuntos, etc., sí que puedes formalizar ese lenguaje en ARP exactamente igual que hemos hecho con el lenguaje de ARP.

Por ejemplo, si quieres formalizar el lenguaje \( \mathcal L_{\rm tc} \) de la teoría de conjuntos, con el convenio de que sus variables sean \( x_0 \equiv 0, x_1\equiv x0, x_2\equiv xx0 \), donde ahora \( x \) y \( 0 \) sólo son signos para construir variables, sólo tienes que empezar definiendo:

\( {\color{blue} 0} = 0, \quad {\color{blue} x} =1, \quad {\color{blue} \lnot} =2, \quad {\color{blue} \rightarrow } = 3, \quad {\color{blue} \forall} = 4, \quad {\color{blue} =} = 5, \quad {\color{blue} \in} = 6 \)

Definimos \( \mbox{Sig}({\color{blue}\mathcal L_{\rm tc}}) = \{0, 1, 2, 3, 4, 5, 6\} \), definimos \( x\in \mbox{Var}({\color{blue}\mathcal L_{\rm tc}}) \) exactamente igual que en ARP, de modo que tenemos un funtor \( x_k \) que a cada número natural \( k \) le hace corresponder la variable \( k \)-ésima de \( {\color{blue}\mathcal L_{\rm tc}} \), etc.

A partir de ahí puedes definir las cadenas de signos, los términos, las fórmulas, los axiomas, los teoremas, etc.

Pero no hace falta que lo hagas por separado para cada lenguaje formal. Sólo tienes que definir que tenemos un "lenguaje formal" siempre que hayamos especificado en ARP varios ingredientes:

  • Una fórmula \( x\in \mbox{Var}({\color{blue}\mathcal L}) \) junto con dos funtores \( x, {\rm ind} \) tales que se pueda demostrar en ARP:

    • \( x_i\in \mbox{Var}({\color{blue}\mathcal L}) \),
    • \( \mbox{ind}(x_i)=i \)
    • \( x\in \mbox{Var}({\color{blue}\mathcal L})\land \mbox{ind}(x)=i\rightarrow x = x_i \).

    Esto te asegura que tenemos infinitas variables, que no son ni más ni menos que las que da el funtor \( x \).
  • Una fórmula \( c\in \mbox{Const}({\color{blue}\mathcal L}) \) con un funtor \( c \) que cumplan las mismas condiciones que para las variables (con el mismo funtor ind) o bien que haya un numeral NC de modo que lo que se prueba es:

    • \( i<\mbox{NC}\rightarrow c_i\in \mbox{Const}({\color{blue}\mathcal L}) \),
    • \( i<\mbox{NC}\rightarrow \mbox{ind}(c_i)=i \)
    • \( c\in \mbox{Var}({\color{blue}\mathcal L})\land \mbox{ind}(c)=i\rightarrow c = c_i\land i<\mbox{NC} \).

    Así cubrimos el caso de un lenguaje con infinitas constantes o bien con un número finito de constantes (tal vez ninguna).

  • Una fórmula \( R\in \mbox{Rel}({\color{blue}\mathcal L}) \) junto con un funtor rang, al que le exigimos lo necesario para que \( \mbox{rang}(R)=n \) signifique que \( R \) es un relator n-ádico, etc.

Y así añadimos todo lo necesario para que quede determinado qué relatores y funtores tiene el lenguaje, etc., así como condiciones que aseguren que un mismo signo no está en dos categorías, etc.

Si quieres los detalles, igual que han hecho falta un par de mensajes para formalizar ARP, podría añadir un par más para formalizar en ARP la lógica de primer orden para lenguajes arbitrarios.

Como digo, esta última parte de la formalización de una teoría dentro de la propia teoría aun me cuesta bastante de entender. A ver si poco a poco voy asimilándola mejor.

Pues, aunque aquí no le podríamos sacar partido y por ello no he hablado del asunto, ¡también podemos formalizar la formalización!  >:D  Quiero decir que puedes formalizar la aplicación \( \zeta\mapsto {\color{blue} \zeta} \) que a cada cadena metamatemática le hace corresponder su formalización, lo cual significa definir un funtor Azul tal que en ARP puedes definir un funtor FA con el que probar:

\( \zeta\in \mbox{Cad}({\color{blue} \mathcal L_{\rm arp}})\rightarrow \mathop\vdash\limits_{\rm\color{blue}ARP}^{\rm FA(\zeta)}\mbox{Azul}(\zeta){\color{blue}\  \in \mbox{Cad}(\mathcal L_{\rm arp})} \),

donde \( x\in \mbox{Cad}(\mathcal L_{\rm arp}) \) es la formalización de la fórmula \( x\in \mbox{Cad}({\color{blue}\mathcal L_{\rm arp}}) \).

07 Agosto, 2023, 12:07 pm
Respuesta #275

Eparoh

  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 983
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
He vuelto  8^)

¡Cuánta paciencia tienes!

La verdad es que es la única virtud que realmente podría considerar que trabajo día a día ::)


Me ha quedado todo bastante más claro, pero aun quedán pequeñas dudas.


Debería poner:

\( \exists h\in\mbox{Sub}(\alpha)\exists mn\leq {\color{red} \ell (}\alpha {\color{red} )}\exists g\in S_m(\mbox{Sub}(\alpha)) \)

Debería ser con lo que he añadido en rojo, ¿no?

\( S_1(\alpha, \beta)\equiv \beta = \alpha \lor \exists x{\color{red} \in \mbox{Sub}(\alpha) \exists}t\in \mbox{Sub}(\beta)(x\in \mbox{Var}({\color{blue}\mathcal L_{\rm arp}})\land t\in \mbox{Term}({\color{blue}\mathcal L_{\rm arp}})\land \beta = S_x^t\alpha) \)

La posibilidad \( \beta = \alpha \) está para incluir el caso de aplicar \( S_1 \) respecto de una variable que no esté en la fórmula inicial, con lo que la sustitución la deja igual.

En la definición de deducción pondrás:  \( \exists j<i\, S_1(d_j, d_i) \) para indicar la posibilidad de que \( d_i \) se deduzca de \( d_j \) por \( S_1 \).

Aquí sería así, ¿no? Porque, si sustituimos la variable, donde la encontraremos será en la fórmula anterior de la deducción, no justo en la que estamos considerando.

\( D_S(x, y) = \left<x {\color{blue}=} y, p_1^1(x_0) {\color{blue}=} x_0, p_1^1(x){\color{orange}=}x, x {\color{blue}=}x, {\color{red}\cancel{x{\color{blue}=}y}},y{\color{blue}=}x\right> \).

que nos permite demostrar el teorema

\( t_1\in \mbox{Term}({\color{blue}\mathcal L_{\rm arp}})\land t_2\in \mbox{Term}({\color{blue}\mathcal L_{\rm arp}})\rightarrow \{t_1{\color{blue}=}t_2\}\mathop\vdash\limits_{\rm \color{blue}ARP}^{D_S(t_1, t_2)}t_{\color{red}2}{\color{blue} =}t_1 \).

Supongo que esto es correcto con las correcciones que he hecho, ¿no? (lo que he marcado en naranja es porque creo que faltaba ponerlo en azul)

Por ejemplo, si queremos enunciar en ARP las reglas de inferencia de la doble negación tenemos que formular algo del estilo de

\( {\color{red}\{}{\color{blue}\lnot\lnot}\alpha{\color{red}\}}\mathop\vdash\limits_{\rm \color{blue}ARP}^{f(\alpha)}\alpha \)

donde \( f \) es un funtor que, a cada fórmula \( \alpha \) le hace corresponder una deducción de \( \alpha \) a partir de \( {\color{blue}\lnot\lnot}\alpha \). Como sabemos deducir \( \alpha \) a partir de \( \lnot\lnot\alpha \), sabemos cómo definir un funtor que nos dé una deducción.

Aquí faltarían las llaves que he puesto, ¿no?

No sé a qué te refieres con cómo se formaliza la negación. No sé si te refieres a \( {\color{blue}\lnot}\alpha \equiv {\color{blue}\lnot}\frown \alpha \), pero me extraña.

Para definir un funtor \( D_{DN}(\alpha) \) habría que hacerlo como lo hacemos informalmente, probando primero que tal fórmula es un teorema (para lo  cual usaremos que previamente hemos probado que otras fórmulas son teoremas), etc.

Pero no deberías quedarte con la idea de que eso de formalizar la lógica es complicadísimo. Tendríamos el mismo problema si me pidieras que te pusiera aquí una demostración de la regla de doble negación, sin partir de nada previo.

Por ejemplo, una demostración razonable de la regla de doble negación (que siga el camino que hemos seguido en el hilo) supone

1) que ya hemos demostrado antes que hay un funtor \( D \) tal que

\( \alpha\in \mbox{Form}({\color{blue}\mathcal L_{\rm arp}})\rightarrow \mathop\vdash\limits_{\rm\color{blue}ARP}^{D(\alpha)}{\color\blue\lnot\lnot}\alpha{\color{blue}\rightarrow}\alpha \)

Esto es la formalización del teorema 2 de la respuesta #9.

2)  que también hemos demostrado ya la regla del modus ponens, es decir, que hemos construido un funtor MP tal que

\( \alpha\in \mbox{Form}({\color{blue}\mathcal L_{\rm arp}})\land \beta\in \mbox{Form}({\color{blue}\mathcal L_{\rm arp}})\rightarrow \{\alpha{\color{blue}\rightarrow}\beta, \alpha\}\mathop\vdash\limits_{\rm\color{blue}ARP}^{\rm MP(\alpha, \beta)}\beta \)

A partir de ahí ya es fácil definir el funtor DN que me pides.

\( \mbox{DN}(x) = D(x)\frown \mbox{MP}({\color{blue}\lnot\lnot}\alpha{\color{blue}\rightarrow}\alpha, {\color{blue}\lnot\lnot}\alpha) \).

En efecto, este funtor, cuando lo calculas en una fórmula \( \alpha \), te calcula una demostración de \( {\color{blue}\lnot\lnot}\alpha{\color{blue}\rightarrow}\alpha \) y le pone a continuación una deducción de \( \alpha \) con premisas \( {\color{blue}\lnot\lnot}\alpha{\color{blue}\rightarrow}\alpha \) y \( {\color{blue}\lnot\lnot}\alpha \), y todo junto es una deducción de \( \alpha \) con premisa \( {\color{blue}\lnot\lnot}\alpha \).

Aquí entiendo lo que quieres decir, pero mi duda era sobre que son exactamente \( \color{blue} \neg \) o \( \color{blue} \rightarrow \).

Cuando definimos en ARP los símbolos lógicos lo hicimos mediante unas fórmulas muy concretas que significaban lo que buscábamos que significaran, pero ahora, al poner aquí dichos símbolos en azul no entiendo muy bien a lo que te refieres. ¿Debo entender que cuando pones \( {\color{blue} \neg} \alpha \) (con \( \alpha \) una fórmula de \( \color{blue} \mathcal{L}_{\rm arp} \)) lo que se entiende es que es la formalización correspondiente a la fórmula \( \lnot\alpha\equiv 1\dot{-} t_\alpha =0 \) que en su día vimos? Pero, si es así, no tiene mucho sentido hablar de \( \color{blue} \neg \) por separado, ¿no? No entiendo entonces que significaría \( {\color{blue} \neg} \frown \alpha \).

Por último, respecto a la formalización de la lógica de primer orden (y la formalización de la formalización que es ya una locura :laugh:), creo que (por mi) no hace falta que añadas esta parte, porque con lo que has comentado me queda claro que es posible hacerlo sin más que meterse en el mundo tedioso de formalizar todo. Además, si no me equivoco (lo he ojeado muy por encima para asegurarme) en tu libro de lógica si que detallas todo esto y, aunque no sea para ARP, creo que con lo que has comentado, todo este hilo y lo que pones en tu libro podría formalizar toda esa parte por mi cuenta (y en algún momento lo haré para ver si es cierto  ::)).

EDITO

Una duda de última hora.

En su día, te pregunté si el último teorema de la respuesta #7 debería ir en rojo y me respondiste que no, pero que para un formalista radical habría que cambiar un poco el enunciado y la demostración para que fuera plenamente formal. Por tanto, este metateorema debe ser también formalizable en ARP, ¿no? Pero, me surge la duda de que esto sea posible pues en la demostación (para el formalista radical) habría que incluir la construcción de \( N(t) \), pero ya vimos que no es posible formalizar el "número denotado por un término sin variables".

Si es posible entonces formalizarlo, ¿cómo sería entonces el teorema de ARP que lo formaliza?

EDITO 2

Se me ha olvidado preguntar otra cosa que tenía en la mente.

Si tenemos que

\( \gamma_1, \cdots, \gamma_m \mathop\vdash\limits_{\rm ARP} \alpha \)

y la deducción está formada por las fórmulas \( \delta_1, \cdots, \delta_n \), se puede concluir entonces que si es \( d=\langle {\color{blue} \delta_1}, \cdots, {\color{blue} \delta_n} \rangle \) se cumple que

\( \mathop\vdash\limits_{\rm ARP} \{{\color{blue} \gamma_1}, \cdots, {\color{blue} \gamma_m}\} \mathop\vdash^d\limits_{\color{blue} \rm ARP} {\color{blue} \alpha} \)

Creo que tiene sentido, y no veo porque no sería cierto, pero ya no me fío de nada ::)

Un saludo.

07 Agosto, 2023, 01:22 pm
Respuesta #276

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
\( \exists h\in\mbox{Sub}(\alpha)\exists mn\leq {\color{red} \ell (}\alpha {\color{red} )}\exists g\in S_m(\mbox{Sub}(\alpha)) \)

Debería ser con lo que he añadido en rojo, ¿no?
[/quote]

Lo he cambiado en el hilo, porque resulta más natural, pero en realidad da lo mismo, por la propia definición de longitud se cumple que \( \ell(\alpha)\leq \alpha \) (pues \( \ell(\alpha) \) es la primera componente de \( \alpha \) como par ordenado más 1).

\( S_1(\alpha, \beta)\equiv \beta = \alpha \lor \exists x{\color{red} \in \mbox{Sub}(\alpha) \exists}t\in \mbox{Sub}(\beta)(x\in \mbox{Var}({\color{blue}\mathcal L_{\rm arp}})\land t\in \mbox{Term}({\color{blue}\mathcal L_{\rm arp}})\land \beta = S_x^t\alpha) \)

La posibilidad \( \beta = \alpha \) está para incluir el caso de aplicar \( S_1 \) respecto de una variable que no esté en la fórmula inicial, con lo que la sustitución la deja igual.

En la definición de deducción pondrás:  \( \exists j<i\, S_1(d_j, d_i) \) para indicar la posibilidad de que \( d_i \) se deduzca de \( d_j \) por \( S_1 \).

Aquí sería así, ¿no? Porque, si sustituimos la variable, donde la encontraremos será en la fórmula anterior de la deducción, no justo en la que estamos considerando.

Cierto. Me salto otras correcciones que has hecho en la que también es justo como dices (las he cambiado en el mensaje correspondiente).

Aquí entiendo lo que quieres decir, pero mi duda era sobre que son exactamente \( \color{blue} \neg \) o \( \color{blue} \rightarrow \).

¡Uf! Ahí no estaba yo situado. Estaba pensando en un lenguaje "normal" de primer orden. Tienes razón. Lo que sucede es que \( \color{blue} \neg \) y \( \color{blue} \rightarrow \) no deben ir en azul. Son un funtor monádico y un funtor diádico, respectivamente, que a cada fórmula o par de fórmulas les hacen corresponder otra, según la definición del negador y del implicador en ARP.

Por último, respecto a la formalización de la lógica de primer orden (y la formalización de la formalización que es ya una locura :laugh:), creo que (por mi) no hace falta que añadas esta parte, porque con lo que has comentado me queda claro que es posible hacerlo sin más que meterse en el mundo tedioso de formalizar todo.

Sólo una observación sobre "el mundo tedioso de formalizarlo todo", y es insistir en que eso no es nada específico ni de ARP ni de la formalización de la lógica, sino que si tratamos de escribir en cualquier lenguaje formal cualquier afirmación matemática nos encontraríamos con el mismo tedio. Sería como intentar programar usando directamente el código máquina. Por ello, la forma natural de convencerse de que algo es formalizable en ARP (o en ZFC o en cualquier teoría axiomática) no es ponerse a formalizar con todo detalle, sino comprobar que no se está afirmando nada que exceda la capacidad de expresión de la teoría correspondiente. Esto es prácticamente trivial en el caso de ZFC mientras uno no se acerque a las clases propias (que sí que dan lugar a impedimentos técnicos de naturaleza similar a los que nos impiden usar cuantificadores no acotados en ARP, con lo que nos podemos encontrar con que tenemos bien claro algo que queremos decir, pero no puede decirse en la teoría), y en el caso de ARP requiere ir comprobando que todos los conceptos que se definen pueden introducirse como funtores y que no usamos cuantificadores fantasmas (como cuando yo razonaba por inducción sobre el cardinal de \( y \), con lo que presuponía un "para todo" fantasma).

Si tenemos que

\( \gamma_1, \cdots, \gamma_m \mathop\vdash\limits_{\rm ARP} \alpha \)

y la deducción está formada por las fórmulas \( \delta_1, \cdots, \delta_n \), se puede concluir entonces que si es \( d=\langle {\color{blue} \delta_1}, \cdots, {\color{blue} \delta_n} \rangle \) se cumple que

\( \mathop\vdash\limits_{\rm ARP} \{{\color{blue} \gamma_1}, \cdots, {\color{blue} \gamma_m}\} \mathop\vdash^d\limits_{\color{blue} \rm ARP} {\color{blue} \alpha} \)

Creo que tiene sentido, y no veo porque no sería cierto, pero ya no me fío de nada ::)

Por el mismo precio puedes poner la \( d \) en azul, para dejar constancia de que no es una variable, sino un término sin variables (o incluso un numeral, si la defines como tal). La respuesta a tu pregunta es que, evidentemente, se puede demostrar. Porque la fórmula por la que preguntas no tiene variables. Y, puesto que es verdadera, es demostrable en ARP, precisamente por el último teorema de la respuesta #7.

En su día, te pregunté si el último teorema de la respuesta #7 debería ir en rojo y me respondiste que no, pero que para un formalista radical habría que cambiar un poco el enunciado y la demostración para que fuera plenamente formal. Por tanto, este metateorema debe ser también formalizable en ARP, ¿no? Pero, me surge la duda de que esto sea posible pues en la demostación (para el formalista radical) habría que incluir la construcción de \( N(t) \), pero ya vimos que no es posible formalizar el "número denotado por un término sin variables".

Si es posible entonces formalizarlo, ¿cómo sería entonces el teorema de ARP que lo formaliza?

Ese teorema no puede formalizarse en ARP, porque es tanto como formalizar una definición del número denotado por un término, y ya hemos visto que no se puede.

Lo que puede discutirse es si el teorema debe ir en rojo o no. Cuando hablaba de "cambiar un poco el enunciado" me refería simplemente a quitar lo de "el número denotado" que produciría urticaria al formalista radical, y dejarlo en "podemos calcular un número tal que".

Preferiría pensar un poco más mi respuesta a esto, porque es más filosófica que matemática. La idea es que formalista radical y finitista radical no son necesariamente sinónimos. La pregunta es si un formalista radical aceptaría que, dado un término de ARP, siempre puede demostrar que es igual a un cierto numeral. Planteado así, ello no requiere que admita que el númeral y el término "significan lo mismo", sino que es una mera afirmación sobre que algo puede ser demostrado. El formalista puede admitirlo sin renunciar a su formalismo radical, pero ¿admitirá la demostración? Yo diría que sí, pero quiero pensar un poco más sobre ello y sobre las implicaciones que tiene. El problema es que necesitaríamos tener delante un formalista radical para ver qué dice, y no lo tenemos.    ;D

07 Agosto, 2023, 05:40 pm
Respuesta #277

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Completo aquí mi respuesta a tu pregunta sobre si el teorema sobre evaluación de términos debería o no ir en rojo.

Como te decía, no es lo mismo formalista que finitista. Un formalista es alguien que quiere trabajar con las teorías axiomáticas prescindiendo por completo de su significado, lo cual no está reñido con que admita, aunque sea a regañadientes, que para ello tiene que aceptar cierta metamatemática informal en la que el significado lo es todo.

En esos términos el teorema en cuestión es un teorema informal, pero con un contenido puramente formalista: habla de que ciertas fórmulas se pueden demostrar en ARP, lo cual tiene perfecto sentido para un formalista, sin entrar en el significado de esas fórmulas.

Otra cosa es qué entendemos por finitismo, no porque no esté clara la idea general, sino porque uno puede ser más o menos generoso poniendo límites al finitismo. Podemos decir que ARP formaliza el finitismo más exigente (si nos olvidamos de los ultrafinitistas, a los que hay que dar de comer aparte). Y sucede que la función que evalúa los funtores de ARP es recursiva, pero no recursiva primitiva.

¿Qué es una función recursiva? En la práctica, las funciones recursivas son las que puede calcular un ordenador, de modo que las funciones recursivas primitivas son parte de —pero no todas— las funciones recursivas. Es posible caracterizar las funciones recursivas con una definición idéntica a la de las funciones recursivas primitivas sin más que añadir una tercera forma de definir funciones, además de la composición y la recursión:

Si \( g \) es una función \( n+1 \)-ádica recursiva, también es recursiva la función \( n \)-ádica definida a partir de ella por minimización:

\( f(x_1,\ldots, x_n) =  \) el mínimo número natural \( x_0 \) que cumple \( {\color{red}g}(x_0, x_1, \ldots, x_n)=0 \),

siempre y cuando podamos asegurar que para todos los valores posibles \( x_1,\ldots, x_n \) siempre existe al menos un número natural \( x_0 \) que cumple \( {\color{red}g}(x_0, \ldots, x_n) = 0 \).

Notemos que no vale el truco de entender que \( f(x_1, \ldots, x_n) \) vale \( 0 \) cuando no existe ningún \( x_0 \) que cumpla lo requerido, porque entonces podría ocurrir que pudiéramos calcular la función \( g \) y no pudiéramos saber cuánto vale \( f \) porque no sepamos si \( g \) toma o no toma el valor cero para algún \( x_0 \). La función \( f \) estaría definida, pero no tendríamos ninguna garantía de que se puede calcular.

En términos de lenguajes de programación, las funciones recursivas primitivas son las que pueden programarse sin usar más que bucles del tipo for n = 1 to k, mientras que las funciones recursivas admiten bucles del tipo while x = 0... que corren el riesgo de que el programa se quede colgado esperando a que \( x \) deje de valer \( 0 \) sin que eso vaya a ocurrir nunca, y así no proporcione ningún resultado.

Y ahí, en las palabras en negrita, está la objeción que un finitista puede poner a las funciones recursivas generales: ¿qué argumentos valen para asegurar que la función \( \color{red} g \) siempre toma el valor cero?

Las funciones recursivas primitivas forman una clase de funciones perfectamente definidas, por lo que dan pie a la formulación de la Aritmética Recursiva Primitiva, que no admite otro tipo de funciones. En cambio, mientras uno puede tener ejemplos de funciones que claramente son recursivas, aunque no recursivas primitivas (como las que hemos discutido en el hilo que no son formalizables en ARP), no se puede dar una definición precisa de cuándo podemos dar por válida una definición de una función recursiva. Está claro que podemos darla por válida cuando nos convenzamos de que efectivamente los mínimos siempre van a existir, pero ¿bajo qué condiciones generales podemos asegurar que eso sucede?

En estos términos, el teorema en cuestión involucra una función recursiva que no es recursiva primitiva. ¿Tiene un formalista algo que objetar en tanto que formalista? Yo diría que no. ¿Y un finitista? Pues no sé. Habría que hablar con uno. En este caso en concreto es fácil programar un ordenador para que calcule la función de la que habla el teorema, y me cuesta creer que un finitista no acepte considerar como "real" una función cuando es posible dar un argumento irrefutable de que un programa de ordenador la calcula y nunca nos va dejar tirados sin acabar el cálculo. Pero eso es una cosa (que podamos dar sin duda por recursiva una función) y otra tener una teoría general sobre funciones recursivas similar a ARP. Por supuesto podemos estudiar las funciones recursivas en teorías axiomáticas más o menos potentes, pero aislar quirúrgicamente las funciones recursivas como ARP aísla las funciones recursivas primitivas ya no me parece viable.

Un concepto relacionado es el de "función demostrablemente recursiva" en una teoría axiomática, es decir, una función definida por composición, recursión y minimización a partir de las funciones recursivas elementales en una teoría axiomática en la que se puede demostrar que los mínimos requeridos siempre existen. Sobre esto podré decir algo más en cuanto haya escrito el siguiente (y último) mensaje del hilo.

08 Agosto, 2023, 12:58 am
Respuesta #278

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Ya he terminado el hilo. Lo que decía que podía añadir sobre las funciones demostrablemente recursivas es que puede probarse que las funciones demostrablemente recursivas en \( {\rm I}\Sigma_1 \) son precisamente las funciones recursivas primitivas, es decir, que si sólo admitimos como funciones recursivas a las que podemos probar que lo son mediante procedimientos estrictamente finitistas, obtenemos precisamente las funciones recursivas primitivas que estudiamos con ARP

Naturalmente, aunque el hilo haya terminado, este hilo de comentarios queda abierto indefinidamente.

08 Agosto, 2023, 11:19 am
Respuesta #279

Eparoh

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

Ya están casi resueltas todas las dudas, pero ciertas cosas se resisten.

Cierto. Me salto otras correcciones que has hecho en la que también es justo como dices (las he cambiado en el mensaje correspondiente).

Como esto no lo has mencionado ni cambiado:

\( D_S(x, y) = \left<x {\color{blue}=} y, p_1^1(x_0) {\color{blue}=} x_0, p_1^1(x){\color{orange}=}x, x {\color{blue}=}x, {\color{red}\cancel{x{\color{blue}=}y}},y{\color{blue}=}x\right> \).

que nos permite demostrar el teorema

\( t_1\in \mbox{Term}({\color{blue}\mathcal L_{\rm arp}})\land t_2\in \mbox{Term}({\color{blue}\mathcal L_{\rm arp}})\rightarrow \{t_1{\color{blue}=}t_2\}\mathop\vdash\limits_{\rm \color{blue}ARP}^{D_S(t_1, t_2)}t_{\color{red}2}{\color{blue} =}t_1 \).

Supongo que esto es correcto con las correcciones que he hecho, ¿no? (lo que he marcado en naranja es porque creo que faltaba ponerlo en azul)

No me queda claro si son correctos los tres cambios que propongo o se te había pasado entre todo lo demás del mensaje.

¡Uf! Ahí no estaba yo situado. Estaba pensando en un lenguaje "normal" de primer orden. Tienes razón. Lo que sucede es que \( \color{blue} \neg \) y \( \color{blue} \rightarrow \) no deben ir en azul. Son un funtor monádico y un funtor diádico, respectivamente, que a cada fórmula o par de fórmulas les hacen corresponder otra, según la definición del negador y del implicador en ARP.

Entiendo. Por hacerme un poco más con todo el tema, vamos a ver si los defino correctamente.

Para la negación, si consideramos que \( \color{blue} \cdot \), \( \color{blue} \dot{-}  \) y \( {\color{blue} |} \cdot {\color{blue}|}  \) son las formalizaciones de los funtores de ARP \( \cdot \), \( \dot{-} \) y \(  \left |{\cdot}\right | \) respectivamente,  definiríamos (por ejemplo)

\( \neg x=\begin{cases}{N_1 {\color{blue} \dot{-}} {\color{blue}|} T_1(x)  {\color{blue} \dot{-}} T_2(x) {\color{blue}|}} {\color{blue} =} N_0&\text{si}& x \in \text{Form}({\color{blue} \mathcal{L}_{\rm arp}})\\0 & \text{si}& \text{no se cumple lo anterior}\end{cases} \)

y

\( x \rightarrow y=\begin{cases}{(N_1 {\color{blue} \dot{-}} {\color{blue}|} T_1(x)  {\color{blue} \dot{-}} T_2(x) {\color{blue}|}) {\color{blue} \cdot} {\color{blue}|} T_1(y)  {\color{blue} \dot{-}} T_2(y) {\color{blue}|}} {\color{blue} =} N_0&\text{si}& x \in \text{Form}({\color{blue} \mathcal{L}_{\rm arp}}) \wedge y \in \text{Form}({\color{blue} \mathcal{L}_{\rm arp}})\\0 & \text{si}& \text{no se cumple lo anterior}\end{cases} \)

Y, con dichas definiciones, se cumpliría que si \( \alpha, \beta \) son fórmulas de ARP, entonces son teoremas de ARP:

\(
\begin{align*}
{\color{blue} \neg \alpha} & = \neg {\color{blue} \alpha}\\
{\color{blue} \alpha \rightarrow \beta} & = {\color{blue} \alpha} \rightarrow {\color{blue} \beta}
\end{align*}
 \)

¿Sería correcto?

Sólo una observación sobre "el mundo tedioso de formalizarlo todo", y es insistir en que eso no es nada específico ni de ARP ni de la formalización de la lógica, sino que si tratamos de escribir en cualquier lenguaje formal cualquier afirmación matemática nos encontraríamos con el mismo tedio. Sería como intentar programar usando directamente el código máquina. Por ello, la forma natural de convencerse de que algo es formalizable en ARP (o en ZFC o en cualquier teoría axiomática) no es ponerse a formalizar con todo detalle, sino comprobar que no se está afirmando nada que exceda la capacidad de expresión de la teoría correspondiente. Esto es prácticamente trivial en el caso de ZFC mientras uno no se acerque a las clases propias (que sí que dan lugar a impedimentos técnicos de naturaleza similar a los que nos impiden usar cuantificadores no acotados en ARP, con lo que nos podemos encontrar con que tenemos bien claro algo que queremos decir, pero no puede decirse en la teoría), y en el caso de ARP requiere ir comprobando que todos los conceptos que se definen pueden introducirse como funtores y que no usamos cuantificadores fantasmas (como cuando yo razonaba por inducción sobre el cardinal de \( y \), con lo que presuponía un "para todo" fantasma).

Lo entiendo sí, pero (a mi parecer) cuando uno empieza con esto (como con cualquier otra rama de las matemáticas) si tiene que pringarse al principio para convencerse de que lo ha entendido bien y llegar a entender realmente los límites expresivos de la teoría. No es formalizar por formalizar todo con mucho detalle, es solo asegurarme de que he comprendido bien los detalles para ya poder dar el paso que mencionas :)

En su día, te pregunté si el último teorema de la respuesta #7 debería ir en rojo y me respondiste que no, pero que para un formalista radical habría que cambiar un poco el enunciado y la demostración para que fuera plenamente formal. Por tanto, este metateorema debe ser también formalizable en ARP, ¿no? Pero, me surge la duda de que esto sea posible pues en la demostación (para el formalista radical) habría que incluir la construcción de \( N(t) \), pero ya vimos que no es posible formalizar el "número denotado por un término sin variables".

Si es posible entonces formalizarlo, ¿cómo sería entonces el teorema de ARP que lo formaliza?

Ese teorema no puede formalizarse en ARP, porque es tanto como formalizar una definición del número denotado por un término, y ya hemos visto que no se puede.

Vale, es lo que pensaba, pero me había liado lo de ponerlo o no en rojo :laugh:

Ahora, sobre los comentarios sobre si el teorema debe o no ir en rojo entiendo lo que comentas (creo) y, ciertamente estoy de acuerdo con todo lo que dices. Solo quiero destacar un par de, lo que creo que son erratas (junto a una aclaración que me hago a mi mismo, marcada en verde, para saber si lo he entendido bien) para saber si he entendido realmente bien lo que son las funciones recursivas o no.

Si \( g \) es una función \( n+1 \)-ádica recursiva, también es recursiva la función \( n \)-ádica definida a partir de ella por minimización:

\( f(x_1,\ldots, x_n) =  \) el mínimo número natural \( x_0 \) que cumple \( {\color{red}g}(x_0, x_1, \ldots, x_n)=0 \),

siempre y cuando podamos asegurar que para todos los valores posibles \( x_1,\ldots, x_n \) siempre existe al menos un número natural \( x_0 \) que cumple \( {\color{red}g}(x_0, \ldots, x_n) = 0 \).

Notemos que no vale el truco de entender que \( f(x_1, \ldots, x_n) \) vale \( 0 \) cuando no existe ningún \( x_0 \) que cumpla lo requerido, porque entonces podría ocurrir que pudiéramos calcular la función \( g \) y no pudiéramos saber cuánto vale \( f \) porque no sepamos si \( g \) toma o no toma el valor cero para algún \( x_0 \). La función \( f \) estaría definida, pero no tendríamos ninguna garantía de que se puede calcular.

[...]

Y ahí, en las palabras en negrita, está la objeción que un finitista puede poner a las funciones recursivas generales: ¿qué argumentos valen para asegurar que la función \( \color{red} g \) siempre toma el valor cero?

Ya he terminado el hilo.

Todo lo bueno se acaba :'(

Voy a ponerme con ello.

Un saludo.