06/12/2019, 07:37:42 pm *
Bienvenido(a), Visitante. Por favor, ingresa o regístrate.

Ingresar con nombre de usuario, contraseña y duración de la sesión
Noticias: Renovado el procedimiento de inserción de archivos GEOGEBRA en los mensajes.
 
 
Páginas: 1 [2] 3 4 ... 17   Ir Abajo
  Imprimir  
Autor Tema: Teorema de Gödel  (Leído 141472 veces)
0 Usuarios y 1 Visitante están viendo este tema.
argentinator
Consultar la FIRMAPEDIA __________________________________________________________________________________________________________________
Administrador
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Argentina Argentina

Mensajes: 7.282

Vean mis posts activos en mi página personal


Ver Perfil WWW
« Respuesta #20 : 08/06/2009, 12:09:33 am »

Gustavo tiene muy claro el asunto, incluso los detalles históricos, lo cual personalmente me resulta de gran provecho.
Así que aprovecho para agradecer tu aporte.

Aún así no tengo del todo claro qué es lo que estamos asumiendo como reglas de juego.
Lo único que saco en limpio hasta ahora es esto:

(1) Podemos asumir que la secuencia de los números naturales está presente en nuestro intelecto, y que ciertas propiedades básicas de ella pueden tomarse como intuitivamente válidas. En lo que a mí respecto, no hay nada intuitivamente válido, pero bueno... si es lo que hay.

(2) Disponemos de una lista de signos gráficos, digamos: [texx]1, \forall{},\exists{},\longrightarrow{},\wedge,\vee,=,(,),x,[/texx] y quizá dos o tres más, pero no más que esos.

(3) Podemos escribir los signos listados en (2) en orden, uno a la derecha del otro, de modo que podemos hacer corresponder a cada número natural ''intuitivo'' (y aún no construido en teoría de conjuntos alguna) un cierto signo. Por ejemplo, si escribo [texx]\wedge\vee1=\exists{})[/texx], estoy diciendo que hay un 1er signo que corresponde a [texx]\wedge[/texx], un 2do signo que sería el [texx]\vee[/texx], un 3er signo que sería el 1, un 4to signo que sería el =, y así sucesivamente.

(4) Los signos listados en (2) al colocarse ordenadamente como se explica en (3), pueden repetirse tantas veces como se desee. Así, por ejemplo, la secuencia [texx]\wedge\wedge(((1))11)=[/texx] que contiene varios signos repetidos, sería válida.

(5) Todo lo que se haga con estas herramientas debe permanecer ''bajo control'', o sea, no debe haber duda de que se llevarán a cabo pasos ''seguros'', que no den lugar a ambigüedad, duda, etc. Para lograr pasos ''seguros'' se procura trabajar con objetos que sean ''intuitivamente'' claros e inconfundibles.

Estas cuestiones intuitivas no me parecen tan obvias, sino todo lo contrario.
Hay unos indígenas australianos que cuentan 1, 2, 3 y muchos. No conocen otros números.
Ellos no manejan ''nuestra'' intuición de número natural. Difícilmente podrían seguir una sentencia ''finitaria'' con más de 3 signos, me parece.
Así que los números que conocemos están ''inculcados'' o ''aprendidos''. No son inherentes al ser humano. Aunque se puede asumir que son un objeto cultural... qué sé yo.

Lo intuitivo acarrea el problema de que no todos los seres humanos intuyen lo mismo, y es por eso que se buscan pruebas sólidas en la ciencia, para no dejarnos llevar por el engaño.
¿Cómo es que los matemáticos, entre ellos el gran formalista Hilbert, terminan diciendo que son ciertas percepciones intuitivas lo que se toma como base de demostraciones lógico-matemáticas seguras?
Incluso Hilbert, según he leído y comentado, criticaba a Pasch por usar la intuición de lo empírico en geometría en vez del razonamiento sintético, y criticaba a los intuicionistas también (es más, creo que él mismo los bautizó con ese nombre en forma algo despectiva).

Así que no queda más remedio que decir: ''Bueno, asumimos que todos los seres humanos tenemos esta intuición colectiva, llamémosla secuencia de números naturales 1, 2, 3, 4, etc., y que Dios nos ampare".

Así que, para no llevar el asunto por vías filosóficas ajenas a la prueba en sí, asumo estas cosas por ahora como válidas.

En todo caso, da toda la sensación de que Hilbert procuraba atenerse a ''intuiciones¨básicas", que fueran tan obvias y elementales que no habría lugar a discusión, y poder hablar entonces de una teoría de la demostración, una metamatemática.
Pero el concepto de ''finito'' no me parece algo tan básico como para incluirlo en ese esquema.

Sin recurrir a la teoría de conjuntos (que estamos tratando de evitar en todo esto porque en la metamatemática no hay ni lógica, ni conjuntos, ni nada), puedo asumir que entiendo intuitivamente el significado de ciertas cantidades pequeñas como 1, 2, 80, 1200, no sé, hasta cierto número ni muy chico ni muy grande, pero que sea manejable, ya sea porque tiene pocas cifras, o por lo que fuere. Puedo decir que ciertas listas de signos son ''finitas'' si puedo enumerarlas o contarlas, y su número es pequeño y está dentro de lo que considero manejable.
¿Pero puedo ir más allá, y hablar con toda generalidad de "todas las secuencias finitas de signos"?
Porque en ese caso, estoy asumiendo que mi intuición elemental entiende sin ambiguedad lo que significa finito.
Y también estoy asumiento que entiendo lo que significa ''todas las secuencias de signos".
¿No hay problemas o dudas al abarcar esa totalidad de secuencias?

Nota: estamos hablando de todas esas secuencias cuando pedimos por ejemplo que dado un enunciado cualquiera debe ser posible verificar mecánicamente en una cantidad finita de pasos si ese enunciado es, o no, un axioma.

Ahora bien, después de toda esta queja, que no sé qué tan en serio pueda tomarse, viene la peor parte, porque para ser honesto con todo el mundo, la verdad es que sí tengo una intuición clara de lo que significa una secuencia finita de signos, o una sucesión finita de pasos mecánicos, y de lo que significa hablar de ''todas esas secuencias'', etc.
Pero la experiencia con totalidades (como el imposible conjunto de todos los conjuntos) es lo que me obliga a dudar.
También está la cuestión de que uno puede definir finitud de maneras alternativas al mero "ser equipotente con los primeros n naturales, para algún n", y esas alternativas no tienen consecuencias claras (al menos para mí) en alguna teoría de conjuntos con axiomas más débiles que los usuales.

Y como estamos en el terreno de la ''carencia de axiomas'', o sea, es todo muy ''débil'', me asusta tener a mano ciertas posibilidades o herramientas "fuertes".

Pero bueno, para poder continuar parece que debemos asumir que:

(6) Se asume o se entiende intuitivamente claro y sin ambigüedad lo que significa una secuencia finita de signos, y una secuencia finita de pasos. Se entiende lo que es concatenar y repetir símbolos.

(7) No sólo se aceptan las convenciones de la (1) a la (6), sino que además se asume que, en cierta manera, todos estamos de acuerdo en lo que significan dichas convenciones. O sea, asumimos que hay un consenso intuitivo, convenciones de lenguaje y comprensión, etc.

Mmmmmm... Es todo cada vez más sospechoso, pero de algún punto debemos partir.
Y aunque quería mostrar mis dudas filosóficas sobre todo esto, no deseo llevar la discusión por ese lado, porque antes que nada quiero entender qué estamos asumiendo para probar el dichoso teorema.

Ahora bien. Gustavo, mencionaste lo de los "palotes" de Hilbert.
Pero creo que la prueba de Godel no viene en ese formato de palotes, ¿o sí?

Lo que entiendo de este asunto viene a ser como sigue (si hay errores, corríjanme):

(A) Partimos de trabajar con ciertos signos en forma ordenada, según se explica en los pasos (1) a (7) que mencioné antes.
Llamamos al contexto de trabajo: metamatemática.

(B) A una secuencia finita de signos dada se le llamará sentencia. No importa cómo esté formada, ni si parecen tener sentido o no, por ejemplo: [texx]=(\wedge\vee\longrightarrow{\longrightarrow{}})\wedge)[/texx]

Para no andar escribiendo cualquier cosa, habrá que elegir cuáles sentencias tendrán sentido para nosotros, y cuáles no.
Se elige un gran grupo de sentencias, y se dice que ellas forma un lenguaje L.
Lo más probable es que la cantidad de sentencias que figuran en L sea infinita (Aggh!!).
Así que, para mantenernos en terreno firme, exigimos que:

(C) Debe haber un método mecánico y claro por el cual, en una cantidad finita de pasos se puede determinar si una determinada sentencia S forma parte o no del lenguaje L.

(D) Se elige, de entre las sentencias del lenguaje L, una lista de sentencias, y se las bautiza como Axiomas. La lista dada puede ser finita o infinita (AUCH!).

Me molesta el hecho de que haya infinitos axiomas, porque se supone que para trabajar con ''pasos seguros'' como Hilbert pretendía, debemos quedarnos en el jardín de las cosas finitas. Sin embargo, por lo que sé, la matemática que conocemos no podría funcionar a toda su potencia con una lista finita de axiomas.
Sin embargo, existe una cosa llamada esquema axiomático, lo cual, en vez de dar un axioma, lo que hace es dar una regla de tal modo que toda sentencia que cumpla esa regla, será un axioma.

Esto me parece de por sí sospechoso, porque involucra una totalidad infinita.
Claro que, a lo mejor estoy teniendo demasiados prejuicios contra las totalidades infinitas.
A lo mejor mi conducta respecto a lo infinito es más bien de un temor supersticioso.

Pero es que... si hablo de un esquema axiomático, ya no estoy escribiendo una secuencia de signos, sino que estoy escribiendo una secuencia de meta-signos.
Un ejemplo de esquema axiomático sería escribir, por ejemplo, que:
para toda secuencia finita de signos, la cual simbolizamos momentáneamente por A, la sentencia [texx]A=(A)[/texx] será un axioma.
Así, generaríamos la lista de axiomas 1=(1), (x1xxx)=(x1xxx), (((1111)))=((((1111)))), y un largo e infinito etcétera.

La letra A en el esquema axiomático anterior no es uno de los signos permitidos según la lista del punto (2).
La letra A es sólo un signo ''informal'' dentro de nuestro lenguaje para comunicar a otros o a uno mismo, que cierta regla habrá de ser utilizada.
La letra A sería un meta-signo, y eso ya me empieza a perturbar bastante la paz, porque nada impediría que uno hable de meta-meta-signos, o de meta-meta-matemática. ¿Hasta dónde llega el asunto?

Tengo que creer en este punto que esos meta-signos se usan de un modo ''razonable y controlado'' por la meta-matemática, pero no me satisface que haya tanta libertad en ello.

De todos modos, aún siendo concientes de esto, podemos seguir adelante un poco más.

Para permitir ese tipo de situaciones que involucran esquemas axiomáticos, y mantenerse aún en una conducta ''finitaria'', se introduce una restricción que recibe el nombre de recursividad, que Gustavo menciona.
Así que, si bien la lista de axiomas no es finita,

(E) se puede, sin embargo, determinar en un número finito de pasos mecánicos si una determinada sentencia es un axioma o no es un axioma. (Definición de Recursividad)

Así que, en realidad, pareciera que no es muy importante aquello de los meta-signos. Uno podría despreocuparse de ellos, o del hecho de estar usando esquemas axiomáticos, siempre y cuando uno esté seguro de que puede determinar en un número finito de pasos si una sentencia es un axioma o no...
Aún así, ¿cómo probar que mi sistema de axiomas satisface esta propiedad, acaso comprobándolos uno a uno?
Claro que eso no se puede... y así veo de nuevo el fantasma de los infinitos y las totalidades por estos lugares, y la verdad es que me dan comezón.

Como sea, terminemos con el asunto.

(F) A una ''lista'' dada de axiomas como se especifica en (D) se la llama sistema axiomático.

(G) Se agrega al sistema axiomático una lista finita de reglas de inferencia, que son, hasta donde logro entender, reglas que especifican si una sentencia dada es un teorema o no es un teorema.
Esta clasificación entre teorema y no-teorema puede tener en principio una apariencia arbitraria. Sería lo mismo que clasificar en cocos y no-cocos.
Además, lo importante de dichas reglas no son tanto ellas mismas, sino que mediante un número finito de pasos mecánicos y perfectamente discernibles se puede determinar si cierta sentencia es o no es un teorema.

En cuanto a las reglas de inferencia, ¿qué rol juegan en todo esto? No son axiomas, no me parece que sean esquemas axiomáticos. ¿Son algo distinto? ¿Se dan en el metalenguaje, al estilo ''esquema''? ¿Cómo debo entenderlas?

Dado que en general no hay más que unas pocas reglas de inferencia, asumo que son finitas.

Por último, te pregunto Gustavo, ¿a qué les llamás exactamente sentencias finitarias?
¿Qué sería una sentencia no finitaria?
No comprendo si te estás refiriendo a ''afirmaciones'' como la de 2 + 3 = 5, que es una afirmación por sí sola, explícita,
o si acaso te estás refiriendo a ''esquemas de afirmaciones'' como una fórmula con meta-signos del tipo A + B = B + A.

Yo estuve usando el término ''sentencia'' como el de ristra ordenada de signos del punto (2), y no como fórmula escrita con meta-signos.

También puede que esté equivocado en el manejo que hago de la terminología de la teoría de modelos, que en realidad casi ni conozco.
¿Debo corregir algo en todo lo dicho?

Saludos
En línea

Numerarius
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 319


Ver Perfil
« Respuesta #21 : 08/06/2009, 01:00:00 pm »

Disculpad. Debido a un error, he duplicado mensajes. 
En línea

Numerarius
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 319


Ver Perfil
« Respuesta #22 : 08/06/2009, 01:01:05 pm »

Bueno. Tal como yo entiendo la demostración de Chaitin, venía a decir lo siguiente.

Algunos números reales son computables. Algunos reales, como Pi, pueden generarse mediante un programa finito. 

Ahora bien, un número real r es aleatorio  si, para generar las n primeras cifras de r, se necesita un programa de n líneas (o de un número próximo a n líneas). Esta idea de hecho, se remonta a Leibniz.  Mediante un método llamado interpolación lagrangiana, se puede demostrar que n puntos, siempre pertenecen a una curva. La idea de Chaitin (tomada de Leibniz) es que un número real (o, por ejemplo, una serie de enteros) son aleatorios si la ley que los genera es excesivamente complicada.

La teoría de Chaitin saca partdo también de una demostración de Turing. La demostración de Turing es más o menos así: el conjunto de las máquinas de Turing es enumerable. Por tanto, el conjunto de los números generables mediante una máquina de Turing es enumerable. Pero R es un conjunto no enumerable. Por tanto, la mayoría de números reales no son computables. 
En línea

Fernando Revilla
Administrador
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 10.548


Las matemáticas son demasiado humanas (Brouwer).


Ver Perfil WWW
« Respuesta #23 : 08/06/2009, 01:58:18 pm »

Existe una concatenación similar entre los números, al concatenar el 2 y el 3 obtenemos el número 23. En el libro damos una definición abstracta de la operación de concatenación (esencialmente que sea una operación isomorfa a la concatenación de símbolos) y vemos que ésta no es la única concatenación posible.

Antes de seguir, me gustaría saber si he interpretado correctamente lo anterior. Llamando [texx]N[/texx] al previsible modelo de la aritmética de primer orden [texx]\mathcal{N}[/texx] se definen las funciones de concatenación:

[texx]\begin{Bmatrix} C_2:N^2\rightarrow{N},\;C_2(n_1,n_2)=n_1n_2\\C_{k}:N^{k}\rightarrow{N},\;C_{k}(n_1,\ldots,n_{k})=C_2\left(C_{k-1}(n_1,\ldots,n_{k-1}),n_{k}\right)\mbox{ si}& k\geq{3}\end{matrix}[/texx]

Las relaciones [texx]k+1[/texx]-arias [texx]R_{k+1}(n_1,\ldots,n_k,n_{k+1})[/texx] a las que dan lugar las funciones de concatenación son recursivas y por tanto expresables en [texx]\mathcal{N}[/texx]. Esto estaría encaminado a dar una variante de la demostración del teorema de Gödel. ¿Es así?.

Saludos.
En línea

Numerarius
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
España España

Mensajes: 319


Ver Perfil
« Respuesta #24 : 08/06/2009, 02:07:14 pm »

Por cierto, el procedimiento que utilizó Gödel para transformar las proposiciones en números fue el siguiente.

Escribir una proposición es permutar una serie de símbolos en una serie de espacios. Bueno, los espacios se expresan mediante números primos (que hacen de base), y los símbolos mediante números que hacen de exponente.

El 2 es el primer lugar, el 3 el segundo, el 5 el tercero.

Y los símbolos pueden ser: "f" es 2 , "(" es 6, "x1" es 59, ")" es 8.

Así, "f(x1)" se expresa así: 2 ² · 3 ⁶ · 5⁵⁹ · 7⁸. 

(Esto es lo que se llama "Numeración de Gödel").
En línea

LauLuna
Pleno*
*****

Karma: +1/-0
Desconectado Desconectado

España España

Mensajes: 541


Ver Perfil WWW
« Respuesta #25 : 08/06/2009, 03:44:35 pm »

Gustavo, si no he entendido mal, cualquier numeración de Gödel usual (incluida la original de Gödel que reproduce Numerarius) da lugar a una concatenación. Lo esencial es que la descomposición en átomos sea unívoca, de manera que cada número de Gödel nos lleve en un número finito de pasos a la fórmula que representa.

Argentinator, no creo que sea razonable partir de que nada es intuitivamente evidente. Decir eso es contradictorio en sí mismo. Desde una posición de escepticismo radical ciertamente ni teoremas ni nada.

El programa de Hilbert para asegurar la consistencia de las matemáticas no era tan filosófico como para partir de una duda cartesiana total. Aceptaba como evidente casi todo lo que intuitivamente consideramos evidente en matemáticas, exceptuando ciertos conceptos demasiado abstractos y alejados de la representación sensible, como el concepto de cardinal transfinito, por ejemplo. La idea era la que transmite Gustavo Piñeiro: basarse en lo finitario, entendiendo lo finitario como aquello que puede comprobarse empíricamente en un número finito de pasos. La estructura de los naturales es muy simple, son simples palotes concatenados. Las fórmulas aritméticas sin cuantificadores, a las que a veces se llama 'fórmulas primas' (Kleene), como '3+2=5', pueden verificarse jugando con palotes. La idea es que "jugando con palotes" no vamos a producir jamás una paradoja. Yo diría que lo finitario puede interpretarse como lo computable, y que lo computable no nos va a llevar jamás a una paradoja.

Naturalmente en la metamatemática de Hilbert sí se utiliza la lógica y sí que se habla de conjuntos de fórmulas, pero procuramos no involucrar conjuntos demasiado grandes o abstractos, nos quedamos dentro de lo computable.

Un detalle técnico: no toda ristra de símbolos de un lenguaje formal es una sentencia. Algunas de esas ristras son 'fórmulas bien formadas', por ejemplo ' 0+x=y', otras no, por ejemplo, '++=+' (el concepto se especifica mediante reglas computables); y dentro de las fórmulas bien formadas llamamos sentencias (o 'fórmulas bien formadas cerradas') a aquellas que no contienen variables libres, es decir, variables que quedan fuera del alcance de todo cuantificador. Antes era más frecuente permitir que los sistemas formales manipulasen fórmulas abiertas; ahora se tiende más a hacer que trabajen sólo con sentencias.

Oye, Argentinator, en cuanto a eso que te preocupa de los australianos (creo que en realidad se trata de los indios piraha, en Brasil, aunque puede haber más de un caso) yo lo plantearía así: todo ser racional tiene en potencia la capacidad de desarrollar la estructura de los números naturales, ésta es inherente a la razón; pero esa capacidad puede quedar en potencia durante mucho tiempo igual que la capacidad de desarrollar las geometrías no euclídeas. En uno y otro caso se trata de construcciones racionales sobre las que es posible demostrar verdades de forma rigurosa. Los seres racionales nacemos con la capacidad de desarrollarlas pero no nacemos ya sabiéndolas, igual que nacemos con la capacidad de desarrollar dientes pero nacemos sin dientes.

Sugiero que para aclarar a qué tipos de sistemas nos estamos refiriendo, como pide Argentinator, alguien proponga un ejemplo concreto de sistema formal axiomático al que se aplique el teorema de Gödel. Lo más natural sería exponer una versión de la aritmética de Peano de primer orden. Sugiero que lo haga Gustavo Piñeiro, ya que probablemente tendrá su versión preferida, por ejemplo, la que utilice en su libro.

Un saludo.
En línea
argentinator
Consultar la FIRMAPEDIA __________________________________________________________________________________________________________________
Administrador
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Argentina Argentina

Mensajes: 7.282

Vean mis posts activos en mi página personal


Ver Perfil WWW
« Respuesta #26 : 08/06/2009, 04:44:31 pm »

LauLuna, espero no haberte hecho enojar.

Puede ser que dudar de todo no sea sano.
Incluso, dudar de todo no sirve para entender el Teorema de Godel.
Pero son dudas que me asaltan constantemente mientras estoy leyendo pruebas sobre la metamatemática.
Y si bien desde algún lugar hay que partir, no creo que olvidarse de las dudas sea lo correcto.
Por ahora puedo olvidarme por un rato de todas esas dudas, pero resulta que también estoy tratando de comprender cuál es el universo del discurso donde se debate el Teorema de Godel.
Como no estoy del todo familiarizado o acostumbrado a la teoría de modelos, necesito comprender cuáles son las reglas de juego, qué cosas se están tomando como punto de partida, qué se acepta y qué no se acepta.
¿De dónde tengo que arrancar? ¿Qué reglas o ideas puedo usar?
Además al poco rato todo se complica. ¿Cómo sé que estoy respetando lo ''finitario'' a cada paso?

Y en cuanto a aceptar la intuición de los números naturales de entrada, creo que hay que aclararlo también, porque no todo el mundo está de acuerdo en este punto.
¿Qué intuición de número natural tengo que usar? Los intuicionistas tienen su versión más restringida a la hora de aceptar lo que es un número. ¿Tengo que usar la versión de ellos o la versión formalista que se me ha enseñado a lo largo de mi vida?  :llorando:

En todo caso no voy a seguir con estos dilemas filosóficos porque ya me cansa hasta a mí mismo, pero pienso que buena parte de mis dudas son legítimas, y que tengo el deber de tenerlas presentes.  :avergonzado:

En el futuro trataré de centrarme en la prueba misma, aunque no me crea ninguno de los pasos que esté haciendo.  :cara_de_queso:
En línea

Gustavo Piñeiro
Visitante
« Respuesta #27 : 08/06/2009, 10:49:13 pm »

Hola!

Permítanme comentar algunas cuestiones de los últimos mensajes.

1. Phidias: Lo has interpretado bien.

2. Argentinator:

2.1. Acerca de los conjuntos infinitos: existe un diferencia crucial entre lo que se llama el infinito potencial y el infinito actual. Una cantidad es potencialmente infinita cuando se acepta que puede crecer sin cota, pero nunca deja de ser finita. El infinito en potencia da la idea de un proceso de crecimiento que nunca se detiene, pero nunca llega a ser "en acto" infinito.

Una totalidad es infinita en acto cuando se asume que existen "ya", "ahora", "al mismo tiempo" todos sus infinitos elementos.

Las paradojas de la teoría de conjuntos surgen al introducir (sin el debido cuidado) totalidades infinitas en acto (el conjunto de todos los conjuntos, etc.)

Las secuencias de símbolos de un lenguaje formal son un conjunto infinito en potencia, no en acto. Asumimos que podemos generar tantas secuencias como queramos de la longitud que queramos, pero siempre será una cantidad finita (aunque creciente) de secuencias de una longitud finita (aunque creciente).

De hecho, la admisión de totalidades actualmente infinitas invalida el teorema de Gödel. Por ejemplo, si se admitiera la siguiente regla de inferencia (no finitaria):

De los infinitos (en acto) enunciados: [texx]P(0)[/texx], [texx]P(1)[/texx], [texx]P(2)[/texx],... se deduce [texx]\forall{x}P(x)[/texx]

entonces el teorema de Gödel sería falso (existiría un sistema recursivo y completo de axiomas para la aritmética).   

2.2. El sistema de axiomas debe ser recursivo, es decir, debe existir un algoritmo que determine en una cantidad finita de pasos si un enunciado propuesto es un axioma, o si no lo es. Pero ¿cómo verificamos que el sistema de axiomas cumple esta propiedad? En realidad, lo que sucede no es que se da el sistema de axiomas por un lado y el algoritmo por el otro, sino que el sistema de axiomas se define mediante el algoritmo que reconoce sus enuncados (no definimos tanto "conjuntos de axiomas" como "algoritmos que reconocen axiomas").

En general, los axiomas se dan mediante una cantidad finita de esquemas. El algoritmo implícito es: dado un enunciado verifique si corresponde a alguno de estos esquemas.

2.3. Una aclaración técnica: una consecuencia de que el sistema de axiomas sea recursivo es que existe un algoritmo que, dada una secuencia de enunciados, determina en una cantidad finita de pasos si esa secuencia es, o no es, una demostración. Sin embargo, esto no significa que exista un algoritmo que determine si un enunciado es, o no es, un teorema. De hecho, Church demostró que si se toman los axiomas de Peano entonces un tal algoritmo no existe.

3. LauLuna: De acuerdo con dar un sistema formal, pero lo haré en otro mensaje para que éste no resulte demasiado extenso.

Saludos a todos!


<<                >>
En línea
Gustavo Piñeiro
Visitante
« Respuesta #28 : 08/06/2009, 11:13:05 pm »

Para definir un sistema formal debemos comenzar por definir los símbolos del lenguaje. El lenguaje tendrá:

1. Símbolos lógicos: [texx]\exists{}[/texx], [texx]\Rightarrow{}[/texx], [texx]-[/texx], [texx]=[/texx].
(El [texx]-[/texx] es el símbolo de negación. El [texx]=[/texx] no siempre se incluye entre los símbolos lógicos, pero en este caso sí lo haremos.)

2. Variables: [texx]x_1[/texx], [texx]x_2[/texx], [texx]x_3[/texx],...
(veremos después que estas variables pueden escribirse usando solamente dos símbolos básicos.)

3. Constante: una sola constante, [texx]0[/texx].

4. Símbolos de funciones: [texx]S[/texx], [texx]+[/texx], [texx]\cdot{}[/texx].
(El uso de la palabra "función" es sólo para darle un nombre común a estos símbolos, no es necesario saber qué es una "función".)

5. Signos de puntuación: [texx]([/texx], [texx])[/texx]

Llamamos expresión a cualquier secuencia finita de símbolos.

Un término se define del siguiente modo:

1. Las variables y la constante son términos.
2. Si [texx]s[/texx] y [texx]t[/texx] son términos entonces [texx](s + t)[/texx], [texx](s\cdot{}t)[/texx] y [texx]S(t)[/texx] son términos.
3. Todo término se obtiene por aplicaciones sucesivas (una cantidad finita de veces) de las reglas anteriores.

(En relación con el comentario anterior sobre el infinito potencial y el infinito actual, nótese que no hablamos del conjunto de todos los términos sino de una construcción paso a paso.)
(A veces, para aliviar la notación, se omiten paréntesis innecesarios y se escribe [texx]s\cdot{}t[/texx] en lugar de [texx](s\cdot{}t)[/texx].)

Una fórmula se define del siguiente modo:

1. Si [texx]s[/texx] y [texx]t[/texx] son términos entonces [texx]s=t[/texx] es una fórmula.
2. Si [texx]F[/texx] es una fórmula y [texx]x_i[/texx] es una variable entonces [texx]\exists{x_i}F[/texx] es una fórmula.
3. Si [texx]F[/texx] y [texx]G[/texx] son fórmulas entonces [texx]-F[/texx] y [texx](F\Rightarrow{}G)[/texx] son fórmulas.
4. Toda fórmula se obtiene por aplicaciones sucesivas (una cantidad finita de veces) de las reglas anteriores.

Definición: decimos que la variable [texx]x_i[/texx] tiene una aparición libre en la fórmula [texx]F[/texx] si esa aparición no está afectada por el cuantificador [texx]\exists{}[/texx] (es decir, si no está precedida por un [texx]\exists{x_i}[/texx]. En principio omito aquí la definición formal del concepto de variable libre.)

Definición: un enunciado es una fórmula en la que ninguna variable tiene apariciones libres (en particular esto sucede si la fórmula no tiene variables).

Para no extenderme demasiado seguiré en otro mensaje.

Saludos!
En línea
Gustavo Piñeiro
Visitante
« Respuesta #29 : 08/06/2009, 11:36:38 pm »

Gustavo, si no he entendido mal, cualquier numeración de Gödel usual (incluida la original de Gödel que reproduce Numerarius) da lugar a una concatenación. Lo esencial es que la descomposición en átomos sea unívoca, de manera que cada número de Gödel nos lleve en un número finito de pasos a la fórmula que representa.

Exactamente, es así. Destaco lo de "numeración de Gödel usual" pues es posible generalizar el concepto de numeración de Gödel de modo tal que no todas ellas provienen de una concatenación.

<<                >>
En línea
argentinator
Consultar la FIRMAPEDIA __________________________________________________________________________________________________________________
Administrador
Pleno*
*****

Karma: +0/-0
Desconectado Desconectado

Sexo: Masculino
Argentina Argentina

Mensajes: 7.282

Vean mis posts activos en mi página personal


Ver Perfil WWW
« Respuesta #30 : 09/06/2009, 12:37:54 am »

Gracias Gustavo por las aclaraciones.
Lo de los infinitos potenciales y actuales me es conocido, y ya me daba cuenta que el infinito que se procura usar es el ''potencial''.
Pero la cuestión es que, en tal caso, cuando se usa una expresión del metalenguaje como por ejemplo 'n|' para indicar que se deben repetir n palotes |||||||||, ese n es un número natural, y no me queda muy claro qué clase de aritmética hay que usar ahí. Ya empiezo a dudar acerca de si puedo usar expresiones como m+n palotes, o dado un número n de palotes, descomponer n en sus factores primos y luego por cada factor primo armar alguna expresión lógica que bla bla...
La aparición del infinito ''actual'' estaría en expresiones como ''P implica Q'' donde P y Q pueden ser fórmulas cualesquiera.
El número total de expresiones que puedo poner en los lugares de P y Q son infinitas.
También puede ser que tenga una fobia exagerada contra el infinito.

Otro lugar donde veo el infinito actual es en la ''memoria de la computadora que escribe sentencias''.
Si yo puedo escribir una sentencia de tamaño tan grande como yo quiera, es que tengo memoria suficiente en algún lugar para ''almacenar'' todos esos signos que las forman. Esos lugares quizá ya están presentes intuitivamente en la mente, así como lo está la secuencia de números naturales. Aunque ahora también podría pensar, si quiero, que la ''memoria'' no es algo con una cantidad ''fija'' de ''celdas'', sino que es algo ''ampliable según la necesidad''. En fin...

Pero no quiero cansar más con esto.

Ya que has definido los términos, fórmulas, y todos los elementos del teorema, sería bueno comenzar a discutir la prueba.
Encontré algo así como un ejercicio sobre consistencia de la lógica, en un libro sobre Godel, y que quizá exponga en un próximo post.
En línea

Gustavo Piñeiro
Visitante
« Respuesta #31 : 09/06/2009, 02:31:03 pm »

Lo de los infinitos potenciales y actuales me es conocido, y ya me daba cuenta que el infinito que se procura usar es el ''potencial''.
Pero la cuestión es que, en tal caso, cuando se usa una expresión del metalenguaje como por ejemplo 'n|' para indicar que se deben repetir n palotes |||||||||, ese n es un número natural, y no me queda muy claro qué clase de aritmética hay que usar ahí. Ya empiezo a dudar acerca de si puedo usar expresiones como m+n palotes, o dado un número n de palotes, descomponer n en sus factores primos y luego por cada factor primo armar alguna expresión lógica que bla bla...
La aparición del infinito ''actual'' estaría en expresiones como ''P implica Q'' donde P y Q pueden ser fórmulas cualesquiera.
El número total de expresiones que puedo poner en los lugares de P y Q son infinitas.

Hola,

En realidad, en la definición del lenguaje formal nunca se habla de "n palotes" de modo que no se necesita ninguna aritmética previa. Por otra parte, la definición de fórmula debe entenderse como una construcción jerarquizada: en ''P implica Q'', P y Q no son cualesquiera, sino fórmulas construidas en pasos previos.

Acerca de la memoria de la computadora, en efecto se va ampliando según sea necesario. Nunca se supone (ni es necesario suponer) que sea infinta en acto. En general eso sucede con todos los elementos del lenguaje formal: por ejemplo, la variables se agregan a medida que son necesarias, nunca es necesario suponer que todas las variables existen "en acto" a la vez.

Saludos!
En línea
LauLuna
Pleno*
*****

Karma: +1/-0
Desconectado Desconectado

España España

Mensajes: 541


Ver Perfil WWW
« Respuesta #32 : 09/06/2009, 04:59:59 pm »

LauLuna, espero no haberte hecho enojar.

¡En absoluto!
En línea
Gustavo Piñeiro
Visitante
« Respuesta #33 : 10/06/2009, 12:01:34 pm »

Hola,

Algunas cuestiones más acerca de la definición del lenguaje formal. En primer lugar, para que la lectura de las fórmulas no se haga humanamente imposible aceptaremos algunas abreviaturas. Ya mencioné antes que usaremos sólo los paréntesis necesarios. Por ejemplo, si siguiéramos al pie de la letra las definiciones deberíamos escribir:

((S(0) + S(S(0))) + S(0))

En lugar de eso escribiremos simplemente:

(S0 + S0) + S0

Usaremos también las siguientes abreviaturas, usuales en lógica:
 
Si [texx]F[/texx] es una fórmula entonces [texx]\forall{x_i}F[/texx] será la abreviatura de [texx]-\exists{x_i}-F[/texx].
Si [texx]F[/texx] y [texx]G[/texx] son fórmulas entonces [texx]F\wedge G[/texx] será una abreviatura de [texx]-(F\Rightarrow{} -G)[/texx].
Si [texx]F[/texx] y [texx]G[/texx] son fórmulas entonces [texx]F\vee G[/texx] será una abreviatura de [texx](-F\Rightarrow{} G)[/texx].

Muchas veces a las variables, en lugar de llamarlas [texx]x_1[/texx], [texx]x_2[/texx], etc. las llamaremos [texx]x[/texx], [texx]y[/texx], etc.

Finalmente, agregamos al lenguaje un símbolo especial, digamos [texx]\otimes{} [/texx], que servirá para escribir sucesiones de fórmulas. Formalmente definimos:

1. Si [texx]F[/texx] es una fórmula entonces [texx]\otimes{} [/texx]F[texx]\otimes{} [/texx] es una sucesión de fórmulas.
2. Si [texx]S[/texx] es una sucesión de fórmulas y [texx]G[/texx] es una fórmula entonces [texx]SG\otimes{}[/texx] es una fórmula.
3. Toda sucesión de fórmulas se obtiene por aplicaciones sucesivas de las reglas anteriores.

Axiomas lógicos:

Por definición, un axioma lógico es cualquier fórmula que se obtenga de los esquemas siguientes. (Como ya dije en otro mensaje, estos esquemas definen en realidad un algoritmo que permite reconocer, dada una fórmula, si ésta es, o no, un axioma lógico.)

1. [texx]F\Rightarrow{}(G\Rightarrow{}F)[/texx], donde [texx]F[/texx] y [texx]G[/texx] son fórmuas cualesquiera.

2. [texx]F\Rightarrow{}(G\Rightarrow{}H)\Rightarrow{}((F\Rightarrow{}G)\Rightarrow{}(F\Rightarrow{}H))[/texx], donde [texx]F[/texx], [texx]G[/texx] y [texx]H[/texx] son fórmuas cualesquiera.

3. [texx](-F\Rightarrow{}-G)\Rightarrow{}(G\Rightarrow{}F)[/texx], donde [texx]F[/texx] y [texx]G[/texx] son fórmuas cualesquiera.

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

5. [texx]\forall{x}(F\Rightarrow{}G)\Rightarrow{}(F\Rightarrow{}\forall{x}G)[/texx] siempre que [texx]x[/texx] no aparezca libre en [texx]F[/texx].

6. [texx]x = x[/texx], donde [texx]x[/texx] es una variable cualquiera.

7. [texx]x = y \Rightarrow{} y = x[/texx], donde [texx]x[/texx] e [texx]y[/texx] son variables cualesquiera.

8. [texx]x = y \Rightarrow{} (y = z\Rightarrow{} x = z)[/texx]

9. [texx]x = y \Rightarrow{} t(z_1, z_2,\ldots z_{k-1},x,z_{k+1}\ldots z_n) = t(z_1, z_2,\ldots z_{k-1},y,z_{k+1}\ldots z_n)[/texx], donde [texx]t[/texx] es un término cualquiera.

10. [texx]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)[/texx], donde [texx]F[/texx] es una fórmula cualquiera.

Los axiomas 9 y 10 dicen esencialmente que si [texx]x=y[/texx] entonces podemos reemplazar libremente [texx]x[/texx] por [texx]y[/texx].

Los esquemas del 1 al 5 son los axiomas de la lógica primer orden, al agregar los otros se obtiene la lógica de primer orden con igualdad. Éste es el sistema de axiomas que se usa en Gödel [texx]\forall{}[/texx], hay otros sistemas posibles. De hecho, para facilitar ciertas demostraciones, en el sistema hemos puesto más axiomas de los que realmente son necesarios. Por ejemplo, las fórmulas que corresponden al esquema 8 pueden deducirse de las demás y por lo tanto no es necesario (aunque tampoco es erróneo) incluirlos.

En otro mensaje tocará hablar de las reglas de inferencia.

Saludos!

<<                >>
En línea
LauLuna
Pleno*
*****

Karma: +1/-0
Desconectado Desconectado

España España

Mensajes: 541


Ver Perfil WWW
« Respuesta #34 : 10/06/2009, 04:33:07 pm »

Gustavo,

me pregunto si en los axiomas lógicos para la igualdad 6-10 en lugar de usar metavariables para variables no deberíamos usar metavariables para términos cualesquiera.

Un saludo.
En línea
Gustavo Piñeiro
Visitante
« Respuesta #35 : 10/06/2009, 07:44:25 pm »

me pregunto si en los axiomas lógicos para la igualdad 6-10 en lugar de usar metavariables para variables no deberíamos usar metavariables para términos cualesquiera.

Hola,

Sí, podrían usarse metavriables para términos cualesquiera. Puede probarse (gracias al esquema 9) que si el esquema 10 vale para variables entonces vale también para términos. Pero todo es cuestión de gustos y conveniencia, así como pusimos el esquema 8 (que en realidad es innecesario ya que se deduce de los otros), de la misma forma podríamos haber puesto metavariables que fueran términos.

Saludos,

Gustavo

<<                >>
En línea
LauLuna
Pleno*
*****

Karma: +1/-0
Desconectado Desconectado

España España

Mensajes: 541


Ver Perfil WWW
« Respuesta #36 : 11/06/2009, 10:03:18 am »

Sí, podrían usarse metavriables para términos cualesquiera. Puede probarse (gracias al esquema 9) que si el esquema 10 vale para variables entonces vale también para términos. Pero todo es cuestión de gustos y conveniencia, así como pusimos el esquema 8 (que en realidad es innecesario ya que se deduce de los otros), de la misma forma podríamos haber puesto metavariables que fueran términos.

En realidad es que depende de la reglas de inferencia. Si vas a incluir la de la Generalización (como es usual), entonces esa regla te permite pasar de las variables a otros términos. Por ejemplo, desde

'x=x'

a

'(para todo x) x=x'

y de ahí a

'0=0'

'S0=S0'

etc.

Lo cierto es que yo estoy más acostumbrado a trabajar con sistemas que sólo usan fórmulas cerradas y por eso no me había dado cuenta de que, probablemente, en el sistema que estás proponiendo bastan las metavariables de variable.

Un saludo.
En línea
Gustavo Piñeiro
Visitante
« Respuesta #37 : 11/06/2009, 10:55:36 pm »

En realidad es que depende de la reglas de inferencia. Si vas a incluir la de la Generalización (como es usual), entonces esa regla te permite pasar de las variables a otros términos.

En efecto, es exactamente así, todo depende de las reglas de inferencia. En nuestro sistema formal usaremos dos reglas de inferencia: (En todo lo que sigue [texx]P[/texx] y [texx]Q[/texx] son fórmulas.)

a) Modus ponens: De [texx]P[/texx] y de [texx]P\Rightarrow Q[/texx] se deduce [texx]Q[/texx].
b) Generalización: De [texx]P[/texx] se deduce [texx]\forall{x}P[/texx], donde [texx]x[/texx] es una variable cualquiera.

Una pregunta que puede surgir es: ¿Por qué las reglas de inferencia se toman aparte de los axiomas? ¿No son axiomas acaso? ¿La regla de generalización no puede escribirse como [texx]P\Rightarrow \forall{x}P[/texx]?   

En principio, la diferencia es que:
a) Un axioma es una fórmula.
b) Una regla de inferencia puede verse como una operación que, dadas ciertas fórmulas, permite generar una fórmula nueva.

Una demostración (veremos en breve) es una sucesión de fórmulas en la que cada una de ellas es, o bien un axioma, o bien es generada por fórmulas anteriores por aplicación de estas operaciones llamadas "reglas de inferencia".

La posible confusión entre axiomas y reglas de inferencia puede provenir de leer las fórmulas apegándose a la interpretación de los símbolos. Cuando leemos [texx]P\Rightarrow (Q\Rightarrow P)[/texx] (axioma 1), solemos entender que el axioma dice: "De [texx]P[/texx] puede deducirse [texx]Q\Rightarrow P[/texx]" o "Si [texx]P[/texx] es verdadera entonces [texx]Q\Rightarrow P[/texx] también lo es". En efecto ésa lectura es la que nos permite entender qué dice el axioma y la que nos convence de que es correcto, pero, en el contexto del programa de Hilbert (que es el contexto en el que se da la definición de demostración que mencioné más arriba) la lectura "correcta" de [texx]P\Rightarrow (Q\Rightarrow P)[/texx] es:

"P flecha paréntesis Q flecha P paréntesis"

Solamente se trabaja a nivel sintáctico, sin interpretar los símbolos. Las reglas de inferencia nos dicen cómo combinar los símbolos para generar nuevas fórmulas.

Creo que sería más claro si en los axiomas en lugar de [texx]\Rightarrow [/texx] se usara, por ejemplo, el símbolo [texx]*[/texx].

De este modo el axioma 1 sería: [texx]P*(Q*P)[/texx]
Otro axioma sería [texx](-P*-Q)*(Q*P)[/texx]

Y el modus ponens diría que si en una demostración aparece [texx]P[/texx] y [texx]P*Q[/texx] entonces podemos agregar más adelante la fórmula [texx]Q[/texx].

Dicho sea de paso, si se agregan como axiomas todas las fórmulas del tipo [texx]P\Rightarrow \forall{x}P[/texx], donde [texx]P[/texx] es una fórmula cualquiera y [texx]x[/texx] es una variable cualquiera, entonces puede usarse el modus ponens como única regla de inferencia.

<<                >>
En línea
LauLuna
Pleno*
*****

Karma: +1/-0
Desconectado Desconectado

España España

Mensajes: 541


Ver Perfil WWW
« Respuesta #38 : 12/06/2009, 08:05:47 am »

Gustavo, permíteme que plantee una cuestión sobre la regla de Generalización.

Así a primera vista parece un tanto arbitraria porque da la impresión de que permite afirmar de todo x lo que antes no habíamos podido afirmar más que de algún término concreto. Por ejemplo, imagina que yo llego a la fórmula

(1)   '0+x = SSS0'

No parece lógico que de ahí pueda pasar a

(2)   '(para todo x) 0+x = SSS0'

De hecho, (2) es falsa en la interpretación estándar de este lenguaje, y desde luego no es un teorema de la aritmética de Peano. Se deduce en seguida que (1) no es un teorema de la aritmética, pero uno se queda pensando cómo garantizan los axiomas y las reglas de inferencia que nunca se vaya a obtener un teorema como (1), es decir, un teorema que junto con Generalización echaría por tierra la consistencia o la corrección de nuestro sistema.

Otra forma de plantear esto es la siguiente. En la lógica pura de primer orden hay una regla semejante a Generalización. La podemos llamar 'introducción del cuantificador universal' (IU), que permite pasar de

'P(t)'

a

'(para todo x) P(x)'.

Pero IU está sometida a restricciones que nos garantizan que 't' representa a un objeto cualquiera o a un objeto arbitrario, de modo que podemos afirmar de todos los objetos aquello que podemos afirmar del objeto designado por 't'. En el sistema que propones, en cambio, Generalización no está sometida a restricción alguna. ¿Qué hay en el sistema que nos garantice que esas restricciones no son necesarias?

Un saludo.
 
En línea
Gustavo Piñeiro
Visitante
« Respuesta #39 : 12/06/2009, 08:34:50 am »

Gustavo, permíteme que plantee una cuestión sobre la regla de Generalización.

Así a primera vista parece un tanto arbitraria porque da la impresión de que permite afirmar de todo x lo que antes no habíamos podido afirmar más que de algún término concreto. Por ejemplo, imagina que yo llego a la fórmula

(1)   '0+x = SSS0'

Hola,

Es que nunca llegarías a demostrar la fórmula '0+x = SSS0' (si como axiomas tomas fórmulas que sean verdaderas para la interpretación usual). Cuando definamos la noción de "verdad" veremos que esta definición se aplica tanto a enunciados como a fórmulas con variables libres y que en este último caso dice que [texx]P(x)[/texx] es verdadera si y sólo si [texx]\forall{x}P(x)[/texx] es verdadera.

Esta definición está en línea con el uso habitual del lenguaje matemático. Cuando queremos decir en lenguaje simbólico que la suma es conmutativa habitualmente escribimos [texx]x + y = y + x[/texx] y muy rara vez [texx]\forall{x}\forall{y}(x + y = y + x)[/texx].

De hecho, en el esquema lógico 6 puse [texx]x = x[/texx] y quedó sobreentendido que esto equivalía a [texx]\forall{x}(x = x)[/texx].

Saludos,

Gustavo

<<                >>
En línea
Páginas: 1 [2] 3 4 ... 17   Ir Arriba
  Imprimir  
 
Ir a:  

Impulsado por MySQL Impulsado por PHP Powered by SMF 1.1.4 | SMF © 2006, Simple Machines LLC XHTML 1.0 válido! CSS válido!