Autor Tema: Sobre la consistencia de la aritmética

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

24 Agosto, 2013, 12:00 am
Leído 7983 veces

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Hace unos días unos mensajes privados entre argentinator y yo derivaron en un diálogo sobre la consistencia de la aritmética, y como considero que podrían interesar a más gente los publico (con su consentimiento) en este hilo (en el que, por supuesto, cualquiera puede participar).

Cita de: argentinator
Ya que hay siempre una aparente separación entre lo sintáctico y lo semántico, sería interesante una teoría que mezcle de algún modo ambas cosas.

Bueno, yo diría más bien que la separación entre lo sintáctico y lo semántico consiste en que la sintaxis es independiente de la semántica y que, al estudiar la semántica, lo que se hace realmente es mezclar la sintaxis con la semántica.

De todos modos, a ver si esto que te voy a decir te parece suficientemente "nuevo":

Creo que has llegado a aceptar que para fundamentar la lógica es necesario trabajar informalmente con números naturales, pero tu pregunta entonces siempre ha sido: ¿qué necesitamos suponer que cumplen exactamente esos números naturales metamatemáticos? Y yo siempre te he venido a decir algo así como "lo que haga falta, con tal de que esté intuitivamente justificado". A ver si te gusta más esta respuesta "nueva":

Es posible desarrollar toda la metamatemática necesaria, digamos, para definir el lenguaje formal de ZFC, lo que es una fórmula de ZFC y lo que es una demostración en ZFC (vamos, lo necesario para abandonar la metamatemática y pasar a trabajar en ZFC) sin suponer nada más que la existencia de los números naturales metamatemáticos, con su cero, su operación siguiente, su suma y su producto, y sin suponer de ellos nada más que los axiomas de Peano de primer orden. Más concretamente: un número finito de axiomas de Peano de primer orden (teniendo en cuenta que hay infinitos axiomas de inducción).

Preciso más aún mi respuesta:

Es posible definir el lenguaje formal de ZFC entendiendo que los "signos" no son garabatitos en un papel, sino que son ciertos números naturales (definimos \( \forall \) como el número 4, definimos \( + \) como el número 15, etc.) entendiendo que las cadenas finitas de signos no son "cadenas finitas" sobrentendiendo un concepto "dudoso" de finitud, sino que son números naturales definidos con aritméticamente, entendiendo que los axiomas de ZFC son también un conjunto de números naturales definido aritméticamente y que el concepto de "tal fórmula es un teorema de ZFC" se define aritméticamente igual que uno puede definir "tal número es primo".

En todo ese proceso, lo único que hace falta suponer de los números naturales para justificar que las definiciones tienen sentido, que los objetos definidos existen realmente, etc. es suponer que cumplen un número finito de axiomas de Peano.

Para ser exacto y que no puedas decir que me guardo ases en la manga. Lo que te digo es que es teóricamente posible (aunque tal nivel de detalle sería tedioso) decir:

Acéptame que existen unos objetos que llamaremos números naturales y que cumplen lo siguiente:

1) (La interpretación metamatemática de) los axiomas lógicos. Por ejemplo,  cualquier fórmula de tipo \( p\rightarrow (q\rightarrow p) \) es un axioma lógico, luego lo que te pido que me aceptes es que siempre que te haga una afirmación del tipo "si x es primo, entonces (si y es par es que x es primo)" no me la cuestionarás, y lo mismo para los otros cinco esquemas de axiomas lógicos según el cálculo deductivo que conté en mi artículo de lógica de primer orden.

2) Una cantidad finita de axiomas de Peano, donde aquí no estoy presuponiendo un concepto de finitud, sino que me refiero a que te diría: "Acéptame este axioma, y éste, y éste, y éste...  y éste", donde los seis primeros "éstes" serían los seis axiomas de Peano de primer orden que no son el principio de inducción (incluyendo los que definen la suma y el producto) y luego habría unos cuantos "éstes" más que corresponderían a casos particulares del principio de inducción.

Y acéptame las dos reglas de inferencia lógicas, el modus ponens y la generalización. Vamos, que si te demuestro \( p \) y te demuestro \( p\rightarrow q \), me tienes que aceptar \( q \) sin rechistar.

Afirmo que sin más que aceptar lo que acabo de decir (que se podría concretar todo lo necesario) es posible construir ZFC, en el sentido de definir con todo rigor (en el sentido de no decir nada que no esté justificado por los axiomas metamatemáticos enumerados antes y por las reglas de inferencia) lo que es demostrar un teorema en ZFC. (Entendiendo que los teoremas, al igual que las demostraciones, serían números convenientemente definidos, pero eso es un truco habitual: del mismo modo que al trabajar en ZFC se pueden definir números y ecuaciones y triángulos, pero todo son oficialmente conjuntos, es posible trabajar en la aritmética de Peano y definir fórmulas y teoremas de modo que todos sean oficialmente números).

De hecho, así podría demostrarse cualquier afirmación metamatemática de las que se demuestran habitualmente en los libros con la única condición de que no involucre modelos (ni en su enunciado ni en su demostración). Esto, además de la construcción de ZFC o de la aritmética de Peano, incluye por ejemplo a los teoremas de incompletitud de Gödel, pero no al teorema de completitud, que sí que requiere modelos.

¿Crees que esto respondería a tus exigencias para aceptar que la matemática está "bien fundada"? Lo que es irrenunciable es que tiene que aceptar que las afirmaciones aritméticas que estaríamos haciendo no podrían ser consideradas como afirmaciones de un lenguaje formal demostradas formalmente, porque con ello caeríamos en un círculo vicioso. Lo que si es cierto es que todas ellas pueden ser formalizadas en la aritmética de Peano una vez la tenemos definida metamatemáticamente, y que si el desarrollo metamatemático lo has realizado con una notación conveniente, no hay absolutamente ninguna diferencia entre la versión metamatemática y la versión formalizada, salvo que la primera ha de entenderse como una lista de afirmaciones razonadas sobre los números naturales metamatemáticos, y en la versión formal puedes olvidarte de cualquier posible significado.

24 Agosto, 2013, 01:50 am
Respuesta #1

argentinator

  • Consultar la FIRMAPEDIA
  • Administrador
  • Mensajes: 7,797
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
Citar
¿Crees que esto respondería a tus exigencias para aceptar que la matemática está "bien fundada"?

No sé si "aceptar que eso está bien fundado",
pero sí que es importante entender el punto de partida que la gente asume de las cosas.
Si las reglas del juego que se van a usar están bien declaradas de antemano, es juego limpio.

Citar
Es posible definir el lenguaje formal de ZFC entendiendo que los "signos"  (...) son ciertos números naturales

Pues esa codificación no me parece algo extraño. De hecho, pienso así en ZFC: un papiro no acotado de cifras en base trece.

Citar
sin suponer nada más que la existencia de los números naturales metamatemáticos, con su cero, su operación siguiente, su suma y su producto, y sin suponer de ellos nada más que los axiomas de Peano de primer orden.

Al menos ahora está restringido (  :) ) el tipo de operaciones que se hacen sobre los naturales.
En cuanto a los axiomas de primer orden, han de versar sólo sobre igualdades o desigualdades relativas a las operaciones aceptadas para los números, digamos siguiente, suma y producto, solamente.
(Donde "solamente" = "dije lo que voy a usar", y no uso lo que nunca dije que iba a usar).

No se puede definir lo que es un número metamatemático, ni siquiera se puede estar seguro de qué propiedades cumple, ni siquiera si las reglas de inferencia tienen algún sentido o son aceptables.
Pero si esas reglas se asumen de entrada en forma explícita (  :) ), entonces hay un punto a partir del cual podemos entendernos.

Citar
Y acéptame las dos reglas de inferencia lógicas, el modus ponens y la generalización.

Acá tengo ganas de "aceptarlo", pero algo me lo impide. Quizá el problema es la "letra chica". No entiendo exactamente lo que estaría "aceptando".

Estos razonamientos no son "garabatos en un papel", sino que están en la imaginación, sostenidos por persistentes neuronitas.

Ahora, la afirmación del tipo "\( \forall x: x  > 1   \rightarrow{x\cdot x > x} \)", se demostraría fácilmente por la inducción de 1er orden.
¿Está entonces demostrada (un proceso que me llevó de unos axiomas hasta aquí), o es verdadera (desde la platónica eternidad por la divina gracia del Gran Inexistente)?

¿O verdaderas son sólo las afirmaciones individuales \( 1  > 1   \rightarrow{1\cdot 1 > 1} \),\( 2  > 1   \rightarrow{2\cdot 2> 2} \), \( 3  > 1   \rightarrow{3\cdot 3 > 3} \), ...?

¿La afirmación para todos los \( x \), era verdadera antes de haberla demostrado por inducción?

A lo mejor eso no importa, y tenga que conformarme conque, "al menos a partir de ese momento se considera verdadera", así que te puedo seguir a partir de ahí.

Me queda algo "descolgada" la noción de "verdad".
¿Qué quiere decir que es cierta una afirmación de los números metamatemáticos?
¿Hace falta decirlo?

¿O basta tomar nota de que "estoy diciendo P" porque "fui capaz de dejar explícitamente dichas unas inferencias que me llevaron desde una hipótesis dada, hasta P"?
¿Hace falta decir que eso es verdadero en algún sentido de la palabra verdad?
¿O sólo puedo estar seguro del proceso que me llevó hasta llegar a P?

Porque si yo "veo" que realizaste un proceso que te llevó, con tus reglas, desde una hipótesis A a una conclusión B, entonces no tengo siquiera que creérmelo. Basta conque "tome nota" de lo que hiciste, y certifique (previa coima) que cumpliste tus propias reglas.
No creo que importe si B es "verdad" en algún sentido.

A mí eso me trae algo de confusión. Decir que una afirmación P es "verdad", es colgarle un adorno (o asignarle un valor de verdad a P, como una función booleana que a cada P le asigna un valor 0 ó 1).



¿Cómo puedo estar seguro de que nunca llegaré a contradicciones con estos números metamatemáticos? ¿No falta algo acá? ¿A nadie le hace ruido el teorema de Godel?

Por más que sea meta-teoría, ¿no le pasa lo mismo que a las "teorías", que no se sabe si son consistentes-incompletas o inconsistentes?
(o sea, ¿no estamos pateando el problema a otro terreno, sólo para disimularlo?).
¿No adolece de peligros de inconsistencia?
¿Se puede afirmar la consistencia de la aritmética de peano de 1er orden, o es sólo una creencia?

24 Agosto, 2013, 01:21 pm
Respuesta #2

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Cita de: argentinator
En cuanto a los axiomas de primer orden, han de versar sólo sobre igualdades o desigualdades relativas a las operaciones aceptadas para los números, digamos siguiente, suma y producto, solamente.
(Donde "solamente" = "dije lo que voy a usar", y no uso lo que nunca dije que iba a usar).

En efecto, así es. Me estaba refiriendo a adoptar como "conceptos básicos" la igualdad, la operación siguiente, la suma y el producto, y te pedía que aceptaras los axiomas lógicos construidos sobre afirmaciones que no involucren más que esos conceptos.

Cita de: argentinator
No se puede definir lo que es un número metamatemático, ni siquiera se puede estar seguro de qué propiedades cumple, ni siquiera si las reglas de inferencia tienen algún sentido o son aceptables.

Bueno, éste es un punto clásico de discrepancia entre nosotros. La "rebaja" que te estoy haciendo a mi planteamiento es que no necesitamos discutir sobre qué propiedades cumplen o no los números naturales metamatemáticos, sino que me basta que me aceptes a priori que cumplen los axiomas lógicos y los axiomas de Peano, así como que me aceptes las dos reglas de inferencia lógicas, y yo afirmo que a partir de ahí se puede demostrar sin trampa alguna todo lo necesario para definir ZFC, o la aritmética de Peano como sistema formal.

Cita de: argentinator
Pero si esas reglas se asumen de entrada en forma explícita (  :) ), entonces hay un punto a partir del cual podemos entendernos.

Por eso pensé que te podría interesar.

Cita de: argentinator
Citar
Y acéptame las dos reglas de inferencia lógicas, el modus ponens y la generalización.

Acá tengo ganas de "aceptarlo", pero algo me lo impide. Quizá el problema es la "letra chica". No entiendo exactamente lo que estaría "aceptando".

No sé si te entiendo. Lo que tendrías que aceptar es que si un axioma dice que "algo1 implica algo2" y otro axioma dice "algo1", entonces tienes que aceptar como demostrado "algo2", y que si otro axioma dice "algo2 implica algo3", como está demostrado "algo2", tienes que aceptar como demostrado "algo3" y, en general, que si "algoA" y "algoA implica algoB" están demostrados, tienes que aceptar como demostrado "algoB". Y algo parecido con la regla de generalización.

Cita de: argentinator
Estos razonamientos no son "garabatos en un papel", sino que están en la imaginación, sostenidos por persistentes neuronitas.

Ahora, la afirmación del tipo "\( \forall x: x  > 1   \rightarrow{x\cdot x > x} \)", se demostraría fácilmente por la inducción de 1er orden.
¿Está entonces demostrada (un proceso que me llevó de unos axiomas hasta aquí), o es verdadera (desde la platónica eternidad por la divina gracia del Gran Inexistente)?

¿O verdaderas son sólo las afirmaciones individuales \( 1  > 1   \rightarrow{1\cdot 1 > 1} \),\( 2  > 1   \rightarrow{2\cdot 2> 2} \), \( 3  > 1   \rightarrow{3\cdot 3 > 3} \), ...?

¿La afirmación para todos los \( x \), era verdadera antes de haberla demostrado por inducción?

A lo mejor eso no importa, y tenga que conformarme conque, "al menos a partir de ese momento se considera verdadera", así que te puedo seguir a partir de ahí.

Eso tendrás que decidirlo tú. Mi opinión es que todo eso es verdad aun sin la necesidad de ninguna demostración formal a partir de ningunos axiomas. Lo máximo que puedo hacer es mostrarte que todas las afirmaciones cuya verdad necesito justificar para construir la metamatemática (la parte de la metamatemática que no involucra modelos, por ejemplo la construcción de ZFC) pueden demostrarse a partir de los axiomas de Peano.

Cita de: argentinator
Me queda algo "descolgada" la noción de "verdad".
¿Qué quiere decir que es cierta una afirmación de los números metamatemáticos?
¿Hace falta decirlo?

¿O basta tomar nota de que "estoy diciendo P" porque "fui capaz de dejar explícitamente dichas unas inferencias que me llevaron desde una hipótesis dada, hasta P"?
¿Hace falta decir que eso es verdadero en algún sentido de la palabra verdad?
¿O sólo puedo estar seguro del proceso que me llevó hasta llegar a P?

Yo creo que sí que hace falta. Porque si concibes toda la construcción como una mera cadena de afirmaciones, al final no tienes nada más que afirmaciones, cuando lo que necesitamos es tener "algo", a saber, hace falta que acabemos en condiciones de decir que esto:

\( \forall xy(\forall u(u\in x\leftrightarrow u\in y)\rightarrow x=y) \)

es un axioma de ZFC y lo que acabo de decir (no el axioma, sino que eso es un axioma) tiene que ser una afirmación con sentido para que, en el futuro, cuando quieras demostrar algo en ZFC sepas que esa cadena de signos (que en este enfoque habría que interpretar como la definición de un cierto número natural) es una de las cadenas de signos que puedes usar legítimamente en una demostración formal.

En suma, aunque consideres a "eso" como un número natural, tienes que aceptar que no es uno de los números naturales que definirás en ZFC usando "eso" y otros axiomas como ése. Más aún, si te empeñas en considerar la afirmación "eso es un axioma" como una afirmación de una teoría formal, caes en el círculo vicioso de que dicha teoría formal necesita a su vez ser definida ¿formalmente?

Creo que, con toda la rebaja que te estoy haciendo, no deja de ser necesario entender que si, al principio de todo, te digo que uno de los puntos de partida será esto:

\( \forall xy(Sx=Sy\rightarrow x=y) \)

no podemos ver esto como una afirmación formal de un lenguaje formal todavía no definida, ni siquiera como un número natural. Sólo podemos ver eso como una escritura taquigráfica de la afirmación en castellano que dice que los números naturales metamatemáticos tienen definida una operación siguiente tal que cada número tiene un siguiente distinto, vamos, que no puede ocurrir que el siguiente del siguiente del siguiente de cero sea el mismo que el siguiente del siguiente de cero.

La rebaja que te estoy haciendo es que, en lugar de partir de que los números naturales cumplen objetivamente cualquier propiedad justificada por la intuición, basta con que aceptes que cumplen objetivamente ésta, y ésta, y ésta y ésta... y ésta propiedades (bajo la base de que la intuición las justifica, pero ahora no son todas, sino sólo unas pocas). Si sobre eso crees que puedes hacer una rebaja aún mayor, queda a tu criterio, pero lo pongo en duda.

Cita de: argentinator
Porque si yo "veo" que realizaste un proceso que te llevó, con tus reglas, desde una hipótesis A a una conclusión B, entonces no tengo siquiera que creérmelo. Basta conque "tome nota" de lo que hiciste, y certifique (previa coima) que cumpliste tus propias reglas.
No creo que importe si B es "verdad" en algún sentido.

A mí eso me trae algo de confusión. Decir que una afirmación P es "verdad", es colgarle un adorno (o asignarle un valor de verdad a P, como una función booleana que a cada P le asigna un valor 0 ó 1).

Tengo serias dudas de que con ese planteamiento se pueda llegar a algún sitio. Al final, tú necesitas saber si es aceptable o no que en una demostración en ZFC se use o no el "número natural metamatemático"

\( \forall xy(\forall u(u\in x\leftrightarrow u\in y)\rightarrow x=y) \)

y eso es tanto como decir que ese "número natural metamatemático" tiene la propiedad de ser un axioma de ZFC. Y eso no es un cero o un uno. Es un "ser o no ser" (un axioma). Pero bueno, no niego a priori la posibilidad de que pudieras erradicar coherentemente toda mención a la verdad de las afirmaciones metamatemáticas.

Cita de: argentinator
¿Cómo puedo estar seguro de que nunca llegaré a contradicciones con estos números metamatemáticos? ¿No falta algo acá? ¿A nadie le hace ruido el teorema de Godel?

Por más que sea meta-teoría, ¿no le pasa lo mismo que a las "teorías", que no se sabe si son consistentes-incompletas o inconsistentes?
(o sea, ¿no estamos pateando el problema a otro terreno, sólo para disimularlo?).
¿No adolece de peligros de inconsistencia?
¿Se puede afirmar la consistencia de la aritmética de peano de 1er orden, o es sólo una creencia?

No sé muy bien en qué sentido dices lo del ruido de Gödel. No sé si te refieres a sus implicaciones o si estás cuestionando que realmente esté demostrado.

Ya sabes mi contestación oficial a eso: no podemos llegar a contradicciones con los números naturales porque las afirmaciones metamatemáticas no son axiomas formales que se aceptan sin más garantía, sino afirmaciones verdaderas sobre unos objetos formales (en el sentido de que no son materiales) con propiedades objetivas.

De todos modos, como he prometido no dedicar este hilo a reabrir polémicas, sino a ser constructivo. Voy a hablarte aquí de otra cosa a este respecto que tal vez te pueda interesar. Se trata de la prueba de Gentzen de la consistencia de la aritmética. Gentzen es una figura relativamente desconocida a nivel popular, al menos si lo comparamos con Gödel, pero no es descabellado decir que es la figura más importante en el mundo de la lógica después de Gödel.

El caso es que Gentzen afirmó haber demostrado "casi finitistamente" la consistencia de la aritmética de Peano, y su prueba ha dado lugar a muchas discusiones filosóficas. Te explico la idea. Ante todo, Gentzen trabajaba con un cálculo deductivo de su invención distinto del usual, el cálculo secuencial, lo cual es relevante para la prueba pero no para la idea que quiero transmitir, porque es totalmente equivalente.

Gentzen definió una forma de asignar a cada paso de una demostración un ordinal menor que \( \epsilon_0 \), que es el supremo de los ordinales

\( \omega,\quad \omega^\omega,\quad \omega^{\omega^\omega},\quad \omega^{\omega^{\omega^\omega}}\ldots \)

De modo que cada consecuencia de líneas anteriores tiene un ordinal mayor, y, en particular, la última línea de la prueba tiene el ordinal mayor de todos, que es el ordinal asignado a la demostración completa.

Y luego demostró que si existe una demostración de una contradicción en la aritmética de Peano, es posible a partir de ella construir otra cuyo ordinal es menor. Esto daría lugar a una sucesión decreciente de ordinales, y como eso no existe, la aritmética de Peano tiene que ser consistente. Equivalentemente, el "plato fuerte" de la prueba es una inducción hasta \( \epsilon_0 \): probó que si no existe una demostración de una contradicción de ordinal menor que \( \alpha \), entonces tampoco la hay de ordinal \( \alpha \), luego no la hay de ningún ordinal posible.

La principal objeción a esta "prueba" es la que expresó no recuerdo quién diciendo "Ah, sí, Gentzen, el tío que demostró la consistencia de la aritmética (es decir, de la inducción hasta \( \omega \)) suponiendo la inducción hasta \( \epsilon_0 \)".

Y la otra objeción que uno puede plantear es que los ordinales son teoría de conjuntos pura y dura, así que no tiene mérito demostrar la consistencia de la aritmética de Peano partiendo de los axiomas de la teoría de conjuntos.

Respondo primero a la segunda objeción que es más fácil. Lo que sucede es que los ordinales menores que \( \epsilon_0 \) son conceptos finitistas, definibles en términos de la aritmética de Peano. En ZFC puede probarse que cada uno de ellos puede construirse en un número finito de pasos a partir de los números naturales mediante sumas, productos y potencias de base \( \omega \). Así, un "ordinal típico" tiene la forma

\( \omega^{\omega^{\omega^9+4}+\omega}+\omega^{\omega^5\cdot 7+\omega^2+4}\cdot 8+\omega^{\omega^3+\omega}+\omega^7\cdot 16+4 \)

Puedes poner más o menos niveles de exponentes, más o menos sumandos, pero todo ordinal menor que \( \epsilon_0 \) tiene esta forma. Esto hace que puedas prescindir por completo de la teoría de conjuntos y definir los ordinales (menores que \( \epsilon_0 \)) como ciertos números naturales que codifiquen este tipo de estructuras (de modo similar a como un número de Gödel codifica la estructura de una fórmula o de una demostración) y definir la relación de orden entre los ordinales mediante una definición recursiva. Es decir, es posible programar a un ordenador para que identifique si un número natural codifica o no un ordinal (menor que \( \epsilon_0 \)) y que determine, dados dos ordinales (entendidos como números naturales), cuál es el mayor de los dos. Por ejemplo, podemos darle al ordenador los ordinales

\( \omega^5+\omega\cdot3 +2 \) y \( \omega^5+\omega\cdot 2 + 3 \)

(los pongo sencillitos, no por ayudar al ordenador, sino porque me da pereza escribir ordinales complicados en LaTeX) y el ordenador puede determinar que el primero es mayor que el segundo.

Así, cuando asignamos ordinales a las demostraciones podemos entender que les estamos asignando números naturales, sólo que ahora, entre los números naturales asignados, tenemos definida (recursivamente) una relación de orden que no es la usual, sino que es la relación "n es menor que m" si corresponde a un ordinal menor que m.

Gentzen demostró la consistencia de AP bajo el supuesto de que esa relación de orden recursiva no permite sucesiones decrecientes de números naturales.

Aclarado este punto, pasamos a la otra objeción. La ventaja de la prueba de Gentzen para alguien preocupado por el finitismo es que la prueba semántica usual supone que toda afirmación aritmética tiene un significado y puede ser verdadera o falsa, pero no ambas cosas. Más concretamente, el argumento es:

Supongamos que alguien pudiera venirnos con una demostración de una contradicción a partir de los axiomas de Peano. Entonces, las primeras afirmaciones de la demostración serían (intuitivamente) verdaderas (porque serían axiomas de Peano, que son todos verdaderos), mientras que la última sería falsa, porque sería una contradicción, luego en algún punto de la prueba se ha pasado de unas premisas verdaderas a una conclusión falsa, pero eso es imposible, porque las reglas de inferencia dan fórmulas verdaderas cuando se aplican a premisas verdaderas.

Como digo, este argumento supone (cosa que yo no tengo problema en admitir) que la hipotética demostración de una contradicción estaría formada por fórmulas que, por muy complejas que pudieran ser, tendrían que ser verdaderas o falsas cuando se interpretan intuitivamente, es decir, parte de que a cualquier fórmula aritmética se le puede asignar objetivamente un valor de verdad. Aunque en la práctica el valor de verdad de una fórmula no puede ser determinado efectivamente, esto no sucede así si las fórmulas forman parte de una demostración bien hecha, ya que sí que sabemos que los axiomas son verdaderos y sabemos que las reglas de inferencia llevan de fórmulas verdaderas a fórmulas verdaderas, luego las fórmulas de una demostración tienen que ser siempre verdaderas, luego no tienen cabida las contradicciones.

Frente a este argumento, el de Gentzen no tiene en cuenta para nada el posible significado intuitivo de las fórmulas de la hipotética prueba de una contradicción. Supone dicha prueba y, sin entrar para nada en el posible significado de sus fórmulas, les asigna ordinales (o números naturales) y luego demuestra por procedimientos puramente sintácticos que la prueba puede ser acortada (no en longitud, pues la prueba que obtiene es en general más larga, pero es menos compleja, en el sentido de que su ordinal es menor).

Por lo tanto, para aceptar la prueba de Gentzen no hay que aceptar que las fórmulas aritméticas tienen un significado intuitivo objetivo, sino que sólo hay que aceptar (y ésta es la rebaja que tal vez te parezca interesante) que las afirmaciones concretas que hace Gentzen en su prueba tienen un significado intuitivo objetivo, es decir, que realmente existe un proceso para asignar ordinales (números naturales) a cada prueba posible (sin tener en cuenta para nada el significado posible de sus fórmulas) y que efectivamente es posible manipular la prueba de una contradicción para acortarla.

Todo el argumento de Gentzen es constructivo, es recursivo, es demostrable a partir de los axiomas de Peano, excepto el punto en el que, tras llegar a que hemos construido (recursivamente) una sucesión infinita decreciente respecto al orden de los ordinales, concluye que eso no puede ser. Ése es el único paso no formalizable en la aritmética de Peano (alguno tenía que haber, por el teorema de incompletitud que impide que una teoría demuestre su propia consistencia).

En resumen, lo que tienes que aceptar es que es imposible construir una sucesión de expresiones como el ordinal que te he pintado antes el LaTeX de modo que cada una sea menor que la siguiente, con respecto a cierta relación recursiva, hecho éste que Gentzen demostró metamatemáticamente, pero que no es formalizable en AP.

Cita de: argentinator
No sé si es buena idea hablar de estas cosas.
Me parece que estoy cada vez peor con esto, porque he tenido que ocuparme de asuntos más cotidianos y urgentes.
Una buena contestación a tu mensaje requeriría que yo esté más empapado del tema.
No he seguido tus artículos porque no he podido, no porque no haya querido.

Oye, que no tienes que disculparte de nada. E insisto que esto no es un intento de meterte en harina a tu pesar. Simplemente creí que podría interesarte lo que te he contado, porque, si bien dudo que lo consideres definitivo, creo que rebaja sustancialmente los requisitos de fundamentación de la matemática y tal vez algún día puedas considerar el tratar de sacar partido a estas ideas.

25 Agosto, 2013, 09:48 am
Respuesta #3

argentinator

  • Consultar la FIRMAPEDIA
  • Administrador
  • Mensajes: 7,797
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
Carlos: te agradezco el esfuerzo que estás haciendo en tratar de ayudarme con estas cuestiones.

Citar
en lugar de partir de que los números naturales cumplen objetivamente cualquier propiedad justificada por la intuición, basta con que aceptes que cumplen objetivamente ésta, y ésta, y ésta y ésta... y ésta propiedades

Bueno, eso creo que puedo aceptarlo sin problemas.
Partiendo de una lista clara y bien delimitada de axiomas y reglas claras de inferencia, ya se puede avanzar.

Citar
afirmaciones que no involucren más que esos conceptos

Bien. Si los conceptos están bien delimitados, así como el tipo de afirmaciones que se hacen sobre ellos, me resulta más fácil de aceptar. De hecho, creo que la sensación de que no se sabe qué puede surgir de la galera es lo que siempre me dejaba perplejo. Es como estar en un océano donde los delfines son los números naturales, pero yo sigo viendo todos los demás peces (o sea, el resto de posibilidades del lenguaje, el pensamiento, la imaginación y la intuición).

Citar
No sé si te entiendo. Lo que tendrías que aceptar es que si un axioma dice que "algo1 implica algo2" y otro axioma dice "algo1", entonces tienes que aceptar como demostrado "algo2", y que si otro axioma dice "algo2 implica algo3", como está demostrado "algo2", tienes que aceptar como demostrado "algo3" y, en general, que si "algoA" y "algoA implica algoB" están demostrados, tienes que aceptar como demostrado "algoB". Y algo parecido con la regla de generalización.

Con eso no habría mayores problemas.
Pero lo que yo preguntaba ahí, o luego, o vaya a saber dónde, es si acaso es lo mismo estar demostrado que ser verdadero, en lo que se refiere a números metamatemáticos.

Citar
Más aún, si te empeñas en considerar la afirmación "eso es un axioma" como una afirmación de una teoría formal, caes en el círculo vicioso de que dicha teoría formal necesita a su vez ser definida ¿formalmente?

Pues que yo no veo que sea un círculo vicioso.
Sino que sería un formalismo de un orden "previo", sostenido desde alguna meta-meta-teoría.
El problema vendría cuando nos demos cuenta que siempre hace falta una meta-teoría anterior, por siempre.
Habría que tomar un punto de partida, y yo buscaría el más simple posible.
¿Los axiomas de Peano? No estoy seguro.

Pero eso es una pregunta que puede postergarse, si es que está claro que sólo se usarán los axiomas de Peano y los axiomas lógicos.

Citar
Y la otra objeción que uno puede plantear es que los ordinales son teoría de conjuntos pura y dura, así que no tiene mérito demostrar la consistencia de la aritmética de Peano partiendo de los axiomas de la teoría de conjuntos.

Estoy seguro que los ordinales pueden definirse con una teoría de conjuntos más sencilla o débil que ZFC.

Citar
En ZFC puede probarse que cada uno de ellos puede construirse en un número finito de pasos a partir de los números naturales mediante sumas, productos y potencias de base \( \omega \)

Conozco ese tipo de cuentitas, pues he estudiado algo de teoría del orden. Es un tema (para mí) muy difícil, y eso que es teoría de conjuntos formal... Ahí no tengo excusas.

Citar
Como digo, este argumento supone (cosa que yo no tengo problema en admitir) que la hipotética demostración de una contradicción estaría formada por fórmulas que, por muy complejas que pudieran ser, tendrían que ser verdaderas o falsas cuando se interpretan intuitivamente, es decir, parte de que a cualquier fórmula aritmética se le puede asignar objetivamente un valor de verdad. Aunque en la práctica el valor de verdad de una fórmula no puede ser determinado efectivamente, esto no sucede así si las fórmulas forman parte de una demostración bien hecha, ya que sí que sabemos que los axiomas son verdaderos y sabemos que las reglas de inferencia llevan de fórmulas verdaderas a fórmulas verdaderas, luego las fórmulas de una demostración tienen que ser siempre verdaderas, luego no tienen cabida las contradicciones.

Esto es lo que yo te preguntaba sobre el sentido de "demostrable" y "verdadero" para los números metamatemáticos y sus propiedades.

Estás hablando ahí sobre la consistencia de la aritmética de los naturales intuitivos o metamatemáticos. Estás hablando de demostraciones (procesos mecánicos que llevan de unas afirmaciones a otras), y por separado, a eso se le asignan "significados", que son valores de verdad (verdaderos o falsos).

Ya estoy viendo 3 mundos:

(1) Unos entes intuitivos llamados números naturales y operaciones aritméticas.
(2) Unas afirmaciones acerca de los objetos de (1).
(3) Unos valores de verdad V ó F.

En el mundo (1) están los naturales 1, 2, ... y las operaciones +, ..
En el (2) están las afirmaciones y los procesos deductivos que te van llevando de unas a otras.
En el (3) están los valores V, F, y quizás también operaciones lógicas de álgebra de Boole binaria corriente.
Y tendría que agregar todavía algo más: unas asociaciones o "funciones" que a cada objeto de (2) le asigna un valor de (3).

Eso es lo que interpreto de ese párrafo tuyo, en que comentas lo que hizo Gentzen.

Citar
Todo el argumento de Gentzen es constructivo, es recursivo, es demostrable a partir de los axiomas de Peano, excepto el punto en el que, tras llegar a que hemos construido (recursivamente) una sucesión infinita decreciente respecto al orden de los ordinales, concluye que eso no puede ser. Ése es el único paso no formalizable en la aritmética de Peano (alguno tenía que haber, por el teorema de incompletitud que impide que una teoría demuestre su propia consistencia).

Bueno, es una cuestión muy interesante.
Cuanto menos se use del lado "informal", más claro irá quedando cuál es ese ingrediente especial que hace que los números naturales no puedan ser formalizados en forma completa.

Y el hecho de que alguien se haya preocupado por demostrar dicha consistencia, quiere decir que no soy el único que tiene preguntas sobre si tienen sentido o no los naturales intuitivos.
Aunque aparentemente Gentzen no parece dudar de dicha consistencia, según interpreto de tus propios párrafos, ¿entonces para qué se puso a hacer una demostración del asunto?

De lo que es obvio no amerita que nadie se ponga a hacer alguna demostración.
¿Qué es entonces el elemento "no obvio" que impulsó a Gentzen a hacer esas deducciones?
Para mí directamente no es obvia la consistencia de los naturales.
A lo mejor para Gentzen (y salvando las obvias distancias entre él y yo), lo "no obvio" es aislar el ingrediente especial no formalizable de los números naturales.


25 Agosto, 2013, 11:52 am
Respuesta #4

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Cita de: argentinator
Carlos: te agradezco el esfuerzo que estás haciendo en tratar de ayudarme con estas cuestiones.

No, si me sale sólo. A menudo leo cosas y pienso: creo que esto le interesaría a argentinator.

Cita de: argentinator
Pues que yo no veo que sea un círculo vicioso.
Sino que sería un formalismo de un orden "previo", sostenido desde alguna meta-meta-teoría.
El problema vendría cuando nos demos cuenta que siempre hace falta una meta-teoría anterior, por siempre.
Habría que tomar un punto de partida, y yo buscaría el más simple posible.
¿Los axiomas de Peano? No estoy seguro.

Pero eso es una pregunta que puede postergarse, si es que está claro que sólo se usarán los axiomas de Peano y los axiomas lógicos.

Creo que decimos lo mismo. En principio tenemos un ascenso infinito de teoría a metateoría a meta-metateoría, etc. El círculo vicioso aparece cuando tratas de detenerlo en una teoría formal sin pasar a una metateoría informal. Suponer los axiomas de Peano (como teoría formal) supone suponer que sabes lo que son términos y fórmulas, variables libres y ligadas, la sustitución de una variable por un término en una fórmula, y que sabes cómo se comportan, lo cual a su vez presupone argumentos inductivos, etc.

Como te digo, todo esto se puede definir y formalizar a partir de los axiomas de Peano, es decir, puedes definir los axiomas de Peano a partir de los axiomas de Peano, definiendo previamente lo que son términos, y fórmulas, y variables libres, etc., y razonando por inducción como te permiten los axiomas de Peano, pero no puedes presuponer todo esto sin caer en un círculo vicioso, a menos que entiendas que no es lo mismo un axioma de Peano (que para mí sería una afirmación en castellano que expresa una verdad los números naturales metamatemáticos, aunque puedas expresarla con una taquigrafía adecuada que la haga indistinguible de una afirmación formal) que un axioma de Peano definido a partir de los axiomas de Peano, que sería un número natural metamatemático concreto.

Pero lo interesante es que a partir de los axiomas de Peano no sólo pueden definirse (necesariamente en otro sentido) los axiomas de Peano, sino también los axiomas y las demostraciones de ZFC, de modo que si admitimos que los axiomas de Peano de partida son afirmaciones verdaderas sobre los números naturales metamatemáticos, entonces cada demostración que puedas ver en cualquier libro de matemáticas puede entenderse como una notación conveniente para un cierto número natural metamatemático, como quien prefiere usar la notación XL para el número 40, aun a riesgo de confundirla con su talla de camisa.

Cita de: argentinator
Estoy seguro que los ordinales pueden definirse con una teoría de conjuntos más sencilla o débil que ZFC.

El problema no es definirlos, sino cuántos se puede demostrar que existen. Por ejemplo, en AP puedes definir ordinales como ciertos números naturales con cierta relación de orden distinta de la usual, pero no puedes definir ninguna relación de orden de la que puedas probar que es un buen orden y cuyo tipo de orden resulte ser igual o mayor que \( \epsilon_0 \). Esto es consecuencia del teorema de consistencia de Gentzen. Si pudiera hacerse tal cosa, toda la prueba de Gentzen podría llevarse a cabo usando esa definición de ordinal, y sería formalizable en AP, con lo que podrías demostrar en AP la consistencia de AP, en contra de los teoremas de Gödel.

Cita de: argentinator
Citar
En ZFC puede probarse que cada uno de ellos puede construirse en un número finito de pasos a partir de los números naturales mediante sumas, productos y potencias de base \( \omega \)

Conozco ese tipo de cuentitas, pues he estudiado algo de teoría del orden. Es un tema (para mí) muy difícil, y eso que es teoría de conjuntos formal... Ahí no tengo excusas.

Trataba de evitar tecnicismos, pero entonces tal vez te sepas lo que es la forma normal de Cantor. Todo lo que estaba explicando es consecuencia directa de que todo ordinal admite una forma normal de Cantor, y que si el ordinal es menor que \( \epsilon_0 \) entonces todos los coeficientes que aparecen en su desarrollo en forma normal son estrictamente menores que él mismo, lo que permite probar que tras un número finito de pasos, todo ordinal queda expresado en términos de \( 0 \) y \( \omega \), de forma única si exigimos que cada término del desarrollo esté en forma normal.

Cita de: argentinator
Ya estoy viendo 3 mundos:

(1) Unos entes intuitivos llamados números naturales y operaciones aritméticas.
(2) Unas afirmaciones acerca de los objetos de (1).
(3) Unos valores de verdad V ó F.

En el mundo (1) están los naturales 1, 2, ... y las operaciones +, ..
En el (2) están las afirmaciones y los procesos deductivos que te van llevando de unas a otras.
En el (3) están los valores V, F, y quizás también operaciones lógicas de álgebra de Boole binaria corriente.
Y tendría que agregar todavía algo más: unas asociaciones o "funciones" que a cada objeto de (2) le asigna un valor de (3).

Eso es lo que interpreto de ese párrafo tuyo, en que comentas lo que hizo Gentzen.

Supongo que te refieres al párrafo en el que comento lo que NO hizo Gentzen, es decir, la prueba semántica de consistencia de AP basada en la existencia de un modelo, por oposición a la prueba sintáctica de Gentzen. No sé si ya ves lo que sucede con esto:

Cita de: argentinator
A mí eso me trae algo de confusión. Decir que una afirmación P es "verdad", es colgarle un adorno (o asignarle un valor de verdad a P, como una función booleana que a cada P le asigna un valor 0 ó 1).

Asignar un valor de verdad no es meramente asignar un 0 o un 1. Sólo puedes decir que has asignado un valor de verdad cuando puedes decir que 1 significa que unos objetos en cuestión cumplen la afirmación y 0 que no la cumplen, y el valor añadido de esto es que entonces tienes la garantía de que cada fórmula, o tiene un 0, o tiene un 1, pero es imposible que un razonamiento correcto te diga que le corresponde un 0 y otro razonamiento correcto te diga que le corresponde un 1, porque los objetos son los que son, y cumplen la fórmula o no la cumplen.

De todos modos, te detallé el argumento clásico (en el que ya sabemos de sobra que discrepamos radicalmente) sólo para enfatizar las diferencias con el argumento de Gentzen (que es el que supuse que te iba a interesar), de modo que continuar por aquí sería volver a la discusión de siempre, y es justo lo que no importa para nada en lo que te estoy planteando ahora.

Cita de: argentinator
Citar
Todo el argumento de Gentzen es constructivo, es recursivo, es demostrable a partir de los axiomas de Peano, excepto el punto en el que, tras llegar a que hemos construido (recursivamente) una sucesión infinita decreciente respecto al orden de los ordinales, concluye que eso no puede ser. Ése es el único paso no formalizable en la aritmética de Peano (alguno tenía que haber, por el teorema de incompletitud que impide que una teoría demuestre su propia consistencia).

Bueno, es una cuestión muy interesante.
Cuanto menos se use del lado "informal", más claro irá quedando cuál es ese ingrediente especial que hace que los números naturales no puedan ser formalizados en forma completa.

No sé si es una cuestión de cantidad. El argumento de Gentzen es (o considero que debe interpretarse como) tan informal como los del teorema de Gödel, etc., sin perjuicio de que pueda formalizarse en ZF o incluso en AP más un axioma que postule la buena ordenación de la relación de orden de los ordinales menores que \( \epsilon_0 \). Una prueba de consistencia de AP consiste, en cualquier caso, en suponer que tenemos una demostración de una contradicción en AP. Dicha demostración puede concebirse, según ya hemos hablado, como un cierto número natural metamatemático, el cual determina a su vez un número finito de números naturales metamatemáticos (las fórmulas que componen la demostración).

La diferencia es que en el argumento semántico a continuación se pasa a considerar que cada uno de esos números metamatemáticos (cada una de las afirmaciones que aparecen en la demostración) tiene que tener un significado y, en particular tiene que ser vedadero o falso en la interpretación natural.

En cambio, en la prueba de Gentzen la hipotética demostración de una contradicción se manipula como un mero número natural, y lo único que hace es (o puede interpretarse como) aplicarle una cierta función recursiva para obtener otro número natural que también es una prueba de una contradicción, pero que tiene asignado un número natural menor. La diferencia es, digo, que Gentzen nunca se plantea que la demostración hipotética signifique nada.

Por ello, la prueba de Gentzen sólo exige interpretar informalmente unas afirmaciones concretas sobre números naturales metamatemáticos, las que aparecen en la demostración, las que explican cómo asignar ordinales (es decir, ciertos números naturales) a cada demostración y cómo es posible manipular una demostración para, a partir de ella, obtener otra de ordinal menor, mientras que el argumento semántico exige admitir que las afirmaciones hipotéticas que aparecerían en una demostración hipotética de una contradicción tendrían que tener una interpretación natural.

Cita de: argentinator
Y el hecho de que alguien se haya preocupado por demostrar dicha consistencia, quiere decir que no soy el único que tiene preguntas sobre si tienen sentido o no los naturales intuitivos.
Aunque aparentemente Gentzen no parece dudar de dicha consistencia, según interpreto de tus propios párrafos, ¿entonces para qué se puso a hacer una demostración del asunto?

De lo que es obvio no amerita que nadie se ponga a hacer alguna demostración.
¿Qué es entonces el elemento "no obvio" que impulsó a Gentzen a hacer esas deducciones?
Para mí directamente no es obvia la consistencia de los naturales.
A lo mejor para Gentzen (y salvando las obvias distancias entre él y yo), lo "no obvio" es aislar el ingrediente especial no formalizable de los números naturales.

Antes de que Gödel demostrara sus teoremas, Hilbert planteó el problema de cómo demostrar que la aritmética (como primer paso antes de abordar el de la teoría de conjuntos) es consistente por medios estrictamente finitistas. Los teoremas de Gödel impusieron una restricción al programa de Hilbert: una demostración de la consistencia de AP nunca podría ser tan elemental como para que fuera demostrable en AP.

No creo que Gentzen se cuestionara la consistencia de AP. Su propósito fue encontrar una demostración de la consistencia de AP que estuviera lo más cerca posible de ser formalizable en AP o, si lo prefieres, que fuera lo más finitista posible, "estirando" el concepto de finitismo lo mínimo posible, y encontró que lo máximo que había que aceptar para asegurar la consistencia de AP (al margen de las técnicas finitistas de Hilbert daba por buenas, y que bastan para que, por ejemplo, las demostraciones de los teoremas de incompletitud de Gödel se consideren totalmente finitistas) era aceptar que las expresiones finitas, concretas, que expresan ordinales menores que \( \epsilon_0 \) en términos de \( 0 \) y \( \omega \), que son objetos finitistas, que pueden ser ordenados por una relación de orden descrita finitistamente, tienen la propiedad (y aquí es donde nos movemos a la frontera del finitismo) de que no es posible construir una sucesión infinitamente decreciente de tales expresiones.

25 Agosto, 2013, 06:58 pm
Respuesta #5

argentinator

  • Consultar la FIRMAPEDIA
  • Administrador
  • Mensajes: 7,797
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
Imagino que cálculos como los de de Gentzen se pueden aplicar a las siguientes teorías formales de primer orden también:

http://en.wikipedia.org/wiki/Presburger_arithmetic
http://en.wikipedia.org/wiki/Robinson_arithmetic
http://en.wikipedia.org/wiki/Elementary_recursive_arithmetic
http://en.wikipedia.org/wiki/Primitive_recursive_arithmetic

Son teorías formales más débiles que AP.

En el último enlace de Wikipedia dice esto:

Citar
PRA is often taken as the basic metamathematical formal system for proof theory, in particular for consistency proofs such as Gentzen's consistency proof of first-order arithmetic.

Según lo que explicaste de AP metamatemático y AP formal, acá se puede interpretar lo mismo, que es posible restringirse metamatemáticamente al uso de las propiedades formales asociadas, y construir una metateoría con métodos restringidos de esa manera.
Así se podría hacer con cualquier lista de axiomas propuestos para los números naturales.



La artimética de Presburger ha sido probada como consistente, aunque tal vez demasiado débil (no tiene multiplicación).
¿El método que prueba la consistencia de esta aritmética, utiliza axiomas metamatemáticos más fuertes que sus análogos formales?

Es decir: el análisis de la completitud o no de AP-formalizada se puede hacer, según me dijiste, usando solamente las herramientas "análogas" de AP-metamatemática (¿o mejor le digo AP-intuitiva?).

Cuando se demuestra la consistencia de la aritmética de Presbuger formalizada, ¿la metamatemática utilizada involucra a los Axiomas de Peano intuitivos o sólo a la aritmética de Presburger intuitiva?

La misma pregunta se podría hacer para las otras aritméticas.
Pero en realidad sólo me parece interesante hacerse la pregunta para las teorías aritméticas formales que están consideradas "consistentes".

Lo que estoy preguntando es si hay alguna de estas teorías que sea, digamos autoconsistente,
lo cual es una palabra que me acabo de inventar, y quiere decir que:

Dada una teoría formal T, con ciertos axiomas lógicos y aritméticos,
si la metamatemática usada para estudiar T
se restringe de modo que sólo use las versiones intuitivas/informales de los axiomas de T,
y si eso basta para demostrar que T es consistente,
entonces decimos que T es autoconsistente.

La idea creo que se entiende, pero para mi propio gusto, no aceptaría eso como una definición.
Es demasiado "meta".



Creo haber leído en alguna parte, mas no puede encontrar el artículo,
que es posible una teoría aritmética formal casi idéntica a la de Peano,
salvo por el hecho de que se restringen las afirmaciones que uno puede hacer sobre la multiplicación (si recuerdo bien, la idea es cuantificar hasta un rango acotado, y no permitir para afirmaciones sobre la multiplicación que se cuantifique para todos los naturales).

Se afirmaba en dicho artículo que una tal teoría es consistente.

Así que de nuevo me pregunto si es autoconsistente.



Luego me preguntaría si entre las que yo llamo teorías autoconsistentes,
habrá alguna que permita usarse como metamatemática de la matemática clásica, o de la mayor parte de ella.



Y en cuanto a PRA (Primitive Recursión Arithmetic), que también se llama Aritmética de Skolem.
¿Qué se sabe de su consistencia?

Por otro lado,
en Wikipedia dice que se usa PRA para la metateoría.
Vos decís que se usa algo más fuerte: AP.

No sé hasta dónde creerle a Wikipedia.
Todo lo que dice es muy incierto.
Aparecen comentarios de opiniones sobre "creencias" de gente que ni sé quién es.
(Claro que si los conociera les creería menos, aunque me caerían más simpáticos...).

¿Cuán pocos axiomas se pueden usar en la zona "meta"?
¿Es posible "rebajarse" hasta una teoría autoconsistente para que todo funcione "bien"?


25 Agosto, 2013, 08:36 pm
Respuesta #6

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Bueno, antes que nada, aclaro una cosa:
Por otro lado,
en Wikipedia dice que se usa PRA para la metateoría.
Vos decís que se usa algo más fuerte: AP.

No sé hasta dónde creerle a Wikipedia.
Todo lo que dice es muy incierto.

Cree a Wikipedia (en esto). Yo he hablado todo el rato de AP por no introducir tecnicismos, pero, ciertamente, teorías más débiles que AP son suficientes.

En segundo lugar:

Lo que estoy preguntando es si hay alguna de estas teorías que sea, digamos autoconsistente,
lo cual es una palabra que me acabo de inventar, y quiere decir que:

Dada una teoría formal T, con ciertos axiomas lógicos y aritméticos,
si la metamatemática usada para estudiar T
se restringe de modo que sólo use las versiones intuitivas/informales de los axiomas de T,
y si eso basta para demostrar que T es consistente,
entonces decimos que T es autoconsistente.

La idea creo que se entiende, pero para mi propio gusto, no aceptaría eso como una definición.
Es demasiado "meta".

La respuesta negativa  esa pregunta es exactamente el contenido del segundo teorema de incompletitud de Gödel. Una teoría nunca es lo suficientemente potente para demostrar su propia consistencia. Para demostrar la consistencia de una teoría T siempre necesitas algo más que la versión metamatemática de los propios axiomas de T.

Imagino que cálculos como los de de Gentzen se pueden aplicar a las siguientes teorías formales de primer orden también:

http://en.wikipedia.org/wiki/Presburger_arithmetic
http://en.wikipedia.org/wiki/Robinson_arithmetic
http://en.wikipedia.org/wiki/Elementary_recursive_arithmetic
http://en.wikipedia.org/wiki/Primitive_recursive_arithmetic

Son teorías formales más débiles que AP.

Cierto. Voy a tomar una como ejemplo para comentar algunas cosas. Consideremos la aritmética de Robinson Q. Esencialmente, es la aritmética de Peano a la que le hemos quitado el principio de inducción, aunque entonces hay que añadirle el axioma que dice que todo natural no nulo es el siguiente de otro natural, porque eso es irrenunciable y en AP se prueba por inducción.

Una de las razones por las que Q es interesante es porque es lo suficientemente potente como para que le sea aplicable el teorema de incompletitud de Gödel, es decir, si una teoría es recursiva (hay un criterio para decidir qué fórmulas son axiomas de la teoría y cuáles no), es consistente, y permite demostrar los axiomas de Q (no necesariamente los de AP), entonces es incompleta. De hecho, puestos a refinar, basta con que sea semirrecursiva.

Ahora bien, cuanto más débil es una teoría, más metamatemática se necesita para trabajar con ella. Por ejemplo, un teorema sobre Q es que, para todo par de numerales \( 0^m \) y \( 0^n \) (aquí llamo, por ejemplo, \( 0^3\equiv 0''' \), es decir, el término que nombra al número \( 3 \) en la teoría) en Q se puede demostrar \( 0^m + 0^n = 0^n + 0^m \) ¿y cómo se demuestra esto? Por inducción sobre \( m \), ¿pero no habíamos quedado en que Q no tenía el axioma de inducción? Ciertamente, pero eso significa que una demostración de \( 0^3+0^5=0^5+0^3 \) no requiere inducción, y una demostración de que \( 0^3+0^6=0^6+0^3 \) tampoco requiere inducción, pero para probar que esto puede probarse para cualquier número de comitas que le pongamos a los sumandos, necesitamos inducción. Por lo tanto, no la hemos eliminado "del todo". Sólo la hemos cambiado de sitio.

Por otra parte, para definir PRA necesitas saber lo que son las funciones recursivas primitivas. No me he parado a pensar cuál sería la forma más "económica" de introducirlas, pero no me sorprendería que hicieran falta argumentos que te hicieran "arrugar la nariz". Muchas de estas teorías "más débiles" requieren criterios "más fuertes" para debilitar los axiomas, como definir el concepto de función recursiva primitiva en el caso de PRA.

Observa que PRA tiene infinitos signos primitivos (no sólo el "siguiente", la suma y el producto, sino uno para cada función recursiva primitiva). Posiblemente podríamos esquivar el concepto mismo de función definida sobre los números naturales metamatemáticos, pues sólo necesitamos enumerar todas las definiciones formales de funciones recursivas, pero aun así, para dar un sentido a qué es un axioma de PRA, creo que no podemos partir de un PRA metamatemático y ya está, porque no sabríamos explicar exactamente de qué partimos sin recurrir a otra teoría axiomática.

Eso sí, lo cierto es que en PRA se puede definir PRA, y AP y ZFC, es decir, si asumes PRA como metamatemática, puedes definir la matemática formal.

Cuando yo te hablaba de AP en los mensajes anteriores, en realidad estaba pensando en \( \rm I\Sigma_1 \), que es AP en la que se restringe el principio de inducción a fórmulas de tipo \( \exists x\,\phi(x,y) \), donde \( \phi(x,y) \) es una fórmula aritmética en la que todos los cuantificadores están acotados (lo cual significa que son todos de la forma \( \forall u<v \) o \( \exists u< v \), de modo que cada variable cuantificada está siempre acotada por otra variable. Si no recuerdo mal, \( \rm I\Sigma_1 \) es ligeramente más fuerte que PRA.

\( \rm I\Sigma_1 \) tiene la propiedad de ser finitamente axiomatizable (los infinitos casos del principio de inducción para fórmulas de tipo \( \Sigma_1 \) pueden demostrarse a partir de un número finito de ellos), pero me preguntaba si considerarías "más simple" desde un punto de vista metamatemático introducir la definición de fórmula \( \Sigma_1 \) para limitar el principio de inducción o si considerarías más simple trabajar con todo AP (aunque, desde luego, es más fuerte) para eliminar trabajo metamatemático.


En el último enlace de Wikipedia dice esto:

Citar
PRA is often taken as the basic metamathematical formal system for proof theory, in particular for consistency proofs such as Gentzen's consistency proof of first-order arithmetic.

Según lo que explicaste de AP metamatemático y AP formal, acá se puede interpretar lo mismo, que es posible restringirse metamatemáticamente al uso de las propiedades formales asociadas, y construir una metateoría con métodos restringidos de esa manera.
Así se podría hacer con cualquier lista de axiomas propuestos para los números naturales.

Sí eso es cierto. Como digo, yo estaba pensando en \( \rm I\Sigma_1 \), pero PRA es casi lo mismo.

La artimética de Presburger ha sido probada como consistente, aunque tal vez demasiado débil (no tiene multiplicación).
¿El método que prueba la consistencia de esta aritmética, utiliza axiomas metamatemáticos más fuertes que sus análogos formales?

Es decir: el análisis de la completitud o no de AP-formalizada se puede hacer, según me dijiste, usando solamente las herramientas "análogas" de AP-metamatemática (¿o mejor le digo AP-intuitiva?).

Cuando se demuestra la consistencia de la aritmética de Presbuger formalizada, ¿la metamatemática utilizada involucra a los Axiomas de Peano intuitivos o sólo a la aritmética de Presburger intuitiva?

No conozco la prueba, pero dudo mucho que pueda hacerse en una teoría más débil que PRA. En cualquier caso, la respuesta a tu pregunta es que no, no puede probarse usando únicamente la aritmética de Presburger intuitiva, por el segundo teorema de incompletitud de Gödel, como ya he dicho antes.

La misma pregunta se podría hacer para las otras aritméticas.
Pero en realidad sólo me parece interesante hacerse la pregunta para las teorías aritméticas formales que están consideradas "consistentes".

Je, je, lo de "están consideradas" es subjetivo, y aquí estamos tú y yo para ejemplificarlo.  :P  En cualquier caso, la respuesta es siempre, negativa, como ya digo.

Creo haber leído en alguna parte, mas no puede encontrar el artículo,
que es posible una teoría aritmética formal casi idéntica a la de Peano,
salvo por el hecho de que se restringen las afirmaciones que uno puede hacer sobre la multiplicación (si recuerdo bien, la idea es cuantificar hasta un rango acotado, y no permitir para afirmaciones sobre la multiplicación que se cuantifique para todos los naturales).

Se afirmaba en dicho artículo que una tal teoría es consistente.

Así que de nuevo me pregunto si es autoconsistente.

No identifico a qué te refieres, pero en cualquier caso, autoconsistente no será.

Luego me preguntaría si entre las que yo llamo teorías autoconsistentes,
habrá alguna que permita usarse como metamatemática de la matemática clásica, o de la mayor parte de ella.

Bueno, autoconsistentes no hay, pero cualquiera, de PRA hacia arriba, puede usarse como metamatemática de la matemática clásica.

Y en cuanto a PRA (Primitive Recursión Arithmetic), que también se llama Aritmética de Skolem.
¿Qué se sabe de su consistencia?

Pues la situación en estos casos es siempre la misma: puedes demostrar la consistencia de una teoría si supones una metateoría que tenga los axiomas de la teoría y un poquito más. Naturalmente, también puedes suponer algo bastante distinto, pero si acabas probando la consistencia que te propones, es que tus hipótesis son en cierto sentido más fuertes que la teoría cuya consistencia has probado (lo cual no significa necesariamente que tus axiomas demuestren todos los axiomas de la teoría cuya consistencia has probado, esto es una sutileza que no importa mucho aquí, pero lo digo por precisión).

En el caso de PRA creo que hay un teorema análogo al de Gentzen para la AP, sólo que el ordinal correspondiente no es \( \epsilon_0 \), sino el ordinal de PRA, que es \( \omega^\omega \), es decir, en PRA puedes definir los ordinales menores que \( \omega^\omega \) como ciertos números naturales. Dichos ordinales son simplemente los polinomios en \( \omega \), como

\( \omega^7\cdot 5+\omega^3\cdot 10+\omega\cdot 9+145 \)

Y puedes definir la relación de orden entre ellos, pero no puedes demostrar que no existen sucesiones infinitas decrecientes. Si añades como axioma que no las hay, entonces puedes demostrar que PRA es consistente.

Un sano ejercicio es si te plantees si te crees que no hay sucesiones decrecientes infinitas de polinomios en \( \omega \), con la relación de orden obvia: es menor el de menor grado, si tienen el mismo grado se compara el coeficiente director, si coinciden miramos el siguiente, etc.

¿Cuán pocos axiomas se pueden usar en la zona "meta"?

Como te comentaba, debilitar los axiomas de una teoría no es sinónimo de "reducir sus axiomas", al contrario, unos axiomas más débiles (en cuanto que permitan probar menos cosas) pueden ser más complicados de describir.

¿Es posible "rebajarse" hasta una teoría autoconsistente para que todo funcione "bien"?

No, y mil veces no.

De todos modos, parece que de repente te has vuelto especialmente "avaricioso" y no te conformas sino con "la mejor" teoría. Creo que, en un principio, en lugar de meterte con sofisticaciones, podrías plantearte si te convencería una fundamentación de la metamatemática basada en AP, o en PRA o en \( \rm I\Sigma_1 \) (insisto en la tercera porque es casi idéntica a AP en cuanto a "aspecto" y simplicidad de presentación y es casi idéntica a PRA en cuanto a "potencia". Ambas tienen en común que sólo pueden probar que están bien ordenados los ordinales menores que \( \omega^\omega \), pero no el propio \( \omega^\omega \).

25 Agosto, 2013, 08:53 pm
Respuesta #7

argentinator

  • Consultar la FIRMAPEDIA
  • Administrador
  • Mensajes: 7,797
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
Citar
Una teoría nunca es lo suficientemente potente para demostrar su propia consistencia.

¿Eso se aplica a "toda" teoría, o a "toda teoría tal que puede definirse en ella el concepto de número natural"?

¿Qué quiere decir ahora una "teoría"?

25 Agosto, 2013, 09:01 pm
Respuesta #8

argentinator

  • Consultar la FIRMAPEDIA
  • Administrador
  • Mensajes: 7,797
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
Citar
podrías plantearte si te convencería una fundamentación de la metamatemática basada en AP, o en PRA

No sé si "convencerme" es la palabra adecuada.
A lo mejor debería decir: "por fin estoy entendiendo el método de trabajo (o eso creo)", y puedo estudiar el tema sin creer que se están enredando las cosas, o dando vueltas en círculos.

Eso es un gran logro.

Pero lo más importante es la posibilidad de restringirse de una manera clara al tipo de afirmaciones metamatemáticas que nos permitimos usar.
Si bastan pocas, y es posible enumerarlas con claridad, eso me tranquiliza bastante.

Algunos (la mayoría) dirán que son "verdaderas", yo las puedo tomar como "un sistema de creencias", o "axiomas mentales".
Pero llegaríamos a las mismas conclusiones, que es lo que realmente importa.

25 Agosto, 2013, 09:02 pm
Respuesta #9

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Citar
Una teoría nunca es lo suficientemente potente para demostrar su propia consistencia.

¿Eso se aplica a "toda" teoría, o a "toda teoría tal que puede definirse en ella el concepto de número natural"?

¿Qué quiere decir ahora una "teoría"?


Las hipótesis exactas son que tenemos un lenguaje formal, seleccionamos unos axiomas en ese lenguaje, con la condición de que exista un criterio efectivo para decidir si una fórmula es o no un axioma (en realidad basta con que se pueda generar una lista con todos los axiomas en la que no aparezca nunca una fórmula que no sea un axioma, no hace falta que podamos predecir en la práctica si una fórmula dada terminará apareciendo en la lista), y de modo que a partir de esos axiomas sea posible demostrar los axiomas de la aritmética de Robinson Q, es decir, los axiomas de Peano menos los de inducción (y más el axioma que dice que todo número diferente de 0 tiene un anterior).

No es necesario que sea una subteoría de AP. Puede ser una teoría como ZF en la que se pueden definir los números naturales y demostrar que cumplen los axiomas de Peano.

Bajo esas hipótesis, si existe un argumento que demuestra la consistencia de esos axiomas y que sea formalizable en la propia teoría (es decir, que no se base en nada más que en los propios axiomas de la teoría), el teorema de Gödel implica que la teoría es contradictoria.

Pero, claro, si tienes una teoría en la que no puedes definir los números naturales, en el sentido de demostrar que existen unos objetos que cumplan como mínimo los axiomas de Q, ¿en qué sentido podría decirse que basta para demostrar su consistencia? Si no puede definir los números naturales, ¿cómo va a definirse a sí misma? Y si no puede definirse a sí misma, mucho menos podrá probar su propia consistencia.