Teorema de Knaster-Tarski

El teorema de Knaster-Tarski ( teorema de Tarski ) es un teorema de la teoría de celosías , formulado por primera vez en un caso particular por Bronisław Knaster y generalizado por Alfred Tarski [1] . Afirma que para cualquier aplicación monotónica de una red completa (es decir, tal que ) el conjunto de todos los puntos fijos también es una red completa. ${\ estilo de visualización f: L \ a L}$ ${\ estilo de visualización \ langle L, \ sqsubseteq \ rangle}$ $l_{1}\sqsubseteq l_{2}\Rightarrow f(l_{1})\sqsubseteq f(l_{2})$ ${\displaystyle \mathrm {Fix} (f)=\{l\in L\mid f(l)=l\))$

El resultado se utiliza en informática teórica , en particular en trabajos sobre la semántica de los lenguajes de programación .

Del teorema de Knaster-Tarski se deduce que una aplicación monótona de una red completa sobre sí misma tiene al menos un punto fijo (ya que una red completa no puede estar vacía). Además, tal mapeo tiene los puntos fijos más pequeños y más grandes [2] . El teorema del punto fijo de Kleene establece que para aplicaciones continuas de Scott (que, como consecuencia de la continuidad, son monótonas) existe un punto fijo más pequeño . Además, el teorema de Kleene también se cumple para cualquier orden parcial completo .

Notas

↑ Tarski, A. Un teorema del punto fijo teórico de celosía y sus aplicaciones // Pacific J. Math .. - 1955. - No. 5. - P. 285-309.
↑ Roland Uhl. Teorema del punto fijo de Tarski (inglés) en el sitio web de Wolfram MathWorld .

Literatura

S. Abramsky, Dov M. Gabbay, TSE Maibaum, Manual de lógica en informática: Volumen 1: Antecedentes: estructuras matemáticas