Autor Tema: Dudas sobre Jerarquía de Levy

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

06 Julio, 2017, 05:07 pm
Leído 1077 veces

alexpglez

  • Novato
  • Mensajes: 119
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Buenas tardes!
Estoy leyendo el libro de Carlos Ivorra sobre lógica (pág 154), y había cuestiones en la jerarquía de Levy que no me quedaban claras.

No me queda muy claro el significado de [texx] \sum_n^T [/texx] y de las demás familias de fórmulas. Interpreto que quiere decir que la fórmula equivale a una traducción de una fórmula [texx] \sum_n [/texx] del lenguaje de la aritmética natural al lenguaje de la teoría T. Pero me da la impresión de que esto no es lo que significa.

Después hay un teorema que no comprendo del todo, en concreto los incisos a) y b):
"a) Si α, β son Σ n , Π n , lo mismo vale para α ∧ β y α ∨ β"
"b) Si α es Π n (resp. Σ n ) y β es Σ n (resp. Π n ), α → β es Σ n (resp. Π n )"

¿En el apartado a) las proposiciones [texx] \alpha [/texx] y [texx] \beta [/texx] son del mismo tipo, y la conjunción y la disjunción aparecen del mismo tipo?
¿En el apartado b), si [texx] \alpha [/texx] es [texx] \Pi_n [/texx] y [texx] \beta [/texx] es [texx] \Sigma_n [/texx], entonces [texx] \alpha \rightarrow \beta [/texx] es [texx] \Sigma_n [/texx]? (Y respectivamente siendo las proposiciones de tipo [texx] \Sigma_n [/texx] y [texx] \Pi_n [/texx], la implicación es [texx] \Sigma_n [/texx])

En caso de ser verdaderas las respuestas, ¿el teorema entonces no sirve para otra combinación de tipos, por ejemplo la conjunción de tipo Sigma y tipo Pi?

Gracias, saludos

06 Julio, 2017, 05:50 pm
Respuesta #1

Carlos Ivorra

  • Administrador
  • Mensajes: 9,079
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
No me queda muy claro el significado de [texx] \sum_n^T [/texx] y de las demás familias de fórmulas. Interpreto que quiere decir que la fórmula equivale a una traducción de una fórmula [texx] \sum_n [/texx] del lenguaje de la aritmética natural al lenguaje de la teoría T. Pero me da la impresión de que esto no es lo que significa.

Sí, pero lo fundamental es lo de "equivale". Una misma fórmula puede ser equivalente a una fórmula de un cierto tipo a partir de unos axiomas y no serlo a partir de otros.

Después hay un teorema que no comprendo del todo, en concreto los incisos a) y b):
"a) Si α, β son Σ n , Π n , lo mismo vale para α ∧ β y α ∨ β"
"b) Si α es Π n (resp. Σ n ) y β es Σ n (resp. Π n ), α → β es Σ n (resp. Π n )"

¿En el apartado a) las proposiciones [texx] \alpha [/texx] y [texx] \beta [/texx] son del mismo tipo, y la conjunción y la disjunción aparecen del mismo tipo?

Sí, no sé si entiendo tu duda. Lo que dice es que si las dos fórmulas son \( \Sigma_n \) o las dos son \( \Pi_n \) entonces la conjunción y la disyunción son del mismo tipo.

¿En el apartado b), si [texx] \alpha [/texx] es [texx] \Pi_n [/texx] y [texx] \beta [/texx] es [texx] \Sigma_n [/texx], entonces [texx] \alpha \rightarrow \beta [/texx] es [texx] \Sigma_n [/texx]? (Y respectivamente siendo las proposiciones de tipo [texx] \Sigma_n [/texx] y [texx] \Pi_n [/texx], la implicación es [texx] \Sigma_n [/texx])

La última [texx] \Sigma_n [/texx] que pones es una [texx] \Pi_n [/texx]. Observa que es consecuencia inmediata del apartado anterior, porque \( \alpha\rightarrow \beta \) es lógicamente equivalente a \( \lnot \alpha\lor \beta \). Como las disyunciones conservan la posición en la jerarquía, sólo hay que tener en cuenta que las implicaciones esconden una negación, que transforma \( \Sigma \) en \( \Pi \) y viceversa.

En caso de ser verdaderas las respuestas, ¿el teorema entonces no sirve para otra combinación de tipos, por ejemplo la conjunción de tipo Sigma y tipo Pi?

Si tienes la conjunción de una fórmula de tipo \( \Sigma_n \) con otra de tipo \( \Pi_n \), entonces ambas son de tipo \( \Sigma_{n+1} \) y de tipo \( \Pi_{n+1} \), luego la conjunción es \( \Sigma_{n+1} \) y \( \Pi_{n+1} \), luego es \( \Delta_{n+1} \).

06 Julio, 2017, 07:22 pm
Respuesta #2

alexpglez

  • Novato
  • Mensajes: 119
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Si tienes la conjunción de una fórmula de tipo \( \Sigma_n \) con otra de tipo \( \Pi_n \), entonces ambas son de tipo \( \Sigma_{n+1} \) y de tipo \( \Pi_{n+1} \), luego la conjunción es \( \Sigma_{n+1} \) y \( \Pi_{n+1} \), luego es \( \Delta_{n+1} \).

Vale creo que entiendo. Lo que haces es dar un teorema para ciertos casos particulares que junto IG e IP al principio o al final (sobre variables que no están en la fórmula), damos una clasificación para toda fórmula.

Tenía otra duda referente a la demostración del teorema. Copio literalmente:
"Ahora tomemos fórmulas α y β equivalentes a fórmulas [texx] \exists x \alpha' [/texx] y \(  \exists y \beta' \), respectivamente, con \( \alpha' \)y \(  \beta'  \) de tipo [texx] \Pi_n [/texx]. Podemos suponer..."
Entiendo que las fórmulas de partida son \(  \Sigma_{n+1}  \). ¿Es así?

¿La demostración para fórmulas de tipo \(  \Pi_{n+1}  \) sería equivalente, sólo que sustituyendo los símbolos \(  \exists  \) por \(  \forall  \)?

06 Julio, 2017, 08:40 pm
Respuesta #3

Carlos Ivorra

  • Administrador
  • Mensajes: 9,079
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Vale creo que entiendo. Lo que haces es dar un teorema para ciertos casos particulares que junto IG e IP al principio o al final (sobre variables que no están en la fórmula), damos una clasificación para toda fórmula.

No sé si te sigo, pero me da la sensación de que tu duda es si toda fórmula aritmética está en algún nivel de la jerarquía de Kleene. La respuesta es afirmativa, pero eso no depende del teorema por el que preguntas, sino que es consecuencia del teorema 2.15, según el cual toda fórmula es lógicamente equivalente a una fórmula en forma prenexa, es decir, formada por una sucesión de cuantificadores y una fórmula sin cuantificadores (que en particular es \( \Delta_0 \)).

El teorema 5.18 sirve para reconocer "a simple vista" en muchos casos la posición de una fórmula dada en dicha jerarquía.


Tenía otra duda referente a la demostración del teorema. Copio literalmente:
"Ahora tomemos fórmulas α y β equivalentes a fórmulas [texx] \exists x \alpha' [/texx] y \(  \exists y \beta' \), respectivamente, con \( \alpha' \)y \(  \beta'  \) de tipo [texx] \Pi_n [/texx]. Podemos suponer..."
Entiendo que las fórmulas de partida son \(  \Sigma_{n+1}  \). ¿Es así?

Sí, pero no entiendo tu duda, así que sospecho que se me escapa algo. Si \( \alpha' \)y \(  \beta'  \) las tomamos de tipo [texx] \Pi_n [/texx], entonces [texx] \exists x \alpha' [/texx] y \(  \exists y \beta' \) son \(  \Sigma_{n+1}  \) por definición. ¿Qué es lo que te lleva a preguntar si es así? Quiero decir que es tan obvio que si lo preguntas es porque algo se te escapa y no logro ver lo que es, para aclarártelo.

¿La demostración para fórmulas de tipo \(  \Pi_{n+1}  \) sería equivalente, sólo que sustituyendo los símbolos \(  \exists  \) por \(  \forall  \)?

Es una opción. La otra es observar que si \( \alpha,\beta \) son \( \Pi_n \), entonces \( \lnot\alpha,\lnot\beta \) son \( \Sigma_n \), luego \( \lnot\alpha\land\lnot \beta \) y \( \lnot\alpha\lor\lnot\beta \) son \( \Sigma_n \), luego sus negaciones son \( \Pi_n \), pero éstas son equivalentes a \( \alpha\lor\beta, \alpha\land \beta \).

Por cierto, aunque es casi lo mismo, me estás preguntado por la jerarquía de Kleene, no la de Lévy.

06 Agosto, 2017, 11:17 pm
Respuesta #4

alexpglez

  • Novato
  • Mensajes: 119
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Hola Carlos, se me pasó responder.

Ya entiendo todo lo referente a la jerarquía de Kleene.

Creo que lo que preguntaba sobre las fórmulas alpha y beta era si se tomaban de esa manera para demostrar. Me confundió el hecho de que, mientras en unos teoremas la demostración es "suponiendo que [texx] a [/texx] es [texx] \Sigma_{n+1} [/texx] entonces existe por definición otra fórmula [texx] a' [/texx], [texx] \Pi_n [/texx] que [texx] a \equiv \exists x a' [/texx]...", y en este se daban menos detalles (no los suficientes para mí, por lo que veo).

Sobre el teorema sobre las fórmulas prenexas. Así "a secas", no implica que todas estén en un puesto en la jerarquía de Kleene, (por ejemplo [texx] \forall x \forall y \phi [/texx] con [texx] \phi [/texx] [texx] \Delta_0 [/texx]). Si no utilizando el teorema del par. (O al menos lo que entiendo es que todos los cuantificadores tienen que estar alternados).

Gracias por todo nuevamente Carlos.

06 Agosto, 2017, 11:31 pm
Respuesta #5

Carlos Ivorra

  • Administrador
  • Mensajes: 9,079
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Sobre el teorema sobre las fórmulas prenexas. Así "a secas", no implica que todas estén en un puesto en la jerarquía de Kleene, (por ejemplo [texx] \forall x \forall y \phi [/texx] con [texx] \phi [/texx] [texx] \Delta_0 [/texx]). Si no utilizando el teorema del par. (O al menos lo que entiendo es que todos los cuantificadores tienen que estar alternados).

Sí, claro. La jerarquía de Kleene está pensada para trabajar en una teoría aritmética mínimamente razonable (como IA), y eso incluye al teorema del par. Si no, habría que definir una fórmula \( \sigma_n \) como una fórmula con un bloque de cuantificadores existenciales, seguido de otro bloque de cuantificadores universales, y así alternando n bloques y luego una fórmula \( \Delta_0 \), pero se da ya la definición con cuantificadores alternados porque con hipótesis mínimas (que siempre vamos a suponer) es equivalente.