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, fo originalmente enunciado por Tarski [1] and so the theorem is often known as Tarski's fixed point theorem. Antes disso, Knaster e Tarski conjuntamente estabeleceram este resultadopara 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.


TeoremaEditar

Seja   um reticulado completo   uma função monótona. Considerem-se os conjuntos  ,   e  , dos pontos fixos, prefixos e posfixos de   respetivamente, ou seja definidos por,

  •  
  •  
  •  

Então verificam-se os seguintes resultados,

  •   é um reticulado completo
  •  
  •  

DemonstraçãoEditar

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:  

Por definição,   para todo  . Daí resulta em particular  , ou seja  .

Lema 2:  

Para todo   tem-se que  , logo   pela monotonicidade de  , ou seja  .

Lema 3:  

Seja  . Para todo   tem-se  , e também   pela monotonicidade de  , do que resulta   para todo o  . Como   o é menor dos majorantes então  , ou seja  .

Lema 4:  

Seja  . De   (lema 3) e   (lema 2), resulta que  . Portanto por definição de   tem-se  , ou seja  .

Conclusão:  

Dos lemas 3 e 4 resulta que  , ou seja  . Como  , então o supremo de   é também maior que todos os elementos de  , e como pertence a   é o seu máximo.


Prosseguimos demonstrando que   é um reticulado completo. Isto é, que todo o   tem um supremo em  .

É importante notar que o teorema não especifica que o supremo   em   é o mesmo que   em  . O teorema diz sim que, para todo o subconjunto de pontos fixos  , o conjunto de pontos fixos que o limitam superiormente tem um mínimo. Defina-se conjunto de majorantes de  , na forma de intervalo, como   onde   em  . Este intervalo é trivialmente um reticulado completo. O objetivo é mostrar que a restrição de   ao reticulado   tem um ponto fixo mínimo em  .


Lema 5:   tem um ponto fixo mínimo em  

Lema 6:  

Para todo   tem-se   por definição de  , e   pela monotonicidade de   e por   ser ponto fixo. Consequentemente  , pois   é por definição o menor majorante de  , ou seja Como   o menor dos majorantes então  .

Conclusão: A restrição de   ao reticulado completo   é da forma  . Aplicando o lema 5 (ao reticulado completo  ) conclui-se que   tem um ponto fixo mínimo em  . Fica demonstrada a existência de valor mínimo entre os pontos fixos que limitam superiormente  , ou seja a existência de   em  .

Ver tambémEditar

Notas

  1. Alfred Tarski (1955). «A lattice-theoretical fixpoint theorem and its applications». Pacific Journal of Mathematics. 5:2: 285–309 
  2. B. Knaster (1928). «Un théorème sur les fonctions d'ensembles». Ann. Soc. Polon. Math. 6: 133–134  With A. Tarski.
  3. Anne C. Davis (1955). «A characterization of complete lattices». Pacific J. Math. 5: 311–319. doi:10.2140/pjm.1955.5.311 

ReferênciasEditar

Leitura relacionadaEditar

  • 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 

Ligações externasEditar