Autor Tema: Teorema de Gödel

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

23 Julio, 2009, 08:43 pm
Respuesta #170

LauLuna

  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 546
  • País: es
  • Karma: +1/-0
  • Sexo: Masculino
Propongo un trato: yo hago la parte fácil y tú la que queda.

De  nuevo tomo 'n y m como sus propios numerales.

Supón Q(n).

Q(n) es por definición:

1. para todo x (x = d(n) -> P(x)).

Como hemos definido m = d(n), Q(n) es lo mismo que

2. para todo x (x = m -> P(x))

Eliminando el cuantificador universal en 2. tenemos:

3. m = m -> P(m)

Como 'm = m' es un axioma lógico, el sistema lo demuestra y tenemos:

4. m = m

Por Modus Ponens en 3. y 4. tienes:

5. P(m)

¡Venga!

23 Julio, 2009, 09:55 pm
Respuesta #171

Cristian C

  • $$\Large \color{#5e8d56}\pi\,\pi\,\pi$$
  • Mensajes: 474
  • Karma: +0/-0
  • Sexo: Masculino
Te agradezco el esfuerzo, LauLuna, pero realmente ignoro qué es lo que has probado.

Partes de \( Q(n) \) pero debemos partir de \( Q[\bar{n}] \) que se define \( \forall{x}(x=\bar{n}\Rightarrow{Q(x)}) \)

Saludos.

Mi primer gran deslumbramiento matemático consistió en comprender que puede demostrarse que existen infinitos de diferente tamaño.
El segundo fue comprender que lo anterior, aun pese a ser correcto, carece de todo significado.

23 Julio, 2009, 10:26 pm
Respuesta #172

LauLuna

  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 546
  • País: es
  • Karma: +1/-0
  • Sexo: Masculino
Tienes razón, Cristian.

He confundido Q(n) con Q[n].

Pero en realidad no hay gran diferencia. Puedes pasar de Q[n] a Q(n) por el método que he usado yo antes:

1. Q[n]
2. para todo x (x = n -> Q(x))
3. n = n -> Q(n)
4. n = n
5. Q(n)

De Q(n) a P[m] es muy fácil, dado que Q(n) es

     para todo x (x = d(n) -> P(x))

que es

     para todo x (x = m -> P(x))

que es

    P[m]

El camino inverso -es decir, desde los paréntesis a los corchetes- puede que tenga un poco más de dificultad.

Espero no haberme confundido de nuevo :(

24 Julio, 2009, 01:46 pm
Respuesta #173

Cristian C

  • $$\Large \color{#5e8d56}\pi\,\pi\,\pi$$
  • Mensajes: 474
  • Karma: +0/-0
  • Sexo: Masculino
Debo estar poniéndome viejo.
Gracias LauLuna. Salía con solo mirarlo un poco.

Mi primer gran deslumbramiento matemático consistió en comprender que puede demostrarse que existen infinitos de diferente tamaño.
El segundo fue comprender que lo anterior, aun pese a ser correcto, carece de todo significado.

31 Agosto, 2009, 01:50 am
Respuesta #174

argentinator

  • Consultar la FIRMAPEDIA
  • Administrador
  • Mensajes: 7,797
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
10. \( x = y \Rightarrow{} F(z_1, z_2,\ldots z_{k-1},x,z_{k+1}\ldots z_n) \Rightarrow{} F(z_1, z_2,\ldots z_{k-1},y,z_{k+1}\ldots z_n) \), donde \( F \) es una fórmula cualquiera.

Tengo una duda con este Axioma tal como está escrito.
Ocurre que Gustavo pone ese Axioma para una fórmula cualquiera,
mientras que en su libro Godel para todos ponen que la fórmula debe ser de tipo "atómica".
Quisiera estar seguro de cuál es la forma correcta.


31 Agosto, 2009, 01:41 pm
Respuesta #175

Gustavo Piñeiro

  • Visitante
10. \( x = y \Rightarrow{} F(z_1, z_2,\ldots z_{k-1},x,z_{k+1}\ldots z_n) \Rightarrow{} F(z_1, z_2,\ldots z_{k-1},y,z_{k+1}\ldots z_n) \), donde \( F \) es una fórmula cualquiera.
Tengo una duda con este Axioma tal como está escrito.
Ocurre que Gustavo pone ese Axioma para una fórmula cualquiera,
mientras que en su libro Godel para todos ponen que la fórmula debe ser de tipo "atómica".
Quisiera estar seguro de cuál es la forma correcta.

Desde el punto de vista sintáctico (que es el que prevalece en ese punto de la demostración) los axiomas deben entenderse como indicación de qué fórmulas es lícito usar en las demostraciones formales.

Se puede probar (por inducción en la complejidad de las fórmulas) que si en el esquema citado sólo se toman fórmulas atómicas, entonces cualquier fórmula del tipo \( x = y \Rightarrow{} F(z_1, z_2,\ldots z_{k-1},x,z_{k+1}\ldots z_n) \Rightarrow{} F(z_1, z_2,\ldots z_{k-1},y,z_{k+1}\ldots z_n) \), donde \( F \) es una fórmula cualquiera, es demostrable (y puede, por ende aparecer en cualquier demostración).

Por lo tanto, al definir el esquema citado, esencialmente es equivalente tomar "fórmulas atómicas" que "fórmulas cualesquiera" (equivalente en el sentido de que en ambos casos se habilita el uso de las mismas fórmulas).

De hecho, y ahora voy más allá de la pregunta, en realidad nos interesa que estén habilitadas las fórmulas del tipo \( s = t \Rightarrow{} F(z_1, z_2,\ldots z_{k-1},s,z_{k+1}\ldots z_n) \Rightarrow{} F(z_1, z_2,\ldots z_{k-1},t,z_{k+1}\ldots z_n) \), donde s y t son términos cualesquiera. Puede probarse (por inducción en la complejidad de s y t) que si se adopta el esquema 10 entonces toda fórmula de este último tipo es demostrable (y puede usarse en las demostraciónes formales, ya sea con fórmulas atómicas o cualesquiera).

En realidad, este último esquema no debe entenderse como "si s = t entonces se puede reemplazar s por t". Más bien debe leerse así: "si se puede probar que el término s es igual al término t entonces, si se puede probar que F vale para s, también se puede probar que F vale para t".

Saludos!

<<                >>

31 Agosto, 2009, 05:02 pm
Respuesta #176

argentinator

  • Consultar la FIRMAPEDIA
  • Administrador
  • Mensajes: 7,797
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
Bueno, gracias por la aclaración.

La cuestión es que aún estoy haciendo el programa en la PC que realiza todos estos cálculos.
Cuando tengo que verificar si cierta expresión es o no un Axioma, o si es o no el Axioma 10, hay una sola posibilidad, que uno tiene que elegir como "Axioma", y lo demás ...
Después quizá lo que estás diciendo de considerar \( s \) y \( t \) términos, es posible que uno pueda "demostrarlo", y no tomarlo como Axioma.

La duda viene porque no sé qué especificar como Axioma en el programa.
Yo como "humano" me puedo creer que entiendo que es más o menos lo mismo poner una cosa que otra más general.
Pero cuanto más general es el Axioma, más complicado es programarlo.
Porque se me hace difícil "explicarle" al programa lo que quiero hacer.

Citar
En realidad, este último esquema no debe entenderse como "si s = t entonces se puede reemplazar s por t". Más bien debe leerse así: "si se puede probar que el término s es igual al término t entonces, si se puede probar que F vale para s, también se puede probar que F vale para t".

Con esto me he confundido.
¿Un Axioma no es acaso una mera fórmula?
Ahí ya lo estás explicando como parte de una demostración, o algo por el estilo.
Si yo quiero entenderlo a nivel de meros "signos", ¿qué dice el Axioma 10?

Entiendo que \( F(z_1,...,z_n) \) es una fórmula que contiene a lo sumo a esas variables \( z_1,...,z_n \).

Ahora, supongamos que estoy analizando con un algoritmo si cierta fórmula es o no el Axioma 10.
Encuentro por ejemplo una expresión como esta:
\( x=y \Rightarrow{(F\Rightarrow{G})} \), donde \( x, y \) son variables y \( F, G  \) son fórmulas.
A continuación, ¿cómo hago para escribir \( F  \) como una fórmula con ciertas variables \( z_1,...,z_n \)?
O sea, lo que el programa recibe como dato de entrada es una fórmula \( F \) en la que ya se ha reemplazado alguna de las variables por \( x \). Tengo que "adivinar" o "reconstruir" la fórmula \( F \) antes de haber sufrido el reemplazo de \( z_j \) por \( x \).
Lo que he hecho en el programa es pensar que, en la fórmula \( F \), todas las ocurrencias de x corresponden a las ocurrencias de alguna variable \( z_j \) en la fórmula original. A esa variable la denoto con "t", por ejemplo, y así detecto la "estructura" orginal de \( F \).
Pero aquí ya estoy haciendo supuestos "heurísticos" de cómo funcionan las cosas.

Como sea, lo he tomado porque ese método de "reconstrucción" es un criterio que me parece "finitista".

Ahora debo analizar la expresión \( G \), para ver si coincide con lo "esperado".
Si reemplazo directamente \( x \) por \( y \), y comparo a ver si \( G \) coincide con \( F(z_1,...,z_{j-1},y,...,z_n) \) puedo obtener cosas muy extrañas.
Por ejemplo si una de las variables de \( F \) ya es la misma \( y \), como en  \( F(z_1,y)  \equiv z_1 = y+y \), y resulta que en realidad la fórmula \( F \) que he detectado es de la forma \( F(x,y) \), lo que tengo es que \( x \) ocupa el lugar de \( z_1 \).
Luego, tras el reemplazo que viene de "\( x=y \)", obtendría \( F(y,y) \), y si \( G \) coincide con eso, estaría obteniendo una coincidencia con el programa... y estaría diciendo que puedo "demostrar" que todo número es igual a su doble... mmmm.

Así que, para solucionar eso, he tomado un enfoque inverso.
He buscado las instancias de la variable \( y \) en la fórmula \( G \), y las he reemplazado por el signo indicador "\( t \)".
Ahora sí comparo \( F(x/t) \) y \( G(x/t) \), y obtengo que la "estructura" de ambas es la misma, observando que ambas tienen la misma forma, las mismas variables, y que el signo "\( t \)" aparece en ambas en los mismos "lugares".

Ese es el método que he hallado para evitar el reemplazo directo de \( x \) por \( y \), que conduce a errores si la variable \( y \) ya figuraba en \( F \).

Pero aún así, esos criterios que usé me parecen demasiado "sacados de la galera".
Probandolo con ejemplos, el método funciona bien, pero aún así, estoy algo "en el aire", sin tener clara la base teórica de todo esto del manipuleo de signos del lenguaje.

¿Hay algún modo de justificar mi procedimiento?
¿O tengo que cambiar mi procedimiento por algún otro?
¿Cómo, si no, detecto la "estructura original"  de una fórmula F, que depende de ciertas variables, para poder luego determinar si una fórmula corresponde o no al Axioma 10?

Con el Axioma 9 he tenido que aplicar un procedimiento análogo.

31 Agosto, 2009, 06:07 pm
Respuesta #177

Gustavo Piñeiro

  • Visitante
Cuando tengo que verificar si cierta expresión es o no un Axioma, o si es o no el Axioma 10, hay una sola posibilidad, que uno tiene que elegir como "Axioma", y lo demás ...
.............
¿Un Axioma no es acaso una mera fórmula?

Un axioma es una mera fórmula. En el esquema 10 se puede tomar "fórmula atómica" o "cualquier fórmula", ambas opciones son correctas y la elección depende de la conveniencia (en este caso de lo que te resulte más fácil de programar). Lo que traté de explicar antes es por qué los axiomas se eligen como se eligen y por qué, en particular, es válido tomar una u otra opción para el esquema 10.

Saludos,

<<                >>

03 Septiembre, 2009, 10:39 pm
Respuesta #178

argentinator

  • Consultar la FIRMAPEDIA
  • Administrador
  • Mensajes: 7,797
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
A ver si encuentro un ejemplo más concreto.
Por ejemplo, el siguiente: ¿satisface o no el Axioma 10?

\( (x'=x\Rightarrow{}(\exists{x}\exists{}{}x'S(x)=(x.x')\Rightarrow{}\exists{x}\exists{}{}xS(x)=(x.x))) \)

Tengo la fórmula \( F(x,x')\equiv{\exists{x}\exists{}{}x'S(x)=(x.x')} \).
Al "sustituir" \( x' \) por \( x \) obtengo la última fórmula \( G\equiv{}\exists{x}\exists{}{}xS(x)=(x.x) \).

Creo que acá la situación es distinta, porque he metido cuantificadores en las fórmulas.

La fórmula \( \exists{x}\exists{}{}x'S(x)=(x.x') \) "estimo" que es demostrable (que "existen"\( x,x' \) cumpliendo esa igualdad vendría de tomar \( x=1,x'=2 \)).
También, previamente puedo haber probado que \( x=x' \), lo cual es perfectamente posible en medio de alguna cadena de inferencias.
Pero esto no tiene nada que ver con el uso posterior de \( x, x' \), que aparecen afectadas por cuantificadores.

¿Está bien ahora que acepte "demostrado" \( G \), que es \( G\equiv{}\exists{x}\exists{}{}xS(x)=(x.x) \)?
Esto último es falso porque si existiera un tal x, cumpliría la ecuación cuadrática \( x^2-x-1=0 \), que no tiene soluciones enteras positivas.

Sin embargo, la expresión completa
\( (x'=x\Rightarrow{}(\exists{x}\exists{}{}x'S(x)=(x.x')\Rightarrow{}\exists{x}\exists{}{}xS(x)=(x.x))) \)
parece encuadrar en el Axioma 10.
Pero a mí me parece que a lo mejor sea demasiado general.

¿Estoy interpretando mal el Axioma 10, o hay que darle un enunciado más preciso?

Si seguimos la versión original del libro "Godel para todos", donde sólo se usan fórmulas atómicas, entonces no hay problemas con los cuantificadores.
Aunque a lo mejor el problema seguirá existiendo cuando quiera uno determinar si fórmulas como la de arriba son "demostrables".

En mi experiencia matemática, mezclar variables libres que después aparecen cuantificadas, son expresiones que están mal formadas.
Pero como estoy siguiendo paso a paso tu construcción, no estoy seguro del lugar en que debe hacerse alguna restricción o aclaración.
Y la verdad es que tampoco sé si hay que hacer tales restricciones, sino que quizá haya que interpretar las situaciones "peculiares" de otro modo, y que haya alguna manera de considerarlas válidas.

04 Septiembre, 2009, 05:52 pm
Respuesta #179

LauLuna

  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 546
  • País: es
  • Karma: +1/-0
  • Sexo: Masculino
A ver si encuentro un ejemplo más concreto.
Por ejemplo, el siguiente: ¿satisface o no el Axioma 10?

\( (x'=x\Rightarrow{}(\exists{x}\exists{}{}x'S(x)=(x.x')\Rightarrow{}\exists{x}\exists{}{}xS(x)=(x.x))) \)

Esto es efectivamente un teorema, pero date cuenta de que es un condicional: sólo podrías obtener el consecuente (y luego el consecuente del consecuente) si pudieras demostrar x=x'; pero esto último no es un teorema.

La aparición de cuantificadores no modifica nada.

Espero que esto aclare algo las cosas.

Un saludo.