En las áreas matemáticas de la teoría del orden y la red , el teorema de Knaster-Tarski , que lleva el nombre de Bronisław Knaster y Alfred Tarski , establece lo siguiente:
- Sea (L, ≤) una red completa y sea f: L → L una función de preservación del orden (wrt ≤). Entonces, el conjunto de puntos fijos de f en L también forma una red completa bajo ≤.
Fue Tarski quien expresó el resultado en su forma más general, [1] y, por lo tanto, el teorema se conoce a menudo como el teorema del punto fijo de Tarski . Algún tiempo antes, Knaster y Tarski establecieron el resultado para el caso especial en el que L es la red de subconjuntos de un conjunto, la red de conjuntos de potencia . [2]
El teorema tiene aplicaciones importantes en semántica formal de lenguajes de programación e interpretación abstracta .
Anne C. Davis demostró una especie de recíproco de este teorema : si cada función de conservación de orden f: L → L en un retículo L tiene un punto fijo, entonces L es un retículo completo. [3]
Consecuencias: puntos fijos mínimo y máximo
Dado que las celosías completas no pueden estar vacías (deben contener un supremum / infimum del conjunto vacío), el teorema en particular garantiza la existencia de al menos un punto fijo de f , e incluso la existencia de un punto fijo mínimo (o mayor ). En muchos casos prácticos, esta es la implicación más importante del teorema.
El punto fijo mínimo de f es el elemento mínimo x tal que f ( x ) = x , o, de manera equivalente, tal que f ( x ) ≤ x ; el dual es válido para el mayor punto fijo , el mayor elemento x tal que f ( x ) = x .
Si f (lim x n ) = lim f ( x n ) para todas las secuencias ascendentes x n , entonces el punto de fijación mínimo de f es lim f n (0) donde 0 es el elemento menor de L, lo que da un resultado más "constructivo" versión del teorema. (Ver: teorema de punto fijo de Kleene .) De manera más general, si f es monótona, entonces el punto fijo mínimo de f es el límite estacionario de f α (0), tomando α sobre los ordinales , donde f α se define por inducción transfinita : f α + 1 = f ( f α ) yf γ para un ordinal límite γ es el límite superior mínimo de f β para todos los ordinales β menores que γ. El teorema dual es válido para el mayor punto fijo.
Por ejemplo, en informática teórica , los puntos mínimos fijos de funciones monótonas se utilizan para definir la semántica del programa . A menudo se usa una versión más especializada del teorema, donde se supone que L es el retículo de todos los subconjuntos de un determinado conjunto ordenado por inclusión de subconjuntos. Esto refleja el hecho de que en muchas aplicaciones solo se consideran tales celosías. Por lo general, se busca el conjunto más pequeño que tenga la propiedad de ser un punto fijo de la función f . La interpretación abstracta hace un amplio uso del teorema de Knaster-Tarski y las fórmulas que dan los puntos de referencia mínimos y mayores.
El teorema de Knaster-Tarski se puede utilizar para una demostración simple del teorema de Cantor-Bernstein-Schroeder . [4] [5]
Versiones más débiles del teorema
Se pueden formular versiones más débiles del teorema de Knaster-Tarski para conjuntos ordenados, pero implican supuestos más complicados. Por ejemplo:
- Sea L un conjunto parcialmente ordenado con el elemento más pequeño (abajo) y sea f: L → L una función que preserva el orden . Además, suponga que existe u en L tal que f (u) ≤ u y que cualquier cadena en el subconjuntotiene supremum. Entonces f admite un punto mínimo fijo .
Esto se puede aplicar para obtener varios teoremas sobre conjuntos invariantes , por ejemplo, el teorema de Ok:
- Para el mapa monótono F: P (X) → P (X) en la familia de subconjuntos (cerrados) no vacíos de X, lo siguiente es equivalente: (o) F admite A en P (X) st, (i) F admite un conjunto invariante A en P (X) es decir , (ii) F admite el conjunto invariante máximo A, (iii) F admite el conjunto invariante mayor A.
En particular, utilizando el principio de Knaster-Tarski se puede desarrollar la teoría de atractores globales para sistemas de funciones iteradas discontinuas no contractivas (multivalor) . Para sistemas de función iterada débilmente contractivos, el teorema del punto fijo de Kantorovitch (conocido también como principio del punto fijo de Tarski-Kantorovitch) es suficiente.
Otras aplicaciones de los principios de punto fijo para conjuntos ordenados provienen de la teoría de ecuaciones diferenciales, integrales y de operador.
Prueba
Repitamos el teorema.
Para una celosía completa y una función monótona en L , el conjunto de todos los puntos fijos de f también es un retículo completo, con:
- como el mayor punto fijo de f
- como el menor punto fijo de f .
Prueba. Comenzamos mostrando que P tiene tanto un elemento menor como un elemento mayor. Sea D = { x | x ≤ f (x) } y x ∈ D (sabemos que al menos 0 L pertenece a D ). Entonces porque f es monótona tenemos f (x) ≤ f (f (x)) , es decir f (x) ∈ D .
Ahora deja (u existe porque D ⊆ L y L es una red completa). Entonces para todo x ∈ D es cierto que x ≤ u y f (x) ≤ f (u) , entonces x ≤ f (x) ≤ f (u) . Por lo tanto, f (u) es una cota superior de D , pero u es el extremo superior, por lo que u ≤ f (u) , es decir, u ∈ D . Entonces f (u) ∈ D (porque f (u) ≤ f (f (u)) ) y entonces f (u) ≤ u de lo que se sigue f (u) = u . Debido a que cada punto fijo está en D , tenemos que u es el punto fijo más grande de f .
La función f es monótona en el enrejado doble (completo). Como acabamos de demostrar, su mayor punto fijo existe. Es el menor punto fijo de L , por lo que P tiene los elementos menores y mayores, es decir, de manera más general, cada función monótona en una red completa tiene un punto fijo mínimo y un punto fijo mayor.
Si un ∈ L y b ∈ L , escribiremos [ un , b ] para el intervalo cerrado con límites a y b : {x ∈ L | a ≤ x ≤ b }. Si a ≤ b , entonces[ a , b ], es una celosía completa.
Queda por probar que P es una red completa. Dejar, W ⊆ P y. Mostraremos que f ([ w , 1 L ]) ⊆ [ w , 1 L ]. De hecho, para cada x ∈ W tenemos x = f (x) y dado que w es el límite superior mínimo de W x ≤ f (w) . En particular w ≤ f (w) . Entonces de y ∈ [ w , 1 L ] se deduce que w ≤ f (w) ≤ f (y) , dando f (y) ∈ [ w , 1 L ] o simplemente f ([ w , 1 L ]) ⊆ [ w , 1 L ]. Esto nos permite ver f como una función en la red completa [ w , 1 L ]. A continuación tiene un punto fijo, por lo menos allí, nosotros el extremo superior de dar W . Hemos demostrado que un subconjunto arbitrario de P tiene un supremo, es decir, P es una red completa.
Ver también
Notas
- ^ Alfred Tarski (1955). "Un teorema de punto fijo teórico-reticular y sus aplicaciones" . Pacific Journal of Mathematics . 5: 2 : 285-309.
- ^ B. Knaster (1928). "Un théorème sur les fonctions d'ensembles". Ana. Soc. Polon. Matemáticas . 6 : 133-134. Con A. Tarski.
- ^ Anne C. Davis (1955). "Una caracterización de celosías completas" . Pacific Journal of Mathematics . 5 (2): 311–319. doi : 10.2140 / pjm.1955.5.311 .
- ^ Ejemplo 3 en R. Uhl, " Teorema del punto fijo de Tarski ", de MathWorld, un recurso web de Wolfram, creado por Eric W. Weisstein.
- ^ Davey, Brian A .; Priestley, Hilary A. (2002). Introducción a las celosías y el orden (2ª ed.). Prensa de la Universidad de Cambridge . págs. 63, 4. ISBN 9780521784511.
Referencias
- Andrzej Granas y James Dugundji (2003). Teoría del punto fijo . Springer-Verlag , Nueva York. ISBN 978-0-387-00173-9.
- Forster, T. (21 de julio de 2003). Lógica, Inducción y Conjuntos . ISBN 978-0-521-53361-4.
Otras lecturas
- S. Hayashi (1985). "Conjuntos auto-similares como puntos fijos de Tarski" . Publicaciones del Instituto de Investigaciones en Ciencias Matemáticas . 21 (5): 1059–1066. doi : 10.2977 / prims / 1195178796 .
- J. Jachymski; L. Gajek; K. Pokarowski (2000). "El principio de Tarski-Kantorovitch y la teoría de los sistemas de funciones iteradas" . Toro. Austral. Matemáticas. Soc . 61 (2): 247–261. doi : 10.1017 / S0004972700022243 .
- EA Ok (2004). "Teoría de conjuntos fijos para correspondencias cerradas con aplicaciones de auto-similitud y juegos". Anal no lineal . 56 (3): 309–330. CiteSeerX 10.1.1.561.4581 . doi : 10.1016 / j.na.2003.08.001 .
- BSW Schröder (1999). "Algoritmos para la propiedad de punto fijo" . Theoret. Computación. Sci . 217 (2): 301–358. doi : 10.1016 / S0304-3975 (98) 00273-4 .
- S. Heikkilä (1990). "Sobre puntos fijos mediante un método de iteración generalizada con aplicaciones a ecuaciones diferenciales e integrales que involucran discontinuidades". Anal no lineal . 14 (5): 413–426. doi : 10.1016 / 0362-546X (90) 90082-R .
- R. Uhl (2003). "Los puntos fijos más pequeños y más grandes de mapeos crecientes de cuasimonotono". Mathematische Nachrichten . 248–249: 204–210. doi : 10.1002 / mana.200310016 .
enlaces externos
- JB Nation, Notas sobre la teoría de la celosía .
- Una aplicación a un problema de combinatoria elemental : dado un libro con 100 páginas y 100 lemas, demuestre que hay algún lema escrito en la misma página que su índice.