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.