Teorema del punto fijo de Kleene

Teorema en teoría de orden y teoría de retículas

Cálculo del punto fijo mínimo 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 de orden y teoría de redes , el teorema de punto fijo de Kleene , llamado así en honor al matemático estadounidense Stephen Cole Kleene , establece lo siguiente:

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

La cadena de Kleene ascendente de f es la cadena

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

Se obtiene iterando f sobre el elemento menor ⊥ 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, se refiere 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

Fuente: ^[3]

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

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

Demostración. Utilizamos la inducción:

• Supongamos que n = 0. Entonces, dado que es el elemento menor. ${\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 se cumple y, como 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, llamémoslo Lo que queda ahora es demostrar que es el menor punto fijo. ${\displaystyle \mathbb {M} }$ ${\displaystyle m.}$ ${\displaystyle m}$

Primero, demostramos que es un punto fijo, es decir que . Como es Scott-continua , , es decir . Además, como y como no tiene influencia en la determinación del supremo tenemos: . Se sigue 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 es de hecho el mínimo punto fijo se puede hacer mostrando que cualquier elemento en es menor que cualquier punto fijo de (porque por la propiedad del supremo , si todos los elementos de un conjunto son menores que un elemento de entonces también es menor que ese mismo elemento de ). Esto se hace por inducción: Supongamos que es algún punto fijo de . Ahora demostramos por inducción sobre que . La base de la inducción obviamente se cumple: ya que es el mínimo elemento 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 monotonía de (de nuevo, implícita por la continuidad de Scott de ), podemos concluir lo siguiente: Ahora, por la suposición de que es un punto fijo de sabemos que y de eso obtenemos ${\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.}$

Véase también

• Otros teoremas de punto fijo

Referencias

1. Alfred Tarski (1955). "Un teorema de punto fijo en teoría de red y sus aplicaciones". Pacific Journal of Mathematics . 5:2 : 285–309., página 305.
2. Patrick Cousot y Radhia Cousot (1979). "Versiones constructivas de los teoremas del punto fijo de Tarski". Pacific Journal of Mathematics . 82:1 : 43–57.
3. Stoltenberg-Hansen, V.; Lindstrom, I.; Griffor, ER (1994). Teoría matemática de dominios por V. Stoltenberg-Hansen. Cambridge University Press. pp. 24. doi :10.1017/cbo9781139166386. ISBN 0521383447.