Teorema de Knaster-Tarski

El teorema de Knaster-Tarski, que lleva los nombres de Bronisław Knaster y Alfred Tarski, es un teorema matemático del área de la teoría de retículos.

Enunciado

Sean ${\displaystyle {\mathcal {A}}:=\langle A,\leq \rangle }$ un retículo completo, ${\displaystyle f\colon A\to A}$ una función monótona y ${\displaystyle P:=\{x\in A\mid f(x)=x\}}$ el conjunto de los puntos fijos de ${\displaystyle f}$ en ${\displaystyle A}$. Entonces ${\displaystyle P\neq \emptyset }$ y ${\displaystyle {\mathcal {P}}:=\langle P,\leq \rangle }$ es también un retículo completo.

Esbozo de demostración

Sean ${\displaystyle \textstyle \bigcup _{\mathcal {A}}}$ y ${\displaystyle \textstyle \bigcap _{\mathcal {A}}}$ las operaciones de supremo e ínfimo de ${\displaystyle {\mathcal {A}}}$, respectivamente.

Los siguientes pasos muestran que para subconjuntos arbitrarios de ${\displaystyle P}$, ${\displaystyle {\mathcal {P}}}$ arroja un ínfimo y un supremo en ${\displaystyle P}$.

1. ${\displaystyle \textstyle \bigcup _{\mathcal {A}}\{x\in A\mid x\leq f(x)\}}$ es punto fijo de ${\displaystyle f}$, siendo además mayor que cualquier otro en ${\displaystyle A}$. Por tanto se trata del supremo ${\displaystyle {\mathcal {P}}}$ de ${\displaystyle P}$.
2. Dualmente al paso 1: ${\displaystyle \textstyle \bigcap _{\mathcal {A}}\{x\in A\mid f(x)\leq x\}}$ es punto fijo de ${\displaystyle f}$, siendo además menor que cualquier otro en ${\displaystyle A}$.
3. Para subconjuntos arbitrarios ${\displaystyle Y\subseteq P}$, se requiere que exista un supremo ${\displaystyle {\mathcal {P}}}$. Los casos ${\displaystyle Y=P}$ y ${\displaystyle Y=\emptyset }$ ya se consideraron en los pasos 1 y 2. Ahora se consideran los demás casos. Para ello se aprovecha el que ${\displaystyle \langle U,\leq \rangle }$ con ${\displaystyle \textstyle U:=\{x\in A\mid \bigcup _{\mathcal {A}}Y\leq x\}}$ es a su vez un retículo completo y que ${\displaystyle f|_{U}}$ es una función monótona ${\displaystyle U\to U}$, que de acuerdo al paso 2 tiene en ${\displaystyle U}$ al menor de sus puntos fijos. Este es el supremo ${\displaystyle {\mathcal {P}}}$ de ${\displaystyle Y}$. En símbolos: ${\displaystyle \textstyle \bigcup _{\mathcal {P}}Y:=\bigcap _{\mathcal {A}}\{x\in A\mid \bigcup _{\mathcal {A}}Y\cup f(x)\ \leq \ x\}}$.
4. Dualmente al paso 3 se muestra que para subconjuntos arbitrarios de ${\displaystyle P}$ existe un ínfimo ${\displaystyle {\mathcal {P}}}$.

Corolarios

Un corolario frecuentemente utilizado es el de la existencia de los puntos fijos ínfimo y supremo para funciones monótonas con respecto a ${\displaystyle \subseteq }$.

Referencias

• Alfred Tarski (1955). «A lattice-theoretical fixpoint theorem and its applications». Pacific Journal of Mathematics. 5:2: 285-309. 
• Garrett Birkhoff, 1967. Lattice Theory, 3rd ed. Vol. 25 of AMS Colloquium Publications. American Mathematical Society. ISBN 978-0-8218-1025-5