Autor Tema: Teorema de recursión transfinita en ZF

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

22 Junio, 2021, 01:12 pm
Leído 1441 veces

Eparoh

  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 983
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Hola a todos, mi pregunta creo que sería la siguiente:

¿Es el teorema de recursión transfinita un teorema en ZF?

En los libros que he consultado en los que no se menciona nada sobre clases enuncian el teorema bajo un concepto ambiguo de "operación" que básicamente es una aplicación de \( V \) en si mismo, siendo \( V \) la clase de todos los conjuntos.

Por tanto, lo que quiero decir es que para establecer este teorema parece necesario emplear el concepto de clase propia para hablar de la clase de todos los conjuntos y de la clase de todos los ordinales en mayor o menor medida, con lo que ¿es posible formular y demostrar el teorema formalmente en ZF?

Un saludo y gracias por las respuestas.


22 Junio, 2021, 01:21 pm
Respuesta #1

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Todo enunciado que involucre clases propias (en realidad con algunas restricciones técnicas sobre la posibilidad de cuantificar sobre clases propias) puede expresarse sin clases propias como un esquema teoremático en el que cada clase se sustituye por la fórmula que la define.

No sé en qué versión concreta del teorema de recursión estás pensando. Como los detalles pueden ser distintos según cuál sea, creo que sería mejor que escribieras un enunciado con clases propias y vemos cómo se puede enunciar alternativamente sin clases propias.

22 Junio, 2021, 01:56 pm
Respuesta #2

Eparoh

  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 983
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Hola Carlos, ¿con esquema teoremático te refieres a decir que por cada elemento de la clase tenemos un teorema?

Una versión del teorema de recursión en la que pensaba al hacer la pregunta es la siguiente:

Si \( G \) es una función sobre \( V \) la clase de todos los conjuntos, entonces existe una única función \( F \) sobre \( \Omega \) la clase de todos los ordinales tal que

\( F(\alpha)=G(F|_\alpha) \)

donde \( F_\alpha=\{F(\gamma): \gamma < \alpha\} \).

Un saludo.

22 Junio, 2021, 02:03 pm
Respuesta #3

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Hola Carlos, ¿con esquema teoremático te refieres a decir que por cada elemento de la clase tenemos un teorema?

No. Me refiero a que para cada fórmula que pongamos en el enunciado tenemos un teorema. Esto quedará más claro al final cuando veamos el caso concreto que planteas, pero antes una duda:

donde \( F_\alpha=\{F(\gamma): \gamma < \alpha\} \).

¿Seguro?

Yo diría que \( F|_\alpha = \{(\gamma, F(\gamma))\mid \gamma<\alpha\} \).

Con tu definición alternativa el teorema también es cierto, pero supone debilitar el enunciado a lo tonto, porque así para definir \( F(\alpha) \) no puedes hacer referencia al valor que toma \( F \) sobre cada ordinal menor que \( \alpha \), sino al conjunto de todos los valores que toma, sin distinguir cuál es la imagen de cada ordinal.

22 Junio, 2021, 02:11 pm
Respuesta #4

Eparoh

  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 983
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
No. Me refiero a que para cada fórmula que pongamos en el enunciado tenemos un teorema. Esto quedará más claro al final cuando veamos el caso concreto que planteas

Vale, creo que entiendo a que te refieres.

donde \( F_\alpha=\{F(\gamma): \gamma < \alpha\} \).

¿Seguro?

Yo diría que \( F|_\alpha = \{(\gamma, F(\gamma))\mid \gamma<\alpha\} \).

Con tu definición alternativa el teorema también es cierto, pero supone debilitar el enunciado a lo tonto, porque así para definir \( F(\alpha) \) no puedes hacer referencia al valor que toma \( F \) sobre cada ordinal menor que \( \alpha \), sino al conjunto de todos los valores que toma, sin distinguir cuál es la imagen de cada ordinal.

Si perdona, efectivamente me refería a lo que propones.

Lo que quería decir es que \( F|_\alpha \) es efectivamente la restricción de \( F \) al ordinal \( \alpha \), es decir una sucesión transfinita sobre \( \alpha \) formada por las imágenes de \( F \) sobre cada elemento de \( \alpha \).

Un saludo.

22 Junio, 2021, 02:45 pm
Respuesta #5

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Bien, entonces tenemos:

Si \( G \) es una función sobre \( V \) la clase de todos los conjuntos, entonces existe una única función \( F \) sobre \( \Omega \) la clase de todos los ordinales tal que

\( F(\alpha)=G(F|_\alpha) \)

donde \( F_\alpha=\{(\gamma, F(\gamma)): \gamma < \alpha\} \).

Vamos a ir traduciendo. La clase \( G:V\longrightarrow V \) estará definida por una fórmula \( \phi(x, y,x_1,\ldots, x_n) \), es decir,

\( G=\{(x, y)\in V\times V\mid \phi(x, y,x_1,\ldots, x_n)\} \),

donde \( x_1,\ldots, x_n \) son posibles parámetros que pueden intervenir en la definición de \( G \).

Que \( G \) sea una función quiere decir que:

  • \( \forall x\exists y\,\phi(x, y,x_1,\ldots, x_n) \),
  • \( \forall xyz(\phi(x,y,x_1,\ldots, x_n)\land \phi(x, z,x_1,\ldots, x_n)\rightarrow y=z) \).

Llama \( \Phi(x_1,\ldots, x_n) \) a la conjunción de estas dos fórmulas, que es una fórmula sin clases propias.

Similarmente, la función \( F:\Omega\longrightarrow V \) estará definida por una fórmula \( \psi(\alpha, y,x_1,\ldots, x_n) \), de modo que

  • \( \forall\alpha(\alpha\in \Omega\rightarrow \exists y\,\psi(x, y,x_1,\ldots, x_n)) \),
  • \( \forall \alpha yz(\alpha\in \Omega\land \psi(x,y,x_1,\ldots, x_n)\land \psi(x, z,x_1,\ldots, x_n)\rightarrow y=z) \).

Llama \( \Psi(x_1,\ldots, x_n) \) a la conjunción de estas dos fórmulas, pero cambiando \( \alpha\in \Omega \) por la definición de ordinal, con lo que no queda ya ninguna clase propia.

La fórmula \( \chi(y, \alpha,x_1,\ldots, x_n)\equiv y=F|_\alpha \) es equivalente a

  • \( \forall u\in y\exists \delta\in \alpha\exists v(u=(\delta, v)\land \psi(\delta, v,x_1,\ldots, x_n)) \),
  • \( \forall \delta\in \alpha\exists v(\psi(\delta, v,x_1,\ldots, x_n)\land (\delta, v)\in y\) \).

La primera fórmula dice que todos los elementos de \( y=F|_\alpha \) son pares \( (\delta,v) \) tales que \( F(\delta)=v \), con \( \delta<\alpha \). La segunda dice que para todo \( \delta<\alpha \) el par \( (\delta, F(\delta)) \) está en \( y \).

Así, el enunciado del teorema de recursión queda así:

Para cada fórmula \( \phi(x, y,x_1,\ldots, x_n) \), es posible construir explícitamente otra fórmula \( \psi(\alpha, y, x_1,\ldots x_n) \) de modo que la fórmula siguiente es un teorema de ZF:

\( \forall x_1\cdots x_n(\Phi(x_1,\ldots, x_n)\rightarrow \Psi(x_1,\ldots, x_n)\land \forall \alpha\in \Omega\exists yz(\chi(y,\alpha,x_1,\ldots, x_n)\land \phi(y,z)\land \psi(\alpha,z)). \)

Esto significa: fijados unos parámetros, si la fórmula \( \phi \) define una función \( F \) sobre \( V \), entonces la fórmula \( \psi \) también define una función sobre los ordinales, y para cada ordinal \( \alpha \) existe un \( y \) tal que \( y=F|_\alpha \) y existe un \( z \) tal que \( z=G(y) \) y \( F(\alpha)=z \).

La única clase que ha quedado ahí es la de \( \alpha\in \Omega \), que de nuevo se puede sustituir por la definición de ordinal, y así ya no hay clases propias.

Esto es la existencia. El enunciado de la unicidad es que para cualquier fórmula \( \phi \) y cualquier par de fórmulas \( \psi \) y \( \psi' \), si se cumple lo anterior tanto con \( \psi \) como con \( \psi' \), entonces

\( \forall \alpha\in \Omega\exists z(\psi(\alpha,z,x_1,\ldots, x_n)\land \psi'(\alpha,z,x_1,\ldots, x_n)) \)

es decir, que hay un mismo \( z \) que cumple \( z=F(\alpha)=F'(\alpha) \), donde \( F \) y \( F' \) son las funciones definidas por \( \psi \) y \( \psi' \).

Si algo del galimatías no está claro, pregunta.

22 Junio, 2021, 03:04 pm
Respuesta #6

Eparoh

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

Creo que está todo claro, salvo un pequeño detalle sobre el que tengo dudas.

Así, el enunciado del teorema de recursión queda así:

Para cada fórmula \( \phi(x, y,x_1,\ldots, x_n) \), es posible construir explícitamente otra fórmula \( \psi(\alpha, y, x_1,\ldots x_n) \) de modo que la fórmula siguiente es un teorema de ZF:

\( \forall x_1\cdots x_n(\Phi(x_1,\ldots, x_n)\rightarrow \Psi(x_1,\ldots, x_n)\land \forall \alpha\in \Omega\exists yz(\chi(y,\alpha,x_1,\ldots, x_n)\land \phi(y,z)\land \psi(\alpha,z)). \)

Cuando aquí dices que es posible construir explícitamente otra formula tal que... Lo que estás diciendo es que dada la fórmula \( \phi(x, y,x_1,\ldots, x_n) \), siguiendo la demostración del teorema obtendríamos la fórmula \( \psi(\alpha, y, x_1,\ldots x_n) \) que es precisamente la que describe la función \( F \) al utilizar clases, ¿no?

Un saludo.

22 Junio, 2021, 03:06 pm
Respuesta #7

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Cuando aquí dices que es posible construir explícitamente otra formula tal que... Lo que estás diciendo es que dada la fórmula \( \phi(x, y,x_1,\ldots, x_n) \), siguiendo la demostración del teorema obtendríamos la fórmula \( \psi(\alpha, y, x_1,\ldots x_n) \) que es precisamente la que describe la función \( F \) al utilizar clases, ¿no?

Efectivamente.