Rincón Matemático

Matemática => Lógica, Conjuntos, Lenguajes Formales => Lógica => Mensaje iniciado por: JordiMath en 26 Septiembre, 2020, 08:12 pm

Título: Teoría de Kripke-Platek
Publicado por: JordiMath en 26 Septiembre, 2020, 08:12 pm
En el libro de Carlos Ivorra de Lógica matemática leo en una página

Si γ es una fórmula \( \triangle{_0} \) de \( £{_a} \) entonces existe una fórmula γ* del tipo \( \triangle{_1} \) en KP.

Y en la página siguiente se dice:

Si γ es una fórmula \( \triangle{_0} \) de \( £_{tc} \) entonces \( γ{_a} \) es \( \triangle{_1} \) en \( IΣ1 \)

¿Al “traducir” cada fórmula al lenguaje de la otra teoría salta un nivel en la correspondiente jerarquía?


Por otro lado, como reflexión más general, planteo cómo entiendo lo que voy leyendo a ver si lo entiendo correctamente:

Por lo que veo, si partimos de los axiomas de la aritmética de Peano y mediante IΣ1 podemos construir conjuntos “creando” una relación de pertenencia y acabamos demostrando algunos axiomas de teoría de conjuntos.

Pero por otro lado, si partimos de los axiomas de teoría de conjuntos (Z* o KP, por ejemplo) llegamos a construir una teoría aritmética equivalente a la de Peano.

¿Es esa la idea de fondo?
Título: Re: Teoría de Kripke-Platek
Publicado por: Carlos Ivorra en 27 Septiembre, 2020, 12:38 am
En el libro de Carlos Ivorra de Lógica matemática leo en una página

Si γ es una fórmula \( \triangle{_0} \) de \( £{_a} \) entonces existe una fórmula γ* del tipo \( \triangle{_1} \) en KP.

Y en la página siguiente se dice:

Si γ es una fórmula \( \triangle{_0} \) de \( £_{tc} \) entonces \( γ{_a} \) es \( \triangle{_1} \) en \( IΣ1 \)

¿Al “traducir” cada fórmula al lenguaje de la otra teoría salta un nivel en la correspondiente jerarquía?

No exactamente. Eso sólo pasa en la base de la jerarquía. Lo que sucede es que, la fórmula \( x\in y \) es \( \Delta_0 \) en KP, pero para definir la relación de pertenencia en \( I\Sigma_1 \), necesitamos una fórmula \( \Delta_1 \). Y recíprocamente, las fórmulas \( z=x+y \), \( z=xy \), etc. son \( \Delta_0 \) en \( I\Sigma_1 \), pero para definirlas en KP necesitamos fórmulas \( \Delta_1 \).

Esto hace que suceda lo que dices: que al traducir fórmulas \( \Delta_0 \) de una teoría a la otra, se convierten en fórmulas \( \Delta_1 \), porque sustituimos conceptos primitivos, sin definición, que son trivialmente \( \Delta_0 \), por conceptos definidos no triviales cuya definición no puede ser menos que \( \Delta_1 \), pero ahí termina la diferencia de nivel.

Si traduces una fórmula \( \Delta_1 \) de una teoría a la otra, obtienes una fórmula \( \Delta_1 \), y lo mismo con fórmulas más complejas. Por ejemplo, la fórmula

\( \exists x\forall u\, u\notin y \)

es \( \Sigma_2 \) en KP, porque \( u\notin y \) es \( \Delta_0 \), al añadirle el \( \forall u \) pasa a ser \( \Pi_1 \) y al añadirle el \( \exists x \) pasa a ser \( \Sigma_2 \), pero su traducción aritmética también es \( \Sigma_2 \) (no aumenta su puesto en la jerarquía), porque ahora la traducción \( u\notin y \) ya no es \( \Delta_0 \), sino \( \Delta_1 \), pero al añadirle \( \forall u \) sigue siendo \( \Pi_1 \) y al añadirle \( \exists x \) sigue siendo \( \Sigma_2 \).

Por lo que veo, si partimos de los axiomas de la aritmética de Peano y mediante IΣ1 podemos construir conjuntos “creando” una relación de pertenencia y acabamos demostrando algunos axiomas de teoría de conjuntos.

Pero por otro lado, si partimos de los axiomas de teoría de conjuntos (Z* o KP, por ejemplo) llegamos a construir una teoría aritmética equivalente a la de Peano.

¿Es esa la idea de fondo?

Sí, pero cada oveja con su pareja: la teoría \( I\Sigma_1 \) es bastante más débil que AP. En \( I\Sigma_1 \) puedes definir una relación de pertenencia, de modo que los teoremas que puedes demostrar en \( I\Sigma_1 \) sobre dicha relación de pertenencia son exactamente los mismos que puedes demostrar en KP más el axioma "todo conjunto es finito".

En cambio, en AP puedes demostrar muchos teoremas más sobre dicha relación de pertenencia que en \( I\Sigma_1 \). Concretamente, los teoremas sobre la relación de pertenencia que puedes demostrar en AP son exactamente los mismos que puedes demostrar en la teoría ZF más el axioma "todo conjunto es finito".

Al revés tenemos algo similar: en KP puedes definir los números naturales, la suma, el producto, etc., y los teoremas sobre números naturales que puedes demostrar en KP son exactamente los mismos que puedes demostrar en \( I\Sigma_1 \). Para demostrar todos los teoremas demostrables en AP no te basta KP, sino que necesitas al menos \( Z^* \). Si pasas de \( Z^* \) a una teoría más fuerte, como ZF sin el axioma de infinitud, con eso puedes demostrar más teoremas, pero no más teoremas aritméticos. Los teoremas aritméticos que puedes probar en ambas teorías son los de AP, ni más ni menos.

La teoría KP tiene interés por muchos motivos, pero uno de ellos es que es equivalente, en el sentido que acabo de describir, a la teoría \( I\Sigma_1 \), que a su vez permite formalizar los razonamientos aritméticos que se consideran finitistas en el sentido más estricto del término (en el marco de la lógica clásica, pues hay quien pone más restricciones al finitismo basadas en negar principios lógicos como el tercio excluso, etc.)
Título: Re: Teoría de Kripke-Platek
Publicado por: JordiMath en 27 Septiembre, 2020, 03:00 pm
Muchas gracias por la explicación tan completa.

Una pequeña pregunta adicional. ¿Cuando hablamos de una teoría más fuerte significa que es una teoría que permite demostrar más teoremas? ¿Cuál es la definición de fortaleza cuando hablamos de una teoría?
Título: Re: Teoría de Kripke-Platek
Publicado por: Carlos Ivorra en 27 Septiembre, 2020, 03:05 pm
Una pequeña pregunta adicional. ¿Cuando hablamos de una teoría más fuerte significa que es una teoría que permite demostrar más teoremas? ¿Cuál es la definición de fortaleza cuando hablamos de una teoría?

He visto que en mi mensaje anterior había puesto AP donde tenía que haber puesto ZF. Al decir que ZF (menos el axioma de infinitud) es más fuerte que \( Z^* \) me refería simplemente a eso, a que en ella se pueden demostrar más teoremas, pero a veces se dice que una teoría A es "más fuerte" que otra B en el sentido de que en A se puede demostrar la consistencia de B, que es otra cosa.
Título: Re: Teoría de Kripke-Platek
Publicado por: JordiMath en 27 Septiembre, 2020, 03:15 pm
Vale, entiendo.

Entonces, ¿no hay ninguna teoría de conjuntos en que se puedan probar más teoremas aritméticos que los de AP?
Título: Re: Teoría de Kripke-Platek
Publicado por: Carlos Ivorra en 27 Septiembre, 2020, 03:21 pm
Entonces, ¿no hay ninguna teoría de conjuntos en que se puedan probar más teoremas aritméticos que los de AP?

Todo lo contrario. Lo que he dicho es que en ZF sin el axioma de infinitud (y, de hecho, en ZFC sin el axioma de infinitud) no se pueden demostrar ni más ni menos teoremas aritméticos que los de AP, pero en cuanto añades el axioma de infinitud ya puedes demostrar muchos otros teoremas aritméticos no demostrables en AP. El más obvio (en cuanto uno conoce los teoremas de incompletitud de Gödel) es la propia consistencia de AP, que es equivalente a una sentencia aritmética. Pero hay muchos más "elementales" en apariencia. Uno de los más conocidos es el teorema de Goodstein:

https://en.wikipedia.org/wiki/Goodstein's_theorem

Luego, si a ZFC le añades más axiomas, como la existencia de un cardinal inaccesible, todavía puedes demostrar más teoremas aritméticos.
Título: Re: Teoría de Kripke-Platek
Publicado por: sugata en 27 Septiembre, 2020, 04:03 pm
Off Topic, con permiso.

Carlos Ivorra, ¿tu libro es accesible  sin conocimientos previos de lógica?

Alguna vez he pensado en leerlo, pero la lógica me suele costar. Por eso pregunto si se necesita una base.

Perdón por el off topic
Título: Re: Teoría de Kripke-Platek
Publicado por: Carlos Ivorra en 27 Septiembre, 2020, 04:07 pm
Carlos Ivorra, ¿tu libro es accesible  sin conocimientos previos de lógica?

Teóricamente sí, en el sentido de que no supone nada conocido. Otra cosa es que, aunque he tratado de explicar todo lo más claramente posible, es bastante técnico. Quizá JordiMath te pueda dar una juicio más práctico que lo que yo pueda decir.

En cualquier caso, si lo coges y te surgen dudas, siempre puedes preguntarlas aquí.
Título: Re: Teoría de Kripke-Platek
Publicado por: JordiMath en 27 Septiembre, 2020, 04:52 pm
Bueno, yo tenía conocimientos de lógica proposicional que ayudan a ir más rápido, entiendo, pero en el libro también se explican.

En mi opinión, si tienes alguna base de conocimiento matemático, no necesariamente lógica, se puede leer y es perfectamente inteligible.

Me leí lo que era una versión anterior llamada “Lógica y teoría de conjuntos”, pero en los nuevos libros creo que Carlos ha separado en dos ese libro, con lo que dos libros resultantes creo que son más completos y entra más en detalle, con lo que creo que aún son más accesibles.
Título: Re: Teoría de Kripke-Platek
Publicado por: sugata en 27 Septiembre, 2020, 05:08 pm
Carlos Ivorra, ¿tu libro es accesible  sin conocimientos previos de lógica?

Teóricamente sí, en el sentido de que no supone nada conocido. Otra cosa es que, aunque he tratado de explicar todo lo más claramente posible, es bastante técnico. Quizá JordiMath te pueda dar una juicio más práctico que lo que yo pueda decir.

En cualquier caso, si lo coges y te surgen dudas, siempre puedes preguntarlas aquí.

Gracias. Me he acercado a tu libro, pero nunca en serio, en profundidad.
Me lo pongo en "siguientes"
Gracias Carlos Ivorra
Título: Re: Teoría de Kripke-Platek
Publicado por: JordiMath en 29 Septiembre, 2020, 04:47 pm
El esquema del pdf adjunto sería un esquema correcto según lo hablado en este post, Carlos?
Título: Re: Teoría de Kripke-Platek
Publicado por: JordiMath en 29 Septiembre, 2020, 06:09 pm
Sigo leyendo sobre KP.

¿Por qué no puede probarse en KP que todo conjunto es finito pero sí puede hacerse en \( IΣ_{1} \)?
Título: Re: Teoría de Kripke-Platek
Publicado por: Carlos Ivorra en 29 Septiembre, 2020, 09:39 pm
En \( I\Sigma_1 \) se demuestra que cada número natural puede identificar con un conjunto a través de su representación binaria, pero el desarrollo binario de un número natural tiene necesariamente un número finito de unos, luego el conjunto determinado por cualquier número natural es necesariamente finito.

En cambio KP es una teoría de conjuntos cuyos axiomas afirman que existen conjuntos que cumplen tales y cuales propiedades, pero no dicen nada sobre si hay o no conjuntos infinitos. Si añadimos como axioma que todo conjunto es finito, obtenemos una teoría totalmente equivalente a \( I\Sigma_1 \), en el sentido de que, por una parte, los teoremas sobre conjuntos que pueden demostrarse en \( I\Sigma_1 \) son exactamente los mismos que pueden probarse en KP más el axioma "todos los conjuntos son finitos" (en cierto modo, la respuesta a tu pregunta de por qué en KP no se puede demostrar que todo conjunto es finito es que porque falta añadir el axioma que afirma tal cosa) y, por otro lado, los teoremas sobre números naturales que pueden probarse en KP (y aquí da igual que añadas o no el axioma de que todo conjunto es finito) son los mismos que pueden demostrarse en \( I\Sigma_1 \).

Así pues, en \( I\Sigma_1 \) todo conjunto es finito porque un número natural sólo puede codificar conjuntos finitos, mientras que KP puede verse como la teoría que resulta de "extirpar" esa finitud inevitable en \( I\Sigma_1 \) y dejar abiertas las dos posibilidades: añadir como axioma que todo conjunto es finito, en cuyo caso tenemos la misma teoría de conjuntos que obtenemos de \( I\Sigma_1 \), pero también añadir como axioma que existen conjuntos infinitos, con lo que pasamos a una teoría mucho más potente, capaz de demostrar más teoremas sobre números naturales.

La idea es que:

1) Los teoremas demostrables en \( I\Sigma_1 \) o KP (más el axioma "todo conjunto es finito") son los demostrables en términos estrictamente finitistas y constructivos, en los que para justificar que existe un número o un conjunto, tienes que mostrar explícitamente cómo encontrarlo.

2) Los teoremas demostrables en AP o ZFC sin el axioma de infinitud más el axioma "todo conjunto es finito" se corresponden con los que se pueden demostrar sin recurrir a conjuntos infinitos arbitrarios (con argumentos que involucren sólo conjuntos finitos o, a lo sumo, conjuntos infinitos definibles explícitamente mediante fórmulas concretas).

3) Los teoremas demostrables en ZFC (sobre conjuntos o, en particular, sobre números naturales) son los que pueden demostrarse con argumentos que involucran conjuntos infinitos, pero sin partir de nada que un matemático (no metido a filósofo) no considere "asumible" sin reservas.

4) Pero todavía pueden demostrarse más teoremas sobre números naturales (plausiblemente verdaderos) si uno acepta axiomas adicionales que un matemático no consideraría "demostrables" o meramente "asumibles como algo evidente", como por ejemplo la posibilidad de extender la medida de Lebesgue a todos los subconjuntos de \( \mathbb R \).

Sí, el esquema que has subido se corresponde con la situación.
Título: Re: Teoría de Kripke-Platek
Publicado por: geómetracat en 29 Septiembre, 2020, 10:36 pm
4) Pero todavía pueden demostrarse más teoremas sobre números naturales (plausiblemente verdaderos) si uno acepta axiomas adicionales que un matemático no consideraría "demostrables" o meramente "asumibles como algo evidente", como por ejemplo la posibilidad de extender la medida de Lebesgue a todos los subconjuntos de \( \mathbb R \).

Sobre esto, tengo una curiosidad. ¿Se conocen teoremas "de interés aritmético" que no sean demostrables en ZFC pero sí en ZFC+axiomas adicionales, como cardinales grandes?
Por teoremas "de interés aritmético" me refiero a cosas del tipo teorema de Goodstein o teorema de Paris-Harrington, y no a cosas tipo \( Con(ZFC) \) (o equivalentes del tipo una ecuación diofántica horrible no tiene solución). No es algo muy bien definido pero espero que se entienda.
Título: Re: Teoría de Kripke-Platek
Publicado por: Carlos Ivorra en 29 Septiembre, 2020, 11:30 pm
Sobre esto, tengo una curiosidad. ¿Se conocen teoremas "de interés aritmético" que no sean demostrables en ZFC pero sí en ZFC+axiomas adicionales, como cardinales grandes?
Por teoremas "de interés aritmético" me refiero a cosas del tipo teorema de Goodstein o teorema de Paris-Harrington, y no a cosas tipo \( Con(ZFC) \) (o equivalentes del tipo una ecuación diofántica horrible no tiene solución). No es algo muy bien definido pero espero que se entienda.

Pues yo estaba pensando en cosas tipo \( Con(ZFC) \), pero al parecer también hay resultados finitistas "más o menos naturales". Recuerdo que hace unos años estuve buscando información sobre eso y todo lo que leía apuntaba hacia el trabajo de Friedman, pero sólo encontré referencias indirectas, enunciados sin demostración, o algunos tochos que había que tener mucho tiempo para leerlos y enterarse de algo. He vuelto a buscar ahora y he encontrado algunas cosas que parecen más asequibles, como esto:

https://arxiv.org/abs/math/9811187

No lo he leído. Lo acabo de encontrar ahora, pero lo he ojeado y la "Proposición B" parece totalmente finitista. Por lo visto Friedman tiene más resultados de este estilo, sobre grafos finitos y cosas así, pero, ya digo, cuando busqué hace tiempo, no encontré detalles. También es verdad que no debí de buscar muy bien, porque, por ejemplo, este artículo es de 1998.
Título: Re: Teoría de Kripke-Platek
Publicado por: geómetracat en 29 Septiembre, 2020, 11:59 pm
Muchas gracias, justo era el tipo de cosas que buscaba. Parece que Friedman es el único que ha hecho cosas en esta línea, pero me parece que requeriría bastante tiempo (al menos a mí) enterarse de los detalles.