Autor Tema: Definición de funcional por R-recursión (con R una relación bien fundada).

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

03 Enero, 2025, 05:31 am
Leído 683 veces

franma

  • $$\Large \color{#5b61b3}\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 1,655
  • País: uy
  • Karma: +2/-0
  • Sexo: Masculino
Buenas a todos,

Debo probar el siguiente enunciado:
Sea \( R \) una relación bien fundada sobre una clase \( U \). Si \( F \) es una clase funcional de dominio \( V \) entonces existe una clase funcional de dominio \( U \) tal que:
\( G(x) = F(\{G(y) : y\in R^{-1}(x) \}) \)

Bien, llamemos "buena función" a una función \( g \) cuyo dominio es \( \text{cl}_R(\{x\}) \) para algún \( x\in U \) y tal que \( g(y) = F(\{g(z): z\in R^{-1}(y)\}) \) (*) para todo \( y\in \text{cl}_R(\{x\}) \).

(*) esto tiene sentido porque si \( z\in R^{-1}(y) \) entonces \( zRy \) pero \( y\in \text{cl}_R(\{x\}) \) luego \( z\in\text{cl}_R(\{x\}) \)

Ahora, observemos que solo puede existir a lo sumo una "buena función" para cada \( x\in U \) pues si \( g \) y \( g' \) son dos tales funciones y llamamos:
\( C := \{y\in \text{cl}_R(\{x\}) : g(y)\neq g'(y)\} \)
Si fuera el caso que \( C\neq \emptyset \) por el post anterior existe \( y_0\in C \) que es \( R \)-minimal (es decir \( R^{-1}(y_0)\cap C =\emptyset \)), luego:
\( g(y_0) = F(\{g(y) : y\in R^{-1}(y_0)\}) = F(\{g'(y) : y\in R^{-1}(y_0)\}) = g'(y_0) \)
lo cual es absurdo pues \( y_0\in C \).

Ahora podemos considerar la clase \( G := \bigcup_{g\in BF(U)} g \) donde \( BF(U) \) son todas las "buenas funciones" de \( U \). Por lo anterior es claro que \( G \) es una funcional, ya que si \( g \) y \( g' \) son dos buenas funciones que están definidas en \( x \) entonces \( g|_{\text{cl}_R(\{x\})} \) y \( g'|_{\text{cl}_R(\{x\})} \) siguen siendo buenas funciones luego coinciden en \( x \). Pero no me sale ver que este definida en todo \( U \) :-[

¿Hasta aquí va bien? ¿Cómo podría terminar el argumento?

Saludos,
Franco.

03 Enero, 2025, 12:10 pm
Respuesta #1

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Sea \( R \) una relación bien fundada sobre una clase \( U \). Si \( F \) es una clase funcional de dominio \( V \) entonces existe una clase funcional de dominio \( U \) tal que:
\( G(x) = F(\{G(y) : y\in R^{-1}(x) \}) \)

Es una forma extraña de enunciarlo. Estás diciendo que puedes definir \( G(x) \) a partir del conjunto \( \{G(y) : y\in R^{-1}(x) \} \), cuando podrías decir que \( G(x) =F(G|_{R^{-1}(x)}) \), lo que significa que puedes definir \( {\color{red}G}(x) \) suponiendo que \( \color{red}G \) ya está definida sobre todos los elementos relacionados con \( x \), es decir, que tienes libertad para usar cada \( G(y) \) tal que \( y\,R\,x \) como quieras a la hora de definir \( {\color{red}G}(x) \), en lugar de restringirte a usar en bloque el conjunto \( \{G(y) : y\in R^{-1}(x) \} \). El enunciado que das es más débil y la prueba es exactamente igual que la versión fuerte.

Y, más en general aún, puedes pedir que \( G(x) = F(x, G|_{R^{-1}(x)}) \), para admitir que uses a \( x \) a la hora de definir \( G(x) \).


Bien, llamemos "buena función" a una función \( g \) cuyo dominio es \( \text{cl}_R(\{x\}) \) para algún \( x\in U \) y tal que \( g(y) = F(\{g(z): z\in R^{-1}(y)\}) \) (*) para todo \( y\in \text{cl}_R(\{x\}) \).

(*) esto tiene sentido porque si \( z\in R^{-1}(y) \) entonces \( zRy \) pero \( y\in \text{cl}_R(\{x\}) \) luego \( z\in\text{cl}_R(\{x\}) \)

Ahora, observemos que solo puede existir a lo sumo una "buena función" para cada \( x\in U \) pues si \( g \) y \( g' \) son dos tales funciones y llamamos:
\( C := \{y\in \text{cl}_R(\{x\}) : g(y)\neq g'(y)\} \)
Si fuera el caso que \( C\neq \emptyset \) por el post anterior existe \( y_0\in C \) que es \( R \)-minimal (es decir \( R^{-1}(y_0)\cap C =\emptyset \)), luego:
\( g(y_0) = F(\{g(y) : y\in R^{-1}(y_0)\}) = F(\{g'(y) : y\in R^{-1}(y_0)\}) = g'(y_0) \)
lo cual es absurdo pues \( y_0\in C \).

En realidad no necesitas el post anterior, porque \( C \) es un conjunto, luego tiene minimal por la propia definición de relación bien fundada.

Ahora podemos considerar la clase \( G := \bigcup_{g\in BF(U)} g \) donde \( BF(U) \) son todas las "buenas funciones" de \( U \). Por lo anterior es claro que \( G \) es una funcional, ya que si \( g \) y \( g' \) son dos buenas funciones que están definidas en \( x \) entonces \( g|_{\text{cl}_R(\{x\})} \) y \( g'|_{\text{cl}_R(\{x\})} \) siguen siendo buenas funciones luego coinciden en \( x \). Pero no me sale ver que este definida en todo \( U \) :-[

Aunque no importa el orden, antes de definir \( G \), podrías demostrar que, para cada \( x\in U \) existe una única \( g_x \) que es una buena función para \( x \), y eso luego te asegura que \( G \) está definida sobre todo \( U \).

Aquí tienes que considerar la clase \( C \) de los \( x\in U \) para los que no existe una buena función, y esta vez sí que necesitas el post anterior para asegurar que, si es no vacía, tiene un minimal \( x \).

Ahora usas que \( \mbox{cl}_R(\{x\}) = \{x\}\cup\bigcup\{\mbox{cl}_R(\{y\})\mid y\,R\, x\} \), y para cada \( y\,R\,x \) tienes que existe una (única) buena función \( g_y \) definida sobre \( \mbox{cl}_R(\{y\}) \), por lo que puedes definir \( g^*=\bigcup\limits_{y\,R\,x}g_y \), que es una función por la unicidad que has demostrado y está definida sobre \( \mbox{cl}_R(\{x\})\setminus \{x\} \).

Finalmente defines \( g_x = g^*\cup\{(x, F(\{g^*(y)\mid y\,R\,x\}))\} \) o, si quieres probar la versión fuerte que te he enunciado al principio, \( g_x = g^*\cup\{(x, F({\color{red}x,} g^*))\} \). Éste es el único cambio que requiere la demostración. En ambos casos se prueba igualmente que \( g_x \) es una buena función para \( x \), y así tienes una contradicción.

03 Enero, 2025, 10:00 pm
Respuesta #2

franma

  • $$\Large \color{#5b61b3}\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 1,655
  • País: uy
  • Karma: +2/-0
  • Sexo: Masculino
Hola Carlos :)

Es una forma extraña de enunciarlo. Estás diciendo que puedes definir \( G(x) \) a partir del conjunto \( \{G(y) : y\in R^{-1}(x) \} \), cuando podrías decir que \( G(x) =F(G|_{R^{-1}(x)}) \), lo que significa que puedes definir \( F(x) \) suponiendo que \( F \) ya está definida sobre todos los elementos relacionados con \( x \), es decir, que tienes libertad para usar cada \( G(y) \) tal que \( y\,R\,x \) como quieras a la hora de definir \( F(x) \), en lugar de restringirte a usar en bloque el conjunto \( \{G(y) : y\in R^{-1}(x) \} \). El enunciado que das es más débil y la prueba es exactamente igual que la versión fuerte.

Esto creo que no lo entiendo. No logro ver realmente cual es la diferencia entre ambas opciones, además, ¿no hay algunas F's que deberían de ser G's?

En realidad no necesitas el post anterior, porque \( C \) es un conjunto, luego tiene minimal por la propia definición de relación bien fundada.

Tienes razón.

Aunque no importa el orden, antes de definir \( G \), podrías demostrar que, para cada \( x\in U \) existe una única \( g_x \) que es una buena función para \( x \), y eso luego te asegura que \( G \) está definida sobre todo \( U \).

Aquí tienes que considerar la clase \( C \) de los \( x\in U \) para los que no existe una buena función, y esta vez sí que necesitas el post anterior para asegurar que, si es no vacía, tiene un minimal \( x \).

Ahora usas que \( \mbox{cl}_R(\{x\}) = \{x\}\cup\bigcup\{\mbox{cl}_R(\{y\})\mid y\,R\, x\} \), y para cada \( y\,R\,x \) tienes que existe una (única) buena función \( g_y \) definida sobre \( \mbox{cl}_R(\{y\}) \), por lo que puedes definir \( g^*=\bigcup\limits_{y\,R\,x}g_y \), que es una función por la unicidad que has demostrado y está definida sobre \( \mbox{cl}_R(\{x\})\setminus \{x\} \).

Finalmente defines \( g_x = g^*\cup\{(x, F(\{g^*(y)\mid y\,R\,x\}))\} \) o, si quieres probar la versión fuerte que te he enunciado al principio, \( g_x = g^*\cup\{(x, F(g^*))\} \). Éste es el único cambio que requiere la demostración. En ambos casos se prueba igualmente que \( g_x \) es una buena función para \( x \), y así tienes una contradicción.

Muy claro. Entendido.

Saludos,
Franco.

03 Enero, 2025, 10:23 pm
Respuesta #3

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Es una forma extraña de enunciarlo. Estás diciendo que puedes definir \( G(x) \) a partir del conjunto \( \{G(y) : y\in R^{-1}(x) \} \), cuando podrías decir que \( G(x) =F(G|_{R^{-1}(x)}) \), lo que significa que puedes definir \( {\color{red}G}(x) \) suponiendo que \( \color{red}G \) ya está definida sobre todos los elementos relacionados con \( x \), es decir, que tienes libertad para usar cada \( G(y) \) tal que \( y\,R\,x \) como quieras a la hora de definir \( F(x) \), en lugar de restringirte a usar en bloque el conjunto \( \{G(y) : y\in R^{-1}(x) \} \). El enunciado que das es más débil y la prueba es exactamente igual que la versión fuerte.

Esto creo que no lo entiendo. No logro ver realmente cual es la diferencia entre ambas opciones, además, ¿no hay algunas F's que deberían de ser G's?

Sí, había letras mal puestas. Ya lo he cambiado. La diferencia es que si pones \( G(x)=F(G|_{R^{-1}(x)}) \) estás diciendo que para definir \( G(x) \) puedes usar la función \( G|_{R^{-1}(x)} \) como quieras, mientras que con el enunciado que has puesto sólo puedes usar el conjunto \( \{G(y)\mid y\,R\,x\} \), que es una forma de usar \( G|_{R^{-1}(x)} \), pero no la única.

Por ejemplo, imagina que tienes una función \( H: U\longrightarrow \mbox{ON} \) inyectiva. Con el enunciado que te digo puedes definir \( G(x)=F(G(y)) \), donde \( y\in R^{-1}(x) \) es el elemento para el que \( H(y) \) es mínimo.

Esto es una definición válida por recursión, pero no encaja en tu enunciado, porque tu enunciado sólo te permite aplicar \( F \) al conjunto \( \{G(y)\mid y\,R\,x\} \), y no a un \( G(y) \) en particular.

Si tienes probado el teorema en general, para deducir tu caso particular basta aplicar el teorema general a la función \( F^*(g) = F(\mathcal Rg) \), donde \( \mathcal Rg =\{v\mid \exists u\, (u, v)\in g\} \) es el rango de \( g \). Porque así \( F^*(G|_{R^{-1}(x)})= F(\{G(y)\mid y\,R\,x\}) \).

03 Enero, 2025, 10:42 pm
Respuesta #4

franma

  • $$\Large \color{#5b61b3}\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 1,655
  • País: uy
  • Karma: +2/-0
  • Sexo: Masculino
Sí, había letras mal puestas. Ya lo he cambiado. La diferencia es que si pones \( G(x)=F(G|_{R^{-1}(x)}) \) estás diciendo que para definir \( G(x) \) puedes usar la función \( G|_{R^{-1}(x)} \) como quieras, mientras que con el enunciado que has puesto sólo puedes usar el conjunto \( \{G(y)\mid y\,R\,x\} \), que es una forma de usar \( G|_{R^{-1}(x)} \), pero no la única.

Perdona Carlos, pero no lo entiendo. ¿Lo que tu escribes no sería lo mismo que poner \( G(x) = F(\{(y,G(y)) : y\in R^{-1}(x)\}) \)? No entiendo eso de "usarlo como quiera".

Con el enunciado que te digo puedes definir \( G(x)=F(G(y)) \), donde \( y\in R^{-1}(x) \) es el elemento para el que \( H(y) \) es mínimo.

Esto es una definición válida por recursión, pero no encaja en tu enunciado, porque tu enunciado sólo te permite aplicar \( F \) al conjunto \( \{G(y)\mid y\,R\,x\} \), y no a un \( G(y) \) en particular.

Esto no lo veo.

Saludos,
Franco.

03 Enero, 2025, 11:41 pm
Respuesta #5

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
¿Lo que tu escribes no sería lo mismo que poner \( G(x) = F(\{(y,G(y)) : y\in R^{-1}(x)\}) \)?

Sí.

No entiendo eso de "usarlo como quiera".

Bueno, el ejemplo que te he puesto pretende ilustrarlo. A ver si aclarándolo te queda también claro esto en general:

Con el enunciado que te digo puedes definir \( G(x)=F(G(y)) \), donde \( y\in R^{-1}(x) \) es el elemento para el que \( H(y) \) es mínimo.

Esto es una definición válida por recursión, pero no encaja en tu enunciado, porque tu enunciado sólo te permite aplicar \( F \) al conjunto \( \{G(y)\mid y\,R\,x\} \), y no a un \( G(y) \) en particular.

Esto no lo veo.

Suponemos que tenemos \( F: U\longrightarrow V \) y \( H: U\longrightarrow \mbox{ON} \) inyectiva, y vamos a ver que si defino \( G: U\longrightarrow V \) mediante \( G(x)=F(G(y)) \), donde \( y \) es el elemento de \( R^{-1}(x) \) donde \( \color{red} H \) toma el valor mínimo, el teorema de recursión en la versión que yo te he enunciado justifica que existe una única función que cumple esto.

Para ello sólo tengo que definir \( F^*: U\longrightarrow V \) mediante

\( F^*(g)=F(g(H^{-1}(\min H[\mathcal Dg]))) \),

donde \( \mathcal Dg = \{u\mid \exists v\, (u, v)\in g\} \) es el dominio de \( g \).

El teorema me garantiza que existe una única \( G: U\longrightarrow V \) que cumple

\( G(x)=F^*(G|_{R^{-1}(x)})=F(G|_{R^{-1}(x)}(H^{-1}(\min H[\mathcal DG|_{R^{-1}(x)}])))=F(G|_{R^{-1}(x)}(H^{-1}(\min H[R^{-1}(x)])))=F(G(y)) \),

donde \( y = H^{-1}(\min H[R^{-1}(x)]) \), es decir, que \( H(y) \) es el mínimo de \( H[R^{-1}(x)] \) o, equivalentemente, de modo que \( y \) es el elemento de \( R^{-1}(x) \) donde \( H \) toma su valor mínimo. Por lo tanto, esta aplicación \( G \) es justo la que quería definir.

Ahora intenta justificar que esta \( G \) está bien definida usando tu enunciado. ¡Es imposible! Tendrías que definir una función \( F^*: U\longrightarrow V \) que, cuando se aplica a \( \{G(y)\mid y\,R\,x\} \), te dé \( F(G(y)) \), concretamente para el \( y \) que hace que \( H(y) \) sea mínimo.

Por concretar, imagina que \( R^{-1}(x) = \{a, b, c\} \), y que \( H(a)=1, H(b)=6, H(c) = 9 \). Pongamos además que \( G(a)=p, G(b)=q, G(c)=r \).

Necesitas definir \( F^* \) sin hacer referencia a \( G \) (porque queremos usar \( F^* \) para definir \( G \)), de modo que \( F^*(\{p, q, r\}) = F(p) \). Pero, ¿cómo puedes elegir \( p \) de \( \{p, q, r\} \) sin saber que \( G(a)=p, G(b)=q, G(c)=r \)? ¡No se puede! Si no conoces las antiimágenes por \( G \) de \( p, q, r \), no puedes saber que \( p \) es el que tiene la antiimagen donde \( H \) toma el valor mínimo.

Con el enunciado que te he puesto yo, todo cuadra, porque \( F^* \) no tiene que actuar sobre \( \{p,q,r\} \), sino sobre \( \{(a, p), (b, q), (c, r))\} \), y si te dan este dato, sí  que puedes conseguir que \( F^*(\{(a, p), (b, q), (c, r))\})=F(p) \) sin hacer referencia a \( G \) justo como yo he definido \( F^* \). Si llamas \( g = \{(a, p), (b, q), (c, r))\} \), calculamos \( \mathcal Dg = \{a, b, c\} \), calculamos \( H[\mathcal Dg] = \{1,6, 9\} \), calculamos \( \min H[\mathcal Dg] = 1 \), calculamos \( H^{-1}(\min H[\mathcal Dg]) = H^{-1}(1)=a \) y finalmente calculamos \( g(H^{-1}(\min H[\mathcal Dg]))= g(a)=p \), por lo que \( F^*(g)=F(p) \).

Pero no dejes que los tecnicismos te mareen. Te he detallado las definiciones al máximo para que veas que, en efecto, de una forma todo cuadra y de la otra no, pero nunca es necesario entrar en estos tecnicismos. Lo que te dice el teorema de recursión en la forma \( G(x)=F(G|_{R^{-1}(x)}) \) es que para definir \( G(x) \) puedes suponer definido \( G|_{R^{-1}(x)} \), es decir, que conoces todas las asignaciones \( y\mapsto G(y) \) para \( y\in R^{-1}(x) \). Si conoces esto, puedes calcular el \( y \) que tiene \( H(y) \) mínimo y calcular su imagen por \( G \), porque sabes cómo actúa \( G \) sobre cada elemento de \( R^{-1}(x) \).

En cambio, si pones \( G(x)=F(\{G(y)\mid y\,R\,x\}) \), tu único dato es el conjunto de imágenes \( A=\{G(y)\mid y\,R\,x\}=\{p, q, r\} \), pero sólo conoces ese conjunto, no sabes cómo actúa \( G \) sobre los elementos de \( R^{-1}(x) \), sólo sabes que, cuando \( G \) actúa sobre todos los elementos de \( R^{-1}(x) \), en total te sale el conjunto \( A \), pero no sabes quién es la antiimagen de cada elemento de \( A \), y en particular no puedes saber qué elemento de \( A \) procede del elemento de \( R^{-1}(x) \) en el que \( H \) toma el valor mínimo.

04 Enero, 2025, 09:59 pm
Respuesta #6

franma

  • $$\Large \color{#5b61b3}\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 1,655
  • País: uy
  • Karma: +2/-0
  • Sexo: Masculino
Hola Carlos,

Gracias por la explicación tan detallada, ya me ha quedado todo claro. Por cierto, a veces hablas de "el y donde G toma su valor mínimo" y otras veces de "el y donde H toma su valor mínimo", entiendo que querías la segunda, ¿no?. Aunque a efectos del ejemplo he entendido, tu versión del teorema nos da más información para definir G.

Saludos,
Franco.

04 Enero, 2025, 10:26 pm
Respuesta #7

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Gracias por la explicación tan detallada, ya me ha quedado todo claro. Por cierto, a veces hablas de "el y donde G toma su valor mínimo" y otras veces de "el y donde H toma su valor mínimo", entiendo que querías la segunda, ¿no?.

Sí. Sólo he encontrado un caso en el que había puesto G en vez de H y lo he arreglado.

04 Enero, 2025, 10:33 pm
Respuesta #8

franma

  • $$\Large \color{#5b61b3}\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 1,655
  • País: uy
  • Karma: +2/-0
  • Sexo: Masculino
Gracias por la explicación tan detallada, ya me ha quedado todo claro. Por cierto, a veces hablas de "el y donde G toma su valor mínimo" y otras veces de "el y donde H toma su valor mínimo", entiendo que querías la segunda, ¿no?.

Sí. Sólo he encontrado un caso en el que había puesto G en vez de H y lo he arreglado.

Tienes razón, me había parecido que eran más veces ::)

De nuevo, muchas gracias.

Saludos,
Franco.