Autor Tema: Σ₁ completitud de Q

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

26 Octubre, 2020, 05:09 pm
Leído 1307 veces

JordiMath

  • $$\Large \color{#5e8d56}\pi\,\pi\,\pi$$
  • Mensajes: 103
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Según la \( Σ_{1} \)-completitud de Q, si una sentencia \( Σ_{1} \) es verdadera en ℕ, es demostrable en Q.

Por otro lado, toda teoría axiomática semirrecursiva T, que se cumple en ℕ, tiene una sentencia \( Σ_{1} \) o \( Π_{1} \), verdadera en ℕ, no demostrable ni refutable en T. Llamemos a esto “miniteorema de incompletitud de Gödel”.

Por lo primero, si tomamos una sentencia verdadera en ℕ, del tipo \( \exists{x}α \), con \( α \) de tipo \( Δ_{0} \), es demostrable en Q, por ser \( Σ_{1} \).

Por tanto, en Q, las únicas sentencias, verdaderas en ℕ, no demostrables serían del tipo \( \forall{x}α \), con \( α \) de tipo \( Δ_{0} \).

Pero esta sentencia sí sería refutable en Q. Es decir, si resultara que esta sentencia es falsa en ℕ, significaría que es cierto que \( ¬\forall{x}α \), con \( α \) de tipo \( Δ_{0} \), lo cual es lo mismo que \( \exists{x}¬α \), que sería una sentencia verdadera en ℕ, de tipo \( Σ_{1} \) y, por tanto, demostrable en Q.

Así pues, si hablamos de Q, el “miniteorema de incompletitud de Gödel” del segundo párrafo quedaría simplificado a:

En la teoría axiomática Q, que se cumple en ℕ, hay al menos una sentencia \( Π_{1} \), verdadera en ℕ, no demostrable en Q.

Dos preguntas:

1. ¿Sería correcto este planteamiento?

2. ¿Este sería el máximo nivel de completitud al que podemos llegar en una teoría axiomática semirrecursiva?

26 Octubre, 2020, 09:20 pm
Respuesta #1

Carlos Ivorra

  • Administrador
  • Mensajes: 9,669
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Según la \( Σ_{1} \)-completitud de Q, si una sentencia \( Σ_{1} \) es verdadera en ℕ, es demostrable en Q.

En efecto, pero no sé si eres consciente de la trivialidad de ese resultado. Una sentencia \( \Sigma_1 \) es algo del estilo de

\[ \exists n\,n^2+n=6\cdot n \]

Eso es verdad, pues se cumple para \( n= 5 \). Entonces, como obviamente puedes demostrar que \( 5^2+2=6\cdot 5 \), también puedes demostrar que \( \exists n\,n^2+n=6\cdot n \).

Es decir, si es verdad que existe un \( n \) que cumple una fórmula \( \Delta_0 \), encuéntralo (lo encontrarás seguro en un número finito de pasos), demuestra que ese \( n \) cumple lo requerido (que siempre se puede, porque las fórmulas \( \Delta_0 \) se pueden comprobar siempre en un número finito de pasos) y con eso tienes demostrada la existencia del \( n \). En suma, siempre puedes demostrar que existe un \( n \) encontrándolo explícitamente.

Por otro lado, toda teoría axiomática semirrecursiva T, que se cumple en ℕ, tiene una sentencia \( Σ_{1} \) o \( Π_{1} \), verdadera en ℕ, no demostrable ni refutable en T. Llamemos a esto “miniteorema de incompletitud de Gödel”.

Ahí hay que precisar que hablamos de una teoría sobre el lenguaje de la aritmética. Si no, no tendría sentido decir que tiene a \( \mathbb N \) por modelo.

Por lo primero, si tomamos una sentencia verdadera en ℕ, del tipo \( \exists{x}α \), con \( α \) de tipo \( Δ_{0} \), es demostrable en Q, por ser \( Σ_{1} \).

Por tanto, en Q, las únicas sentencias, verdaderas en ℕ, no demostrables serían del tipo \( \forall{x}α \), con \( α \) de tipo \( Δ_{0} \).

No, eso no es cierto, puedes tener sentencias no demostrables mucho más complicadas, de tipo \( \Sigma_n \) o \( \Pi_n \) para \( n \) todo lo grande que quieras.

Pero esta sentencia sí sería refutable en Q. Es decir, si resultara que esta sentencia es falsa en ℕ, significaría que es cierto que \( ¬\forall{x}α \), con \( α \) de tipo \( Δ_{0} \), lo cual es lo mismo que \( \exists{x}¬α \), que sería una sentencia verdadera en ℕ, de tipo \( Σ_{1} \) y, por tanto, demostrable en Q.

Así pues, si hablamos de Q, el “miniteorema de incompletitud de Gödel” del segundo párrafo quedaría simplificado a:

En la teoría axiomática Q, que se cumple en ℕ, hay al menos una sentencia \( Π_{1} \), verdadera en ℕ, no demostrable en Q.

Dos preguntas:

1. ¿Sería correcto este planteamiento?

Sí, es correcto. Más en general, si la teoría \( T \) extiende a \( Q \), entonces podemos asegurar que la sentencia en cuestión será \( \Pi_1 \).

Pero particularizar el teorema a \( Q \) no es una buena idea (otra cosa es a una extensión arbitraria de \( Q \)), porque ahí es trivial. Un ejemplo de sentencia \( \Pi_1 \) no demostrable en \( Q \) es

\[ \forall xy\, x+y=y+x \].

Y es que \( Q \) es una teoría muy, muy pobre.

2. ¿Este sería el máximo nivel de completitud al que podemos llegar en una teoría axiomática semirrecursiva?

Dicho así en general, sin ninguna conexión con la aritmética, es rotundamente falso. Existen muchas teorías axiomáticas recursivas completas, pero no permiten hablar de números naturales, o por lo menos, sólo de forma muy restringida. Por ejemplo, existen axiomatizaciones (recursivas) completas de la geometría euclídea elemental (donde "elemental" tiene un significado muy preciso destinado a excluir precisamente la posibilidad de hablar plenamente de números naturales en la teoría).

Ahora, en el caso de una teoría aritmética semirrecursiva, en efecto, siempre contendrá sentencias indecidibles de tipo \( \Pi_1 \) (y más complicadas también).

26 Octubre, 2020, 10:00 pm
Respuesta #2

JordiMath

  • $$\Large \color{#5e8d56}\pi\,\pi\,\pi$$
  • Mensajes: 103
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Entendido.

Muchas gracias!!