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

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

22 Junio, 2023, 02:02 am
Respuesta #100

manooooh

  • $$\Large \color{#9c57a6}\pi\,\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 4,791
  • País: ar
  • Karma: +1/-0
  • Sexo: Masculino
Hola

En esta oportunidad vengo a aportar mi granito de arena y hacer una consulta. :)

Como también contamos con la premisa \( R\cdot s_1(0)=R\cdot s_2(0) \), la regla de inducción general \( I \) nos permite concluir \( R\cdot s_1(x)=R\cdot s_2(x) \). Como ya hemos señalado, el uso de \( I \) conlleva únicamente un uso de \( I_0 \) respecto de la misma variable a la que se aplicaba \( I_0 \) a la deducción dada y aplicaciones típicas de \( S_1 \) a teoremas que podemos incorporar a la lista de los $\gamma_i$, luego no hemos incorporado ningún uso de \( I_0 \) respecto de ninguna variable "nueva".

Corregir los $...$.


¿Por qué usas una imagen en vez de tipearlo en el editor? Supongo que porque no existe en MathJax el ambiente que usas para agregar líneas verticales a ciertas líneas. ¿Son necesarias? Sé que tienen que ver por la introducción de una hipótesis, pero si esas líneas no son importantes, si quieres puedo transcribir la imagen sin ellas en el foro.

Y la duda sería:

Por el teorema de deducción, de \( \alpha_1\ldots, \alpha_n \) se deduce la implicación \( \lnot\alpha\rightarrow (\beta\land \lnot\beta) \), pero \( \lnot(\beta\land\lnot\beta) \) es uno de los teoremas que hemos probado sobre los conectores), luego la regla del modus tollens nos da \( \lnot\lnot\alpha \) y la doble negación nos permite concluir \( \alpha \).

¿Por qué no escribes \( \neg(\neg\alpha) \)? Porque si la negación es un operador, desde la secundaria entiendo que no pueden ponerse dos operadores juntos, como \( 2+-3 \) sino que lo correcto es \( 2+(-3) \). Y más sabiendo que tratas un tema tan delicado como es lógica matemática, donde cada signo cuenta. Si es por un tema de ahorro de escritura, vale de acuerdo... a medias. Me seguiría sorprendiendo de todas maneras :laugh:

Saludos

22 Junio, 2023, 08:41 am
Respuesta #101

Carlos Ivorra

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

Ya está. Gracias. Es que tiendo a poner dólares de forma refleja.

¿Por qué usas una imagen en vez de tipearlo en el editor? Supongo que porque no existe en MathJax el ambiente que usas para agregar líneas verticales a ciertas líneas.

Eso es.

¿Son necesarias? Sé que tienen que ver por la introducción de una hipótesis, pero si esas líneas no son importantes, si quieres puedo transcribir la imagen sin ellas en el foro.

Si no fueran importantes también podría transcribirla yo. Pero es necesario marcar las líneas que dependen de hipótesis para que quede claro que no se pueden usar una vez aplicado el teorema de deducción. Además, sería incongruente hablar en el texto de dichas marcas y que luego no estuvieran en los ejemplos.

¿Por qué no escribes \( \neg(\neg\alpha) \)? Porque si la negación es un operador, desde la secundaria entiendo que no pueden ponerse dos operadores juntos, como \( 2+-3 \) sino que lo correcto es \( 2+(-3) \). Y más sabiendo que tratas un tema tan delicado como es lógica matemática, donde cada signo cuenta. Si es por un tema de ahorro de escritura, vale de acuerdo... a medias. Me seguiría sorprendiendo de todas maneras :laugh:

Por lo que veo aquí:

https://es.wikipedia.org/wiki/Doble_negaci%C3%B3n_%28l%C3%B3gica%29

es bastante habitual. Sólo habría dos motivos para poner paréntesis:

1) Que fueran necesarios para evitar ambigüedades.
2) Que existiera cierta costumbre más o menos consolidada de ponerlos.

Pero no se da ninguno de los dos casos.

22 Junio, 2023, 06:53 pm
Respuesta #102

Eparoh

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

Lo primero, como ya es costumbre, erratas/comentarios y dudas:

Teorema de deducción  Si se cumple

\( \alpha_1,\ldots, \alpha_n, \alpha\mathop{\vdash}\limits_{\rm ARP}\beta \)

y en la deducción no se usan las reglas \( S_1 \) ni \( I_0 \) respecto de variables que estén en \( \alpha \), entonces

\( \alpha_1,\ldots, \alpha_n\mathop{\vdash}\limits_{\rm ARP}\alpha\rightarrow \beta \)

Teorema de deducción (variante) A partir de una deducción

\( \alpha_1,\ldots, \alpha_n, \alpha\mathop{\vdash}\limits_{\rm ARP}\beta \)

en la que no se usen \( S_1 \) ni \( I_0 \) respecto de variables que estén en \( \alpha \) podemos construir una deducción

\( \gamma_1,\ldots, \gamma_r, \alpha_1,\ldots, \alpha_n\mathop{\vdash}\limits_{\rm ARP}\alpha\rightarrow \beta \),

donde \( \gamma_1, \ldots, \gamma_r \) son teoremas de ARP, en la cual sólo se usan las reglas \( S_1 \) e \( I_0 \) respecto de variables respecto a las que ya se usaban estas reglas en la deducción dada o bien respecto de variables que podemos elegir arbitrariamente.

¿No sería mejor poner un "ni" que un "o"?

Concretamente, vamos a usarlo para demostrar este teorema:

\( x+z=y+z\rightarrow x=y \)


En la última línea, \( I \) se aplica sobre 5 y 15, no sobre 5 y 14.
 
Comentario de la demostración
[...]

En la línea (3) añadimos como hipótesis \( x+0=y+0 \) (llamaremos hipótesis a las premisas que luego vayamos a eliminar usando el teorema de deducción). A partir de este punto está prohibido usar las reglas \( S_1 \) e \( I_0 \) respecto de las variables \( x, y \).

[...]

La línea (6) es la hipótesis de inducción para \( z \), y tenemos que probar que lo mismo vale para \( Sz \) (esto lo obtendremos en la línea (14)). A partir de aquí está prohibido usar las reglas \( S_1 \) e \( I_0 \) respecto de \( x, y, z \).

[...]
[cerrar]

Uso práctico del teorema de deducción
[...]

En un momento dado añadimos una fórmula \( \alpha \) como hipótesis y continuamos deduciendo sin usar \( S_1 \) ni \( I_0 \) respecto de las variables de \( \alpha \). Esto es lo que hacemos en nuestro ejemplo, por ejemplo en la línea (6).

Luego añadimos \( \alpha' \) como hipótesis y evitamos usar \( S_1 \) e \( I_0 \) respecto de variables en \( \alpha' \) y en \( \alpha \). En nuestro ejemplo hacemos eso en la línea (7) y así llegamos a la línea (13).

En general tenemos una deducción:

\( \delta_1, \ldots, \delta_m, \alpha, \delta_{m+2}, \ldots, \delta_{m+m'}, \alpha', \delta_{m+m'+2}\ldots, \beta'. \)

En este punto aplicamos el teorema de deducción, que nos da una deducción

\( \gamma_1, \ldots, \gamma_r, \delta_1, \ldots, \delta_m,\alpha, \delta_{m+2}, \ldots, \delta_{m+m'}\mathop{\vdash}\limits_{\rm ARP}\alpha'\rightarrow \beta'
 \)
en la que podemos asegurar que no se usa \( S_1 \) ni \( I_0 \) respecto de las variables de \( \alpha \).

Ahora prolongamos esta deducción —y en la práctica marcaremos las líneas comprendidas entre \( \alpha' \) y \( \beta' \) con una línea vertical para indicar que ya no contamos con ellas— sin usar \( S_1 \) ni \( I_0 \) respecto de las variables de \( \alpha \), hasta llegar a

\( \gamma_1, \ldots, \gamma_r, \delta_1, \ldots, \delta_m,\alpha, \delta_{m+2}, \ldots, \beta. \)

[...]

Así hemos encadenado dos usos del teorema de deducción, pero igualmente podríamos haber encadenado cualquier número de usos. La clave está en que cada vez que lo aplicamos —en virtud del segundo enunciado— podemos asegurar que la deducción que obtenemos no usa las reglas \( S_1 \) ni \( I_0 \) respecto de variables prohibidas por las aplicaciones que tenemos pendientes.

[...]

Lo que si tenemos que cuidar es no usar ninguna regla de inferencia derivada que requiera un uso de \( S_1 \) o \( I_0 \) respecto de variables prohibidas. Ciertamente, las reglas \( I_1, I_2 \) o \( I \) esconden un uso \( I_0 \) respecto de la misma variable, por lo que tampoco podemos usarlas respecto de variables prohibidas.

[...]
[cerrar]
Lo mismo sobre el uso de "y" u "o", junto a una pequeña errata con \( S_1 \) en el segundo spoiler.

Demostración del teorema de deducción
Sea \( \delta_1,\ldots, \delta_m \) una deducción con premisas \( \alpha_1,\ldots, \alpha_n, \alpha \) que termina en \( \delta_m\equiv \beta \) y vamos a ver cómo construir la deducción requerida de \( \alpha\rightarrow \beta \). Sea \( R \color{red} \equiv \color{black}1\dot{-} t_\alpha \), que es un término en el que aparecen las mismas variables que en \( \alpha \).

Pongamos que \( \delta_i\equiv s_i=t_i \), y vamos a demostrar que \( \delta'_i\equiv R\cdot s_i=R\cdot t_i \) es un teorema para todo \( i \).

[...]

Si \( \delta_i \equiv \alpha \), entonces hay que probar

\( \delta'_i \equiv (1\dot{-}  |s_i-t_i|)\cdot s_i=(1\dot{-}  |s_i-t_i|)\cdot t_i, \)

y esta fórmula se deduce aplicando \( S_1 \) (respecto de variables \( x, y \) elegidas libremente) a la fórmula en verde en el último spoiler de la respuesta #9 (que incluimos entre los teoremas \( \gamma_i \)).

[...]

  • Para la regla \( S_2 \) tenemos que demostrar que

    \( \begin{array}{c}
    R\cdot t_1=R\cdot t_2\\
    \hline
    R\cdot s(t_1)=R\cdot s(t_2)
    \end{array} \)

    es una regla de inferencia válida. Vamos a probar, de hecho, el teorema

    \( R\cdot t_1=R\cdot t_2\rightarrow R\cdot s(t_1)=R\cdot s(t_2). \)

    La regla se sigue, entonces, de aplicar MP (y sólo tenemos que incorporar este teorema a la lista de los \( \gamma_i \)). En primer lugar observamos que

    \( R\cdot t_1=R\cdot t_2\rightarrow (R=0\lor t_1=t_2), \)

    pues, por definición de la implicación (y la propiedad 4 del valor absoluto), se trata de la fórmula

    \( (1\dot{-}  R\cdot |t_1-t_2|)\cdot R\cdot |t_1-t_2|=0, \)

    que es un caso particular de \( (1\dot{-}  x)\cdot x = 0 \).

    Por otra parte,

    \( R=0\rightarrow R\cdot s(t_1)=R\cdot s(t_2), \)

    \( t_1=t_2\rightarrow R\cdot s(t_1)=R\cdot s(t_2). \)

    La primera implicación se debe a que, por definición, es la fórmula

    \( (1\dot{-}  R)\cdot R\cdot |s(t_1)-s(t_2)|=0 \)

    [...]
  • Para la regla \( I_0 \) tenemos que probar:

    \( \begin{array}{c}
    R\cdot s_1(0)=R\cdot s_2(0),\ R\cdot s_1(Sx)\color{red}\cancel{)}\color{black}=R\cdot h(x, s_1(x)),\ R\cdot s_2(Sx)=R\cdot h(x,s_2(x))\\
    \hline
    R\cdot s_1(x)=R\cdot s_2(x)
    \end{array}
     \)
    bajo el supuesto de que la variable \( x \) no está en \( R \).

    [...]
[cerrar]

A parte de las dos erratillas marcadas en rojo, voy comentando en orden las cosas que he marcado en naranja que no llego a tener claras:

  • Realmente, no vemos que \( \delta'_i \) sea un teorema, sino que es consecuencia de las premisas \( \alpha_1, \cdots, \alpha_n \), ¿no?
    Porque si, por ejemplo, \( \delta_i \) es una premisa, entonces no se ve que \( \delta'_i \) sea un teorema, sino que se deduce a partir de la premisa.
  • ¿La fórmula marcada en verde no debería ser justo la de encima de la que marcaste? Y, la consideramos tomando (por ejemplo), \( s \equiv z \), ¿no?
  • También habría que añadir los teoremas necesarios para demostrar MP, ¿no?
  • No veo claro como se obtine la fórmula azul a partir de la propiedad 4 del valor absoluto.
  • Tampoco lo veo, porque, por definición, a mi me sale: \( (1 \dot{-}R) \cdot \left |{R s(t_1) - R s(t_2)}\right | \)
  • El uso de este hecho en la demostración (y que haría que no fuera válida en otro caso) es al obtener que \( R\cdot s_1(x)=R\cdot s_2(x)\rightarrow R\cdot s_1(Sx)=R\cdot s_2(Sx) \) y tomar esto como parte de las hipótesis de \( I \), porque si \( x \) apareciera en \( R \), entonces la hipótesis correspondientes de \( I \) serían \( R(0) \cdot s_1(0) = R(0) \cdot s_2(0) \) y \( R(x)\cdot s_1(x)=R(x)\cdot s_2(x)\rightarrow R(Sx)\cdot s_1(Sx)=R(Sx)\cdot s_2(Sx) \), ¿no?

Reducción al absurdo Del teorema de deducción se sigue inmediatamente que en ARP también podemos razonar por reducción al absurdo:

Teorema (Reducción al absurdo)
Si se cumple

\( \alpha_1,\ldots, \alpha_n, \lnot \alpha\mathop{\vdash}\limits_{\rm ARP}\beta\land \lnot\beta \)

y en la deducción no se usan las reglas \( S_1 \) ni \( I_0 \) respecto de variables que aparecen en \( \alpha \), entonces

\( \alpha_1,\ldots, \alpha_n\mathop{\vdash}\limits_{\rm ARP}\alpha. \)

Demostración
Por el teorema de deducción, de \( \alpha_1\ldots, \alpha_n \) se deduce la implicación \( \lnot\alpha\rightarrow (\beta\land \lnot\beta) \), pero \( \lnot(\beta\land\lnot\beta) \) es uno de los teoremas que hemos probado sobre los conectores), luego la regla del modus tollens nos da \( \lnot\lnot\alpha \) y la doble negación nos permite concluir \( \alpha \).
[cerrar]

Una pequeña errata con los paréntesis y otra vez lo del y/o que, si no te parece que tengo razón, ya estarás cansado de leerlo en este mensaje ::).

Respecto al contenido en si, si no me equivoco, ya tenemos todo lo necesario para poder utilizar el cálculo proposicional "sin preocuparnos" de las tediosas demostraciones de ARP, ¿no? ¿Queda alguna sorpresa que ARP pueda darnos?

Por último, respecto del ejercicio que planteas sobre "demostrar" que \( 0=1 \) utilizando un mal uso del teorema de deducción, he conseguido hacerlo para \( S_1 \), pero ahora mismo no se me ocurre para nada como podría hacerse solo utilizando \( I_0 \) o alguna forma de inducción (todo lo que he intentado termina llevándome en algún momento a utilizar \( S_1 \)). Dejo aquí lo que conseguí:

Spoiler
\( \begin{array}{cll}
(1) & x=0 & \text{Hipótesis}\\
(2) & 1=0 & S_1\, 1\\
(3) & x=0 \rightarrow 1=0 & \text{"Tma. deducción"}\\
(4) & 0=0 \rightarrow 1=0 & S_1\, 3\\
(5) & 0=0 & \text{Teorema}\\
(6) & 1=0 & \text{MP} 4,5

\end{array} \)
[cerrar]

Un saludo.

23 Junio, 2023, 12:16 am
Respuesta #103

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Lo primero, como ya es costumbre, erratas/comentarios y dudas:

Me has dejado unos mensajes sin apenas erratas para que me confíe y ahora te estás ensañando.  ::)

A lo que no te respondo es que es exactamente como dices.

¿No sería mejor poner un "ni" que un "o"?

Se podría discutir, pero te he hecho caso. La única que no he cambiado (salvo despiste) es ésta:

Luego añadimos \( \alpha' \) como hipótesis y evitamos usar \( S_1 \) e \( I_0 \) respecto de variables en \( \alpha' \) y en \( \alpha \). En nuestro ejemplo hacemos eso en la línea (7) y así llegamos a la línea (13).

¿La fórmula marcada en verde no debería ser justo la de encima de la que marcaste? Y, la consideramos tomando (por ejemplo), \( s \equiv z \), ¿no?

Sí, la versión concreta que usamos de la fórmula en verde es

\( (1\dot{-}  |x-y|)x=(1\dot{-}  |x-y|)y. \)

Ahí sustituimos \( x, y \) por \( s_i, t_i \), respectivamente.

No veo claro como se obtiene la fórmula azul a partir de la propiedad 4 del valor absoluto.

Por la definición de la implicación y la disyunción, la fórmula en azul es:

\( (1\dot{-} |Rt_1-Rt_2|)R|t_1-t_2| \)

Y ahora ten en cuenta que \( R \equiv 1\dot{-} t_\alpha \), que es el tipo de término que la propiedad 4 permite sacar factor común en un valor absoluto, luego al aplicarla vemos que esta fórmula equivale a

\( (1\dot{-} R|t_1-t_2|)R|t_1-t_2| \).

He añadido estas explicaciones.

Tampoco lo veo, porque, por definición, a mi me sale: \( (1 \dot{-}R) \cdot \left |{R s(t_1) - R s(t_2)}\right | \)

Claro, pero \( R\equiv 1\dot{-} t_\alpha \), luego es la clase de término que la propiedad 4 del valor absoluto permite sacar factor común.

El uso de este hecho en la demostración (y que haría que no fuera válida en otro caso) es al obtener que \( R\cdot s_1(x)=R\cdot s_2(x)\rightarrow R\cdot s_1(Sx)=R\cdot s_2(Sx) \) y tomar esto como parte de las hipótesis de \( I \), porque si \( x \) apareciera en \( R \), entonces la hipótesis correspondientes de \( I \) serían \( R(0) \cdot s_1(0) = R(0) \cdot s_2(0) \) y \( R(x)\cdot s_1(x)=R(x)\cdot s_2(x)\rightarrow R(Sx)\cdot s_1(Sx)=R(Sx)\cdot s_2(Sx) \), ¿no?

Exacto.

Respecto al contenido en si, si no me equivoco, ya tenemos todo lo necesario para poder utilizar el cálculo proposicional "sin preocuparnos" de las tediosas demostraciones de ARP, ¿no? ¿Queda alguna sorpresa que ARP pueda darnos?

Por supuesto que quedan sorpresas. ¿De verdad te has creído que ARP no tiene cuantificadores?  :P

Tenemos que probar que en ARP se puede decir \( \forall x <t(\cdots) \) y \( \exists x< t(\cdots) \).

Por último, respecto del ejercicio que planteas sobre "demostrar" que \( 0=1 \) utilizando un mal uso del teorema de deducción, he conseguido hacerlo para \( S_1 \), pero ahora mismo no se me ocurre para nada como podría hacerse solo utilizando \( I_0 \) o alguna forma de inducción (todo lo que he intentado termina llevándome en algún momento a utilizar \( S_1 \)). Dejo aquí lo que conseguí:

Spoiler
\( \begin{array}{cll}
(1) & x=0 & \text{Hipótesis}\\
(2) & 1=0 & S_1\, 1\\
(3) & x=0 \rightarrow 1=0 & \text{"Tma. deducción"}\\
(4) & 0=0 \rightarrow 1=0 & S_1\, 3\\
(5) & 0=0 & \text{Teorema}\\
(6) & 1=0 & \text{MP} 4,5
\end{array} \)
[cerrar]

 :aplauso:

En cuanto al mal uso de la inducción, se trata de "demostrar" que \( \alpha(0) \) y \( \alpha(x)\rightarrow \alpha(Sx) \) para cierta fórmula \( \alpha \) que no cumpla esto para realmente todo \( x \), pero sí para \( x=0 \) y para todo \( x \) que cumpla una premisa elegida adecuadamente, por ejemplo si tomas como premisa \( x=1 \), se trata de elegir una fórmula que valga para \( x = 0, 2 \), pero no para \( x = 1 \), con lo que al pseudodemostrar la implicación que proporciona el teorema de deducción y aplicarla a \( x=1 \) obtengas una contradicción. Te pongo en spoiler una posibilidad (la más simple que cumple estos requisitos):

Spoiler
\( x\cdot(2\dot{-}x) = 0 \)
[cerrar]


23 Junio, 2023, 12:53 am
Respuesta #104

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
He añadido a la respuesta #11 una nota y un ejercicio para completar todo lo tocante al cálculo proposicional, pues no era material suficiente como para dedicarle un nuevo mensaje.

23 Junio, 2023, 10:33 am
Respuesta #105

Eparoh

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

Me has dejado unos mensajes sin apenas erratas para que me confíe y ahora te estás ensañando.  ::)

😈

¿No sería mejor poner un "ni" que un "o"?

Se podría discutir, pero te he hecho caso. La única que no he cambiado (salvo despiste) es ésta:

Luego añadimos \( \alpha' \) como hipótesis y evitamos usar \( S_1 \) e \( I_0 \) respecto de variables en \( \alpha' \) y en \( \alpha \). En nuestro ejemplo hacemos eso en la línea (7) y así llegamos a la línea (13).

Completamente de acuerdo.

Sí, la versión concreta que usamos de la fórmula en verde es

\( (1\dot{-}  |x-y|)x=(1\dot{-}  |x-y|)y. \)

Ahí sustituimos \( x, y \) por \( s_i, t_i \), respectivamente.

Claro, lo que me refería es que, como la fórmula verde es cierta para cualquier término \( s \), pues tomábamos \( s \equiv x \) (me confundí y puse \( z \) en lugar de \( x \) en el mensaje anterior).

No veo claro como se obtiene la fórmula azul a partir de la propiedad 4 del valor absoluto.

Por la definición de la implicación y la disyunción, la fórmula en azul es:

\( (1\dot{-} |Rt_1-Rt_2|)R|t_1-t_2| \)

Y ahora ten en cuenta que \( R \equiv 1\dot{-} t_\alpha \), que es el tipo de término que la propiedad 4 permite sacar factor común en un valor absoluto, luego al aplicarla vemos que esta fórmula equivale a

\( (1\dot{-} R|t_1-t_2|)R|t_1-t_2| \).

He añadido estas explicaciones.

Tampoco lo veo, porque, por definición, a mi me sale: \( (1 \dot{-}R) \cdot \left |{R s(t_1) - R s(t_2)}\right | \)

Claro, pero \( R\equiv 1\dot{-} t_\alpha \), luego es la clase de término que la propiedad 4 del valor absoluto permite sacar factor común.

Me traicionó el pensar en \( R \) como un término genérico y no recordar su definición ::)

Por supuesto que quedan sorpresas. ¿De verdad te has creído que ARP no tiene cuantificadores?  :P

Tenemos que probar que en ARP se puede decir \( \forall x <t(\cdots) \) y \( \exists x< t(\cdots) \).

Voy a tener que comprarme un sombrero sólo para quitármelo ante ARP :aplauso:

Supongo que, por lo que pones, los cuantificadores no acotados sí es ya pedir demasiado, ¿no?

En cuanto al mal uso de la inducción, se trata de "demostrar" que \( \alpha(0) \) y \( \alpha(x)\rightarrow \alpha(Sx) \) para cierta fórmula \( \alpha \) que no cumpla esto para realmente todo \( x \), pero sí para \( x=0 \) y para todo \( x \) que cumpla una premisa elegida adecuadamente, por ejemplo si tomas como premisa \( x=1 \), se trata de elegir una fórmula que valga para \( x = 0, 2 \), pero no para \( x = 1 \), con lo que al pseudodemostrar la implicación que proporciona el teorema de deducción y aplicarla a \( x=1 \) obtengas una contradicción. Te pongo en spoiler una posibilidad (la más simple que cumple estos requisitos):

Spoiler
\( x\cdot(2\dot{-}x) = 0 \)
[cerrar]

Claro. Mira que le di algunas vueltas, y me rondaban ideas parecidas, pero no llegaban a materializarse bien. Ahora con esta pista creo que ya sí lo he conseguido:

Spoiler

[cerrar]

He añadido a la respuesta #11 una nota y un ejercicio para completar todo lo tocante al cálculo proposicional, pues no era material suficiente como para dedicarle un nuevo mensaje.

Muy interesante la nota, porque deja completa constancia de que ARP es tan potente (aunque, por lo que me has dicho de los cuantificadores, lo es más) como el cálculo proposicional ordinario, y me parece increíble que así sea sabiendo de donde hemos comenzado.

23 Junio, 2023, 03:07 pm
Respuesta #106

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Claro, lo que me refería es que, como la fórmula verde es cierta para cualquier término \( s \), pues tomábamos \( s \equiv x \) (me confundí y puse \( z \) en lugar de \( x \) en el mensaje anterior).

Sí, te había entendido. Y da igual que tomes \( s\equiv z \) o \( s\equiv x \), porque \( s(x) \) y \( s(y) \) son los mismos en cualquier caso.

Voy a tener que comprarme un sombrero sólo para quitármelo ante ARP :aplauso:

Supongo que, por lo que pones, los cuantificadores no acotados sí es ya pedir demasiado, ¿no?

Según se mire: se puede definir una teoría axiomática usual ARP\( ^+ \), con sus cuantificadores usuales, de modo que los teoremas de ARP coinciden con los teoremas de ARP\( ^+ \) con cuantificadores acotados. Pero eso no creo que podamos demostrarlo aquí, y tampoco es necesario para trabajar razonablemente con ARP.

Claro. Mira que le di algunas vueltas, y me rondaban ideas parecidas, pero no llegaban a materializarse bien. Ahora con esta pista creo que ya sí lo he conseguido:

Spoiler

[cerrar]

 :aplauso:

Muy interesante la nota, porque deja completa constancia de que ARP es tan potente (aunque, por lo que me has dicho de los cuantificadores, lo es más) como el cálculo proposicional ordinario, y me parece increíble que así sea sabiendo de donde hemos comenzado.

Sí, por estas cosas (y otras) me pareció oportuno divulgar un poco ARP.

26 Junio, 2023, 10:13 am
Respuesta #107

Eparoh

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

No he encontrado ninguna errata en el último mensaje ;D

Pero, si tengo algunos comentarios.

En la propiedad 3, tal vez sería bueno poner un "si, y solo si", en lugar de solo una implicación, porque aunque sea directo, deja claro que eso es un teorema de ARP y queda justificado todas las veces que se usa después.

Y luego, en la prueba de 12 se utiliza que si \( z \not = 0 \) y \( xz=yz \), entonces \( x=y \), y tal vez estaría bien añadirlo como un último apartado al ejercicio del mensaje anterior, porque no aparece esto reflejado por ningún lado en el hilo.

Por último, igual también estaría claro aclarar al final del mensaje anterior algo como que desde ese momento se razonará de la forma usual, donde se utilizan las reglas básicas de inferencia así como el teorema de deducción sin especificarlo, porque hay un salto muy grande de las demostraciones anteriores a las de la relación de orden, en el sentido de que ya no se usan para nada las reglas \( S_1 \) o \( S_2 \), etc.

26 Junio, 2023, 12:42 pm
Respuesta #108

argentinator

  • Consultar la FIRMAPEDIA
  • Administrador
  • Mensajes: 7,797
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
Hay algo que no me cae simpático en la exposición, al principio,
ya que primero se definen unas funciones "en el aire",
digamos, fuera del lenguaje ARP,
y en particular aparecen el número 0 y la función S.

Luego, en el lenguaje ARP aparecen 0 y S para nombrar signos del lenguaje.

Cuando se establece \(F(algo)\) como la función denotada por ese "algo",
tenemos que \(F(S)\) es la función sucesor,
pero con la notación que se viene utilizando quedaría así:

\(F(S)\) denota \(S\)

y entonces la letra "S" tendría dos significados distintos a ambos lados del verbo "denota".

Si bien por el contexto uno puede descifrarlo,
para mi gusto sería mejor usar notación diferente en ambos contextos.
Por ejemplo, "s" para el signo del lenguaje ARP tal que \(F(s)\) es \(S\),
y lo mismo "o" para el signo que denote luego a \(0\).

(O bien al revés, según convenga especificar los naturales de una manera, y los numerales de otra).


26 Junio, 2023, 03:25 pm
Respuesta #109

argentinator

  • Consultar la FIRMAPEDIA
  • Administrador
  • Mensajes: 7,797
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
Principio de inducción Si probamos que el número cero tiene una propiedad y, suponiendo que un número arbitrario \( n \) la posee, podemos justificar que lo mismo le sucede a su siguiente, podemos concluir que todos los números naturales tienen dicha propiedad.

En efecto, si algún número natural no tuviera la propiedad, existiría un mínimo número natural sin ella. No podría ser el cero, porque hemos probado que la tiene, luego tendría que ser el siguiente de otro número \( n \), pero como el siguiente de \( n \) es el menor número natural que no tiene la propiedad y \( n \) es menor que el siguiente de \( n \) (porque aparece justo antes en la sucesión), el número \( n \) debería tenerla, pero estamos suponiendo que hemos razonado que en tal caso el siguiente de \( n \) también la tiene, con lo que tenemos una contradicción.

Naturalmente, estos argumentos suponen que hablamos de una propiedad objetiva, que tenga sentido asegurar que un número la tiene o no la tiene. Nosotros sólo necesitaremos usar estos principios respecto de propiedades que, más que eso, sabremos cómo comprobar explícitamente si un número dado la tiene o no.


Creo que ya hemos comentado sobre eso,
pero le sigo dando vueltas.

La manera de trabajar parece propia del constructivismo o el intuicionismo (formas de pensar que yo no sé distinguir).

Esa exigencia de "si sabemos justificar que" me parece que cuelga de demasiada subjetividad.
Puede haber dos individuos distintos, tal que uno "sabe justificar" el paso inductivo, y el otro no sabe.

Si alguien sabe justificar el paso inductivo de una propiedad de los naturales,
entonces el Principio de Inducción, tal como está enunciado ahí,
permite concluir que la propiedad es verdadera para todos los naturales.

Si ahora viene otro individuo que no sabe justificar el paso inductivo,
¿la propiedad deja de tener un valor de verdad concreto para los naturales, o sigue siendo verdadera?

Si este individuo, más lento a la hora de justificar el paso inductivo,
hace su demostración después que otra persona,
está descubriendo algo que ya era verdadero de "antes".

Y como nadie puede asegurar haber sido realmente el primero en demostrar dicho paso inductivo, entonces la propiedad ya era verdadera antes de probarla.

Por eso veo algo innecesario tener la necesidad de decir o suponer todo ese asunto de
"y si sabemos justificar que" bla bla bla.

Por otra parte, cuando hablás del Principio de Buena Ordenación (o del Mínimo),
no parece que pongas el mismo tipo de prevenciones.

____________________

Bajo un lenguaje formal (digamos AP, ZFC, o lo que fuere),
no es lo mismo "demostrable" que "verdadero".

Pero ¿qué significa "demostrable" fuera de una teoría axiomática?
¿Cómo distinguir "demostrable" de "verdadero"?

Y en tal caso, cuando se habla de los números naturales en forma absoluta,
fuera de toda teoría axiomática,
¿realmente hay diferencia entre "demostrable" y "verdadero", en lo referente al Principio de Inducción?