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

0 Usuarios y 2 Visitantes están viendo este tema.

30 Junio, 2023, 04:22 am
Respuesta #140

argentinator

  • Consultar la FIRMAPEDIA
  • Administrador
  • Mensajes: 7,797
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
Ya te respondí a eso.

No puedo tomar la opción (c).

Es que ahí mencionaste dos cosas: "sé que es cierto" y "lo he demostrado".

Que "lo he demostrado", pues sí.

Para decir que algo "sé que es cierto", tengo que tener claro qué quiere decir eso.
Y es de nuevo irse por las ramas.

30 Junio, 2023, 07:55 am
Respuesta #141

Eparoh

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

Está bien, aunque puedes simplificar el final. Una vez tienes que \( \forall u\leq x \,u = 0 \), eso ya daña a la vista porque es falso para \( x=1 \), así que basta con que sustituyas  \( x=1 \) y te queda \( \forall u\leq 1\, u = 0 \) y ahora sólo tienes que eliminar el generalizador a partir de \( 1\leq 1 \) para concluir que \( 1=0 \).

Otra opción más breve:

Spoiler
La clave está en suponer algo sobre \( y \), pero más fácil que \( xy = 0 \) es suponer simplemente

\( y = 0 \)

De ahí se sigue

\( y \leq x \rightarrow y = 0 \).

Aplicando ilícitamente IG, tienes

\( \forall u\leq x\, u = 0 \)

y por el teorema de deducción (incorrecto)

\( y = 0\rightarrow \forall u\leq x\, u = 0 \).

Sustituyendo \( y \) por \( 0 \) y usando \( 0 = 0 \) llegas a \( \forall u\leq x\, u = 0 \), y eso te da la misma contradicción que has obtenido tú, o también por el camino que he puesto yo antes del spoiler.
[cerrar]

Completamente cierto. No me di cuenta de que puedes generalizar a partir de "términos cualesquiera" porque puedes sustituir en la fórmula que te da la generalización los términos que quieras ::) Por eso fui por el camino un poco más largo.

Por tanto, volviendo al ejercicio, para encontrar una contradicción a partir del falso "teorema", debería encontrar una fórmula \( \alpha \) para la cual se pueda demostrar en ARP que \( y \leq x \rightarrow \alpha(y) \), pero que no sea verdadera

No, no necesitas demostrar eso. Si el falso teorema fuera un teorema, podrías sustiuir \( x, y \) por valores concretos, y así obtienes una implicación que dice que si la hipótesis se cumple para un \( x \) concreto y un \( y \) concreto, entonces \( \alpha(u) \) se cumple para todos los \( u\leq x \), no sólo para el \( y \) que has fijado para que se cumpla la hipótesis, y eso no tiene por qué ser cierto. Te pongo un ejemplo:

Spoiler
Toma \( \alpha(y) \equiv y = 0 \). Si suponemos \( (y\leq x\rightarrow \alpha(y))\rightarrow \forall u\leq x\,\alpha(u) \), haciendo \( x = 1, y = 0 \) queda:

\( (0\leq 1\rightarrow 0 = 0)\rightarrow \forall u\leq 1\, u = 0. \)

Puedes probar el antecedente, pero el consecuente es falso cual billete de 7 euros. Que la hipótesis se cumpla para \( y = 0, x = 1 \) no garantiza que \( \alpha(u) \) se cumpla para todo \( u\leq 1 \).
[cerrar]

Cierto, de nuevo me volvió a traicionar mi cabeza no dejándome ver que si tienes un teorema en ARP puedes sustituir por los términos que te de la gana  :banghead:

De todas formas, lo que principalmente quería decir y que si es cierto, es que no puedes tomar \( \alpha \) como una fórmula verdadera pues entones, aunque el "falso" teorema igual sigue siendo falso (en el sentido de que no es demostrable en ARP), la fórmula en sí es verdadera y, por el teorema de corrección, no podríamos deducir de ella nada falso en ARP.

Un saludo.

30 Junio, 2023, 12:38 pm
Respuesta #142

Carlos Ivorra

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

No puedo tomar la opción (c).

Es que ahí mencionaste dos cosas: "sé que es cierto" y "lo he demostrado".

Que "lo he demostrado", pues sí.

Para decir que algo "sé que es cierto", tengo que tener claro qué quiere decir eso.
Y es de nuevo irse por las ramas.

Pero ahí "es cierto" era únicamente un recurso lingüístico para no repetir el planteamiento. A riesgo de abusar de tu paciencia, permíteme un último intento. Si con esta versión no te decantas por ninguna opción, prometo no intentarlo más. Las opciones son ahora:

a) No me extrañaría que el día menos pensado pudiera venirme alguien que me muestre en un papel un funtor de ARP junto con dos razonamientos que emplean correctamente la definición de rango de un funtor y sin errores de cálculo que prueben, respectivamente, que el rango de ese funtor es 15 en un razonamiento y 17 en otro.

b) Creo que es imposible que pueda venirme alguien que me muestre en un papel un funtor de ARP junto con dos razonamientos que emplean correctamente la definición de rango de un funtor y sin errores de cálculo que prueban, respectivamente, que el rango de ese funtor es 15 en un razonamiento y 17 en otro.

c) Es imposible que pueda venirme alguien que me muestre en un papel un funtor de ARP junto con dos razonamientos que emplean correctamente la definición de rango de un funtor y sin errores de cálculo que prueban, respectivamente, que el rango de ese funtor es 15 en un razonamiento y 17 en otro, y sé que es imposible porque lo he demostrado.

d) He demostrado que todo funtor de ARP tiene un único rango asignado, pero, a pesar de mi demostración, no estoy convencido de que el día menos pensado no pueda venirme alguien que me muestre en un papel un funtor de ARP junto con dos razonamientos que emplean correctamente la definición de rango de un funtor y sin errores de cálculo que prueban, respectivamente, que el rango de ese funtor es 15 en un razonamiento y 17 en otro.

e) No me puedo decantar por ninguna de las anteriores.

30 Junio, 2023, 12:39 pm
Respuesta #143

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
De todas formas, lo que principalmente quería decir y que si es cierto, es que no puedes tomar \( \alpha \) como una fórmula verdadera pues entones, aunque el "falso" teorema igual sigue siendo falso (en el sentido de que no es demostrable en ARP), la fórmula en sí es verdadera y, por el teorema de corrección, no podríamos deducir de ella nada falso en ARP.

Cierto.

30 Junio, 2023, 05:26 pm
Respuesta #144

argentinator

  • Consultar la FIRMAPEDIA
  • Administrador
  • Mensajes: 7,797
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
Ya te respondí a eso.

No puedo tomar la opción (c).

Es que ahí mencionaste dos cosas: "sé que es cierto" y "lo he demostrado".

Que "lo he demostrado", pues sí.

Para decir que algo "sé que es cierto", tengo que tener claro qué quiere decir eso.
Y es de nuevo irse por las ramas.

Pero ahí "es cierto" era únicamente un recurso lingüístico para no repetir el planteamiento. A riesgo de abusar de tu paciencia, permíteme un último intento. Si con esta versión no te decantas por ninguna opción, prometo no intentarlo más. Las opciones son ahora:

a) No me extrañaría que el día menos pensado pudiera venirme alguien que me muestre en un papel un funtor de ARP junto con dos razonamientos que emplean correctamente la definición de rango de un funtor y sin errores de cálculo que prueben, respectivamente, que el rango de ese funtor es 15 en un razonamiento y 17 en otro.

b) Creo que es imposible que pueda venirme alguien que me muestre en un papel un funtor de ARP junto con dos razonamientos que emplean correctamente la definición de rango de un funtor y sin errores de cálculo que prueban, respectivamente, que el rango de ese funtor es 15 en un razonamiento y 17 en otro.

c) Es imposible que pueda venirme alguien que me muestre en un papel un funtor de ARP junto con dos razonamientos que emplean correctamente la definición de rango de un funtor y sin errores de cálculo que prueban, respectivamente, que el rango de ese funtor es 15 en un razonamiento y 17 en otro, y sé que es imposible porque lo he demostrado.

d) He demostrado que todo funtor de ARP tiene un único rango asignado, pero, a pesar de mi demostración, no estoy convencido de que el día menos pensado no pueda venirme alguien que me muestre en un papel un funtor de ARP junto con dos razonamientos que emplean correctamente la definición de rango de un funtor y sin errores de cálculo que prueban, respectivamente, que el rango de ese funtor es 15 en un razonamiento y 17 en otro.

e) No me puedo decantar por ninguna de las anteriores.

Me decanto por la (c).

Estaba entre la c y la d.
Pero no veo cómo podrían haber dos razonamientos contradictorios y así probar algo como el caso d.

Igual esa frase que pusiste "sé que es imposible porque...".
No me siento con esa convicción.













30 Junio, 2023, 05:29 pm
Respuesta #145

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Me decanto por la (c).

Estaba entre la c y la d.
Pero no veo cómo podrían haber dos razonamientos contradictorios y así probar algo como el caso d.

Igual esa frase que pusiste "sé que es imposible porque...".
No me siento con esa convicción.

Vale, gracias por colaborar en la encuesta.  :P   Vamos bien. Veremos cómo evoluciona el asunto a medida que avances en el hilo.

30 Junio, 2023, 11:06 pm
Respuesta #146

argentinator

  • Consultar la FIRMAPEDIA
  • Administrador
  • Mensajes: 7,797
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
Me decanto por la (c).

Estaba entre la c y la d.
Pero no veo cómo podrían haber dos razonamientos contradictorios y así probar algo como el caso d.

Igual esa frase que pusiste "sé que es imposible porque...".
No me siento con esa convicción.

Vale, gracias por colaborar en la encuesta.  :P   Vamos bien. Veremos cómo evoluciona el asunto a medida que avances en el hilo.

Es lo menos que puedo hacer después de haberte fastidiado con las comillas y asuntos por el estilo.

Además me ha servido para cuestionar las cosas desde varios puntos de vista.

La unicidad de las funtores es alho que parece razonable pero no.me pardce obvio.
Y todavía estoy dándome contra la definición del rango. Así:  :banghead: :banghead: :banghead:

01 Julio, 2023, 12:25 am
Respuesta #147

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Es lo menos que puedo hacer después de haberte fastidiado con las comillas y asuntos por el estilo.

No sé por qué dices eso. Yo te respondo con mucho gusto a todo lo que planteas. No sé qué te hace pensar que me disgusta algo.

Además me ha servido para cuestionar las cosas desde varios puntos de vista.

Esa era la idea. Mi propósito es ver si tus objeciones a lo general se aplican a lo particular o cada cosa particular te convence.

La unicidad de las funtores es alho que parece razonable pero no.me pardce obvio.
Y todavía estoy dándome contra la definición del rango. Así:  :banghead: :banghead: :banghead:

Te adjunto un código en Python que determina la estructura de un funtor:

Código: [Seleccionar]
def leenum(s):
    """Dada una cadena que empieza por un numeral,
        devuelve su índice y el resto de la cadena"""
   
    n = 0
    while s[0] == "s":      #Mientras encuentra "s", los cuenta, los quita y repite.
        n +=1
        s = s[1:]
    if s[0] != "0":         #Si cuando se acaban las "s" no hay un "0", error.
        raise Exception
    else:
        s = s[1:]           #Quita el "0".
    return n, s

def lee(s):
    """Dada una cadena, devuelve el funtor por el que empieza,
    su rango y el resto de la cadena"""
   
    p = s[0]            #Primer signo de la cadena
    resto = s[1:]       #Resto de la cadena
   
    if p == "s":
        resp = p    #El funtor es "s"
        rang = 1    #El rango es 1
       
    if p == "c":
        resp = p    #El funtor es "c"
        rang = 1    #El rango es 1
       
    if p == "p":
        ind1, resto = leenum(resto)         #Primer numeral
        ind2, resto = leenum(resto)         #Segundo numeral
        if ind2 < ind1:                     #Comprueba que ind1 <= ind 2
            raise Exception
        else:
            resp = "p_{}^{}".format(ind1, ind2)     #el funtor es p_ind1^ind2
            rang = ind2                             #El rango es ind2
           
    if p == "k":
        h, m, resto = lee(resto)        #Lee el funtor h y su rango
        g, rang, resto = lee(resto)     #Lee el funtor g1 y su rango
        resp = "k(" + h + ", " + g      #Empieza a formatear la salida
        for i in range(1,m):            #Bucle para leer los siguientes funtores
            g, n, resto = lee(resto)    #Lee otro funtor g y su rango
            if n != rang:               #Si el rango no es el mismo, error
                raise Exception
            resp = resp + ", " + g      #Continúa el formateado
        resp = resp + ")"               #Termina el formateado cerrando el paréntesis

    if p == "r":
        g, n, resto = lee(resto)        #Lee el primer funtor de la recursión
        h, m, resto = lee(resto)        #Lee el segundo funtor
        if m != n + 2:                  #Comprueba la relación entre los rangos
            raise Exception
        resp = "r("+g+", "+h+")"
        rang = n+1
    return resp, rang, resto

def esunfuntor(s):
    """Lee la cadena "s" y da su estructura si empieza por un funtor,
    o dice que no empieza por un funtor si no es así."""
    try:
        funtor, rango, resto = lee(s)
        print("La cadena")
        print(s)
        print("es el funtor:")
        print(funtor)
        print("de rango", rango)
        if resto != "": print("seguido de", resto)
    except Exception:
        print("La cadena no empieza por un funtor")

#Ejemplo:
esunfuntor("rckrps0s0kspsss0sss0psss0sss0ps0sss0")

Su salida con el ejemplo que he puesto al final del código (que es el mismo que está en el hilo) es:

Código: [Seleccionar]
La cadena
rckrps0s0kspsss0sss0psss0sss0ps0sss0
es el funtor:
r(c, k(r(p_1^1, k(s, p_3^3)), p_3^3, p_1^3))
de rango 2

El programa va leyendo la cadena dada de izquierda a derecha. Si te convences de que en cada momento la definición de funtor no permite que haga otra cosa distinta de lo que hace, eso debería convencerte de que la estructura de un funtor está unívocamente determinada.

01 Julio, 2023, 12:43 pm
Respuesta #148

argentinator

  • Consultar la FIRMAPEDIA
  • Administrador
  • Mensajes: 7,797
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
Es lo menos que puedo hacer después de haberte fastidiado con las comillas y asuntos por el estilo.

No sé por qué dices eso. Yo te respondo con mucho gusto a todo lo que planteas. No sé qué te hace pensar que me disgusta algo.


No digo que estés fastidiado, sino que yo he sido algo fastidioso, jeje.


04 Julio, 2023, 12:09 pm
Respuesta #149

Eparoh

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

Aún no he terminado de leer el último mensaje (curiosamente, por tener vacaciones tengo menos tiempo para sentarme a leerlo ::)), pero dejo las erratas, dudas y comentarios que tengo de momento.

Por ejemplo, ahora podemos clasificar a los números naturales en {\it pares} e {\it impares,} según si \( r(D, 2)=0 \) o \( r(D, 2)=1 \). Equivalentemente, por la unicidad de la división euclídea, los números pares son los de la forma \( 2n \) y los impares los de la forma \( 2n+1 \). Es fácil probar que
\( r(ab,2)=r(a, 2)r(b, 2), \)

de modo que el producto de par por par o par por impar es par, mientras que el producto de impares es impar.

Teorema Se cumple:
  • \( z=\left<z_1,z_2\right>_2 \),
  • \( z_1+ z_2\leq z \),
  • \( z=\left<x, y\right>_2\rightarrow x=z_1\land y=z_2 \).

Demostración
Ya hemos demostrado la primera afirmación. Respecto de la segunda, se cumple trivialmente si \( z_1=z_2=0 \), así que podemos suponer que \( z_1+z_2\geq 1 \), en cuyo caso

\( 2z=2\left<z_1,z_2\right>\geq (z_1+z_2)(z_1+z_2+1)=(z_1+z_2)^2+(z_1+z_2) \)

\( \geq (z_1+z_2)\cdot 1+(z_1+z_2)=2(z_1+z_2), \)

luego \( z_1+z_2\leq z \).

Si \( z=\left<x, y\right>_2 \), llamando \( r=x+y \), tenemos que \( 2z=r(r+1)+2x \), con \( x\leq r \), luego

\( r(r+1)\leq 2z\leq r^2+r+2x\leq r^2+3r<r^2+3r+2=(r+1)(r+2), \)

y antes hemos probado que esto implica \( r=G(z)=z_1+z_2 \), luego

\( (z_1+z_2)(z_1+z_2+1)+2z_1=2z=r(r+1)+2x \)

implica que \( 2x=2z_1 \), luego \( x=z_1 \), y entonces \( z_1+z_2=x+y \) implica que \( y=z_2 \).
[cerrar]

Respecto a la segunda propiedad, creo que no hace falta demostrar tampoco nada porque en lo anterior se ha visto que \( z_1+z_2=G(z) \) y que \( G(z) \leq z \), ¿no?

Sucesiones finitas Ahora podemos formalizar la codificación de las sucesiones finitas de números naturales expuesta en este mensaje.

Concretamente, podemos considerar el funtor

\( \left<x, y, z\right>_3=\left<\left<x, y\right>_2, z\right>_2 \)

y las proyecciones \( z^3_1=(z_1)_1 \), \( z^3_2=(z_1)_2 \), \( z^3_{\color{red}3\color{black}}=z_2 \), de modo que

\( z=\left<z_1,z_2,z_3\right>,\qquad z = \left<u, v, w\right>_3\rightarrow u = z_1\land v=z_2\land w=z_3. \)

Aquí había una pequeña errata y me parece que en algún lugar habría que especificar que dada una variable \( n \), la notación \( n_1, n_2 \) significa \( z_1(n), z_2(n) \), ¿no?

Finalmente definimos una nueva familia de infinitos funtores:

\( \left<x_1,\ldots, x_n\right>^n_\infty=\left<n\color{red}\dot{-} \color{black}1,\left<x_1,\ldots, x_n\right>_n\right>_2+1. \)

Así, cada número natural no nulo \( s \) codifica una única sucesión. Podemos considerar que el número natural \( 0 \) codifica la sucesión vacía que tiene \( 0 \) términos. Más precisamente, definimos la longitud de un número natural como

\( \ell(s)=(1\dot{-}(1\dot{-} s))(s_1+1). \)

Así, \( \ell(0)=0 \), mientras que si \( s\neq 0 \), entonces \( \ell(s)>0 \) y \( s_1=\ell(s)\dot{-}1 \).

Esto no sería más bien \( \ell(s)=(1\dot{-}(1\dot{-} s))((s \dot{-} 1)_1+1) \) y que \( (s \dot{-} 1)_1=\ell(s)\dot{-}1 \).

Teorema \( \ell(s)=\ell(t)\land (\forall i<\ell(s)\, s_i=t_i)\rightarrow s=t \).

Demostración
Si \( \ell(s)=\ell(t)=0 \), entonces \( s=t=0 \). Supongamos que \( \ell(s)=\ell(t)>0 \). Entonces

\( l=(s\dot{-} 1)_1=\ell(s)\dot{-} 1=\ell(t)\dot{-} 1=(t\dot{-} 1)_1. \)

Veamos por inducción que

\( i\leq l \rightarrow R(s, l\dot{-} i)=R(t, l\dot{-} i). \)

Para \( i=0 \) tenemos que

\( R(s, l)=s_0=t_0=R(t, l). \)

Si es cierto para \( i<l \), entonces \( i+1\leq l \), luego \( i+1+(l\dot{-} (i+1))=l \), de donde \( (l\dot{-}(i+1))+1=l\dot{-} i \). Por lo tanto,

\( R(s, l\dot{-}(i+1))_1=R(s, (l\dot{-} (i+1))+1)=R(s, l\dot{-} i)=R(t, l\dot{-} i)=R(t, l\dot{-} (i+1))_1. \)

Por otra parte,

\( R(s, l\dot{-}(i+1))_{\color{red}2\color{black}}=s_{i+1}=t_{i+1}=R(t, l\dot{-}(i+1))_{\color{red}2\color{black}}, \)

luego \( R(s, l\dot{-}(i+1))=R(t, l\dot{-}(i+1)) \). Esto completa la inducción y, aplicándolo a \( i=l \) obtenemos

\( (s\dot{-} 1)_2=R(s, 0)=R(t, 0)=(t\dot{-} 1)_2, \)

pero \( (s\dot{-} 1)_1=l=(t\dot{-} 1)_1 \), luego de hecho \( s\dot{-} 1=t\dot{-} 1 \), luego \( s=t \).
[cerrar]

Pequeña errata en la demostración.

Así, cada número natural no nulo \( s \) codifica una única sucesión.

[...]

Una comprobación rutinaria muestra que

\( p^\infty_i(\left<x_0,\ldots, x_{n-1}\right>^n_\infty)=x_i, \)

lo que prueba que toda sucesión finita de números naturales está codificada por un número natural.

Veo un poco confusas estas afirmaciones tal y como están hechas.

La primera nos dice que cada natural \( s \) codifica una única sucesión y esto está claro, pero para verlo formalmente, ¿no es mejor poner la afirmación más adelante cuando se vea claro que si es \( l=\ell(s) \) entonces \( s=\langle s_0, \cdots, s_{l \dot{-} 1} \rangle \)?

Mientras que la segunda, veo que ambas cosas que se dicen son ciertas, pero no veo la relación clara entre ellas. Quiero decir que lo que dices sobre que "esto prueba que toda sucesión finita está codificada por un natural", ¿no es trivial simplemente por la definición de sucesión finita que hemos dado al ya saber que \( <x, y>_2 \) representa un único natural?

Un saludo.