Teorias Simples em Complexidade Descritiva
(Trabalho de Doutorado em Andamento)
por
Steffen Lewitzka

Relatório sobre os meus estudos nos últimos 12 meses

O objetivo dos meus estudos é encontrar e investigar métodos e técnicas da teoria dos modelos que poderiam servir como ferramentas para resolver problemas na teoria da complexidade descritiva - uma área fundamental da informática teórica. Em particular, a teoria dos modelos finitos tem se mostrado muito eficaz nos últimos anos como ferramenta para descrever classes de complexidade por meio de extensões da lógica de primeira ordem. Tais desenvolvimentos levaram recentemente a tentativas muito promissoras de se tratar modelos finitos com as poderosas técnicas da teoria clássica dos modelos. Um dos possíveis pontos de partida é a área denominada de embedded finite model theory. Muitas estruturas interessantes neste contexto têm uma teoria simples, como as smoothly approximable structures, descobertas por Hrushovski e Lachlan. As teorias simples tornaram-se um campo principal nos estudos em teoria dos modelos durante os ultimos 4-5 anos, generalizando as teorias estáveis (toda teoria estável é simples). As teorias simples foram introduzidas em 1980 por S. Shelah [12] e ficaram despercebidas por alguns anos. No início dos anos 90 Hrushovski provou que a teoria de um ultraproduto de corpos finitos é simples e não estável. As suas aplicações espetaculares à geometria algébrica chamaram muita atenção e levaram a um estudo geral das teorias simples. Mais progresso foi obtido por B. Kim [5] na sua tese de PhD na qual ele provou entre outras coisas que as teorias simples permitem a definição de uma noção de independência entre subconjuntos dos modelos que satisfaz propriedades muito interessantes. (Esse artigo de Kim oferece também uma ótima introdução à área.) O resultado é que grande parte da teoria da estabilidade que também tem importância para a informática teórica continua sendo válida no contexto mais geral das teorias simples e muitas questões são acessíveis duma forma mais fácil e elegante neste novo cenário.

Impulsos significativos nos estudos das teorias simples têm sido dados por, entre outros, Prof. Enrique Casanovas [3],[4] da Universidade de Barcelona, Espanha, que é uns dos pesquisadores representativos na área. Desde junho do ano passado quando Casanovas me convidou para uma conferência em Barcelona - onde me dei conta da importância das teorias simples para os meus objetivos - continuamos mantendo o contato para discutir problemas e idéias, junto com o meu orientador Ruy de Queiroz. Em Setembro deste ano nos encontramos de novo em Barcelona num Workshop sobre teorias simples. Desde o meu primeiro encontro com Casanovas no ano passado tenho me dedicado intensamente ao estudo das teorias simples. Uma exposição detalhada encontra-se na minha monografia (Simple First Order Theories, Dezembro 1999, 35pp., submetida como exame de qualificação) que elaborei nos meses de Outubro a Dezembro do ano passado. Esse trabalho foi acompanhado do estudo de uma parte dos artigos mencionados na bibliografia (com a outra parte trabalho atualmente). Nos primeiros capítulos da monografia descrevo a relevância da teoria dos modelos (finita e clássica) para a informática teórica e dou alguns resultados da Descriptive Complexity que se obtêm por métodos da teoria de modelos finitos. Essas apresentações refletem parte dos meus estudos na área da Descriptive Complexity do último ano. No restante trato duas áreas dentro de embedded finite model theory que usam ferramentas da teoria clássica dos modelos. Na parte principal apresento as teorias simples como cenário possível para as investigações dos problemas relevantes. Exponho os problemas em aberto em teorias simples no último capítulo. Nos últimos meses estudei sobretudo os artigos [2] e [4] (versão antiga), [10],[13].

Plano para os próximos 12 meses

Um dos problemas em aberto mais importantes em teorias simples é se existe a possibilidade de reduzir tipos fortes de Lascar a tipos fortes (Lstp=stp-problem). A questáo mais geral é se uma teoria simples admite eliminação de hiperimaginários. Esse problema está ligado à existência de bases canônicas. Numa teoria simples existem bases canônicas se e somente se a teoria admite eliminação de hiperimaginários [10]. Nestas teorias a eliminação de hiperimaginários implica Lstp=stp. Hart, Pillay e Kim demonstraram a existência de bases canônicas na forma de hiperimaginários [4]. O problema Lstp=stp obteve em alguns casos especiais uma resposta positiva de Kim e Buechler. Kim demostrou em [7] que toda teoria pequena admite eliminação de hiperimaginários. Buechler e Shami demonstraram independentemente que em toda teoria baixa vale Lstp=stp, [1], [12]. Há muito pouco Buechler, Pillay e Wagner conseguiram provar que toda teoria supersimples admite eliminação de hiperimaginários [2]. Neste sentido as teorias supersimples e as teorias baixas são subclasses importantes das teorias simples. Casanovas conseguiu uma caracterização interessante das teorias supersimples através da contagem de tipos parciais [3]. Uma continuação deste trabalho encontra-se em [9]. Muitas pesquisam dedicam-se à busca de exemplos de teorias simples que não são baixas. Casanovas e Kim em [4] encontraram um exemplo de uma teoria supersimples. (As smoothly approximable structures que têm importância para a finite embedded model theory são simples e baixas e não estáveis.) Esses resultados formam o estado-da-arte do conhecimento na área. Durante os últimos meses estudei os artigos relevantes. Nos próximos meses continuarei estudando estes assuntos para conseguir um melhor entendimento que me habilita a resolver problemas neste cenário. O problema Lstp=stp fica aberto para uma outra subclasse das teorias simples, chamadas teorias supersimples locais. Esta subclasse pretendo estudar detalhadamente no futuro. Como comportam-se os problemas mencionados acima nesta subclasse? Que relação existe entre teorias supersimples locais e teorias baixas? Será que toda teoria baixa também é supersimples local? (Suspeitamos que isso não é o caso.)

Acabo de começar os estudos do problema Lstp=stp num contexto geral sob um outro ponto de vista:

Em toda teoria (simples ou não) há três relações de equivalência de especial importância. São as relações EL de Lascar, EKP de Kim e Pillay e ES de Shelah. A primeira é a menor relação de equivalência que é invariante e limitada (bounded), a segunda é a menor relação de equivalência que é tipo-definível e limitada e a terceira é uma relação de equivalência tipo definível e limitada, definida por ES(a,b) se e somente se E(a,b) para cada relação de equivalência finita e definível E. Obviamente obtemos que EL está contida em EKP e EKP está contida em ES. Vale o seguinte:
(1) stp(a/A)=stp(b/A) se e somente se ES(a,b), (ES definível sobre A).
(2) Lstp(a/A)=Lstp(b/A) se e somente se EL(a,b).

Se Aut(C/A) é o grupo de todos os automorfismos do modelo monstro C que fixam A então Autf(C/A) (= o grupo gerado por todos os automorfismos que são a identidade em algum submodelo elementar M de C que contém A e tem cardinalidade menor do que C) é um subgrupo normal de Aut(C/A). O quociente Aut(C/A)/Autf(C/A) denomina-se grupo de Lascar. Chamaremos uma teoria T de G-compacta se e somente se EL=EKP e Autf(C) é fechado na topologia de Aut(C). (Aut(C) é um grupo topológico com uma base de semi-abertos determinada pelos conjuntos O(ab) formados por os automorfismos que enviam uma tupla a para outra b. Não é em geral compacto, mas é Hausdorff.) Durante muito tempo estava em aberto a questão de se existem teorias não G-compactas. Ziegler encontrou recentemente um exemplo onde EL=EKP não vale. Posteriormente tem-se encontrado também exemplos nos quais Autf(C) não é fechado. As teorias simples são G-compactas. Sob a hipótese de que EL=EKP, o problema Lstp=stp pode ser reformulado para a questão de se EKP=ES. Em toda teoria G-compacta com eliminação de hiperimaginários vale Lstp=stp. Em particular, se T é estavel, Lstp=stp. (Porque uma teoria estável elimina os hiperimaginários.) Acredito que a perspectiva ao problema Lstp=stp descrita acima é muito promissora e pretendo me dedicar a estas questões no futuro. Ainda há poucos resultados e publicações com respeito a essas pesquisas, fato que estimulará a minha produtividade. Espero que nos próximos meses tanto a orientação pelo meu professor Ruy de Queiroz como a colaboração e o intercâmbio com Enrique Casanovas da Universidade de Barcelona continuem sendo tão eficazes como estão atualmente.

Bibliografia

[1] S. Buechler; Lascar strong types in some simple theories, J. Symbolic Logic, to appear
[2] S. Buechler, A. Pillay, F. O. Wagner; Supersimple Theories, preprint (September 2000)
[3] E. Casanovas; The number of types in simple theories, Annals of Pure and Applied Logic, 98 (1999)
[4] E. Casanovas, B. Kim; A supersimple nonlow theory, Notre Dame J. of Formal Logic, Volume ?, Number ?, (1999)
[5] B. Hart, B. Kim, A. Pillay; Coordinatization and canonical bases in simple theories, to appear in J. Symbolic Logic (March 2000)
[6] B. Kim; Simple first order theories, Ph.D. Thesis, Univ. of Notre Dame, Indiana, (1996)
[7] B. Kim; A note on Lascar strong types in simple theories, J. Symbolic Logic, 63 (1998) 926-936
[8] B. Kim, A. Pillay; From stability to simplicity, The Bull, Symbolic Logic 4 (1998) 17-36
[9] O. Lessmann; Counting partial types in simple theories, Department of Mathematics and Computer Science, Univ. of Illinois, Chicago, IL 60607
[10] A. Pillay; Definability and definable groups in simple theories, J. Symbolic 63 (1998) 788-796
[11] A. Pillay, D. Lascar; Hyperimaginaries and automorphism groups, preprint (1998)
[12] Z. Shami; Definabiltiy in low simple theories, to appear in J. Symbolic Logic
[13] S. Shelah; Simple unstable theories, Ann. Math. Logic 19 (1980) 177-203
[14] F. O. Wagner; Simple theories and hyperimaginaries, Mathematical Institute, Univ. of Oxford
[15] F. O. Wagner; Simple Theories. Mathematics and its Applications 503, Kluwer, (2000)

Recife, 19 de Setembro de 2000
Steffen Lewitzka

Última atualização: 11 de Outubro de 2000, 09:49:40 GMT-0200.