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; 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. 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. 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.

Teorema

Seja $⟨L,\le ⟩$ um reticulado completo $f:L\to L$ uma função monótona. Considerem-se os conjuntos $P$, $Pre$ e $Pos$, dos pontos fixos, prefixos e posfixos de $f$ respetivamente, ou seja definidos por,

• $P=\{x\in L\mid f(x)=x\}$
• $Pre=\{x\in L\mid f(x)\le x\}$
• $Pos=\{x\in L\mid f(x)\ge x\}$

Então verificam-se os seguintes resultados,

• $⟨P,\le ⟩$ é um reticulado completo
• $\min P=\bigwedge Pre$
• $\max P=\bigvee Pos$

Demonstração

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: $Pos\ne \mathrm{\varnothing }$

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

Lema 2: $x\in Pos⟹f(x)\in Pos$

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

Lema 3: $\bigvee Pos\in Pos$

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

Lema 4: $\bigvee Pos\in Pre$

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

Conclusão: $\bigvee Pos=\max P$

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

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

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

Lema 5: $f:L\to L$ tem um ponto fixo mínimo em $L$

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

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

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

Ver também

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

Referências

• Predefinição:Citar livro
• Predefinição:Citar livro

Leitura relacionada

• Predefinição:Citar periódico
• Predefinição:Citar periódico
• Predefinição:Citar periódico
• Predefinição:Citar periódico
• Predefinição:Citar periódico
• Predefinição:Citar periódico
• Predefinição:Citar periódico

Ligações externas

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