Teorema del punto fijo de Kleene

Teorema de la teoría del orden y la teoría de la red.

Cálculo del punto mínimo de fijación de f ( x ) = ⁠1/10⁠ x ² + atan ( x )+1 usando el teorema de Kleene en el intervalo real [0,7] con el orden habitual

En las áreas matemáticas del orden y la teoría de la red , el teorema del punto fijo de Kleene , que lleva el nombre del matemático estadounidense Stephen Cole Kleene , establece lo siguiente:

Teorema del punto fijo de Kleene. Supongamos que es un orden parcial completo dirigido (dcpo) con un elemento mínimo, y sea una función continua de Scott (y por lo tanto monótona ) . Luego tiene un punto mínimo fijo , que es el supremo de la cadena ascendente de Kleene. ${\displaystyle (L,\sqsubseteq )}$ ${\displaystyle f:L\to L}$ ${\displaystyle f}$ ${\displaystyle f.}$

La cadena ascendente de Kleene de f es la cadena

${\displaystyle \bot \sqsubseteq f(\bot )\sqsubseteq f(f(\bot ))\sqsubseteq \cdots \sqsubseteq f^{n}(\bot )\sqsubseteq \cdots }$

obtenido iterando f en el elemento mínimo ⊥ de L . Expresado en una fórmula, el teorema establece que

${\displaystyle {\textrm {lfp}}(f)=\sup \left(\left\{f^{n}(\bot )\mid n\in \mathbb {N} \right\}\right)}$

donde denota el punto menos fijo. ${\displaystyle {\textrm {lfp}}}$

Aunque el teorema del punto fijo de Tarski no considera cómo se pueden calcular los puntos fijos iterando f a partir de alguna semilla (además, pertenece a funciones monótonas en redes completas ), este resultado a menudo se atribuye a Alfred Tarski , quien lo demuestra para funciones aditivas. ^[1] Además, el teorema del punto fijo de Kleene se puede extender a funciones monótonas utilizando iteraciones transfinitas. ^[2]

Prueba[3]

Primero tenemos que demostrar que la cadena ascendente de Kleene existe en . Para demostrarlo, demostramos lo siguiente: ${\displaystyle f}$ ${\displaystyle L}$

Lema. Si es un dcpo con un elemento mínimo y es continuo de Scott, entonces ${\displaystyle L}$ ${\displaystyle f:L\to L}$ ${\displaystyle f^{n}(\bot )\sqsubseteq f^{n+1}(\bot ),n\in \mathbb {N} _{0}}$

Prueba. Usamos inducción:

• Supongamos que n = 0. Entonces desde es el elemento mínimo. ${\displaystyle f^{0}(\bot )=\bot \sqsubseteq f^{1}(\bot ),}$ ${\displaystyle \bot }$
• Supongamos que n > 0. Entonces tenemos que demostrar que . Reordenando obtenemos . Por suposición inductiva, sabemos que eso se cumple, y debido a que f es monótona (propiedad de las funciones continuas de Scott), el resultado también se cumple. ${\displaystyle f^{n}(\bot )\sqsubseteq f^{n+1}(\bot )}$ ${\displaystyle f(f^{n-1}(\bot ))\sqsubseteq f(f^{n}(\bot ))}$ ${\displaystyle f^{n-1}(\bot )\sqsubseteq f^{n}(\bot )}$

Como corolario del Lema tenemos la siguiente cadena ω dirigida:

${\displaystyle \mathbb {M} =\{\bot ,f(\bot ),f(f(\bot )),\ldots \}.}$

De la definición de un dcpo se deduce que tiene un supremo, llámelo. Lo que queda ahora es demostrar que es el punto menos fijo. ${\displaystyle \mathbb {M} }$ ${\displaystyle m.}$ ${\displaystyle m}$

Primero, demostramos que es un punto fijo, es decir, que . Porque es Scott-continuo , es decir . Además, desde y porque no influye en la determinación del supremo tenemos: . De ello se deduce que , haciendo un punto fijo de . ${\displaystyle m}$ ${\displaystyle f(m)=m}$ ${\displaystyle f}$ ${\displaystyle f(\sup(\mathbb {M} ))=\sup(f(\mathbb {M} ))}$ ${\displaystyle f(m)=\sup(f(\mathbb {M} ))}$ ${\displaystyle \mathbb {M} =f(\mathbb {M} )\cup \{\bot \}}$ ${\displaystyle \bot }$ ${\displaystyle \sup(f(\mathbb {M} ))=\sup(\mathbb {M} )}$ ${\displaystyle f(m)=m}$ ${\displaystyle m}$ ${\displaystyle f}$

La prueba de que, de hecho, es el punto menos fijo se puede hacer demostrando que cualquier elemento de es más pequeño que cualquier punto fijo de (porque, según la propiedad de supremum , si todos los elementos de un conjunto son más pequeños que un elemento de entonces también es más pequeño que ese mismo elemento de ). Esto se hace por inducción: supongamos que hay algún punto fijo de . Ahora lo demostramos por inducción . La base de la inducción obviamente se cumple: puesto que es el elemento menor de . Como hipótesis de inducción, podemos suponer que . Ahora hacemos el paso de inducción: a partir de la hipótesis de inducción y la monotonicidad de (nuevamente, implícita en la continuidad de Scott de ), podemos concluir lo siguiente: Ahora, bajo el supuesto de que es un punto fijo de sabemos que y de que conseguimos ${\displaystyle m}$ ${\displaystyle \mathbb {M} }$ ${\displaystyle f}$ ${\displaystyle D\subseteq L}$ ${\displaystyle L}$ ${\displaystyle \sup(D)}$ ${\displaystyle L}$ ${\displaystyle k}$ ${\displaystyle f}$ ${\displaystyle i}$ ${\displaystyle \forall i\in \mathbb {N} :f^{i}(\bot )\sqsubseteq k}$ ${\displaystyle (i=0)}$ ${\displaystyle f^{0}(\bot )=\bot \sqsubseteq k,}$ ${\displaystyle \bot }$ ${\displaystyle L}$ ${\displaystyle f^{i}(\bot )\sqsubseteq k}$ ${\displaystyle f}$ ${\displaystyle f}$ ${\displaystyle f^{i}(\bot )\sqsubseteq k~\implies ~f^{i+1}(\bot )\sqsubseteq f(k).}$ ${\displaystyle k}$ ${\displaystyle f,}$ ${\displaystyle f(k)=k,}$ ${\displaystyle f^{i+1}(\bot )\sqsubseteq k.}$

Ver también

• Otros teoremas del punto fijo

Referencias

1. Alfred Tarski (1955). "Un teorema del punto fijo teórico de la red y sus aplicaciones". Revista Pacífico de Matemáticas . 5:2 : 285–309., página 305.
2. Patrick Cousot y Radhia Cousot (1979). "Versiones constructivas de los teoremas del punto fijo de Tarski". Revista Pacífico de Matemáticas . 82:1 : 43–57.
3. Stoltenberg-Hansen, V.; Lindstrom, I.; Griffin, ER (1994). Teoría matemática de dominios de V. Stoltenberg-Hansen. Prensa de la Universidad de Cambridge. págs.24. doi :10.1017/cbo9781139166386. ISBN 0521383447.