Autor Tema: Duda sobre la jerarquía de Lévy

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

29 Febrero, 2024, 07:23 pm
Leído 1029 veces

Eparoh

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

Tengo una duda sobre las fórmulas de tipo \( \Sigma_n \) o \( \Pi_n \) en el lenguaje de la teoría de conjuntos respecto de una teoría axiomática T (en concreto, yo estoy trabajando en ZFC).

Por definición, una fórmula \( \phi \) de \( \mathcal{L}_{\text{tc}} \) se dice que es de tipo \( \Sigma_n \) (para el otro caso es análogo pero comenzando por un cuantificador universal en lugar del existencial), si existe una fórmula \( \alpha \) sin descriptores y con todos sus cuantificadores acotados de modo que

\( \underset{\text{T}}{\vdash} \phi \leftrightarrow \exists x_1 \forall x_2 \cdots \alpha \)

donde la cadena de cuantificadores se alterna \( n \) veces.

Ahora, mi duda es que a esta nueva fórmula no se le pide nada sobre sus variables libres, pero he visto que en algunas demostraciones se presupone que tiene las mismas variables libres que \( \phi \). Mi duda es entonces si se puede conseguir siempre esto. Diría que sí pues, al obtener una fórmula equivalente a la dada pero sin descriptor si se obtiene una nueva fórmula con las mismas variables libres, pero no llego a ver como probar esto en general.

Un saludo.

29 Febrero, 2024, 11:36 pm
Respuesta #1

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Pon que \( \phi(y_1, \ldots, y_m) \) tiene libres las variables indicadas, y es equivalente a \( \exists x_1\forall x_2\cdots \alpha(x_1,\ldots, x_n, y_1, \ldots, y_m, z_1,\ldots, z_r) \), con más variables libres \( z_i \). Observa que esto significa que la equivalencia se cumple para todos los \( y_i, z_j \). Entonces

\( \phi(y_1, \ldots, y_m)\leftrightarrow \exists z_1\cdots z_rx_1\forall x_2\cdots \alpha \)

Y la última fórmula es equivalente a otra de la forma \( \exists x\forall x_2\cdots \alpha(x, x_2,\ldots, y_1,\ldots, y_m) \), porque varios cuantificadores seguidos del mismo tipo se pueden contraer en uno solo. (Si no sabes esto lo hablamos, pero es un hecho básico sobre la jerarquía de Lévy, así que sospecho que lo sabrás.)

Esto prueba que puedes eliminar las variables que sobren. Si falta alguna \( y_i \), siempre puedes añadirla pasando a \( \alpha \land (y_i = y_i) \).

01 Marzo, 2024, 06:20 pm
Respuesta #2

Eparoh

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

Muchas gracias por las aclaraciones. Está todo claro, aunque esto

Y la última fórmula es equivalente a otra de la forma \( \exists x\forall x_2\cdots \alpha(x, x_2,\ldots, y_1,\ldots, y_m) \), porque varios cuantificadores seguidos del mismo tipo se pueden contraer en uno solo. (Si no sabes esto lo hablamos, pero es un hecho básico sobre la jerarquía de Lévy, así que sospecho que lo sabrás.)

no lo conozco realmente, ya que solo estoy utilizando esta jerarquía para "matar" de golpe que muchas expresiones son absolutas en modelos transitivos y solo he mirado un poco la definición y el resultado que me interesaba (y es donde me surgió la duda). Al comentarlo tú he mirado la demostración en tu libro, pero no termino de ver del todo estas equivalencias

\( \exists xy \beta \leftrightarrow \exists u \forall xy (u=(x,y) \rightarrow \beta) \leftrightarrow \exists u \forall x\in u \forall y \in u (u=(x,y) \rightarrow \beta) \)

Un saludo.

01 Marzo, 2024, 11:52 pm
Respuesta #3

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Al comentarlo tú he mirado la demostración en tu libro, pero no termino de ver del todo estas equivalencias

\( \exists xy \beta \leftrightarrow \exists u \forall xy (u=(x,y) \rightarrow \beta) \leftrightarrow \exists u \forall x\in u \forall y \in u (u=(x,y) \rightarrow \beta) \)

Mmm. En mi libro de lógica digo que eso se prueba análogamente al resultado correspondiente de la jerarquía de Kleene, pero no es tan análogo. La diferencia es que todo número natural se puede ver como un par ordenado, mientras que no todo conjunto es un par ordenado. Tengo que detallar el teorema para el caso de la jerarquía de Lévy. Hay que razonar inductivamente. Te indico aquí la idea considerando por ejemplo el caso de una fórmula \( \Sigma_3 \), es decir, de la forma \( \alpha(x)\equiv \exists x_1\forall x_2\exists x_3\beta(x, x_1, x_2, x_3) \), con \( \beta \) de tipo \( \Delta_0 \). Queremos ver que \( \exists x \alpha \) también es \( \Sigma_3 \). En efecto:

\( \exists x\alpha \leftrightarrow \exists xx_1\forall x_2\exists x_3\beta\leftrightarrow \exists w\exists z\in w\exists xx_1\in z(w = (x, x_1)\land \forall x_2\exists x_3\beta)\leftrightarrow\\\qquad \leftrightarrow\exists w\forall x_2\exists x_3\exists z\in w\exists xx_1\in z(w=(x, x_1)\land \beta) \),

y la última fórmula es \( \Sigma_3 \).

Los cuantificadores se pueden intercambiar porque \( w = (x, x_1) \) determina a \( z =\{x, x_1\} \) y a \( x, x_1 \). La implicación que no es inmediata es \( \leftarrow \).

Para probarla fijamos \( w \) que cumpla \( \forall x_2\exists x_3\exists z\in w\exists xx_1\in z(w=(x, x_1)\land \beta(x, x_1, x_2, x_3) \).

Tomamos \( x_2 = \emptyset \), con lo que existe un \( x_3\in w \) tal que existen \( z\in w \) y \( x, x_1\in z \) tales que \( w = (x_, x_1) \) y \( \beta(x, x_1, \emptyset, x_3) \).

Falta probar que \( \forall x_2\exists x_3\beta(x, x_1, x_2, x_3) \). Fijamos \( x_2 \), con lo que existe un \( x'_3 \) tal que existen \( z'\in w \) y \( x', x'_1\in z \) de modo que \( w = (x', x'_1) \) y \( \beta(x', x'_1, x_2, x'_3) \), pero como \( w=(x, x_1) = (x', x'_1) \), tenemos que \( x' = x, x'_1 = x_1 \), luego \( \beta(x, x_1, x_2, x'_3) \), luego \( \exists x_3\beta(x, x_1, x_2, x_3) \).

Con esto hemos probado que \( w = (x, x_1)\land \forall x_2\exists x_3\beta \), luego

\( \exists w\exists z\in w\exists xx_1\in z(w = (x, x_1)\land \forall x_2\exists x_3\beta). \)

La otra implicación es más simple, porque fijamos de antemano \( w, z, x, x_1 \) y entonces, para todo \( x_2 \) existe un \( x_3 \) tal que existen \( z, x, x_1 \) (los que tenemos fijados desde el principio) que cumplen \( w = (x, x_1)\land \beta \).

03 Marzo, 2024, 10:05 am
Respuesta #4

Eparoh

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

Muchas gracias por la respuesta. Creo que está todo aclarado, al menos he entendido la idea con el caso particular que propones. En cuanto tenga un poco de tiempo la semana que viene intentaré probar el caso general con estas nuevas anotaciones y veré si me surge alguna nueva duda.

Un saludo.

03 Marzo, 2024, 01:55 pm
Respuesta #5

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Creo que está todo aclarado, al menos he entendido la idea con el caso particular que propones. En cuanto tenga un poco de tiempo la semana que viene intentaré probar el caso general con estas nuevas anotaciones y veré si me surge alguna nueva duda.

He puesto en mi libro de lógica la demostración del teorema 6.2. El caso del cuantificador existencial lo he dejado para n = 3, como en este hilo, porque el caso general es idéntico. El único punto no inmediato es que si tienes \( \exists w\exists z\in w\exists xx_1\in x(w = (x, x_1)\land \cdots) \) los cuantificadores acotados se pueden intercambiar con otros cualesquiera porque \( x, x_1 \) están completamente determinados por \( w \), luego, aunque los metas dentro de otros cuantificadores y esto podría hacer que \( x, x_1 \) dependieran de los valores de otras variables, en realidad no es así, porque sólo dependen de \( w \).