En las áreas matemáticas de la teoría del orden y la red , el teorema del punto fijo de Kleene , que lleva el nombre del matemático estadounidense Stephen Cole Kleene , establece lo siguiente:
- Teorema de punto fijo de Kleene. Suponer es un orden parcial dirigido-completo (dcpo) con un elemento mínimo, y sea ser un Scott-continuo (y por lo tanto monótono ) función . Luego tiene un punto menos fijo , que es el supremo de la cadena Kleene ascendente de
La cadena ascendente de Kleene de f es la cadena
obtenido por iterando f en el menos elemento ⊥ de L . Expresado en una fórmula, el teorema establece que
dónde denota el punto menos fijo.
Aunque el teorema del punto fijo de Tarski no considera cómo se pueden calcular los puntos fijos iterando f de alguna semilla (también, pertenece a funciones monótonas en retículas completas ), este resultado a menudo se atribuye a Alfred Tarski quien lo prueba para funciones aditivas [1] Además, el teorema de punto fijo de Kleene se puede extender a funciones monótonas usando iteraciones transfinitas. [2]
Prueba [3]
Primero tenemos que mostrar que la cadena ascendente de Kleene de existe en . Para demostrar eso, probamos lo siguiente:
- Lema. Si es un dcpo con un elemento mínimo, y es Scott-continuo, entonces
- Prueba. Usamos inducción:
- Suponga n = 0. Entonces desde es el elemento mínimo.
- Suponga que n> 0. Entonces tenemos que demostrar que . Al reorganizar obtenemos. Por suposición inductiva, sabemos que se cumple, y debido a que f es monótona (propiedad de las funciones continuas de Scott), el resultado también se cumple.
Como corolario del Lema tenemos la siguiente cadena ω dirigida:
De la definición de dcpo se deduce que tiene un supremo, llámalo Lo que queda ahora es mostrar que es el punto menos fijo.
Primero, mostramos que es un punto fijo, es decir, que . Porquees Scott-continuo ,, es decir . Además, desde y porqué no influye en la determinación del supremo que tenemos: . Resulta que, haciendo un punto fijo de .
La prueba de que es de hecho el punto menos fijo que se puede hacer mostrando que cualquier elemento en es más pequeño que cualquier punto fijo de (porque por propiedad de supremum , si todos los elementos de un conjunto son más pequeños que un elemento de Después también es más pequeño que el mismo elemento de ). Esto se hace por inducción: suponga es un punto fijo de . Ahora probamos por inducción sobre que . La base de la inducción obviamente sostiene: desde es el menor 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 monotonicidad de (de nuevo, implícito por la continuidad de Scott de ), podemos concluir lo siguiente: Ahora, asumiendo que es un punto fijo de lo sabemos y de eso obtenemos
Ver también
- Otros teoremas del punto fijo
Referencias
- ^ Alfred Tarski (1955). "Un teorema de punto fijo teórico-reticular y sus aplicaciones" . Pacific Journal of Mathematics . 5: 2 : 285-309., página 305.
- ^ Patrick Cousot y Radhia Cousot (1979). "Versiones constructivas de los teoremas del punto fijo de Tarski" . Pacific Journal of Mathematics . 82: 1 : 43–57.
- ^ Stoltenberg-Hansen, V .; Lindstrom, I .; Griffor, ER (1994). Teoría matemática de dominios por V. Stoltenberg-Hansen . Prensa de la Universidad de Cambridge. págs. 24 . doi : 10.1017 / cbo9781139166386 . ISBN 0521383447.