Autor Tema: Jerarquía de Kleene

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

22 Septiembre, 2020, 09:41 pm
Leído 1386 veces

JordiMath

  • $$\Large \color{#5e8d56}\pi\,\pi\,\pi$$
  • Mensajes: 103
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
¿Las fórmulas con descriptor no afectan a la jerarquía de Kleene?

Leo que la fórmula:

\( <x,y>\equiv{z|2z=(x+y)(x+y+1)+2x} \)

es de tipo \( Δ_{0} \)

¿El descriptor no supone que pase a ser del tipo \( Σ_{1} \) al ser la descripción propia equivalente a un cuantificador existencial, aunque con unicidad?

24 Septiembre, 2020, 10:23 pm
Respuesta #1

Carlos Ivorra

  • Administrador
  • Mensajes: 9,668
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Tienes que distinguir entre fórmulas \( \Sigma_n, \Pi_n \) o \( \Delta_n \) en sentido estricto y las que lo son en sentido amplio por ser equivalentes (en una teoría dada) a fórmulas del tipo correspondiente en sentido estricto. Por ejemplo,

\( x\mid y \equiv \exists z\, y = xz \)

No es \( \Sigma_1 \) en sentido estricto, pero es \( \Sigma_1 \) porque

\( x\mid y \leftrightarrow \exists z\leq y\, y = xz \).

En cuanto a tu pregunta, por definición, las fórmulas \( \Sigma_n, \Pi_n \) o \( \Delta_n \) en sentido estricto no tienen descriptores, luego una fórmula con descriptores nunca puede ser de ninguno de estos tipos en sentido estricto. Ahora bien, puede serlo en sentido no estricto, y para situarla en la jerarquía de Kleene tenemos que eliminar los descriptores.

Por otro lado, yendo al ejemplo concreto que pones, \( <x, y> \) no es una fórmula \( \Delta_0 \), en sentido estricto ni no estricto, porque no es una fórmula, es un término. Por definición, un término \( t \) es \( \Delta_0 \) si lo es la fórmula \( z=t \), donde \( z \) es una variable que no esté en \( t \). En este caso,

\( z=\left<x,y\right>\leftrightarrow 2z=(x+y)(x+y+1)+2x \),

y la fórmula de la derecha es obviamente \( \Delta_0 \).

24 Septiembre, 2020, 11:11 pm
Respuesta #2

JordiMath

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