Autor Tema: Teorema de Gödel

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

14 Junio, 2009, 12:07 pm
Respuesta #60

LauLuna

  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 545
  • País: es
  • Karma: +1/-0
  • Sexo: Masculino
Como los programas reales sólo pueden hacer cálculos con conjuntos finitos, me da la impresión de que el teorema de Gödel o el problema de la parada no debe de ser fácil de programar en un ordenador.

No sé exactamente lo que quieres decir con lo de cálculos con conjuntos finitos, pero por lo que entiendo, no es correcto. Claramente hay programas que deciden si un número natural es primo, y lo hacen para todo número natural. Como esto es muy evidente, imagino que no te he entendido bien.

No puedo juzgar sobre si es o no fácil programar un ordenador para que demuestre el teorema de Gödel pero desde luego es posible. Todo sistema formal axiomático puede convertirse en un algoritmo que genera teoremas, y siempre es posible introducir (parte de) la metateoría del sistema en otro sistema formal axiomático.

En concreto, el sistema formal que Gustavo Piñeiro está construyendo (al que sólo le faltan ya, creo, los axiomas aritméticos) será capaz de demostrar una fórmula equivalente, bajo la interpretación usual, al primer teorema de incompletitud de Gödel:

"si el sistema es consistente, hay enunciados de su lenguaje indecidibles en el sistema'

Así que si Argentinator se empeña en convertir el sistema en un algoritmo generador de teoremas, lo conseguirá tarde o temprano.

Gustavo, quedamos en que llamamos teoremas sólo a los enunciados demostrables. Bien, casi mejor; esto no altera nada pero es posible que haya que recordarlo luego a lo largo de la demostración.

Un saludo



14 Junio, 2009, 02:47 pm
Respuesta #61

Numerarius

  • Lathi
  • Mensajes: 312
  • Karma: +0/-0
  • Sexo: Masculino
Como los programas reales sólo pueden hacer cálculos con conjuntos finitos, me da la impresión de que el teorema de Gödel o el problema de la parada no debe de ser fácil de programar en un ordenador.

No sé exactamente lo que quieres decir con lo de cálculos con conjuntos finitos, pero por lo que entiendo, no es correcto. Claramente hay programas que deciden si un número natural es primo, y lo hacen para todo número natural. Como esto es muy evidente, imagino que no te he entendido bien.


Bueno, el conjunto de los números primos es recursivamente enumerable. Así que, en teoría se podría demosrtrar la propiedad"ser primo" para cualquier número natural.

Pero a lo que me refería es a lo siguiente: para demosrar que existen infinitos números primos, no recorres toda la serie  de los números naturales. Porque el conjunto N es infinito. Así que, por muchos números que recorra el computador, sólo habrás recorrido una parte infinitesimal de los números naturales.

Así que la exstencia de infinitos números primos, se demuestra matemáticamente. La demostración de Euclides era que dados todos los números primos: (1·2·3....n) se construye el número:

x= (1·2·3....·n) + 1. Número que no es divisible por 1, por 2, por 3....ni por n. Así que o x es primo, o existe un número primo entre n y x. 


14 Junio, 2009, 02:56 pm
Respuesta #62

Numerarius

  • Lathi
  • Mensajes: 312
  • Karma: +0/-0
  • Sexo: Masculino
argentinator, supongo que sí puede haber un programa que decida, para cadenas finitas, si éstas son teoremas o no. También podría haber un programa que decida si son fórmulas bien formadas o no.

Por ejemplo, esta proposición

\( \exists x \;x= 0 \)

podría ser un teorema (si es que es demostrable en el sistema). En cambio:

\( p\land \lnot\; p \)

Una proposición como ésta es falsa, así que no sería demostrable como teorema  en el sistema, a no ser que el sistema fuera inconsistente. Sin embargo, es una proposición bien formada. Una proposición falsa puede estar bien formada.

En cambio la proposición

(((((((((((((((((((((((((((((8

no está bien formada.
 



14 Junio, 2009, 03:48 pm
Respuesta #63

Gustavo Piñeiro

  • Visitante
supongo que sí puede haber un programa que decida, para cadenas finitas, si éstas son teoremas o no.

No siempre es así, depende de cada teoría. Si los axiomas forman un conjunto recursivo entonces existe un algoritmo que determina si una sucesión finita de signos es una fórmula y si una sucesión finita de fórmulas es una demostración. Pero no necesariamente sucede lo mismo con los teoremas. (Dicho en términos técnicos, los teoremas forman un conjunto recursivamente numerable, pero no siempre un conjunto recursivo. Es decir, existe un algoritmo que va generando los teoremas "uno por uno", pero no necesariamente uno que los "reconozca".)

Gustavo, quedamos en que llamamos teoremas sólo a los enunciados demostrables. Bien, casi mejor; esto no altera nada pero es posible que haya que recordarlo luego a lo largo de la demostración.

Si es necesario, lo recordaremos.

Un saludo,

14 Junio, 2009, 03:57 pm
Respuesta #64

Gustavo Piñeiro

  • Visitante
Algunas definiciones:

Definición: Un conjunto de axiomas es consistente si no existe una fórmula \( P \) tal que \( P \) y \( -P \) sean a la vez demostrables.

Puede probarse que si un conjunto de axiomas no es consistente entonces toda fórmula \( Q \) es demostrable. Esto se debe, básicamente, al hecho de que cualesquiera sean \( P \) y \( Q \), la fórmula \( P\Rightarrow (-P\Rightarrow Q) \) es demostrable.

En un sistema inconsistente todo es demostrable y todo es refutable (refutable significa que su negación sea demostrable). Los sistemas inconsistentes son triviales en el peor sentido de la palabra.

Definición: Un conjunto de axiomas es \( \omega  \)-consistente si no existe una fórmula \( P(x) \) tal que \( P(0) \), \( P(1) \), \( P(2) \),... y \( \exists{x}(-P(x)) \) sean a la vez demostrables.

Aunque la segunda definición involucra un infinito actual, es importante destacar que ambas sólo utilizan conceptos sintácticos (que dependen de manipulaciones de signos, independientemente de su significado).

Es fácil probar que todo conjunto \( \omega  \)-consistente es también consistente, sin embargo no vale la recíproca (podremos dar un  contraejemplo después de demostrar el teorema de Gödel).

Si agregamos la regla de inferencia no finitaria que cité en un comentario anterior (y que invalida el teorema de Gödel) en ese caso sí valdría que todo conjunto consistente es también \( \omega  \)-consistente.

<<                >>

15 Junio, 2009, 08:36 pm
Respuesta #65

LauLuna

  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 545
  • País: es
  • Karma: +1/-0
  • Sexo: Masculino
Definición: Un conjunto de axiomas es consistente si no existe una fórmula \( P \) tal que \( P \) y \( -P \) sean a la vez demostrables.

Hay un problema con esta definición: la fórmula esa que no debe existir no sabemos exactamente qué relación tiene con el conjunto de axiomas. Deberíamos decir que no existe una fórmula tal que ella y su negación son consecuencias lógicas del conjunto de axiomas. Pero para eso tendríamos que definir 'consecuencia lógica', y tal vez eso no sea necesario.

Quizá sería mejor decir que no existe una fórmula tal que ella y su negación son demostrables en el sistema, pero entonces deberíamos hablar de cuándo es consistente un sistema, no un conjunto de axiomas.

Gustavo, ¿hay alguna razón por la que prefieras hablar de la consistencia de un conjunto de axiomas mejor que de la consistencia de un sistema?

Sucede lo mismo para la definición de omega-consistencia.

Un saludo.


15 Junio, 2009, 08:53 pm
Respuesta #66

Gustavo Piñeiro

  • Visitante
Definición: Un conjunto de axiomas es consistente si no existe una fórmula \( P \) tal que \( P \) y \( -P \) sean a la vez demostrables.

Hay un problema con esta definición: la fórmula esa que no debe existir no sabemos exactamente qué relación tiene con el conjunto de axiomas.

En realidad sí lo sabemos, porque ya definimos qué quiere decir que una fórmula sea demostrable:

Definición: una demostración es una sucesión finita de fórmulas en la que cada una de ellas es, o bien un axioma (propio o lógico), o bien se dedude de fórmulas anteriores por aplicación de las reglas de inferencia.

Definición: una fórmula es demostrable si es la última fórmula en una demostración.


Por otra parte (no encuentro ahora la cita) también dije que usaríamos "conjunto de axiomas" y "sistema de axiomas" como sinóinimos.

Si mis formalismos llevan a confusión, realmente no tengo ningún inconveniente en ceder esta tarea de desarrollarlos a quien desee tomarla. No tiene más que "levantar la mano" y yo gustosamente le cederé mi puesto en esta especie de "estrado virtual" en el que siento que me hallo. :)

Saludos,

Gustavo

15 Junio, 2009, 08:55 pm
Respuesta #67

argentinator

  • Consultar la FIRMAPEDIA
  • Administrador
  • Mensajes: 7,738
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
  • Vean mis posts activos en mi página personal
    • Mis posts activos (click aquí)

Si mis formalismos llevan a confusión, realmente no tengo ningún inconveniente en ceder esta tarea de desarrollarlos a quien desee tomarla. No tiene más que "levantar la mano" y yo gustosamente le cederé mi puesto en esta especie de "estrado virtual" en el que siento que me hallo. :)



¡No! ¡No cambiemos ahora de chivo expiatorio!  >:D
Si cambiamos mucho las cosas se va a armar una confusión terrible.
Creo que basta conque nos pongamos de acuerdo en el significado de los formalismos que se van a usar.


15 Junio, 2009, 09:49 pm
Respuesta #68

argentinator

  • Consultar la FIRMAPEDIA
  • Administrador
  • Mensajes: 7,738
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
  • Vean mis posts activos en mi página personal
    • Mis posts activos (click aquí)
Hice antes unas preguntas, pero las cambio de lugar para que no se mezclen tanto las cosas:


Axiomas lógicos:
...
Por definición, un axioma lógico es cualquier fórmula que ...
...
4. \( \forall{x}F(x)\Rightarrow{}F(x/t) \).
Una explicación aquí: \( x \) respresenta una variable cualquiera y cuando escribimos \( F(x) \) entendemos que \( x \) es una variable libre en F, \( t \) es un término y \( F(x/t) \) es la fómrula que se obtiene reemplazando toda aparición de la variable \( x \) por el término \( t \). Una restricción: si \( t \) tiene variables, ninguna de éstas puede aparecer afectada por un cuantificador al efectuarse el reemplazo.

Hola.

No me queda muy claro todo esto.
Es claro que la regla es ''reemplazar x por t'', pero no entiendo bien qué pasa con los eventuales cuantificadores.

1er pregunta: Se ha establecido que todo término contiene constantes o variables. En particular x es una variable. ¿Qué pasa si deseo reemplazar x por t, cuando t es un término que ''adentro'' contiene a la misma x?
¿No es esto algo mal definido, no queda algo recurrente e infinito, como producto de reemplazos sin fin?

2da pregunta: En cuanto a la restricción de los cuantificadores...
Si t es un término, es una lista de signos en la que no figura el signo de cuantificación \( \exists{} \).
Así que si pido que las variables que figuran en t no estén afectadas por cuantificadores, entiendo que esos cuantificadores son ''externos'' a t. Así que imagino que se refiere a cuantificadores que podrían aparecer dentro de F.
¿Pero qué significa exactamente la restricción?
Lo que entiendo es que ''una vez efectuado el reemplazo de x por t no debe quedar ninguna variable en t afectada por un cuantificador de los que había en F''.
Creo que lo entiendo, pero aún así no lo veo muy claro.

Una cuestión filosófica:
Para decidir si una expresión es un término o no lo es, tengo que rechazar por ejemplo las expresiones que tengan cuantificadores.
Cuando se da la definición de término, está bien, se hace de modo constructivo.
Pero ¿qué pasa si me dan una expresión t cualquiera, y debo determinar si es o no un término?
Para probarlo, debo pasar uno a uno por sus signos, y si encuentro un símbolo que no corresponde a constantes o variables o paréntesis, concluir que t no es un término.
Sin embargo, no estoy seguro de si la propiedad de ''no ser un término'' forma parte de las reglas que definen lo que es un término.
Me refiero a que yo me doy cuenta con mi propia razón que una expresión no es un término, pero no estoy seguro de si esto se deduce propiamente de las reglas dadas, las cuales se dan en ''positivo'' (o sea, para afirmar cuándo tengo un término), pero no en negativo (cuando deseo probar que algo no es un término).

No sé si entiende esta última duda, o si es demasiado quisquilloso de mi parte.
Pero es que no quiero usar ''razonamientos'' que no están estipulados en el conjunto de reglas que se han aceptado hasta ahora.
No creo que haya hechos que pueda dar por sobreentendidos, porque a la larga puede ser fuente de falacias.


15 Junio, 2009, 11:44 pm
Respuesta #69

argentinator

  • Consultar la FIRMAPEDIA
  • Administrador
  • Mensajes: 7,738
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
  • Vean mis posts activos en mi página personal
    • Mis posts activos (click aquí)
Comenté antes que si se agregara la siguiente regla de inferencia:

De los infinitos enunciados \( P(0), P(1), P(2),... \) se deduce \( \forall{x}P(x) \).

Entonces el teorema anterior sería falso y también sería falso el teorema de Gödel.

Me parece que acá hay cosas que no estoy entendiendo.

Cuando hablás de P(0), P(1), P(2), ¿los números 0, 1, 2, qué vendrían a ser: acaso 0, S0, SS0, etc.?
En todo caso, si tengo una proposición P, con una variable x, parece que entiendo lo que significa P(x).
Según lo que se ha estado hablando, sería una fórmula en la cual aparece la variable x en forma libre.
Ahora por el axioma de reemplazo, para 0, 1, 2, etc., tendría que P(0), P(1), P(2), etc., tienen sentido.
Pero en lugar de x pueden ir cosas como (s+t), (s.t), donde s y t son términos que incluyen variables, constantes, etc.
Me da la sensación de que me está faltando algo, o sobrando. Por ejemplo, no sé qué hacer con P(3+4), mientras aún no sé que 3+4 es 7.

¿Faltan axiomas aritméticos tal vez?