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

Esbozo de demostración

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

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

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

• Datos: Q609612