Teorema de Knaster-Tarski

En las áreas matemáticas de orden y teoría de redes , el teorema de Knaster-Tarski , llamado así en honor a Bronisław Knaster y Alfred Tarski , establece lo siguiente:

Sea ( L , ≤) una red completa y sea f : L → L una función que preserva el orden (monótona) con respecto a ≤ . Entonces, el conjunto de puntos fijos de f en L forma una red completa bajo ≤ .

Fue Tarski quien formuló el resultado en su forma más general, ^[1] y por eso 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 donde L es la red de subconjuntos de un conjunto, la red de conjuntos potencia . ^[2]

El teorema tiene aplicaciones importantes en la semántica formal de los lenguajes de programación y en la interpretación abstracta , así como en la teoría de juegos .

Anne C. Davis demostró una especie de recíproco de este teorema : si cada función que preserva el orden f : L → L en una red L tiene un punto fijo, entonces L es una red completa. ^[3]

Consecuencias: puntos fijos mínimo y máximo

Como las redes completas no pueden estar vacías (deben contener un supremo y un ínfimo 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 punto fijo máximo ). En muchos casos prácticos, esta es la implicación más importante del teorema.

El punto fijo menor de f es el elemento menor x tal que f ( x ) = x , o, equivalentemente, tal que f ( x ) ≤ x ; el dual se cumple para el punto fijo mayor , el elemento mayor 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 fijo mínimo de f es lim f ⁿ (0) donde 0 es el elemento mínimo de L , lo que da una versión más "constructiva" del teorema. (Véase: Teorema del punto fijo de Kleene .) De forma 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 ^α ) y f ^γ para un ordinal límite γ es el límite superior mínimo de f ^β para todos los ordinales β menores que γ. ^[4] El teorema dual se cumple para el punto fijo máximo.

Por ejemplo, en la informática teórica , los puntos mínimos fijos de funciones monótonas se utilizan para definir la semántica del programa ; véase Punto mínimo fijo § Semántica denotacional para un ejemplo. A menudo se utiliza una versión más especializada del teorema, donde se supone que L es la red de todos los subconjuntos de un determinado conjunto ordenados por inclusión de subconjuntos . Esto refleja el hecho de que en muchas aplicaciones solo se consideran dichas redes. 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 fijos mínimo y máximo.

El teorema de Knaster-Tarski se puede utilizar para dar una prueba simple del teorema de Cantor-Bernstein-Schroeder . ^[5]^[6]

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 suposiciones más complicadas. Por ejemplo: ^{[ cita requerida ]}

Sea L un conjunto parcialmente ordenado con un elemento mínimo (inferior) y sea f : L → L una función monótona . Además, supongamos que existe u en L tal que f ( u ) ≤ u y que cualquier cadena en el subconjunto tiene un supremo. Entonces f admite un punto mínimo fijo . $\{x\in L\mid x\leq f(x),x\leq u\}$

Esto se puede aplicar para obtener varios teoremas sobre conjuntos invariantes , por ejemplo, el teorema de Ok:

Para la función monótona F : P ( X ) → P ( X ) en la familia de subconjuntos no vacíos (cerrados) de X, las siguientes son equivalentes: (o) F admite A en P ( X ) st , (i) F admite el conjunto invariante A en P $A\subseteq F(A)$ ( X ) ie , (ii) F admite el conjunto invariante máximo A, (iii) F admite el conjunto invariante más grande A. $A=F(A)$

En particular, utilizando el principio de Knaster-Tarski se puede desarrollar la teoría de atractores globales para sistemas de funciones iteradas no contractivas discontinuas (multivaluadas) . Para sistemas de funciones iteradas débilmente contractivas es suficiente el teorema de Kantorovich (conocido también como principio de punto fijo de Tarski-Kantorovich).

Otras aplicaciones de los principios de punto fijo para conjuntos ordenados provienen de la teoría de ecuaciones diferenciales , integrales y de operadores.

Prueba

Reformulemos el teorema.

Para una red completa y una función monótona en L , el conjunto de todos los puntos fijos de f también es una red completa , con: $\langle L,\leq \rangle$ $f\colon L\rightarrow L$ $\langle P,\leq \rangle$

$\bigvee P=\bigvee \{x\in L\mid x\leq f(x)\}$ como el punto fijo más grande de f
$\bigwedge P=\bigwedge \{x\in L\mid x\geq f(x)\}$ como el punto fijo mínimo de f .

Demostración. Empezamos por demostrar que P tiene un elemento mínimo y un elemento máximo. Sea $D = {x | x \leq f (x)}$ y $x \in D$ (sabemos que al menos 0 _L pertenece a D ). Entonces, como f es monótona, tenemos $f (x) \leq f (f (x))$ , es decir, $f (x) \in D$ .

Ahora sea ( u existe porque $D$ $\subseteq$ $L$ y L es una red completa). Entonces para todo $x$ $\in$ $D$ es cierto que $x$ $\leq$ $u$ y $f$ $($ $x$ $) \leq$ $f$ $($ $u$ $)$ , por lo que $x$ $\leq$ $f$ $($ $x$ $) \leq$ $f$ $($ $u$ $)$ . Por lo tanto, f ( u ) es un límite superior de D , pero u es el límite superior mínimo, por lo que $u$ $\leq$ $f$ $($ $u$ $)$ , es decir, $u$ $\in$ $D$ . Entonces $f$ $($ $u$ $) \in$ $D$ (porque $f$ $($ $u$ $) \leq$ $f$ $($ $f$ $($ $u$ $)))$ y por lo tanto $f$ $($ $u$ $) \leq$ $u$ de lo que se sigue f ( u ) = u . Como cada punto fijo está en D tenemos que u es el punto fijo más grande de f . $u=\bigvee D$

La función f es monótona en la red dual (completa) . Como acabamos de demostrar, su punto fijo máximo existe. Es el punto fijo mínimo de L , por lo que P tiene elementos mínimos y máximos; es decir, de manera más general, toda función monótona en una red completa tiene un punto fijo mínimo y un punto fijo máximo. $\langle L^{op},\geq \rangle$

Para a , b en L escribimos [ a , b ] para el intervalo cerrado con límites a y $b : {x \in L | a \leq x \leq b}$ . Si a ≤ b , entonces ⟨[ a , b ], ≤⟩ es un retículo completo.

Queda por demostrar que P es una red completa. Sea , $W$ $\subseteq$ $P$ y . Demostramos que $f$ $([$ $w$ $, 1$ $L$ $]) \subseteq [$ $w$ $, 1$ $L$ $]$ . De hecho, para cada $x$ $\in$ $W$ tenemos x = f ( x ) y dado que w es el límite superior mínimo de W , $x$ $\leq$ $f$ $($ $w$ $)$ . En particular $w$ $\leq$ $f$ $($ $w$ $)$ . Entonces de $y$ $\in [$ $w$ $, 1$ $L$ $]$ se sigue que $w$ $\leq$ $f$ $($ $w$ $) \leq$ $f$ $($ $y$ $)$ , dando $f$ $($ $y$ $) \in [$ $w$ $, 1$ $L$ $]$ o simplemente $f$ $([$ $w$ $, 1$ $L$ $]) \subseteq [$ $w$ $, 1$ $L$ $]$ . Esto nos permite ver a f como una función en la red completa [ w , 1 _L ]. Entonces tiene un punto fijo mínimo allí, lo que nos da el límite superior mínimo de W. Hemos demostrado que un subconjunto arbitrario de P tiene un supremo, es decir, P es una red completa. $1_{L}=\bigvee L$ $w=\bigvee W$

Calcular un punto fijo de Tarski

Chang, Lyuu y Ti ^[7] presentan un algoritmo para encontrar un punto fijo de Tarski en una red totalmente ordenada , cuando la función de preservación del orden está dada por un oráculo de valores . Su algoritmo requiere consultas, donde L es el número de elementos en la red. En cambio, para una red general (dada como un oráculo), demuestran un límite inferior de consultas. $O(\log L)$ $\Omega (L)$

Deng, Qi y Ye ^[8] presentan varios algoritmos para encontrar un punto fijo de Tarski. Consideran dos tipos de retículos: ordenamiento por componentes y ordenamiento lexicográfico . Consideran dos tipos de entrada para la función f : oráculo de valores o una función polinómica. Sus algoritmos tienen la siguiente complejidad de tiempo de ejecución (donde d es el número de dimensiones y N _i es el número de elementos en la dimensión i ):

Los algoritmos se basan en la búsqueda binaria . Por otra parte, determinar si un punto fijo dado es único es computacionalmente difícil:

Para d = 2, para una red de componentes y un oráculo de valores, la complejidad de es óptima. ^[9] Pero para d > 2, hay algoritmos más rápidos: $O(\log ^{2}L)$

Fearnley, Palvolgyi y Savani ^[10] presentaron un algoritmo que utiliza únicamente consultas. En particular, para d = 3, solo se necesitan consultas. $O(\log ^{2\lceil d/3\rceil }L)$ $O(\log ^{2}L)$
Chen y Li ^[11] presentaron un algoritmo que utiliza únicamente consultas. $O(\log ^{\lceil (d+1)/2\rceil }L)$

Aplicación en la teoría de juegos

El teorema del punto fijo de Tarski tiene aplicaciones en los juegos supermodulares . ^[8] Un juego supermodular (también llamado juego de complementos estratégicos ^[12] ) es un juego en el que la función de utilidad de cada jugador tiene diferencias crecientes , por lo que la mejor respuesta de un jugador es una función débilmente creciente de las estrategias de los otros jugadores. Por ejemplo, considere un juego de competencia entre dos empresas. Cada empresa tiene que decidir cuánto dinero gastar en investigación. En general, si una empresa gasta más en investigación, la mejor respuesta de la otra empresa es gastar más en investigación también. Algunos juegos comunes se pueden modelar como juegos supermodulares, por ejemplo, la competencia de Cournot , la competencia de Bertrand y los juegos de inversión .

Como las funciones de mejor respuesta son monótonas, el teorema del punto fijo de Tarski se puede utilizar para demostrar la existencia de un equilibrio de Nash de estrategia pura (PNP) en un juego supermodular. Además, Topkis ^[13] demostró que el conjunto de PNE de un juego supermodular es una red completa, por lo que el juego tiene un PNE "más pequeño" y un PNE "más grande".

Echenique ^[14] presenta un algoritmo para encontrar todas las PNE en un juego supermodular. Su algoritmo primero utiliza secuencias de mejor respuesta para encontrar la PNE más pequeña y más grande; luego, elimina algunas estrategias y repite hasta que se encuentran todas las PNE. Su algoritmo es exponencial en el peor de los casos, pero se ejecuta rápidamente en la práctica. Deng, Qi y Ye ^[8] muestran que una PNE se puede calcular de manera eficiente al encontrar un punto fijo de Tarski de una aplicación que preserva el orden asociada con el juego.

Véase también

Cálculo μ modal

Notas

^ Alfred Tarski (1955). "Un teorema de punto fijo en teoría de retículos y sus aplicaciones". Revista del Pacífico de Matemáticas . 5 (2): 285–309. doi : 10.2140/pjm.1955.5.285 .
^ B. Knaster (1928). "Un teorema sobre las funciones de conjuntos". Ana. Soc. Polon. Matemáticas. 6 : 133–134. Con A. Tarski.
^ Anne C. Davis (1955). "Una caracterización de redes completas". Revista del Pacífico de Matemáticas . 5 (2): 311–319. doi : 10.2140/pjm.1955.5.311 .
^ Cousot, Patrick; Cousot, Radhia (1979). "Versiones constructivas de los teoremas del punto fijo de Tarski". Pacific Journal of Mathematics . 82 : 43–57. doi : 10.2140/pjm.1979.82.43 .
^ Uhl, Roland. "Teorema del punto fijo de Tarski". MathWorld .Ejemplo 3.
^ Davey, Brian A.; Priestley, Hilary A. (2002). Introducción a los enrejados y el orden (2.ª ed.). Cambridge University Press . pp. 63, 4. ISBN 9780521784511.
^ Chang, Ching-Lueh; Lyuu, Yuh-Dauh; Ti, Yen-Wu (23 de julio de 2008). "La complejidad del teorema del punto fijo de Tarski". Ciencias de la computación teórica . 401 (1): 228–235. doi :10.1016/j.tcs.2008.05.005. ISSN 0304-3975.
^ abc Dang, Chuangyin; Qi, Qi; Ye, Yinyu (1 de mayo de 2020). Cálculos y complejidades de los juegos de puntos fijos y supermodulares de Tarski (informe). arXiv.org.
^ Etessami, Kousha; Papadimitriou, Christos; Rubinstein, Aviad; Yannakakis, Mihalis (2020). Vidick, Thomas (ed.). "Teorema de Tarski, juegos supermodulares y la complejidad de los equilibrios". 11.ª Conferencia sobre innovaciones en informática teórica (ITCS 2020) . Leibniz International Proceedings in Informatics (LIPIcs). 151. Dagstuhl, Alemania: Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik: 18:1–18:19. doi : 10.4230/LIPIcs.ITCS.2020.18 . ISBN. 978-3-95977-134-4.S2CID202538977 .
^ Fearnley, John; Pálvölgyi, Dömötör; Savani, Rahul (11 de octubre de 2022). "Un algoritmo más rápido para encontrar puntos fijos de Tarski". Transacciones ACM sobre algoritmos . 18 (3): 23:1–23:23. arXiv : 2010.02618 . doi :10.1145/3524044. ISSN 1549-6325. S2CID 222141645.
^ Chen, Xi; Li, Yuhao (13 de julio de 2022). "Límites superiores mejorados para encontrar puntos fijos de Tarski". Actas de la 23.ª Conferencia de la ACM sobre economía y computación . EC '22. Nueva York, NY, EE. UU.: Association for Computing Machinery. págs. 1108–1118. arXiv : 2202.05913 . doi :10.1145/3490486.3538297. ISBN 978-1-4503-9150-4. Número de identificación del sujeto 246823965.
^ Vives, Xavier (1990-01-01). "Equilibrio de Nash con complementariedades estratégicas". Journal of Mathematical Economics . 19 (3): 305–321. doi :10.1016/0304-4068(90)90005-T. ISSN 0304-4068.
^ Topkis, Donald M. (1979-11-01). "Puntos de equilibrio en juegos submodulares de n personas de suma no nula". Revista SIAM sobre control y optimización . 17 (6): 773–787. doi :10.1137/0317054. ISSN 0363-0129.
^ Echenique, Federico (1 de julio de 2007). "Encontrar todos los equilibrios en juegos de complementos estratégicos". Journal of Economic Theory . 135 (1): 514–532. doi :10.1016/j.jet.2006.06.001. ISSN 0022-0531.

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 . Cambridge University Press. ISBN 978-0-521-53361-4.

Lectura adicional

S. Hayashi (1985). "Conjuntos autosimilares como puntos fijos de Tarski". Publicaciones del Instituto de Investigación 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 sistemas de funciones iteradas". Bull. Austral. Math. Soc . 61 (2): 247–261. doi : 10.1017/S0004972700022243 .
EA Ok (2004). "Teoría de conjuntos fijos para correspondencias cerradas con aplicaciones a la autosimilitud y los juegos". Nonlinear Anal . 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 del punto fijo". Theoret. Comput. Sci . 217 (2): 301–358. doi : 10.1016/S0304-3975(98)00273-4 .
S. Heikkilä (1990). "Sobre puntos fijos a través de un método de iteración generalizado con aplicaciones a ecuaciones diferenciales e integrales que involucran discontinuidades". Nonlinear Anal . 14 (5): 413–426. doi :10.1016/0362-546X(90)90082-R.
R.Uhl (2003). "Puntos fijos más pequeños y más grandes de mapeos crecientes cuasimonótonos". Mathematische Nachrichten . 248–249: 204–210. doi :10.1002/mana.200310016. S2CID 120679842.

Enlaces externos

JB Nation, Notas sobre la teoría de redes.
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.