Teorema de Knaster–Tarski

O Teorema de Knaster–Tarski, por Bronisław Knaster e Alfred Tarski, é um resultado matemático em teoria da ordem sobre reticulados que diz o seguinte:

Seja L um reticulado completo e f : L → L uma função monótona. Então o conjunto de pontos fixos de f em L também é um reticulado completo.

O teorema determina ainda a forma geral do máximo e do mínimo do conjunto de pontos fixos de f. O teorema na sua forma mais geral, foi originalmente enunciado por Tarski;^[1] e assim o teorema é muitas vezes conhecido como teorema do ponto fixo de Tarski. Antes disso, Knaster e Tarski conjuntamente estabeleceram este resultado para o caso especial em que L é um reticulado de subconjuntos de um conjunto.^[2] Este teorema tem aplicações importantes na área de semântica formal de linguagens de programação e interpretações abstratas. O reverso deste teorema foi demonstrado por Anne C. Davis.^[3] Assim sendo, verifica-se também o seguinte: Se toda e qualquer função monótona f : L → L num dado reticulado L tem pontos fixos, então L é um reticulado completo.

Seja ${\displaystyle \langle L,\leq \rangle }$ um reticulado completo ${\displaystyle f\colon L\rightarrow L}$ uma função monótona. Considerem-se os conjuntos ${\displaystyle P}$, ${\displaystyle Pre}$ e ${\displaystyle Pos}$, dos pontos fixos, prefixos e posfixos de ${\displaystyle f}$ respetivamente, ou seja definidos por,

• ${\displaystyle P=\{x\in L\mid f(x)=x\}}$
• ${\displaystyle Pre=\{x\in L\mid f(x)\leq x\}}$
• ${\displaystyle Pos=\{x\in L\mid f(x)\geq x\}}$

Então verificam-se os seguintes resultados,

• ${\displaystyle \langle P,\leq \rangle }$ é um reticulado completo
• ${\displaystyle \min \ P=\bigwedge Pre}$
• ${\displaystyle \max \ P=\bigvee Pos}$

Começamos por demonstrar que P tem mínimo e máximo, e que são respetivamente o supremo e ínfimo dos pontos prefixos e posfixos. Como ambos os casos são duais, apresentamos apenas a demonstração do primeiro, ou seja que o máximo de P existe e é o máximo de Pos. Como Pos contém P, basta demonstrar que o supremo de Pos pertence a P para concluir que é o seu máximo.

Lema 1: ${\displaystyle Pos\neq \emptyset }$

Por definição, ${\displaystyle \bot \leq f(x)}$ para todo ${\displaystyle x\in L}$. Daí resulta em particular ${\displaystyle \bot \leq f(\bot )}$, ou seja ${\displaystyle \bot \in Pos}$.

Lema 2: ${\displaystyle x\in Pos\implies f(x)\in Pos}$

Para todo ${\displaystyle x\in pos}$ tem-se que ${\displaystyle x\leq f(x)}$, logo ${\displaystyle f(x)\leq f(f(x))}$ pela monotonicidade de ${\displaystyle f(x)}$, ou seja ${\displaystyle f(x)\in Pos}$.

Lema 3: ${\displaystyle \bigvee Pos\in Pos}$

Seja ${\textstyle u=\bigvee Pos}$. Para todo ${\displaystyle x\in Pos}$ tem-se ${\displaystyle x\leq u}$, e também ${\displaystyle f(x)\leq f(u)}$ pela monotonicidade de ${\displaystyle f}$, do que resulta ${\displaystyle x\leq f(x)\leq f(u)}$ para todo o ${\displaystyle x\in Pos}$. Como ${\displaystyle u}$ o é menor dos majorantes então ${\displaystyle u\leq f(u)}$, ou seja ${\displaystyle u\in Pos}$.

Lema 4: ${\displaystyle \bigvee Pos\in Pre}$

Seja ${\textstyle u=\bigvee Pos}$. De ${\displaystyle u\in Pos}$ (lema 3) e ${\displaystyle x\in Pos\implies f(x)\in Pos}$ (lema 2), resulta que ${\displaystyle f(u)\in Pos}$. Portanto por definição de ${\displaystyle u}$ tem-se ${\displaystyle f(u)\in u}$, ou seja ${\displaystyle u\in Pre}$.

Conclusão: ${\displaystyle \bigvee Pos=\max P}$

Dos lemas 3 e 4 resulta que ${\textstyle \bigvee Pos\in (Pos\cap Pre)}$, ou seja ${\textstyle \bigvee Pos\in P}$. Como ${\displaystyle P\subseteq Pos}$, então o supremo de ${\displaystyle Pos}$ é também maior que todos os elementos de ${\displaystyle P}$, e como pertence a ${\displaystyle P}$ é o seu máximo.

Prosseguimos demonstrando que ${\displaystyle P}$ é um reticulado completo. Isto é, que todo o ${\displaystyle U\subseteq P}$ tem um supremo em ${\textstyle \bigvee U\in P}$.

É importante notar que o teorema não especifica que o supremo ${\textstyle \bigvee U}$ em ${\displaystyle \langle P,\leq \rangle }$ é o mesmo que ${\textstyle \bigvee U}$ em ${\displaystyle \langle L,\leq \rangle }$. O teorema diz sim que, para todo o subconjunto de pontos fixos ${\displaystyle \langle U\rangle }$, o conjunto de pontos fixos que o limitam superiormente tem um mínimo. Defina-se conjunto de majorantes de ${\displaystyle U}$, na forma de intervalo, como ${\displaystyle [u,\top ]=\{x:u\leq x\leq \top \}}$ onde ${\textstyle u=\bigvee U}$ em ${\displaystyle \langle L,\leq \rangle }$. Este intervalo é trivialmente um reticulado completo. O objetivo é mostrar que a restrição de ${\displaystyle f:L\rightarrow L}$ ao reticulado ${\displaystyle [u,\top ]}$ tem um ponto fixo mínimo em ${\displaystyle [u,\top ]}$.

Lema 5: ${\displaystyle f:L\rightarrow L}$ tem um ponto fixo mínimo em ${\displaystyle L}$

Lema 6: ${\displaystyle f([u,\top ])\subseteq [u,\top ]}$

Para todo ${\displaystyle x\in U\subseteq P}$ tem-se ${\displaystyle x\leq u}$ por definição de ${\displaystyle u}$, e ${\displaystyle x=f(x)\leq f(u)}$ pela monotonicidade de ${\displaystyle f}$ e por ${\displaystyle u}$ ser ponto fixo. Consequentemente ${\displaystyle u\leq f(u)}$, pois ${\displaystyle u}$ é por definição o menor majorante de ${\displaystyle U}$, ou seja Como ${\displaystyle u}$ o menor dos majorantes então ${\displaystyle f(u)\in [u,\top ]}$.

Conclusão: A restrição de ${\displaystyle f}$ ao reticulado completo ${\displaystyle [u,\top ]}$ é da forma ${\displaystyle f:[u,\top ]\rightarrow [u,\top ]}$. Aplicando o lema 5 (ao reticulado completo ${\displaystyle [u,\top ]}$) conclui-se que ${\displaystyle f:[u,\top ]\rightarrow [u,\top ]}$ tem um ponto fixo mínimo em ${\displaystyle [u,\top ]}$. Fica demonstrada a existência de valor mínimo entre os pontos fixos que limitam superiormente ${\displaystyle U}$, ou seja a existência de ${\textstyle \bigvee U}$ em ${\displaystyle \langle P,\leq \rangle }$.

• Teorema do ponto fixo de Kleene
• Teorema do ponto fixo de Kantorovitch
• μ-calculo modal

Notas

• Andrzej Granas and James Dugundji (2003). Fixed Point Theory. [S.l.]: Springer-Verlag, New York. ISBN 0-387-00173-5 
• Forster, T. Logic, Induction and Sets. [S.l.: s.n.] ISBN 0-521-53361-9 

• S. Hayashi (1985). «Self-similar sets as Tarski's fixed points». Publ. RIMS Kyoto Univ. 21 (5): 1059–1066. doi:10.2977/prims/1195178796 
• J. Jachymski; L. Gajek; K. Pokarowski (2000). «The Tarski-Kantorovitch principle and the theory of iterated function systems». Bull. Austral. Math. Soc. 61 (02): 247–261. doi:10.1017/S0004972700022243 
• E.A. Ok (2004). «Fixed set theory for closed correspondences with applications to self-similarity and games». Nonlinear Anal. 56 (3): 309–330. doi:10.1016/j.na.2003.08.001 
• B.S.W. Schröder (1999). «Algorithms for the fixed point property». Theoret. Comput. Sci. 217 (2): 301–358. doi:10.1016/S0304-3975(98)00273-4 
• S. Heikkilä (1990). «On fixed points through a generalized iteration method with applications to differential and integral equations involving discontinuities». Nonlinear Anal. 14 (5): 413–426. doi:10.1016/0362-546X(90)90082-R 
• R. Uhl (2003). «Smallest and greatest fixed points of quasimonotone increasing mappings». Mathematische Nachrichten. 248–249: 204–210. doi:10.1002/mana.200310016 
• Brunner, Andreas B. M.; Malta, Paulo R. S. (2020). «Teoremas de ponto fixo de Banach e Knaster-Tarski, revistos» (PDF). Revista Matemática Universitária. 2: 1–21. doi:10.21711/26755254/rmu202021 

• J. B. Nation, Notes on lattice theory.