Autor Tema: Teorema de Gödel

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

17 Junio, 2009, 10:54 pm
Respuesta #90

Gustavo Piñeiro

  • Visitante
Para darle el toque final a la saga de las dudas totales, me cuestiono acerca de la operación misma de concatenar signos.

La operación de concatenaicón de signos es crucial en la demostración del teorema de Gödel que tengo intención de mostrar. De hecho, no exagero, está enteramente basada en ella.

Ahora que Gustavo ha puesto todas las reglas, ando con ganas de practicar con algunas deducciones.  
Saludos

Tal vez convenga entonces mostrar, a modo de ejemplo, un conjunto recursivo de axiomas aritméticos. El sistema clásico es el de los "axiomas de Peano de primer orden", que se pueden escribir así (dejo tácitos todos los cuantificadores universales (los \( \forall{} \)) necesarios para que las fórmulas sean enunciados):

1. \( Sx = Sy \Rightarrow x = y \)
2. \( Sx\neq 0 \) (que es una abreviatura de \( -(Sx = 0) \))
3. \( x + 0 = x \)
4. \( x + Sy = S(x + y) \)
5. \( x\cdot{0} = 0 \)
6. \( x\cdot{Sy} = x\cdot{y}+x \)
7. \( P(0)\Rightarrow (\forall{x}(P(x)\Rightarrow P(Sx))\Rightarrow \forall{y}P(y)) \)

Todo enunciado finitario (en el sentido de "verificable mecánicamente") verdadero es demostrable a partir de estos axiomas. Tal vez, argentinator, quieras practicar deduciendo que 1 + 1 = 2 o que la suma es conmutativa (este último no es un enunciado finitario pero sí uno de los que Hilbert consideraba intuitivamente evidentes).

(A propósito de un comentario anterior sobre cómo podría redactarse un algoritmo para reconocer si una expresión es un término, en la página 96 del libro hay una descripción de un algoritmo para reconocer fórmulas que pued adapatrse fácilmente a los términos.)

<<                >>

18 Junio, 2009, 06:15 am
Respuesta #91

argentinator

  • Consultar la FIRMAPEDIA
  • Administrador
  • Mensajes: 7,797
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
Hay muchos otros sistemas axiomáticos, como por ejemplo los de la teoría de conjuntos.

Lo que yo te pregunto es si estos axiomas de Peano que has puesto son relevantes para el Teorema de Godel.
Creo que dijiste que no en cierto momento, y además estamos usando ya cierta intuición de los ''numerales'' y nos hemos autorizado a operar con ellos cuando se ha definido recursivamente el concepto de verdad matemática.

He leído este punto en vuestro libro, y aparece de nuevo acá, y la verdad es que no entiendo bien la mesconlanza entre estos axiomas de Peano sobre los números y las operaciones con números que ya estamos usando desde la definición de verdad matemática.
Definición: Diremos que un enunciado atómico t = s es verdadero si t y s representan el mismo número, y falso en caso contrario.

La cuestión es que tenemos varias cosas dando vueltas por ahí: reglas de formación de fórmulas, reglas de inferencia, axiomas lógicos, noción de verdad matemática, y axiomas de teorías particulares.
Cuando se establece la noción de verdad matemática, ya se habla allí de números, y se trabaja con ellos, y se establecen operaciones aritméticas e igualdades.
Después uno puede establecer axiomas para la teoría que se le de la gana, pero en principio me la imagino algo despegada de todo lo anterior.
Sin embargo los axiomas de Peano hablan otra vez de números.

Además, los axiomas 3, 4, 5 y 6, ¿no se enredan con las igualdades de los numerales, que se suponen ciertas ya en la definición de verdad?
O sea, si reemplazo las variables x, y  por valores constantes, obtengo cosas que ya tenía.

Es cierto que estos axiomas dicen más que la aritmética intuitiva que veníamos usando, pero me incomoda el hecho de que haya cierta superposición entre ambas cosas.

Nota: Los axiomas de Peano los conozco hace mucho, pero verlos metamatemáticamente me está haciendo cortocircuito en la cabeza.

Saludos

18 Junio, 2009, 06:50 am
Respuesta #92

argentinator

  • Consultar la FIRMAPEDIA
  • Administrador
  • Mensajes: 7,797
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
Tal vez, argentinator, quieras practicar deduciendo que 1 + 1 = 2

¿No es que 1+1 era igual a 2 ya desde la definición de verdad matemática?
¿Qué diferencia hay si lo pruebo a partir de los Axiomas de Peano?
¿Los números de la teoría de Peano, son otros números distintos a los de la noción de verdad matemática recursiva, o son los mismos números que ahora se han ganado la lotería y tienen más privilegios?

18 Junio, 2009, 09:59 am
Respuesta #93

LauLuna

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

Gustavo no ha dicho, por lo que recuerdo, que el teorema de Gödel sea independiente de los axiomas aritméticos; creo que dijo que podemos definir la noción de verdad en el lenguaje formal sin necesidad de introducir los axiomas aritméticos, tal como él ha hecho.

Pero el teorema de Gödel sólo se aplica a sistemas que contienen la aritmética de Peano (o casi, este 'casi' puede hacerse preciso).

Por otra parte, hay que distinguir entre el razonamiento fuera del sistema y el razonamiento dentro del sistema. El cálculo de la verdad de un enunciado formal se ha planteado hasta ahora sólo fuera del sistema; Gustavo ha dicho en qué casos es verdadero un enunciado formal, no ha dicho que el sistema pueda computar el valor de verdad de los enunciados formales. Para calcular el valor de verdad ciertamente hay que dominar las operaciones aritméticas suma y producto (puedes representarte la función S como la operación de sumar 1) y hay que conocer el funcionamiento de las constantes lógicas, pero todo ese conocimiento se supone en nosotros, los que hacemos el cálculo, no en el sistema, que todavía no contaba siquiera con los axiomas aritméticos.

Entonces ciertamente suponemos conocimiento aritmético en nosotros antes de construir el sistema, pero si no fuera así ¿cómo podríamos nosotros dotar de axiomas aritméticos al sistema? Es el conocimiento más o menos intuitivo previo el que nos permite formalizar la aritmética en un conjunto axiomas. Lo que hacemos en esos axiomas es sólo expresar nuestra concepto de número natural.

Gustavo ¿es el momento de decir algo sobre el esquema de inducción, para decir precisamente que es un esquema y no un axioma?

18 Junio, 2009, 12:14 pm
Respuesta #94

Gustavo Piñeiro

  • Visitante
Repasemos:

1. Tenemos dos grupos de conceptos "dando vueltas": conceptos sintácticos y conceptos semánticos.

1.1. Los conceptos sintácticos son claros y precisos y dependen solamente de manipulaciones de signos que no toman en cuenta su significado. Entre los conceptos sintácticos destaco el de "enunciado demostrable" o "teorema".

Importante: que un enunciado sea demostrable (o no demostrable) depende (además de las reglas de inferencia, que suponemos fijadas: modus ponens y generalización) de los axiomas aritméticos que se elijan. Más concretamente: un enunciado que sea demostrable para un sistema de axiomas puede no serlo para otro. Ejemplo trivial: 1 + 1 = 4 no es demostrable a partir de los axiomas de Peano, pero sí a partir de un sistema inconsistente de axiomas.

Puse los axiomas de Peano a modo de ejemplo porque argentinator decía que "quería practicar algunas deducciones" y no puede haber deducciones (formales) sin axiomas. Y le propuse como "ejercicio" que mostrara que 1 + 1 = 2 es demostrable a partir de los axiomas de Peano. Ahora bien, podría suceder que 1 + 1 = 2 no fuera demostrable, si los axiomas elegidos fueran otros.

1.2. Los conceptos semánticos se basan esencialmente en el significado que se le atribuya a los signos. El único que hemos definido es el de "verdad", que depende de cuestiones más bien filosóficas como nuestra concepción del universo. El enunciado 1 + 1 = 2 es verdadero.

1 + 1 = 2 es siempre verdad, pero puede ser, o no, demostrable según qué sistema de axiomas aritméticos elijamos.

2. El principal objetivo del programa de Hilbert era elegir axiomas de tal modo que "demostrable" y "verdadero" fueran equivalentes. Que el escurridizo y difícil concepto de "verdad" (que involucra infinitos actuales) pudiera ser capturado por el más preciso y prístino de "demostrabilidad" (que sólo requiere infinitos potenciales y, por ende, podía ser aceptado por los intuicionistas).

3. Puse como ejemplo los axiomas de Peano porque es el sistema más usado (hay otros). El teorema de Gödel, tal como lo voy a enunciar, no se aplica solamente a sistemas que contengan los axiomas de Peano (aunque más o menos así lo enunció originalmente Gödel). El teorema de Gödel se aplica a todo sistema en el que los enunciados finitarios verdaderos sean demostrables. (Además de que el sistema debe ser omega-consistente.) (Por "finitario" entendemos "cuya verdad puieda verificarse mecánicamente en una cantidad finita de pasos".)

Gustavo ¿es el momento de decir algo sobre el esquema de inducción, para decir precisamente que es un esquema y no un axioma?

Ya lo has dicho. Los otros axiomas también pueden ser vistos como esquemas, todo depende de cómo los leamos: si en \( x + 0 = x \) leemos a \( x \) como una variable cualquiera entonces es un esquema, si la leemos como una variable específica entonces es un axioma.

Tal vez, argentinator, quieras practicar deduciendo que 1 + 1 = 2
¿Los números de la teoría de Peano, son otros números distintos a los de la noción de verdad matemática recursiva, o son los mismos úmeros que ahora se han ganado la lotería y tienen más privilegios?

Ya lo comenté más arriba, agrego ahora: los números son siempre los mismos números.

<<                >>

18 Junio, 2009, 12:50 pm
Respuesta #95

Gustavo Piñeiro

  • Visitante
Agrego un poco de confusión: 1 + 1 = 2 es siempre verdad, pero S0 + S0 = SS0 podría ser falso, todo depende de qué interpretación se le dé a los signos. Nosotros hemos fijado la interpretación usual en la que el símbolo 0 representa el número cero, S es "sucesor" y + es la suma, pero hay otras interpretaciones posibles.

18 Junio, 2009, 12:54 pm
Respuesta #96

Gustavo Piñeiro

  • Visitante
Un bonito ejercicio sería éste: de los axiomas de Peano tomemos solamente el 1 y el 2:

1. \( Sx = Sy \Rightarrow x = y \)
2. \( Sx\neq 0 \) (que es una abreviatura de \( -(Sx = 0) \))

El ejercicio pediría determinar si el enunciado 1 + 1 = 2 es un teorema, es decir, si S0 + S0 = SS0 es demostrable a partir de estos dos axiomas (más los axiomas lógicos, que implícitamente siempre se incluyen).

18 Junio, 2009, 01:08 pm
Respuesta #97

Gustavo Piñeiro

  • Visitante
Y agrego una pregunta más:

Si le damos a los signos un significado tal que S0 + S0 = SS0 es un enunciado falso ¿de todos modos sería un enunciado demostrable a partir de los axiomas de Peano? La respuesta es sí, ya que "ser demostrable" no depende del significado de los signos.

(Nota: si cambiamos el significado de los signos entonces habremos de cambiar la definición de verdad, pues la verdad depende del significado. Es posible asignar significados a los signos de tal modo que S0 + S0 = SS0 sea falso.)

<<                >>

18 Junio, 2009, 01:56 pm
Respuesta #98

argentinator

  • Consultar la FIRMAPEDIA
  • Administrador
  • Mensajes: 7,797
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
Bueno, gente. Todas estas explicaciones acerca de lo sintáctico y lo semántico han sido de lo más oportunas, porque no me daba cuenta que con la definición de verdad empezaba la distinción entre verdadero y demostrable. Me parecía todo parte de lo mismo.
Así que más que agradecido, porque no habría entendido nada de lo que se dijera después.
Ahora que está explicado resulta todo más evidente. Además, ya se había dicho creo que había que distinguir sintaxis de semántica, y que eso venía a ser distinguir demostrable de verdadero, pero por alguna extraña razón no podía ''verlo''. Estaba mareado con todas las definiciones.

Voy a intentar hacer algo, pero ando apurado y sospecho que va a estar mal. Igual ahí va:

A ver: supongamos que defino la propiedad de ser Gustavo-verdadero acorde a las reglas de verdad matemática que dio Gustavo en su momento, y que Gustavo-falso quiere decir falsedad matemática en el sentido que dio Gustavo.

Ahora defino la propiedad de ser  Banana-falso a toda expresión que sea Gustavo-falsa, y además a todas aquellas expresiones de la forma \( 1+t=St \) y \( t+1=St \) para cada término \( t \) que satisfaga \( t=1 \), \( t=2 \) o \( t=3 \).
En cualquier otro caso, decimos que una expresión es Banana-verdadera.

Si tomo la Banana-verdad como noción de Verdad estaría diciendo que 1+1 es falso pero demostrable.

Mi intención es hacer falsas las expresiones que involucran ciertos números pequeños, y a partir de allí en adelante, que todo siga siendo verdadero.
Pero no sé si voy bien encaminado. Mmm...


18 Junio, 2009, 02:57 pm
Respuesta #99

LauLuna

  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 546
  • País: es
  • Karma: +1/-0
  • Sexo: Masculino
Un bonito ejercicio sería éste: de los axiomas de Peano tomemos solamente el 1 y el 2:

1. \( Sx = Sy \Rightarrow x = y \)
2. \( Sx\neq 0 \) (que es una abreviatura de \( -(Sx = 0) \))

El ejercicio pediría determinar si el enunciado 1 + 1 = 2 es un teorema, es decir, si S0 + S0 = SS0 es demostrable a partir de estos dos axiomas (más los axiomas lógicos, que implícitamente siempre se incluyen).

Hombre, parece que sin los axiomas que regulan el signo + no podemos demostrar '1+1 = 2'.