Autor Tema: Sobre la categoricidad de los axiomas de Peano en 2º orden

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

10 Enero, 2012, 11:11 am
Leído 7112 veces

Raúl Aparicio Bustillo

  • $$\Large \color{#9c57a6}\pi\,\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 3,113
  • Karma: +0/-3
  • Sexo: Masculino
Que  la axiomática de Peano no es categórica en primer orden no es dificil de ver, por ejemplo utilizando los teoremas de completitud semántica de los lenguajes de primer orden y el primer teorema de incompletitud de Gödel:si tengo una formula que afirma de si misma (entre otras cosas) que es verdadera y no demostrable (que en una teoría aritmética recursiva la tengo)  es verdadera, o sea,  no puede ser verdadera en todos los modelos (luego hay más de un modelo), porque entonces sí sería demostrable por el teorema de completitud (absurdo)

Ahora bien, en 2º orden todo es aparentemente genial porque la teoría se vuelve categórica, y no hay modelos raros con números no estandar (claro que los modelos no estandar son raros precisamente porque tenemos una noción metamatemática de finitud y los números no estandar son infinitos sólo en nuestro sentido metamatemático de infinitud). Ahora bien, esta teoría, ¿es categórica con un cálculo deductivo de segundo orden que se pueda usar en la práctica (nunca he visto explicitamente una axiomática y unas reglas de inferencia para un cálculo deductivo de segundo orden) o para que sea categórica necesitaríamos usar un cálculo deductivo con infinitos axiomas y/o infinitas reglas de inferencia que no sean recursivos (es decir, que esos axiomas infinitos no los podríamos expresar mediante un número finito de esquemas axiomáticos y/o "esquemas de regla de inferencia"), que en la práctica no podemos usar. Si la situación es la segunda y esto sucede además para cualquier teoría con un mínimo de interés matemático entonces comprendo  porque muchos matemáticos consideran que podemos limitarnos a trabajar con teorías de primer orden.

Lo que no llego a comprender muy bien es cómo todas las fórmulas de teoría de conjuntos son equivalentes a una fórmula pura de segundo orden. Sea A un axioma cualquiera de ZFC, podemos usar un cálculo deductivo en segundo orden que lleve un axioma B equivalente a la negación del axioma A. Este axioma de segundo orden haría que ZFC fuera inconsistente. No entiendo como los axiomas y/o reglas de inferencia nuevos que se añaden al cálculo deductivo de primer orden pueden llevar "encubiertos" axiomas o reglas de inferencia que de primer orden.

11 Enero, 2012, 10:30 am
Respuesta #1

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Ahora bien, en 2º orden todo es aparentemente genial porque la teoría se vuelve categórica, y no hay modelos raros con números no estandar (claro que los modelos no estandar son raros precisamente porque tenemos una noción metamatemática de finitud y los números no estandar son infinitos sólo en nuestro sentido metamatemático de infinitud).

No es tan genial. Lo que sucede entonces es que puedes tener teorías consistentes que no tengan modelos o, lo que en el fondo es lo mismo, que puedes tener unos axiomas que impliquen una consecuencia en el sentido de que si los axiomas son verdaderos (en un modelo) la consecuencia es necesariamente verdadera también, y, sin embargo, no es posible deducir la "consecuencia" de los axiomas mediante el cálculo deductivo.

Ahora bien, esta teoría, ¿es categórica con un cálculo deductivo de segundo orden que se pueda usar en la práctica (nunca he visto explicitamente una axiomática y unas reglas de inferencia para un cálculo deductivo de segundo orden) o para que sea categórica necesitaríamos usar un cálculo deductivo con infinitos axiomas y/o infinitas reglas de inferencia que no sean recursivos (es decir, que esos axiomas infinitos no los podríamos expresar mediante un número finito de esquemas axiomáticos y/o "esquemas de regla de inferencia"), que en la práctica no podemos usar. Si la situación es la segunda y esto sucede además para cualquier teoría con un mínimo de interés matemático entonces comprendo  porque muchos matemáticos consideran que podemos limitarnos a trabajar con teorías de primer orden.

El concepto de "ser categórica" no depende de ningún cálculo de ductivo: los axiomas de Peano de segundo orden son categóricos en el sentido de que dos modelos cualesquiera de dichos axiomas son necesariamente isomorfos, y eso no depende de ningún cálculo deductivo.

Hace muchos años que no toco libros de lógica, así que no sabría darte referencias (seguro que las hay), pero creo recordar que en el segundo artículo en el que expuso sus teoremas de incompletitud, Gödel definía un cálculo deductivo de segundo orden para la aritmética.

Lo que no llego a comprender muy bien es cómo todas las fórmulas de teoría de conjuntos son equivalentes a una fórmula pura de segundo orden. Sea A un axioma cualquiera de ZFC, podemos usar un cálculo deductivo en segundo orden que lleve un axioma B equivalente a la negación del axioma A. Este axioma de segundo orden haría que ZFC fuera inconsistente. No entiendo como los axiomas y/o reglas de inferencia nuevos que se añaden al cálculo deductivo de primer orden pueden llevar "encubiertos" axiomas o reglas de inferencia que de primer orden.

Aquí me pierdo. ¿Puedes precisar o dar alguna referencia de a qué te refieres?

11 Enero, 2012, 12:22 pm
Respuesta #2

Óscar Matzerath

  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 567
  • Karma: +0/-0
  • Sexo: Masculino
Hola,

Si quieres echar un vistazo a cálculos deductivos de 2º orden, en el libro de Takeuti "Proof theory" tienes una buena muestra (son cálculos tipo Gentzen, pero no debería haber mucho problema en convertirlos a reglas de deducción natural o incluso cálculos tipo Hilbert).

Hay muchos cálculos distintos de 2º orden, dependiendo de qué te interese. Los más débiles consisten en una ampliación de cálculos de primer orden con reglas para la eliminación y la introducción de cuantificadores de segundo orden, análogas a las reglas para los cuantificadores de primer orden.
Cálculos más fuertes involucran típicamente esquemas axiomáticos del tipo axioma de comprensión:

\( \exists X \forall x_1...x_n (Xx_1...x_n \leftrightarrow \varphi(x_1,...,x_n)) \) (o variantes con parámetros)

Especialmente interesantes son los cálculos completos para la semántica de Henkin de segundo orden, y estos son los más estándar cuando uno habla de cálculos deductivos para la lógica de segundo orden. En particular, muy interesantes son los cálculos de segundo orden para la aritmética, ya que su estudio (junto con cálculos debilitados) es clave en áreas de lógica como la "reverse mathematics".

Saludos

11 Enero, 2012, 11:27 pm
Respuesta #3

Raúl Aparicio Bustillo

  • $$\Large \color{#9c57a6}\pi\,\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 3,113
  • Karma: +0/-3
  • Sexo: Masculino
Citar
No es tan genial. Lo que sucede entonces es que puedes tener teorías consistentes que no tengan modelos o, lo que en el fondo es lo mismo, que puedes tener unos axiomas que impliquen una consecuencia en el sentido de que si los axiomas son verdaderos (en un modelo) la consecuencia es necesariamente verdadera también, y, sin embargo, no es posible deducir la "consecuencia" de los axiomas mediante el cálculo deductivo.  [\
Hola,

Si quieres echar un vistazo a cálculos deductivos de 2º orden, en el libro de Takeuti "Proof theory" tienes una buena muestra (son cálculos tipo Gentzen, pero no debería haber mucho problema en convertirlos a reglas de deducción natural o incluso cálculos tipo Hilbert).

Hay muchos cálculos distintos de 2º orden, dependiendo de qué te interese. Los más débiles consisten en una ampliación de cálculos de primer orden con reglas para la eliminación y la introducción de cuantificadores de segundo orden, análogas a las reglas para los cuantificadores de primer orden.
Cálculos más fuertes involucran típicamente esquemas axiomáticos del tipo axioma de comprensión:

\( \exists X \forall x_1...x_n (Xx_1...x_n \leftrightarrow \varphi(x_1,...,x_n)) \) (o variantes con parámetros)

Especialmente interesantes son los cálculos completos para la semántica de Henkin de segundo orden, y estos son los más estándar cuando uno habla de cálculos deductivos para la lógica de segundo orden. En particular, muy interesantes son los cálculos de segundo orden para la aritmética, ya que su estudio (junto con cálculos debilitados) es clave en áreas de lógica como la "reverse mathematics".

Saludos
quote]

Sí, soy consciente de esas limitaciones que tienen los cálculos en segundo orden , imagino que en teoría de conjuntos no es muy útil y por eso no se usa. Ahora bien, en la Aritmética de Peano algo de utilidad sí tiene,  te quitas los modelos estandar, pero al igual que nuestra concepción metamatemática de número natural  nos hace ver que estos verifican los axiomas en primer orden también nos hace ver si reforzamos el (esquema de) axioma de inducción de primer orden de PA para convertirlo en el axioma de segundo orden (que se ve que es una versión fuerte del esquema, podemos decir que P(x) si x verifica una determinada fórmula, ahora bien, hay predicados unarios que no son expresables por fórmulas) que nuestros números naturales lo verifican.

Donde sí tengo una cierta laguna es en esto de que haya formulas verdaderas no demostrables en ningún cálculo deductivo en segundo orden. En primer orden no es tan problemático   porque todas las verdades son en principio demostrables y los esquemas y reglas del cálculo deductivo son "razonables" simplemente con la interpretación que damos a los símbolos lógicos cuando los parafreseamos en castellano: "no", "implica que", "algun" , "cualquier", etc... Ahora bien, en segundo orden, para poder afirmar eso de que "hay verdades no demostrables" está claro que tienes que tener un concepto de verdad previo a la lógica. Interpretando las conectivas de forma usual no es dificil determinar la veracidad de una fórmula compuesta a partir de las fórmulas atómicas que la integran. Así que el problema se reduce a dar una definición de verdad para fórmulas atómicas. Ahora bien, en AP es sencillo, siendo  el único relator  el signo igual.Por supuesto necesitas dar una interpretación a la función siguiente y a + y *. Donde no tengo tan claro como se hace es por ejemplo en ZFC, o en NFA


 
Citar
Aquí me pierdo. ¿Puedes precisar o dar alguna referencia de a qué te refieres?   [\quote]

Bueno, fue a raíz de leer  http://philsci-archive.pitt.edu/1620/1/How_Set_Theory_Impinges_on_Logic.pdf


 
Citar
Si quieres echar un vistazo a cálculos deductivos de 2º orden, en el libro de Takeuti "Proof theory" tienes una buena muestra (son cálculos tipo Gentzen, pero no debería haber mucho problema en convertirlos a reglas de deducción natural o incluso cálculos tipo Hilbert).   [\quote]

Gracias por la referencia, Oscar.




12 Enero, 2012, 01:05 pm
Respuesta #4

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Donde sí tengo una cierta laguna es en esto de que haya formulas verdaderas no demostrables en ningún cálculo deductivo en segundo orden.

Bueno, toma por ejemplo la aritmética de Peano de segundo orden. Para ella es cierta el teorema de incompletitud de Gödel, que te da una sentencia G que no es demostrable ni refutable. Tiene sentido decir que G es verdadera, pues equivale a que no es demostrable. Así que tienes una afirmación verdadera no demostrable en AP y, por otra parte, si añades a AP el axioma \( \lnot G \) tienes una teoría consistente que no tiene modelos.

Ahora bien, en segundo orden, para poder afirmar eso de que "hay verdades no demostrables" está claro que tienes que tener un concepto de verdad previo a la lógica. Interpretando las conectivas de forma usual no es dificil determinar la veracidad de una fórmula compuesta a partir de las fórmulas atómicas que la integran. Así que el problema se reduce a dar una definición de verdad para fórmulas atómicas. Ahora bien, en AP es sencillo, siendo  el único relator  el signo igual.Por supuesto necesitas dar una interpretación a la función siguiente y a + y *. Donde no tengo tan claro como se hace es por ejemplo en ZFC, o en NFA

En general, si construyes una teoría de conjuntos (recursiva) de segundo orden, en ella hay sentencias indecidibles, luego, o bien la teoría no tiene modelo alguno, lo cual la hace muy "pintoresca", o bien tiene algún modelo, en el cual una sentencia indecidible cualquiera (o bien su negación) será verdadera y no demostrable.

Citar
Aquí me pierdo. ¿Puedes precisar o dar alguna referencia de a qué te refieres?   

Bueno, fue a raíz de leer  http://philsci-archive.pitt.edu/1620/1/How_Set_Theory_Impinges_on_Logic.pdf

Pues lo he leído y no sé a qué se refiere. Yo de lógica he estudiado lo que he necesitado para produndizar en las pruebas de consistencia en teoría de conjuntos. Por lo demás nunca me ha interesado especialmente.

13 Enero, 2012, 12:34 am
Respuesta #5

Óscar Matzerath

  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 567
  • Karma: +0/-0
  • Sexo: Masculino
Hola,

Sobre el artículo de Mosterín, lo único que viene a decir es que en realidad, como decía Quine, la lógica de segundo orden no es más que teoría de conjuntos disfrazada de cordero.

A cada sentencia de la teoría de conjuntos \( \sigma \) podemos asociar una sentencia de segundo orden  \( \sigma^* \), de manera que \( \sigma^* \) es lógicamente válida si y solo si \( \sigma \) es verdadera en el universo V (para que esto tenga sentido hay que hacer la suposición filosófica de que hay un único modelo "verdadero" de la teoría de conjuntos). Esto es debido a que \( \sigma^* \) es una sentencia de segundo orden lógicamente válida si y solo si es verdadera en toda estructura. Pero las estructuras de segundo orden no son más que conjuntos (junto con tal vez subconjuntos y relaciones) y las variables de segundo orden toman valores en los subconjuntos de la estructura. Esto es lo que nos permite "traducir" de teoría de conjuntos a segundo orden: el hecho de que en segundo orden podamos hablar no solo de elementos, sino también de subconjuntos arbitrarios. En el artículo hay unos cuantos ejemplos de formalizaciones de sentencias de teoría de conjuntos en lógica de segundo orden (existencia de inaccesibles, axioma de elección, GCH, etc).

Esto quiere decir que la verdad en lógica de segundo orden es un concepto que se escapa totalmente de nuestro control, tanto como la "verdad" en teoría de conjuntos. Es bueno observar que todo esto solo tiene sentido si uno tiene una posición filosófica cercana al platonismo, de manera que tiene sentido hablar de "teoría de conjuntos" y "lógica de segundo orden" en un sentido absoluto. Si uno no es tan platonista, lo que esto indica es que no tiene sentido hablar de lógica de segundo orden si no tienes una teoría de conjuntos detrás sobre la que apoyarte (es decir, solo tiene sentido hablar de lógica de 2º orden como lógica formalizada en una teoría de conjuntos de 1º orden), al contrario de la lógica de primer orden, que al ser r.e. (que en la práctica se traduce en tener un cálculo) es esencialmente independiente de la teoría de conjuntos (no voy a entrar en lo que habla Mosterín al respecto, pues la suposición de que hay conjuntos infinitos me parece muy razonable, y porque si solo admitimos estructuras finitas la lógica de primer orden se vuelve intratable).

Sobre lo de añadir como axioma a un cálculo deductivo la negación de un axioma de ZFC, pongamos añadir ¬AC (la sentencia asociada en la lógica de segundo orden, se entiende). Bien, lo puedes hacer. Pero entonces o bien (posición platonista) 1) en el modelo "verdadero" de la teoría de conjuntos AC es verdadera y entonces tu cálculo no es correcto (pues entonces la sentencia que expresa AC en 2º orden es lógicamente válida) o 2) en el modelo "verdadero" de teoría de conjuntos AC es falsa y entonces el cálculo es correcto (pero ZFC no puede ser la teoría "buena" de conjuntos). Si tu posición es más realista, lo único que esto implica es que la lógica de 2º orden es absolutamente dependiente de la teoría de conjuntos que tenga detrás. Si estás formulando lógica de 2º orden en ZFC, AC es una sentencia de 2º orden lógicamente válida, mientras que si formulas lógica de 2º orden en ZF + ¬AC, AC no es lógicamente válida. En consecuencia, tu cálculo será correcto o no dependiendo de qué teoría de conjuntos estés usando como soporte.

Como ves, toda esta discusión con lógicas de 2º orden (y de órdenes superiores) en un sentido absoluto se vuelve demasiado dependiente de supuestos filosóficos, lo cual es un motivo para no tomarla como base para fundamentar la matemática (aparte de que la noción de verdad de 2º orden te obliga a mojarte sobre todas las cuestiones de teoría de conjuntos, no es r.e., y muchas más propiedades indeseables).

Saludos

13 Enero, 2012, 12:56 am
Respuesta #6

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Gracias Óscar.

En el artículo hay unos cuantos ejemplos de formalizaciones de sentencias de teoría de conjuntos en lógica de segundo orden (existencia de inaccesibles, axioma de elección, GCH, etc).

Pues es verdad. No había seguido leyendo.

Es bueno observar que todo esto solo tiene sentido si uno tiene una posición filosófica cercana al platonismo, de manera que tiene sentido hablar de "teoría de conjuntos" y "lógica de segundo orden" en un sentido absoluto.

Sin embargo, me llama la atención la posición de Mosterín cuando dice que "no sabemos si la GCH es (o si queremos que sea) verdadera". Ahí parece estar aceptando que ese "sentido absoluto" puede ser en último extremo una mera cuestión de convenio. Me parece muy poco serio.

13 Enero, 2012, 07:37 pm
Respuesta #7

Raúl Aparicio Bustillo

  • $$\Large \color{#9c57a6}\pi\,\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 3,113
  • Karma: +0/-3
  • Sexo: Masculino
Citar
Es bueno observar que todo esto solo tiene sentido si uno tiene una posición filosófica cercana al platonismo

Entonces sin asumir el platonismo como posición filosófica  esta equivalencia entre fórmulas puras de segundo orden y fórmulas de ZFC ¿ya se vuelve un tanto controvertida o seguiría siendo cierta? Es que me surgen ciertas dudas pero claro, me surgen sólo si asumo al menos que mediante los axiomas (solo los lógicos , sin asumir ninguna teoría ni de segundo ni tampoco de primer orden, en particular ningun teorema de ZFC claro) y reglas de inferencia de algun cálculo deductivo correcto en segundo orden (no pongo la condición de que sea recursivo ,que creo que es lo que en inglés llaman "efectiveness", y que creo que se refiere a que en el caso de que el numero de axiomas es finito, o que si es infinito al menos el proceso de comprobar si una formula cualquiera es o no axioma si se pueda realizar en un número finito de pasos, lo cual implica en particular que los infinitos axiomas se puedan "resumir" en un número finito de esquemas axiomáticos y que el número de axiomas usados en la demo sean también finitos) se pueda realmente deducir alguna fórmula del lenguaje de  ZFC

Porque claro, si esto es así, entonces distingo 3 casos (sea A la fórmula deducida en concreto):

a) Que A sea teorema de ZFC, entonces está claro que esa fórmula ha de ser un teorema en cualquier teoría de conjuntos

b) Que \(   \lnot A  \)  sea teorema de ZFC, entonces ZFC es inconsistente

c) Que ni \(  t A  \)   ni \(   \lnot A  \)  sean teoremas de A. Entonces podemos (y debemos) añadir A a los axiomas de ZFC



14 Enero, 2012, 12:34 am
Respuesta #8

Óscar Matzerath

  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 567
  • Karma: +0/-0
  • Sexo: Masculino
Hola,

La verdad es que no me gusta mucho meterme en asuntos filosóficos como estos, que son más bien problema de un filósofo de la matemática.

Como ya digo, si uno tiene una posición realista, la única postura que a mí me parece sensata es no hablar de lógica de 2º orden en sentido absoluto y hacerlo únicamente como una lógica formalizada en una teoría de conjuntos, pongamos ZFC (aunque esto es discutible, como todo en estos asuntos filosóficos). En tal caso, la equivalencia entre sentencias de 2º orden y sentencias de 1º orden de la teoría de conjuntos funciona igual, solo que ahora esta equivalencia es un teorema de ZFC que habla sobre lógicas formalizadas en ZFC (que en el realidad no son más que conjuntos). Por supuesto, si lo haces en ZFC, ahora la sentencia de 2º orden que expresa "vale el axioma de elección" será lógicamente válida, mientras que la sentencia que expresa "vale GCH" no puedes saber si es lógicamente válida o no (en ZFC ni es teorema "la sentencia de 2º orden que expresa "vale GCH" es lógicamente válida" ni su negación).

Desde esta postura, no tiene sentido hablar de cálculos correctos de 2º orden fuera de ZFC (pues no existe la lógica de 2º orden en sentido absoluto). Moviéndose en el marco de lógica de 2º orden formalizada en ZFC, si en tu cálculo añades la sentencia de 2º orden que expresa (por ejemplo) la negación de AC, el cálculo no será correcto, mientras que si añades la sentencia de 2º orden que expresa que vale GCH no podrás saber si es correcto o no (no será un teorema de ZFC que tu cálculo es correcto, ni será teorema que tu cálculo no es correcto). Por cierto, observa que todo esto sólo tiene sentido como teoremas sobre un cálculo formalizado en ZFC (aunque el cálculo en sí mismo sí pueda tener sentido "absoluto", si es finito o recursivo).

Saludos

14 Enero, 2012, 12:29 pm
Respuesta #9

Raúl Aparicio Bustillo

  • $$\Large \color{#9c57a6}\pi\,\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 3,113
  • Karma: +0/-3
  • Sexo: Masculino
Citar
Desde esta postura, no tiene sentido hablar de cálculos correctos de 2º orden fuera de ZFC (pues no existe la lógica de 2º orden en sentido absoluto)

Mis problemas está en eso, que no veo la necesidad de usar ZFC para dar sentido a un cálculo deductivo de segundo orden. Pero bueno, creo que antes de seguir planteando cuestiones aquí en el foro sobre este tema voy a estudiar algo sobre ella, mirarme la referencia que me diste, etc...

Saludos