Autor Tema: Axiomatización finita

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

23 Septiembre, 2024, 07:58 pm
Leído 4016 veces

Eparoh

  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 982
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Hola a todos.

En este artículo se habla sobre un concepto de axiomatización finita que es distinto del usual (que el número de axiomas propios de la teoría es finito), pero no llego a entender muy bien que significa. ¿Alguien podría explicarlo y dar ejemplos de en que se distingue de la forma habitual de presentar la lógica de primer orden? ¿Es equivalente a esta o al menos a una parte de esta? (Porque el sistema S2 me recuerda un poco a lógica de segundo orden)

En particular, ¿cómo se puede formalizar ZFC y obtener que es finitamente axiomatizable utilizando esta formalización de la lógica predicativa?

Un saludo y gracias por las respuestas.

24 Septiembre, 2024, 12:13 am
Respuesta #1

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Lo he ojeado un poco y no entiendo lo que hace, entre otras cosas porque habla de una regla de inferencia D que no define, sino que remite a otros artículos.

24 Septiembre, 2024, 07:37 am
Respuesta #2

Eparoh

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

Si no lo entiendes tú...  ::)

Se supone que explica las reglas de inferencia D y G en la sección 3 y da algoritmos para ellas. La regla D parece como una especie de modus ponens y sustitución mezcladas, lo que pasa es que no me queda muy claro lo que hace tampoco a mi /:

Un saludo

24 Septiembre, 2024, 12:42 pm
Respuesta #3

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Se supone que explica las reglas de inferencia D y G en la sección 3 y da algoritmos para ellas. La regla D parece como una especie de modus ponens y sustitución mezcladas, lo que pasa es que no me queda muy claro lo que hace tampoco a mi /:

Sí, da unos algoritmos para las reglas, pero no son muy ilustrativos. Lo que hace es arreglárselas para que las variables puedan representar según el contexto proposiciones o individuos, de modo que en una misma fórmula una misma variable nunca cumple las dos funciones a la vez. Eso le permite expresar esquemas axiomáticos como axiomas individuales. En la sección 10 pone el axioma que se supone que equivale al esquema del reemplazo, aunque yo no lo entiendo.

24 Septiembre, 2024, 03:12 pm
Respuesta #4

Eparoh

  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 982
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Hola Carlos.

Gracias por echarle un vistazo, pero me reitero en que si tú no lo entiendes, poco aspiro yo ahora mismo a entenderlo. Esa manía de escribir papers de forma críptica  :-\

Lo guardaré para el futuro, porque no deja de parecerme interesante la idea.

Un saludo.

24 Septiembre, 2024, 06:37 pm
Respuesta #5

Guli-Guli

  • «―»
  • $$\Large \color{#5e8d56}\pi\,\pi\,\pi$$
  • Mensajes: 264
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Por aportar algo a este asunto, encontré este artículo de Wikipedia sobre la regla D: Condensed detachment

Ahí aparece una sección llamada Advantages que dice lo siguiente:

Citar
For automated theorem proving condensed detachment has a number of advantages over raw modus ponens and uniform substitution.

At a Modus Ponens and substitution proof you have an infinite number of choices for what you can substitute for variables. This means that you have an infinite number of possible next steps. With condensed detachment there are only a finite number of possible next steps in a proof.

The D-notation for complete condensed detachment proofs allows easy description of proofs for cataloging and search. A typical complete 30 step proof is less than 60 characters long in D-notation (excluding the statement of the axioms.)

Creo que aquí está la clave: las reglas D y G sólo permiten inferir un número finito de posibles pasos en el sistema S1, que es imprescindible para saber si una teoría axiomática es finitamente axiomatizada en el sentido fuerte que se define en el artículo de Norman D. Megill.

¿Alguien podría explicarlo y dar ejemplos de en que se distingue de la forma habitual de presentar la lógica de primer orden? ¿Es equivalente a esta o al menos a una parte de esta? (Porque el sistema S2 me recuerda un poco a lógica de segundo orden.)

En particular, ¿cómo se puede formalizar ZFC y obtener que es finitamente axiomatizable utilizando esta formalización de la lógica predicativa?

Pues que ser finitamente axiomatizable a la Megill es una condición más fuerte que ser finitamente axiomatizable en el sentido usual, ya que la segunda sólo pides que haya un número finito de axiomas no lógicos, mientras que la primera sí que necesitas que haya también un número finito de axiomas lógicos.

El sistema S1 tiene catorce axiomas lógicos, por lo que puedes transformar una teoría finitamente axiomatizable en el sentido usual en otra que sea finitamente axiomatizable en el sentido fuerte "pasándolo" al sistema S1 u otro equivalente (S2, por ejemplo).

Sí, el sistema S2 es simplemente una lógica de segundo orden que equivale al sistema S1. Yo diría que esto es fundamental por una razón: se puede transformar cualquier teoría axiomática formulada en la lógica de primer orden por otra de segundo orden mediante la extensión predicativa. Esto es importante para el caso de la teoría ZFC: su extensión predicativa es finitamente axiomatizable en el sentido usual (pues es NBG). Así, "metes" esos axiomas en S2 y obtienes una formulación ZFC que resulta ser finitamente axiomatizable en el sentido de Megill.

A ver si con esto te sirva de ayuda en algo, Eparoh.

Posdata:
Creo que he detectado una errata en la fórmula que aparece en la sección 10 del artículo de Magill: en vez de \( \forall{x}\exists{z}\forall{y} \) que aparece en el medio debería ser simplemente \( \forall{x}\forall{y} \). Me parece curioso que los revisores pasaran esto por alto.

24 Septiembre, 2024, 07:27 pm
Respuesta #6

Eparoh

  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 982
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Hola Guli-Guli.

En ese artículo de Wikipedia tampoco se explica claramente lo que es la regla D (y sigo sin ver que es, como se aplica y para que sirve  ::)) y sigo sin ver su relación con el modus ponens.

Todo lo que comentas es más o menos lo que pone en el artículo, pero no lo veo claro. Por ejemplo, no llego a entender completamente que significa que en una demostración haya únicamente una cantidad finita de posibles pasos a dar. Me gustaría ver un ejemplo de como esto se da con el sistema S1, pero no con las reglas de inferencia usuales para ver si así consigo entenderlo.

Un saludo.

24 Septiembre, 2024, 10:01 pm
Respuesta #7

Guli-Guli

  • «―»
  • $$\Large \color{#5e8d56}\pi\,\pi\,\pi$$
  • Mensajes: 264
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
En ese artículo de Wikipedia tampoco se explica claramente lo que es la regla D y sigo sin ver su relación con el modus ponens.

Te paso un artículo que explica con mucho detalle la regla D por si quieres echar un vistazo: Principal Type-Schemes and Condensed Detashment

También te paso el artículo Weaker D-Complete Logics que define la regla D de forma básica (de hecho, remite al primer artículo que enlacé aquí), pero se ve que esta regla es una especie de modus ponens combinado con sustituciones previas.

Me gustaría ver un ejemplo de como esto se da con el sistema S1, pero no con las reglas de inferencia usuales para ver si así consigo entenderlo.

El segundo artículo ejemplifica el uso de esta regla en una lógica proposicional (no es exactamente S1, pero para entender la regla D da lo mismo, creo).

Por ejemplo, no llego a entender completamente que significa que en una demostración haya únicamente una cantidad finita de posibles pasos a dar.

Eso no es lo que se dice en el artículo de Margill. El autor define teoría finitamente axiomatizable como teoría axiomática donde cada paso de una demostración cualquiera admite una cantidad finita de elecciones.

Por ejemplo, si tienes una demostración donde en un determinado paso se aplica la regla de sustitución, entonces tienes infinitas formas de llegar a la misma demostración: tantas como variables a sustituir.

La regla D no tiene ese fenómeno, o al menos eso dice la Wikipedia. Entiendo que será porque la regla, detallada en el primer artículo enlazado, pide condiciones muy restrictivas para poder ser aplicada.

(y sigo sin ver que es, como se aplica y para que sirve  ::))

Para qué sirve no tengo ni idea. Lo que sí te digo es que eso de hallar una teoría finitamente axiomatizable para ZFC me parece una excusa barata por parte autor para justificar el uso de la regla D.

Esto es así porque existe otra forma de generalizar el concepto de teoría finitamente axiomatizable que se hizo toda la vida: hallando su extensión predicativa al pasarlo a la lógica de segundo orden y viendo si esa extensión es conservativa y finitamente axiomatizable.

Por ejemplo, las teorías de primer orden ZFC y AP no son finitamente axiomatizables, pero si lo son al pasarlos a sus respectivas extensiones conservativas BNG y ACA\( {}_0 \).

Lo único que hace el sistema S1 es forzar a que la lógica subyacente siga siendo la lógica de primer orden. Pero ya digo, es forzarlo mucho.

Todo lo que digo aquí son ideas que saco por si te sirve de algo, no es que lo tenga estudiado a detalle como un experto en estos temas. Esto es todo lo que te puedo aportar, Eparoh.

26 Septiembre, 2024, 12:14 pm
Respuesta #8

Eparoh

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

Muchas gracias por las referencias Guli-Guli. Les echaré un vistazo.

Un saludo.