TEORIA GEOM´ETRICA DE GRUPOS Pedro V. Silva
Transcrição
TEORIA GEOM´ETRICA DE GRUPOS Pedro V. Silva
TEORIA GEOMÉTRICA DE GRUPOS Curso de pré-doutorado, Universidade Federal da Bahia 2014 Pedro V. Silva Neste curso, faremos uma digressão por alguns dos grandes desenvolvimentos que a teoria de grupos sofreu nos últimos 30 anos, dos autômatos de Stallings aos grupos hiperbólicos de Gromov e aos grupos automáticos de Epstein, Thurston et al.... Veremos uma nova e inesperada álgebra que se relaciona de forma surpreendente com muitas outras áreas: combinatória, geometria, sistemas dinâmicos, teoria de autômatos e linguagens, topologia. Índice 1 Grupos 1.1 Grupos de permutações . . . 1.2 Noção abstrata de grupo . . . 1.3 Homomorfismos e quocientes 1.4 Outros conceitos . . . . . . . 1.5 Exercı́cios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 4 4 5 7 8 2 Grafos e autômatos 2.1 Palavras e linguagens . 2.2 Grafos . . . . . . . . . 2.3 Autômatos . . . . . . 2.4 Sistemas de reescrita . 2.5 Exercı́cios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 10 11 12 16 17 . . . . . . . . . . . . racionais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 19 22 24 27 29 . . . . . . . . . . 3 Grupos livres 3.1 Construção . . . . . . . . 3.2 Propriedades básicas . . . 3.3 Autômatos e subconjuntos 3.4 Grafos de Cayley . . . . . 3.5 Exercı́cios . . . . . . . . . . . . . . 4 Representação de subgrupos 4.1 Construção de Stallings . . 4.2 Aplicações . . . . . . . . . . 4.3 A métrica profinita . . . . . 4.4 Exercı́cios . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 Bordo de um grupo livre 5.1 Palavras infinitas . . . . . . . . . 5.2 A métrica dos prefixos e o espaço 5.3 Construção do bordo . . . . . . . 5.4 Exercı́cios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 31 34 39 42 . . . . . . de Cantor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 43 44 46 47 . . . . . . . . . . . . . . . . . . . . 6 Pontos fixos de endomorfismos 49 6.1 O subgrupo dos pontos fixos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 6.2 Pontos fixos no bordo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 6.3 Exercı́cios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 7 Apresentações de grupos 56 7.1 Geradores e relatores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 7.2 Grupos finitamente apresentáveis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 2 7.3 7.4 7.5 7.6 Decidibilidade . . . . . . . . Diagramas de van Kampen Funções isoperimétricas . . Exercı́cios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 59 63 65 8 Produto livre e generalizações 8.1 Produto livre . . . . . . . . . 8.2 Generalizações . . . . . . . . 8.3 Grupos de grafo . . . . . . . . 8.4 Exercı́cios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 67 69 70 72 9 Grupos hiperbólicos 9.1 Grafos hiperbólicos . . . . . . 9.2 Grafos de Cayley hiperbólicos 9.3 Propriedades . . . . . . . . . 9.4 Exercı́cios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74 74 76 79 82 10 Grupos automáticos 10.1 Estruturas automáticas . 10.2 Caraterização geométrica 10.3 Propriedades . . . . . . . 10.4 Exercı́cios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85 85 88 91 95 . . . . . . . . Bibliografia 96 Índice de conceitos 97 3 1 Grupos Começamos este curso lembrando fatos básicos sobre grupos que já foram estudados na graduação. 1.1 Grupos de permutações Uma grande parte da Matemática é dedicada ao estudo de funções. E dentro do estudo das funções, merece destaque o estudo das permutações. Uma permutação de um conjunto X é simplesmente uma função bijetiva σ : X → X. À primeira vista, o conceito parece um pouco restritivo... a maior parte das funções não são bijetivas... mas muitas funções importantes, na Matemática e fora dela, são bijetivas: • Álgebra linear: isomorfismos de um espaço vetorial. • Topologia: homeomorfismos de espaços métricos/topológicos. • Sistemas dinâmicos: em geral, as transformações consideradas são homeomorfismos. • Fı́sica quântica: as transformações na mecânica quântica assumem-se reversı́veis (e bijetivas). Uma das coisas mais importantes e úteis que se podem fazer com funções é compô-las. É claro que a composição de duas permutações de um conjunto X é ainda uma permutação de X. E a função inversa de uma permutação de X é ainda uma permutação de X. Estas duas operações (composição e inversão) são fundamentais na construção do conceito de grupo de permutações: Seja SX o conjunto de todas as permutações do conjunto X e seja 1X a permutação identidade. Dizemos que G ⊆ SX é um grupo de permutações se: • G é fechado para composição; • 1X ∈ G; • a permutação inversa de uma permutação em G está também em G. Eis alguns exemplos de grupos de permutações: • SX (diz-se o grupo simétrico sobre X); • o conjunto dos automorfismos de um espaço vetorial; • o conjunto dos auto-homeomorfismos de um espaço métrico/topológico; 1.2 Noção abstrata de grupo Historicamente, o estudo dos grupos começou por ser o estudo dos grupos de permutações, e em muitos casos grupos bem concretos que interessavam à Fı́sica e a várias áreas da Matemática. Na segunda metade do século XIX, apareceu uma outra perspetiva do conceito de grupo, bem mais abstrata, que dispensava permutações e composição. Na versão abstrata, um grupo é um conjunto não vazio G, no qual está definida uma operação binária · : G × G → G satisfazendo as seguintes propriedades: 4 (G1) Associatividade: a · (b · c) = (a · b) · c para todos a, b, c ∈ G. (G2) Existência de elemento neutro: existe um elemento 1G ∈ G tal que 1G · a = a · 1G = a para todo a ∈ G. (G3) Existência de inversos: para todo a ∈ G, existe um elemento b ∈ G tal que a · b = b · a = 1G . É fácil mostrar que o elemento neutro é único e que cada elemento tem um único inverso. Em geral, designamos o neutro por 1 e o inverso de a por a−1 . Se só exigirmos (G1) e (G2), a estrutura é chamada de monóide. Exemplo 1.1 Seja n ∈ N e seja GLn (R) o conjunto de todas as matrizes n × n invertı́veis com entradas reais. Então GLn (R), com o produto de matrizes, constitui um grupo. É claro que todo grupo de permutações satisfaz os axiomas (G1) – (G3), pois a composição de funções é associativa, a identidade funciona como elemento neutro e cada permutação inversa é um inverso no sentido de (G3). Veremos mais adiante que os dois conceitos de grupo (o abstrato e o de grupo de permutações) são essencialmente equivalentes. Mas primeiro necessitamos de relembrar alguns conceitos básicos. Seja G um grupo (quando falamos de um grupo abstrato genérico, dispensamo-nos de referir a operação binária · e escrevemos ab em vez de a · b). Dizemos que H ⊆ G é um subgrupo de G e escrevemos H ≤ G se: • 1G ∈ H; • se a, b ∈ H, então ab ∈ H; • se a ∈ H, então a−1 ∈ H. Isto equivale a dizer que H é ele próprio um grupo quando consideramos a restrição a H × H da operação binária em G. Exemplo 1.2 Seja n ∈ N e seja SLn (R) o conjunto de todas as matrizes n × n com entradas reais e determinante 1. Então SLn (R) constitui um subgrupo do grupo GLn (R) do Exemplo 1.1. 1.3 Homomorfismos e quocientes Outro conceito fundamental é o conceito de homomorfismo. Sejam G, H grupos. Uma função ϕ : G → H é um homomorfismo (de grupos) se (ab)ϕ = (aϕ)(bϕ) para todos a, b ∈ G. Se ϕ : G → H é um homomorfismo, então é fácil verificar as seguintes propriedades: • 1G ϕ = 1H ; • a−1 ϕ = (aϕ)−1 para todo a ∈ G. 5 Um isomorfismo bijetivo é um isomorfismo. Dois grupos G e H dizem-se isomorfos (e escrevemos G∼ = H) se existir um isomorfismo ϕ : G → H. Note-se que nesse caso a função inversa ϕ−1 : H → G é também um isomorfismo. Um isomorfismo de um grupo nele próprio é um automorfismo. Analogamente se define homomorfismo de monóides, mas exige-se também a igualdade 1ϕ = 1, pois no caso dos monóides esta não resulta automaticamente da igualdade (ab)ϕ = (aϕ)(bϕ). Podemos agora estabelecer a mencionada equivalência entre os conceitos de grupo (abstrato) e grupo de permutações (Teorema de Cayley): Teorema 1.3 (Cayley 1854, Jordan 1870) Todo grupo é isomorfo a algum grupo de permutações. Prova. Seja G um grupo e seja SG o grupo simétrico sobre o conjunto G. Dado g ∈ G, seja σg ∈ SG a permutação definida por aσg = ag. Seja H = {σg | g ∈ G}. Temos • σ1 = 1G , • σgh = σg σh , • σg−1 = σg−1 para todos g, h ∈ G, logo H é um subgrupo de SG . Finalmente, σ : G → H é um isomorfismo (a injetividade resulta de g 6= h ⇒ 1σg 6= 1σh ). Vamos agora introduzir o conceito de grupo quociente. A ideia é fazer uma partição dos elementos de um grupo G em classes de equivalência [g] (g ∈ G) de forma a que o conjunto das classes possa constituir um grupo sob a operação induzida (g, h ∈ G). [g][h] = [gh] Para que esta operação esteja bem definida e dê efetivamente origem a um grupo, é preciso que a classe N = [1] seja um subgrupo do seguinte tipo: Se G é um grupo e N ≤ G, dizemos que N é um subgrupo normal e escrevemos N E G se aN a−1 = N para cada a ∈ G. Além do mais, verifica-se que para cumprir o nosso programa precisamos que a partição seja constituı́da por classes da forma [a] = aN = N a. Isto conduz-nos ao conceito de grupo quociente: Seja G um grupo e N EG. Seja G/N = {N a | a ∈ G} com a operação binária (N a)(N b) = N ab. Então G/N constitui um grupo, que se diz o grupo quociente de G por N . Exemplo 1.4 SLn (R) E GLn (R) para todo n ∈ N. De fato, se P ∈ GLn (R), então det(P −1 ) = (det(P ))−1 , logo det(M ) = 1 implica det(P M P −1 ) = (det(P ))(det(M ))(det(P −1 )) = 1, e o subgrupo é normal. O grupo quociente consiste então em todas os conjuntos de matrizes do tipo (SLn (R))M (M ∈ GLn (R)). Podemos encontrar uma descrição mais simples? A resposta é dada com a ajuda dos teoremas do homomorfismo, que relacionam homomorfismos e quocientes. É claro que se N E G, então a projeção canónica πN : G → G/N a 7→ N a 6 é um homomorfismo. Por outro lado, dado um homomorfismo de grupos ϕ : G → H, o núcleo de ϕ é definido por Ker(ϕ) = 1ϕ−1 . Teorema 1.5 Seja ϕ : G → H um homomorfismo de grupos. Então: (i) Ker(ϕ) E G; (ii) se N E G e N ⊆ Ker(ϕ), então existe um e um só homomorfismo de grupos Φ : G/N → H tal que πN Φ = ϕ, G πN ϕ /H < Φ G/N dado por (N a)Φ = aϕ; (iii) se ϕ for sobrejetivo e N = Ker(ϕ), então Φ é um isomorfismo. A prova é simples, e já foi estudada em cursos de álgebra na graduação. Agora podemos revisitar o grupo quociente do Exemplo 1.4. Seja R∗ o grupo constituı́do por R \ {0}, com a operação produto. Exemplo 1.6 GLn (R) / SLn (R) ∼ = R∗ . Consideremos ϕ : GLn (R) → R∗ definida por M ϕ = det(M ). Como det(M M 0 ) = (det(M ))(det(M 0 )) para todas matrizes M, M 0 ∈ GLn (R), ϕ é um homomorfismo, além do mais sobrejetivo. Finalmente, Kerϕ = SLn (R), logo obtemos GLn (R) / SLn (R) = GLn (R) / Ker(ϕ) ∼ = R∗ pelo Teorema 1.5(iii). 1.4 Outros conceitos Dado um grupo G, dizemos que H ≤ G tem ı́ndice finito se G = Hg1 ∪ . . . ∪ Hgn para algum número finito de elementos g1 , . . . , gn ∈ G. Nesse caso, o menor n possı́vel diz-se o ı́ndice de H em G e designa-se por [G : H]. Dado X ⊆ G, é fácil de ver que o conjunto dos elementos da forma xε11 . . . xεnn , onde n ≥ 0, xi ∈ X e εi ∈ {1, −1} para i = 1, . . . , n, constitui o menor subgrupo de G contendo X. Diz-se o subgrupo de G gerado por X e representa-se por hXi. Um (sub)grupo diz-se finitamente 7 gerado se puder ser gerado por um subconjunto finito. Usaremos a notação H ≤f.g. G para exprimir que H é um subgrupo finitamente gerado de G. Nem todo grupo é finitamente gerado: para quem dominar argumento de cardinalidade, é fácil ver que todo o grupo finitamente gerado é enumerável, e existem grupos não enumeráveis (por exemplo, o grupo aditivo dos reais). Um grupo gerado por um único elemento diz-se um grupo cı́clico. A menos de isomorfismo, (Z, +) é o único grupo cı́clico infinito. Dado n ≥ 1, existe também um único grupo cı́clico com n elementos a menos de isomorfismo, e é designado por Cn . Se Cn = hai, então Cn = {a, a2 , . . . , an−1 , an = 1}. Dado um elemento a de um grupo G, a ordem de a é a cardinalidade do subgrupo hai. Um elemento pode ter ordem finita ou infinita. Dados grupos G e H, podemos definir uma operação em G × H através de (g, h)(g 0 , h0 ) = (gg 0 , hh0 ). Com esta operação, G × H é um grupo que se diz o produto direto dos grupos G e H. 1.5 Exercı́cios (1.1) Seja G= R∗ R 0 R∗ com a operação produto de matrizes. Mostre que: (a) G é um grupo; (b) H= 1 Z 0 1 é um subgrupo cı́clico de G. (1.2) Sejam G e H grupos. (a) Mostre que H pode ser visto como um subgrupo de G × H. ∼ G. (b) Mostre que nesse caso (G × H)/H = (1.3) Seja G = R × R∗ com a operação (x, y)(x0 , y 0 ) = (x + yx0 , yy 0 ). Mostre que: (a) G é um grupo; 8 (b) H = R × {1} é um subgrupo normal de G; (b) G/H ∼ = R∗ . (1.4) Mostre que C35 ∼ = C5 × C7 . (1.5) Seja G um grupo e sejam a, b ∈ G tais que H, aHb ≤ G. Mostre que aHb = aHa−1 = b−1 Hb. (1.6) Seja H um subgrupo de ı́ndice finito de um grupo G. Mostre que: (a) xHx−1 é um subgrupo de ı́ndice finito de G para todo x ∈ G; (b) só existe um número finito de subgrupos da forma xHx−1 (x ∈ G). 9 2 Grafos e autômatos O conceito de autômato é fundamental na teoria da computação, e tem-se revelado da maior utilidade para a moderna teoria de grupos. Vamos apresentar em seguida alguns conceitos e resultados básicos. 2.1 Palavras e linguagens Neste contexto, usamos o termo alfabeto para designar um conjunto e os seus elementos são chamados de letras. Muito apropriadamente, uma sequência finita de letras é chamada de palavra. Isto inclui a palavra vazia, que convencionamos representar pelo sı́mbolo 1. As palavras não vazias (no alfabeto A) são geralmente representadas na forma a1 a2 . . . an com a1 , . . . , an ∈ A. O comprimento da palavra a1 . . . an é n, e o comprimento da palavra vazia é 0. Designamos o comprimento da palavra u por |u|. Ao longo deste curso, A designará sempre um alfabeto finito, pelo que não faremos mais referências a esse fato. O conjunto de todas as palavras em A é designado por A∗ , e A é identificado com o conjunto das palavras de comprimento 1. Escrevemos também A+ = A∗ \ {1}. Podemos definir um produto em A∗ , dito de concatenação. Para palavras não vazias, é definido por (a1 . . . an )(b1 . . . bm ) = a1 . . . an b1 . . . bm , e a palavra vazia funciona como elemento neutro. Com esta operação, A∗ é um monóide. Mas não é um monóide qualquer, pois satisfaz a seguinte propriedade (dita universal): Proposição 2.1 Seja ϕ : A → M uma função de A num monóide M qualquer. Então existe um único homomorfismo de monóides Φ : A∗ → M que estende a função ϕ: A _ ϕ /M > Φ A∗ Prova. É fácil ver que Φ tem que ser definido por (a1 . . . an )Φ = (a1 ϕ) . . . (an ϕ) e 1Φ = 1, e que é realmente um homomorfismo de monóides. O significado desta propriedade é que A tem em relação a A∗ o mesmo comportamento que a base de um espaço vetorial V tem em relação a V , quando substituı́mos homomorfismos por aplicações lineares. Logo podemos pensar em A como uma base de A∗ . As diferenças são as seguintes: • Nem todo monóide tem uma base: a menos de isomorfismo, só os monóides da forma A∗ têm uma base. • A é a única base de A∗ . 10 Como A∗ satisfaz a propriedade universal relativamente a A, diz-se o monóide livre sobre A. Certas relações entre palavras são muito importantes. Dadas u, v ∈ A∗ , dizemos que: • u é um prefixo de v se v = uy para alguma y ∈ A∗ ; • u é um sufixo de v se v = xu para alguma x ∈ A∗ ; • u é um fator de v se v = xuy para algumas x, y ∈ A∗ . Um subconjunto de palavras em A é chamado de A-linguagem, ou simplesmente linguagem quando o alfabeto está implı́cito ou é irrelevante. A teoria de linguagens é um ramo importante da teoria da computação que pretende classificar as linguagens e explorar o potencial algorı́tmico das diversas subclasses. O trabalho pioneiro de Noam Chomsky nos anos 50 está na sua origem, pelo que a teoria de linguagens se desenvolveu inicialmente no seio da Linguı́stica e não da Informática ou da Matemática. A teoria deve importantes contribuições ao informático brasileiro Imre Simon. Se L é uma A-linguagem, é habitual designar por L∗ o conjunto de todas as palavras do tipo u1 u2 . . . un com n ≥ 0 e ui ∈ L para todo i. Claro que se n = 0 temos a palavra vazia. Isto faz de L∗ é o submonóide de A∗ gerado por L. É desagradável que se tenha instucionalizado o uso da notação ∗ com dois significados diferentes (monóide livre e submonóide gerado por), mas felizmente não há confusão quando escrevemos A∗ . 2.2 Grafos Os grafos são estruturas combinatórias que desempenham um papel muito importante em várias áreas da Matemática, pura ou aplicada, e da Computação. Neste curso, designaremos por grafo uma estrutura do tipo Γ = (V, E), onde V é um conjunto não vazio (o conjunto dos vértices) e E um conjunto de pares (não ordenados) de elementos de V (arestas). É habitual descrever um grafo geometricamente utlizando pontos para representar os vértices e linhas para representar as arestas. Eis um exemplo de um grafo com 7 vértices e 5 arestas: • • • • • • • Note-se que nenhuma aresta pode ligar um vértice a si próprio! Um grafo com um número finito de vértices diz-se finito. Dois vértices dizem-se adjacentes se estiverem ligados por uma aresta. O grafo diz-se conexo se quaisquer dois vértices estiverem ligados por uma sequência de arestas (isto é, se pertencerem a uma sequência de vértices adjacentes). Um isomorfismo de grafos estabelece uma bijeção entre os vértices que preserva a adjacência (isto é, a estrutura é a mesma a menos da designação dos vértices). Dois grafos são isomorfos se houver um isomorfismo entre eles. Um isomorfismo de um grafo nele próprio é um automorfismo. Uma variante deste conceito é a noção de grafo orientado, em que cada aresta está dotada de uma orientação especı́fica. Formalmente, um grafo orientado é uma estrutura do tipo Γ = (V, E), onde V é um conjunto não vazio e E ⊆ V ×V . É habitual descrever um grafo orientado geometricamente 11 utlizando pontos para representar os vértices e setas para representar as arestas. Eis um exemplo de um grafo orientado com 4 vértices e 4 arestas: *•o •j 2.3 • •e Autômatos Um autômato pode ser descrito informalmente como um grafo orientado em que as arestas têm rótulos que não são mais do que letras de um certo alfabeto finito. Além disto, alguns vértices são chamados de iniciais e outros (que podem ser ou não os mesmos!) de terminais. Também é habitual utilizar uma representação geométrica, em que os vértices iniciais (respetivamente finais) são identificados por uma seta que entra (respetivamente sai), sem rótulo: Exemplo 2.2 Autômato no alfabeto A = {a, b}: b o /•j a *•p b a Formalmente, se A é um alfabeto finito, um A-autômato é uma estrutura do tipo A = (Q, I, T, E), onde • Q é um conjunto; • E ⊆ Q × A × Q; • I, T ⊆ Q. O conjunto Q é o conjunto dos vértices, I é o conjunto dos vértices iniciais, T é o conjunto dos vértices terminais e E é o conjunto das arestas. Se não designarmos vértices iniciais nem terminais, temos a estrutura simplificada (Q, E), que se diz um A-grafo. O autômato A = (Q, I, T, E) diz-se finito se Q for finito. Dois autômatos A = (Q, I, T, E) e A0 = (Q0 , I 0 , T 0 , E 0 ) dizem-se isomorfos se existir uma bijeção ϕ : Q → Q0 tal que Iϕ = I 0 , T ϕ = T 0 e (p, a, q) ∈ E ⇔ (pϕ, a, qϕ) ∈ E 0 para todos p, q ∈ Q e a ∈ A (isto é, têm a mesma estrutura a menos da designação dos vértices). A grande utilidade de um A-autômato é que ele permite definir uma A-linguagem do seguinte modo: Um caminho não trivial em A = (Q, I, T, E) é uma sequência a a a 1 2 n q0 −→q 1 −→ . . . −→qn tal que (qi−1 , a, qi ) ∈ E para i = 1, . . . , n. O seu rótulo é a palavra a1 . . . an ∈ A∗ . Diz-se um 1 caminho bem-sucedido se q0 ∈ I e qn ∈ T . Consideramos também o caminho trivial q −→q para 12 cada q ∈ Q (o rótulo é a palavra vazia 1), que é bem-sucedido se q ∈ I ∩ T . Representamos por u p−→q qualquer caminho de rótulo u ligando p a q. Um caminho que começa e termina no mesmo vértice diz-se um loop. A linguagem L(A) reconhecida por A é o conjunto dos rótulos dos caminhos bem-sucedidos em A. Uma A-linguagem L diz-se racional se L = L(A) para algum A-autômato finito A. Exemplo 2.3 A linguagem do autômato do Exemplo 2.2 é o conjunto de todas as palavras no alfabeto A = {a, b} onde a letra a ocorre um número par de vezes. Um A-autômato A = (Q, I, T, E) diz-se determinı́stico se tiver um único estado inicial e (p, a, q), (p, a, r) ∈ E ⇒ q = r para todos p, q, r ∈ Q e a ∈ A. A vantagem de um autômato ser determinı́stico é que, para testar se uma palavra u é reconhecida pelo autômato, basta considerar no máximo um caminho de rótulo u a partir do estado inicial. Por outro lado, podemos alargar o conceito de autômato admitindo também arestas com rótulo 1: são os autômatos com transições-1. O teorema seguinte mostra que estas 3 versões de autômato são equivalentes no que respeita a linguagens: Proposição 2.4 Seja L uma A-linguagem. As condições seguintes são equivalentes: (i) L é racional; (ii) L = L(A) para algum A-autômato finito determinı́stico A; (iii) L = L(A) para algum A-autômato finito com transições-1 A; (iv) existe um homomorfismo de monóides ϕ : A∗ → M com M finito tal que L = Lϕϕ−1 . Prova. (ii) ⇒ (i) ⇒ (iii). Imediato. (iii) ⇒ (iv). Seja A = (Q, I, T, E) um A-autômato finito com transições-1 tal que L = L(A). Seja M 0 = 2Q×Q o conjunto de todas as relações binárias no conjunto Q. Dadas R, S ∈ M 0 , a sua composição é definida por R ◦ S = {(p, q) ∈ Q × Q | (p, r) ∈ R, (r, q) ∈ S para algum r ∈ Q}. Esta operação é associativa e a relação identidade 1Q funciona como elemento neutro, logo M 0 é de fato um monóide (finito). Definimos uma função ϕ : A∗ → M 0 do seguinte modo. Para toda palavra u ∈ A∗ , fazemos u uϕ = {(p, q) ∈ Q × Q | existe um caminho p−→q em A}. Temos (uv)ϕ = (uϕ) ◦ (vϕ) para todas u, v ∈ A∗ . Em particular, (uϕ) ◦ (1ϕ) = (u · 1)ϕ = uϕ = (1 · u)ϕ = (1ϕ) ◦ (uϕ) 13 para todo u ∈ A∗ , logo M = im(ϕ) munido da operac cão de composição é um monóide finito com elemento neutro 1ϕ, e ϕ : A∗ → M é um homomorfismo sobrejetivo de monóides. Claro que L ⊆ Lϕϕ−1 . Reciprocamente, suponhamos que uϕ = vϕ com v ∈ L. Então existe v u um caminho I 3 i−→t ∈ T em A. Mas então existe também um caminho i−→t, logo u ∈ L. Assim se conclui que L = Lϕϕ−1 como pretendido. (iv) ⇒ (ii). Seja A = (M, 1M , Lϕ, E) com E = {(x, a, y) ∈ M × A × M | y = x(aϕ)}. u É claro que A é um A-autômato finito determinı́stico. Além disso, p−→q é um caminho se e só se q = p(uϕ). Logo L(A) = {u ∈ A∗ | 1M (uϕ) ∈ Lϕ} = Lϕϕ−1 = L e a prova está completa. Para além do determinismo, há outras propriedades importantes de autômatos. Dizemos que um autômato A = (Q, I, T, E) é: • aparado se todo vértice ocorre nalgum caminho bem-sucedido; • completo se, para todos p ∈ Q e a ∈ A, existe alguma aresta da forma (p, a, q). A seguir mostramos que o conjunto das A-linguagens racionais é fechado para os operadores booleanos: Proposição 2.5 Sejam K, L A-linguagens racionais. Então as linguagens K ∪ L, K ∩ L e A∗ \ L são racionais. Prova. Como K∩L = A∗ \((A∗ \K)∪(A∗ \L)), basta mostrar o resultado para união e complemento. Para a união, tomamos a união disjunta de dois autômatos reconhecendo K e L. Para o complemento, recordamos que na prova de (iv) ⇒ (ii) da Proposição 2.4 construimos um autômato finito que além de determinı́stico é completo. Se trocarmos os vértices terminais pelos não-terminais num tal autômato, passaremos a reconhecer o complemento da linguagem. No entanto, há um método mais construtivo de lidar com a interseção: dados A-autômatos A = (Q, I, T, E) e A0 = (Q0 , I 0 , T 0 , E 0 ), definimos o produto direto A×A0 = (Q×Q0 , I ×I 0 , T ×T 0 , E 00 ) com E 00 = {((p, p0 ), a, (q, q 0 )) | (p, a, q) ∈ E, (p0 , a0 , q 0 ) ∈ E 0 }. Proposição 2.6 Dados A-autômatos A e A0 , L(A × A0 ) = L(A) ∩ L(A0 ). Prova. Basta observar que os caminhos bem sucedidos em A × A0 são da forma a a a 1 2 n 0 0 → (q0 , q00 )−→(q 1 , q1 )−→ . . . −→(qn , qn ) →, com a1 , . . . , an ∈ A, onde a a a 1 2 n → q0 −→q 1 −→ . . . −→qn → 14 é um caminho bem sucedido em A e a a a 1 n 0 2 0 → q00 −→q 1 −→ . . . −→qn → é um caminho bem sucedido em A0 . A classe das linguagens racionais também é fechada para os operadores produto e estrela: Proposição 2.7 Sejam K, L A-linguagens racionais. Então as linguagens KL e K ∗ são racionais. Prova. Suponhamos que A = (Q, I, T, E) e A0 = (Q0 , I 0 , T 0 , E 0 ) são A-autômatos finitos reconhecendo K e L, respetivamente. POdemos assumir que Q ∩ Q0 = ∅. Definimos um A-autômato finito com transições-1 B = (Q ∪ Q0 , I, T 0 , E ∪ E 0 ∪ (T × {1} × I 0 )). /ij *t A 1 i0 k A0 + t0 / Os caminhos bem-sucedidos em B são da forma u 1 v I 3 i−→t−→i0 −→t0 ∈ T 0 com t ∈ T , i0 ∈ I 0 , u ∈ K e v ∈ L, logo L(B) = {uv | u ∈ K, v ∈ L} = KL. Por outro lado, seja z ∈ / Q. Definimos um A-autômato finito com transições-1 B 0 = (Q ∪ {z}, z, z, E ∪ ({z} × {1} × I) ∪ (T × {1} × {z})). i j_ o *t A 1 /z 1 É fácil ver que L(B 0 ) = K ∗ . Pela Proposição 2.4, as linguagens KL e K ∗ são racionais. Como as linguagens finitas são obviamente racionais, resulta das Proposições 2.5 e 2.7 que qualquer linguagem obtida a partir de linguagens finitas utilizando um número finito de vezes os operadores união, produto e estrela é necessariamente racional. O recı́proco é também verdadeiro: Teorema 2.8 (Kleene 1956) Seja L ⊆ A∗ . Então as condições seguintes são equivalentes: 15 (i) L é racional; (ii) L pode ser obtida a partir de A-linguagens finitas utilizando um número finito de vezes os operadores união, produto e estrela. A demonstração de (i) ⇒ (ii) é proposta no Exercı́cio 2.8. Podemos também mostrar que as linguagens racionais se comportam muito bem relativamente a homomorfismos: Proposição 2.9 Sejam A, B alfabetos finitos e ϕ : A∗ → B ∗ um homomorfismo de monóides. (i) Se K ⊆ A∗ é racional, então Kϕ é racional. (ii) Se L ⊆ B ∗ é racional, então Lϕ−1 é racional. Prova. (i) Seja A um A-autômato finito reconhecendo K. Substituindo cada rótulo a em A por uma aresta ou sucessão de arestas de rótulo aϕ, obtemos um B-autômato finito (com transições-1 se 1 ∈ Aϕ) que reconhece Kϕ. Pela Proposição 2.4, Kϕ é racional. (ii) Seja L0 = L ∩ (A∗ ϕ). Pelas alı́nea (i) e pela Proposição 2.5, L0 é racional. Pela Proposição 2.4, existe um homomorfismo de monóides θ : B ∗ → M com M finito tal que L0 = L0 θθ−1 . Seja ψ : A∗ → M o homomorfismo definido por ψ = ϕθ. Então (L0 ϕ−1 )ψψ −1 = L0 ϕ−1 ϕθθ−1 ϕ−1 = L0 θθ−1 ϕ−1 = L0 ϕ−1 , logo L0 ϕ−1 é racional. Como Lϕ−1 = L0 ϕ−1 , resulta que Lϕ−1 é racional. 2.4 Sistemas de reescrita Os sistemas de reescrita são uma ferramenta importante na álgebra e na teoria da computação. Vamos apresentar algumas noções básicas que serão úteis para o estudo do grupo livre. Seja A um alfabeto finito. Um sistema de reescrita em A é um subconjunto R of A∗ × A∗ (isto é, uma relação binária em A!). Recebem aqui um nome diferente porque vamos usá-los numa perspetiva diferente: vão-nos permitir substituir fatores dentro de palavras: Dadas u, v ∈ A∗ , escrevemos u −→R v (redução elementar) se existirem (r, s) ∈ R e x, y ∈ A∗ tais que u = xry e v = xsy. Escrevemos u −→∗R v (redução) se u = v ou se existir alguma cadeia x = z0 −→R z1 −→R . . . −→R zm = y. Sempre que não haja confusão possı́vel, omitimos o ı́ndice Dizemos que R é: R. • redutor se |r| > |s| para todo (r, s) ∈R; • noetheriano se não existir nenhuma cadeia infinita de reduções elementares w0 −→R w1 −→R w2 −→R . . . 16 • confluente se, sempre que u−→∗ v e u−→∗ w, existir alguma z ∈ A∗ tal que v−→∗ z e w−→∗ z: u ∗ ∗ w ∗ /v / z ∗ É claro que todo sistema de reescrita redutor é necessariamente noetheriano. Uma palavra u ∈ A∗ é irredutı́vel se não existir v ∈ A∗ tal que u−→v. Seja Irr(R) o conjunto de todas as palavras irredutı́veis de A∗ com respeito a R. Proposição 2.10 Seja R ⊆ A∗ × A∗ um sistema de reescrita noetheriano e confluente. Para toda palavra u ∈ A∗ , existe uma e uma só v ∈ Irr(R) tal que u−→∗ v. Prova. O ser noetheriano garante a existência, a confluência garante a unicidade. 2.5 Exercı́cios (2.1) Seja M um monóide finito não trivial. Mostre que a propriedade universal não é válida para nenhum subconjunto de M , e que portanto M não possui uma base. (2.2) Quantos grafos de 4 vértices existem, a menos de isomorfismo? (2.3) Quantos grafos orientados de 2 vértices existem, a menos de isomorfismo? (2.4) Seja A = {a, b}. Construa um A-autômato finito reconhecendo cada uma das seguintes Alinguagens: (a) {palavras acabando em aba}; (b) {palavras de comprimento par}. (2.5) Seja A = {0, 1}. Construa um A-autômato finito reconhecendo todos os números naturais divisı́veis por 3, escritos em binário. (2.6) Considere os seguintes autômatos: o b /• a /• a ` b • ~ o a /• ` b b B• A B 17 /• b a b (a) Determine L(A) e L(B). (b) Construa um autômato finito reconhecendo L(A) ∩ L(B). (2.7) Seja A = {a, b} e seja A o A-autômato com transições-1 descrito por a /1j a b *2 / 1 Usando os algoritmos implı́citos na prova da Proposição 2.4, construa um autômato finito determinı́stico completo que reconheça A∗ \ L(A). (2.8) Seja A um alfabeto finito e seja A = (Q, 0, T, E) um A-autômato com Q = {0, . . . , m}. Dados (k) p, q ∈ Q e k ∈ {0, . . . , m + 1}, seja Lp,q o conjunto dos rótulos dos caminhos p−→q em que todos os vértices intermédios são < k. (a) Mostre que (k) (k) (k) ∗ L(k+1) = L(k) p,q p,q ∪ Lp,k (Lk,k ) Lk,q para todos p, q, k ∈ Q. (b) Usando recursivamente a alı́nea (a), demonstre a implicação (i) ⇒ (ii) do Teorema 2.8. (2.9) Seja A = {a, b} e considere o sistema de reescrita em A definido por R= {(ab, 1)}. (a) Mostre que R é redutor e confluente. (b) Calcule Irr(R). 18 3 Grupos livres Nesta secção definimos os grupos livres e estudamos algumas das suas propriedades básicas. 3.1 Construção Seja A um alfabeto. Queremos que o grupo livre sobre A seja um grupo que satisfaça a propriedade universal na classe dos grupos (analogamente à Proposição 2.1). Começamos por introduzir um conjunto A−1 de inversos formais of A (i.e. a 7→ a−1 define uma e = A ∪ A−1 , estendemos bijeção de A com um conjunto A−1 disjunto de A). Usando a notação A −1 −1 ∗ ∗ e →A e através de indutivamente a função a 7→ a a uma transformação :A • 1−1 = 1, • (a−1 )−1 = a (a ∈ A), • (ua)−1 = a−1 u−1 e+ , a ∈ A). e (u ∈ A e∗ , pelo que é chamada de Note-se que esta transformação satisfaz (u−1 )−1 = u para todo u ∈ A involução. Esta involução será importante para os chamados homomorfismos involutivos. Se G é e∗ → G se diz involutivo se u−1 ϕ = (uϕ)−1 para um grupo, um homomorfismo (de monóides) ϕ : A ∗ e todo u ∈ A . e por Definimos agora um sistema de reescrita em A e RA = {(aa−1 , 1) | a ∈ A}. É fácil provar que: Lema 3.1 O sistema de reescrita RA é redutor e confluente. Prova. É claro que o sistema é redutor. Para a confluência, supomos que x00 −→x01 −→ . . . −→x0n , x00 −→x10 −→ . . . −→xm0 , são duas sequências de transições em RA . Basta mostrar a confluência localmente, construindo a 19 grelha x00 / x01 / ... / x0n x10 / x11 / ... / x1n .. . .. . .. . / xm1 xm0 / ... / xmn / pode representar uma redução elementar ou igualdade passo a passo (onde cada seta mesmo). Para completar cada quadrado, basta mostrar a confluência para qualquer caso da forma / x 1 y1 u x 2 y2 −1 −1 −1 e∗ e onde u = x1 a1 a−1 1 y1 = x2 a2 a2 y2 com xi , yi ∈ A e ai ∈ A. Se as ocorrências de a1 a1 e a2 a2 forem disjuntas, podemos reproduzir a redução de tipo alternativo em cada uma das palavras x1 y1 e x2 y2 . Caso as ocorrências se sobreponham, resulta imediatamente x1 y1 = x2 y2 . Logo é válida a confluência local, que implica a confluência no sentido geral do termo. e Seja RA = Irr(RA ). As palavras de RA dizem-se reduzidas. São precisamente as palavras em A e Pela Proposição 2.10 e pelo Lema 3.1, obtemos: sem fatores do tipo aa−1 (a ∈ A). e∗ , existe uma única palavra reduzida u ∈ RA tal que Lema 3.2 Seja A um alfabeto. Dada u ∈ A ∗ u −→RA u. e∗ por Definimos uma relação de equivalência ρA em A u ρA v se u = v e∗ , definimos Designando por uρA a classe de equivalência de u ∈ A e∗ /ρA = {uρA | u ∈ A e∗ }. FA = A Mostramos em seguida que FA é um grupo que satisfaz a propriedade universal: 20 Teorema 3.3 Seja A um alfabeto. Então: (i) FA é um grupo para a operação binária (uρA )(vρA ) = (uv)ρA . (ii) A função ι : A → FA a 7→ aρA é injetiva. (iii) Seja ϕ : A → G uma função de A num grupo G qualquer. Então existe um único homomorfismo de grupos Φ : FA → G tal que ιΦ = ϕ: ϕ A _ ι /G > Φ FA Prova. (i) Primeiro há que mostrar que a operação está bem definida. Suponhamos que u ρA u0 e v ρA v 0 . Será que (uv)ρA (u0 v 0 )? Efetivamente, de u = u0 e v = v 0 resulta (pela unicidade no Lema 3.2) que uv = u v = u0 v 0 = u0 v 0 , logo (uv)ρA (u0 v 0 ) e a operação está bem definida. e∗ se É imediato que a operação é associativa e tem elemento neutro 1ρA . Como para todo u ∈ A −1 −1 −1 tem uu−1 = 1, resulta que (uρA )(u ρA ) = (uu )ρA = 1ρA . Analogamente, (u ρA )(uρA ) = 1ρA , logo FA é um grupo. (ii) Como todas as letras são palavras reduzidas, a injetividade resulta do Lema 3.2. e → G fazendo a−1 ϕ0 = (iii) Começamos por estender a função ϕ : A → G a uma função ϕ0 : A −1 (aϕ) (a ∈ A). Pela propriedade universal (Proposição 2.1), existe um único homomorfismo de e∗ → G que estende ϕ0 . Note-se que este homomorfismo é involutivo. monóides Φ0 : A e∗ , é fácil ver que uΦ0 = uΦ0 , logo u ρA v implica uΦ0 = vΦ0 . Podemos então definir Dado u ∈ A uma função Φ : FA → G através de (uρA )Φ = uΦ0 e∗ ). (u ∈ A e∗ → FA a É fácil verificar que Φ é na realidade um homomorfismo de grupos. Designando por θ : A projeção canónica, obtemos um diagrama ϕ A _ ϕ0 e A /G ? O ` Φ Φ0 e∗ /A θ / FA que é composto de três diagramas comutativos. Logo ιΦ = ϕ. Finalmente, a unicidade de Φ resulta do fato de Aθ gerar o grupo FA , pelo que Φ vem determinado por ϕ. 21 Face ao Teorema 3.3, podemos dizer que FA é o grupo livre sobre A. É simples verificar que RA com a operação binária (u, v) 7→ uv constitui um grupo e que FA → RA uρA 7→ u é um isomorfismo de grupos. Por isso é muito comum identificar o grupo livre com o conjunto das palavras reduzidas. Nós também faremos isso quando for conveniente. Usaremos também a e∗ . notação uρA = u para todo u ∈ A Além do mais, estendemos a FA vários dos conceitos introduzidos na Subsecção 2.1. Por exemplo, dados g, h ∈ FA , temos |g| = |g| e g é prefixo de h se e só se g é prefixo de h. 3.2 Propriedades básicas A primeira consequência da existência dos grupos livres é a seguinte: Teorema 3.4 Todo o grupo é isomorfo a algum quociente de um grupo livre. Prova. Seja G um grupo e seja A ⊆ G um subconjunto gerador de G (poderı́amos até tomar o próprio G!). Pela propridade universal, a inclusão A ,→ G induz um homomorfismo de grupos Φ : FA → G, que é sobrejetivo dado que G = hAi. Logo G ∼ = FA /Ker(Φ) pelo Teorema 1.5(iii). Em seguida vamos determinar quando dois grupos livres são isomorfos. Teorema 3.5 Sejam A e B conjuntos. Então as condições seguintes são equivalentes: (i) FA ∼ = FB ; (ii) |A| = |B|. |A| Prova. (i) ⇒ (ii). Seja ϕ : FA → FB um isomorfismo. Seja C2 o produto direto de |A| cópias do grupo cı́clico C2 . Suponhamos que A = {a1 , . . . , am }. Para i = 1, . . . , m, designamos por |u|ai e∗ . Note-se que |u|a = |u|a , a soma dos expoentes das ocorrências de a/a−1 na palavra u ∈ A i i |A| logo isto permite definir |g|ai para todo g ∈ FA . Seja πA : FA → C2 a função definida por gπA = (|g|a1 , . . . , |g|am ). É rotina verificar que πA é um homomorfismo sobrejetivo de grupos. |B| Definindo de forma análoga πB : FB → C2 , temos também um homomorfismo sobrejetivo. Suponhamos que g ∈ Ker(πA ). Então |g|ai é par para i = 1, . . . , m. Daqui resulta que |gϕ|b é par para todo b ∈ B, logo gϕ ∈ Ker(πB ) e portanto Ker(πA ) ⊆ Ker(ϕπB ). Pelo Teorema 1.5(ii), |B| existe um homomorfismo Φ : FA /Ker(πA ) → C2 tal que o diagrama FA ϕ / FB πB FA /Ker(πA ) Φ 22 / C |B| 2 |A| comuta. Note-se que Φ é sobrejetivo porque ϕπB é sobrejetivo. Como FA /Ker(πA ) ∼ = C2 pelo |A| |B| |A| Teorema 1.5(iii), resulta a existência de um homomorfismo sobrejetivo C2 → C2 . Como |C2 | = |B| 2|A| e |C2 | = 2|B| , segue que |A| ≥ |B|. Aplicando o mesmo argumento ao isomorfismo ϕ−1 : FB → FA , concluimos qu |A| = |B|. (ii) ⇒ (i). É imediato que qualquer bijeção A → B induz um isomorfismo FA → FB . Um subconjunto B de um grupo G dix-se uma base de G se B gera G e não existe nenhuma palavra reduzida não vazia bε11 . . . bεnn no alfabeto B que seja igual a 1 em G. Isto equivale a dizer que a inclusão B ,→ G induz um isomorfismo FB → G. Em particular, G tem que ser um grupo livre. É claro que A é uma base de FA , mas existem muitas mais (como veremos na Secção 4), ao contrário do caso dos monóides livres. Podemos então concluir do Teorema 3.5 que todas as bases de um mesmo grupo livre possuem o mesmo número de elementos. Este número diz-se a dimensão do grupo livre (logo dim(FA ) = |A|). É comum designar por Fn o grupo livre de dimensão n (que é único a menos de isomorfismo). O grupo livre F2 estará presente em muitos exemplos e exercı́cios. Assumiremos genericamente A = {a, b} como base para F2 . e∗ /ρA ), é imporQuando um grupo é definido como quociente (é o caso do grupo livre FA = A tante saber resolver o problema da palavra, isto é, saber em que condições (algoritmicamente, isto é, queremos ser capazes de dizer SIM ou NÃO!) duas palavras representam o mesmo elemento. Dizemos então que o problema da palavra é decidı́vel. No caso dos grupos livres, é muito fácil: e∗ representam o mesmo elemento se e só se u = v. u, v ∈ A O problema da conjugação constitui um desafio menos óbvio. Aqui o objetivo é determinar algoritmicamente se dois elementos g, h ∈ G são ou não conjugados, isto é, se existe algum x ∈ G tal que g = xhx−1 . É fácil ver que a relação de conjugação é uma relação de equivalência. Uma palavra reduzida u ∈ RA diz-se ciclicamente reduzida se não for da forma u = ava−1 com e a ∈ A. Lema 3.6 Seja u ∈ RA . Então existem x, v ∈ RA tais que u = xvx−1 e v é ciclicamente reduzida. Além disso, x e v são únicas. Prova. A existência é fácil. Suponhamos agora que u = xvx−1 = ywy −1 com v, w ciclicamente reduzidas. Se |x| < |y|, então y = xz para alguma z ∈ RA não vazia, logo v = zwz −1 , contradizendo v ciclicamente reduzida. Por simetria, |x| > |y| também está excluı́da, logo |x| = |y| e obtemos sucessivamente x = y e v = w. Dizemos que a palavra v no enunciado anterior é o núcleo cı́clico de u. Um grupo diz-se: • de torsão se todos seus elementos tiverem ordem finita; • livre de torsão se o elemento neutro for o único elemento de ordem finita. Corolário 3.7 FA é livre de torsão. Prova. Seja g ∈ FA \{1}. Pelo Lema 3.6, podemos escrever g = xvx−1 com x ∈ RA e v ciclicamente reduzida. Dado n ≥ 1, temos g n = (xvx−1 )n ρA = (xv n x−1 )ρA . Como g 6= 1, também v 6= 1 e logo xv n x−1 é reduzida. Logo g n = xv n x−1 6= 1 e portanto g n tem ordem infinita. 23 Se u = vw for uma palavra ciclicamente reduzida, então a palavra wv é também ciclicamente reduzida. Diz-se um conjugado cı́clico de u. Note-se que u = w−1 (wv)w, logo os conjugados cı́clicos são de fato conjugados no grupo livre. É claro que só existe um número finito de conjugados cı́clicos para uma dada palavra. É fácil ver que a relação “ser conjugado cı́clico de” é uma relação de equivalência. Teorema 3.8 Seja A um alfabeto e g, h ∈ FA . Então as condições seguintes são equivalentes: (i) g e h são conjugados em FA ; (ii) os núcleos cı́clicos de g e h são conjugados cı́clicos. Prova. (i) ⇒ (ii). Como o único conjugado de 1 é ele próprio, podemos assumir que g 6= 1. Seja e Como ser conjugado cı́clico é uma relação de g = xux−1 com u ciclicamente reduzido. Seja a ∈ A. equivalência, basta mostrar que o núcleo cı́clico v de aga−1 é um conjugado cı́clico de u. Se x 6= 1, então v = u, logo podemos assumir que x = 1. Se aua−1 for reduzida, então mais uma vez u = v. Como u 6= 1 (pois g 6= 1), podemos assumir que au não é reduzida (o outro caso é análogo). Então podemos escrever u = a−1 w, logo aga−1 = aua−1 = aa−1 wa−1 = wa−1 . Como u é ciclicamente reduzida, não pode terminar em a. Logo wa−1 ∈ RA e aga−1 = wa−1 . Como w não começa por a (senão u = a−1 w não seria reduzida), resulta que wa−1 = v. Portanto v é um conjugado cı́clico de u. (ii) ⇒ (i). No grupo livre, toda a palavra é conjugada do seu núcleo cı́clico, e os conjugados cı́clicos são conjugados. Agora basta recordar que a relação de conjugação é uma relação de equivalência. Daqui resulta a solução do problema da conjugação de FA , pois os núcleos cı́clicos são efetivamente computáveis, assim como os seus conjugados cı́clicos. Exemplo 3.9 a−1 (ba)2 é conjugado de b−1 ab3 em F2 , mas não de ba3 b−1 a−1 b−1 . Com efeito, os núcleos cı́clicos destas três palavras são respetivamente bab, ab2 e a2 b−1 , donde resulta a afirmação. 3.3 Autômatos e subconjuntos racionais Veremos em seguida alguns resultados clássicos dos anos 60 e 70 que estabeleceram as primeiras relações entre a teoria de grupos e a teoria de autômatos. Lema 3.10 RA é uma linguagem racional. 24 e ∪ {1} e Prova. Seja Q = A e p ∈ Q \ {a−1 }}. E = {(p, a, a) | a ∈ A, e Definimos o A-autômato finito A = (Q, 1, Q, E). Os caminhos bem-sucedidos neste autômato são da forma a1 a2 a3 an 1−→a 1 −→a2 −→ . . . −→an e e ai 6= a−1 . Daqui resulta que L(A) = RA , pelo que RA é racional. com n ≥ 0, ai ∈ A i−1 Exemplo 3.11 Se A = {a, b}, o autômato construı́do na prova do Lema 3.10 é a b = bL b o aL m` a / b a 1o b−1 a / a−1 b a−1 b−1 o ~ b−1 N m a−1 b−1 b−1 ! - a−1 P / a−1 e∗ , escrevemos L = {u | u ∈ L}. O resultado seguinte (Teorema Dada uma linguagem L ⊆ A de Benois) foi pioneiro nas relações entre grupos livres e autômatos, e mostrou que a redução de palavras não constituı́a um problema: e e Teorema 3.12 (Benois 1969) Seja L uma A-linguagem racional. Então L é também uma Alinguagem racional que pode ser calculada algoritmicamente a partir de L. e Prova. Seja A = (Q, I, T, E) um A-autômato finito reconhecendo L. Definimos uma sucessão (An )n de autômatos finitos com transições-1 do seguinte modo. Seja A0 = A. Assumindo que An = (Q, I, T, En ) já está definido, consideramos todas as instâncias de pares ordenados (p, q) ∈ Q × Q tais que: −1 aa 1 e mas nenhum caminho p−→q. existe um caminho p−−→q em An para algum a ∈ A, (1) É claro que só existe um número finito de instâncias de (1) em An . Seja En+1 a união de En com novas arestas da forma (p, 1, q), onde (p, q) ∈ Q × Q é uma instância de (1) em An , e seja 25 An+1 = (Q, I, T, En+1 ). Note que An = An+k para todo k ≥ 1 caso não exista nenhuma instância de (1) em An . Como Q é finito, a sucessão (An )n tem que se tornar constante, digamos a partir de Am . Vamos mostrar que L = L(Am ) ∩ RA . (2) Seja u ∈ L. Então existe uma sucessão de reduções elementares u = u0 −→RA u1 −→RA . . . −→RA un = u. Uma indução simples mostra que ui ∈ L(Ai ) para i = 0, . . . , n. Logo u ∈ L(Ak )∩RA ⊆ L(Am )∩RA . Resulta que L ⊆ L(Am ) ∩ RA . u Para a inclusão oposta, começamos por notar que todo caminho p−→q em Ai+1 dá origem a v um caminho p−→q em Ai , tal que v pode ser obtido a partir de u inserindo um número finito de fatores da forma aa−1 . Logo L(Am ) = L(Am−1 ) = · · · = L(A0 ) = L (3) e portanto L(Am ) ∩ RA ⊆ L(Am ) = L. Isto completa a prova de (2). Pelos Lema 3.10 e Proposição 2.5, a linguagem L é racional. A natureza construtiva destes dois resultados permite a construção efetiva de um autômato reconhecendo L a partir do autômato A. A noção de linguagem racional pode ser estendida a subconjuntos de outros monóides/grupos. Seja M um monóide. Podemos definir um M -autômato ou autômato sobre M como sendo um autômato em que os rótulos das arestas são elementos de M . Então L(A), o conjunto dos rótulos dos caminhos bem-sucedidos, é naturalmente um subconjunto de M . Um subconjunto X ⊆ M dis-se racional se X = L(A) para algum M -autômato finito A. O resultado seguinte generaliza a Proposição 2.9(i): Proposição 3.13 Seja ϕ : M → N um homomorfismo de monóides e seja X ⊆ M racional. Então Xϕ é um subconjunto racional de N . Prova. Seja A um M -autômato tal que L(A) = X. Se substituirmos cada rótulo m ∈ M de uma aresta de A por mϕ, obtemos um N -autômato A0 tal que L(A0 ) = Xϕ. Logo Xϕ é racional. No contexto dos grupos, a noção de subconjunto racional é uma útil generalização do conceito de subgrupo finitamente gerado. O resultado seguinte comprova a legitimidade deste perspetiva, mesmo para grupos arbitrários: Teorema 3.14 (Anisimov e Seifert 1975) Seja H um subgrupo de um grupo G. Então as condições seguintes são equivalentes: (i) H é um subconjunto racional de G; (ii) H é finitamente gerado. 26 Prova. (i) ⇒ (ii). Seja A = (Q, I, T, E) um G-autômato tal que H = L(A). Podemos assumir que A é aparado (caso contrário suprimimos os vértices supérfluos). Seja A ⊆ G o conjunto (finito) dos rótulos das arestas de A. Escrevendo m = |Q|, definimos −1 k X = H ∩ (∪2m−1 k=0 (A ∪ A ) ). Como A é finito, X é um subconjunto finito de H. Vamos provar que H = hXi. Dado h ∈ H, podemos escrever h = a1 a2 . . . an para algum caminho a a a 1 2 n I 3 q0 −→q 1 −→ . . . −→qn ∈ T em A (logo a1 , . . . , an ∈ A). Vamos mostrar que h ∈ hXi por indução sobre n. Se n < 2m, então h ∈ X por definição de X. Logo podemos assumir que n ≥ 2m e que a hipótese é válida para menos que n fatores. Seja u = a1 . . . an−m e v = an−m+1 . . . an . Eliminando w ciclos desnecessários, podemos tomar um caminho qn−m −→qn de comprimento < m (isto é, com menos de m arestas). Logo uw ∈ L(A) = H e pela hipótese de indução uw ∈ hXi. Por outro lado, −1 k w−1 v ∈ ∪2m−1 k=0 (A ∪ A ) e w−1 v = (w−1 u−1 )(uv) ∈ H, logo w−1 v ∈ X. Daqui resulta que h = (uw)(w−1 v) ∈ hXi, logo H = hXi é finitamente gerado. (ii) ⇒ (i). Seja H = hh1 , . . . , hm i. Definimos um G-autômato com um só vértice A = ({q}, q, q, E), onde −1 E = {q} × {h1 , . . . , hm , h−1 1 , . . . , hm } × {q}. É imediato que H = L(A), logo H é racional. 3.4 Grafos de Cayley A existência de inversos nos grupos conduz naturalmente ao conceito de autômato inverso. Dado e um A-autômato A = (Q, I, T, E), dizemos que A é: • involutivo se satisfaz (p, a, q) ∈ E ⇔ (q, a−1 , p) ∈ E para todo a ∈ A; • inverso se é determinı́stico, aparado e involutivo. Uma boa ilustração destes conceitos é dada pelos grafos de Cayley de grupos. Seja G um grupo e gerado por A. O grafo de Cayley ΓA (G) é um A-grafo que tem os elementos de G como vértices e arestas da forma a e g −→ga (g ∈ G, a ∈ A). Fixando a identidade 1 como o único vértice inicial e terminal (num autômato, chamamos um tal vértice de ponto base), obtemos um autômato inverso. Qual é a sua linguagem? Precisamente o 27 e∗ tais que u = 1 em G. Isto é, se π : A e∗ → G designar o homomorfismo conjunto das palavras u ∈ A involutivo que estende a inclusão A ,→ G (e que é sobrejetivo porque G = hAi), então a linguagem reconhecida pelo autômato é 1π −1 , linguagem de suma importância para a compreensão da estrutura de G! Esta linguagem está intimamente ligada ao problema da palavra de G, discutido na Subsecção 7.3. Na representação de autômatos inversos (e grafos de Cayley) é habitual omitir a representação das arestas com rótulo em A−1 . Exemplo 3.15 O grupo simétrico S3 (permutações do conjunto {1, 2, 3} é gerado pelas permutações a = (123) e b = (12). O respetivo grafo de Cayley é a •V k b +•o b >• b a F• a ~ b a a a •T b b • Note-se que podemos omitir a designação dos vértices devido à natureza simétrica dos grafos de Cayley. Como G actua à esquerda no grafo por translações (isto é, cada elemento x ∈ G transforma a a o vértice g ∈ G em xg e a aresta g −→ga em xg −→xga), sempre tem um automorfismo deste grafo levando qualquer vértice p em qualquer vértice q. Dizemos que um tal grafo é transitivo nos vértices. O grafo de Cayley de FA (relativamente à base canónica A) é fácil de descrever. Como 1θ−1 = e∗ → FA , ΓA (FA ) não pode conter ciclos cujo rótulo seja RA para o homomorfismo canónico θ : A uma palavra reduzida. Sendo assim, se omitirmos a representação das arestas com rótulo em A−1 , obtemos uma árvore infinita. 28 Exemplo 3.16 Se A = {a, b}, podemos descrever uma porção de ΓA (FA ) por · ·O · b ··· /• O a · ·O · a / ··· · ·O · b b ··· a /• O b /• O a /• O a b a / ··· b ··· ··· b /• O a ··· a / ··· b ··· 3.5 Exercı́cios (3.1) Seja A um alfabeto finito. Mostre que o produto direto Z|A| é o grupo abeliano livre sobre A. (3.2) Mostre que {abn , b} é uma base de F2 para todo n ∈ Z. (3.3) Seja H = han ba−n | n ∈ Ni ≤ F2 . Mostre que H não é finitamente gerado. (3.4) Determine se os seguintes pares de palavras representam elementos conjugados de F2 : (a) b−1 abb−1 ab−1 a−1 ba−1 baa−1 e bab−1 aa−1 aba−2 bb−2 ; (b) bababb−2 a−1 baa−2 b−1 e b−3 a−1 a3 b−1 a−2 ab2 a−2 b3 . e∗ (3.5) Seja A um alfabeto finito. Mostre que a linguagem das palavras ciclicamente reduzidas de A é racional. (3.6) Seja A o autômato descrito por b /• _ /•p a b−1 • b a−1 / Construa a sucessão de autômatos com transições-1 definida na prova do Teorema 3.12. 29 (3.7) Seja A um alfabeto finito. Mostre que: e (a) para todo X ⊆ FA , X é um subconjunto racional de FA se e só se X é uma A-linguagem racional; (b) o conjunto dos subconjuntos racionais de FA é fechado para os operadores booleanos. (3.8) Construa ΓA (G) para: (a) G = C2 × C4 e A = {(1, 0), (0, 1)}. (b) G = Z × Z e A = {(1, 0), (0, 1), (1, 1)}. 30 4 Representação de subgrupos Os autômatos finitos constituem hoje a forma mais eficiente de representar um subgrupo finitamente gerado H de um grupo livre FA . O algoritmo conhecido como construção de Stallings constrói um autômato inverso S(H) que tem imensas aplicações (embora no artigo original de Stallings ele usasse imersões de grafos, o que é mais complicado). Várias das ideias presentes eram já conhecidas de matemáticos como Reidemeister, Schreier, e sobretudo Serre. 4.1 Construção de Stallings Uma das maiores contribuições de Stallings é mesmo o algoritmo para construir S(H): (1) Tomando um conjunto finito de geradores h1 , . . . , hm de H em forma reduzida, começamos por construir o chamado autômato flor F(H), em que pétalas rotuladas pelas palavras reduzidas hi (e as arestas inversas, para que seja um autômato involutivo) são coladas a um ponto base q0 : h2 0• P h1 hm a a (2) Numa segunda fase, identificamos successivamente pares de arestas da forma q ←−p−→r até obtermos um autômato determinı́stico (inverso, de fato!), designado por S(H). Note-se que, como o número de arestas diminui a cada dobragem, acabamos sempre por obter um autômato inverso, dito autômato de Stallings de H. Exemplo 4.1 Construção do autômato de Stallings de H = ha2 , ab−1 c, ci: F(H): •J a •O o b a ? qO0 d a c • 31 c 1a dobragem: •J a •o a,b a q o D 0 / 3 q0 o Q / c 2a dobragem e S(H): •t a,b a c Há duas questões naturais no que respeita a esta construção: • O resultado final depende da ordem em que as dobragens de arestas são feitas? • O resultado final depende do conjunto finito de geradores de H escolhido? Veremos que a resposta é NÃO a ambas as questões. Para mostrar isso, precisamos de introduzir e um novo conceito. Dizemos que um A-autômato finito A é SFG se: • A é inverso; • A tem um ponto base (o vértice inicial é também o único vértice terminal); • todo vértice ocorre nalgum caminho bem-sucedido de rótulo reduzido. Veremos mais adiante que estes autômatos são precisamente os autômatos de Stallings de subgrupos finitamente gerados de FA (o que explica a designação SFG). e Lema 4.2 Sejam A e A0 A-autômatos SFG. Então as condições seguintes são equivalentes: (i) A ∼ = A0 ; (ii) L(A) ∩ RA = L(A0 ) ∩ RA . Prova. (i) ⇒ (ii). Autômatos isomorfos têm a mesma linguagem. (ii) ⇒ (i). Sejam A = (Q, q0 , q0 , E) e A0 = (Q0 , q00 , q00 , E 0 ). Definimos uma função ϕ : Q → Q0 u v do seguinte modo. Seja q ∈ Q. Como A é SFG, possui um caminho q0 −→q −→q0 com uv ∈ RA . u v Logo uv ∈ L(A0 ) ∩ RA e A0 possui um caminho q00 −→q 0 −→q00 . Definimos qϕ = q 0 . w z Será que ϕ está bem definida? Suponhamos que q0 −→q −→q0 é um caminho alternativo com w z wz ∈ RA , e q00 −→p0 −→q00 é um caminho em A0 . Pelo menos uma das palavras uz, uw−1 é reduzida, logo uz ∈ L(A0 ) ou uw−1 ∈ L(A0 ). Como A0 é determinı́stico, resulta facilmente que ϕ está bem definida. Note-se que q0 ϕ = q00 (considerando u = v = 1). 32 u v w z Sejam p, q ∈ Q. Tomemos caminhos q0 −→q −→q0 e q0 −→p−→q0 em A com uv, wz ∈ RA . Se u v w z pϕ = qϕ = q 0 , então existem caminhos q00 −→q 0 −→q00 e q00 −→q 0 −→q00 em A0 . Usando um argumento análogo ao do parágrafo anterior, obtemos uw−1 ∈ L(A) ou uz ∈ L(A). Como A é determinı́stico, resulta que p = q, logo ϕ é injetiva. u v Suponhamos agora que (p0 , a, q 0 ) ∈ E 0 . Como A0 é SFG, possui caminhos q00 −→p0 −→q00 e w z q00 −→q 0 −→q00 com uv, wz ∈ RA . Logo uma das palavras uaw−1 , uaz, v −1 aw−1 , v −1 az −1 é reduzida, u a w −1 e pertencerá a L(A). Assumindo que é uaw , obtemos um caminho q0 −→p−→q −→q0 em A, donde resulta que pϕ = p0 e qϕ = q 0 . Em particular, ϕ é sobrejetiva! Além disso, mostrámos que (pϕ, a, qϕ) ∈ E 0 implica (p, a, q) ∈ E. A implicação recı́proca é análoga, logo ϕ é um isomorfismo de autômatos. Teorema 4.3 (Stallings 1983) Seja H ≤f.g. FA . Então: (i) S(H) é um autômato SFG; (ii) L(S(H)) ∩ RA = H. Prova. (i) É claro que S(H) é inverso e tem um ponto base. Por outro lado, já é verdade que todo o vértice de F(H) ocorre nalgum caminho bem-sucedido de rótulo reduzido. Esta propriedade se mantém ao longo do processo de dobragens, pois L(F(H)) ⊆ L(S(H)). (ii) É fácil ver que L(F(H)) ⊆ H. Por outro lado, se A0 resulta do autômato involutivo A por uma dobragem de arestas, o argumento usado para provar (3) implica que L(A0 ) = L(A). Daqui se conclui que L(S(H)) = L(F(H)) ⊆ H e logo L(S(H)) ∩ RA ⊆ L(S(H)) ⊆ H. Reciprocamente, seja u ∈ H. Suponhamos que h1 , . . . , hm foram os geradores de H usados na construção. Então u = hεi11 . . . hεinn para alguns n ≥ 0, i1 , . . . , in ∈ {1, . . . , m} e ε1 , . . . , εn ∈ {1, −1}. É claro que hεi11 . . . hεinn ∈ L(F(H)) ⊆ L(S(H)). Como uma palavra da forma aa−1 só pode ser rótulo de ciclos num autômato inverso, resulta que u = hεi11 . . . hεinn ∈ L(S(H)) e logo H ⊆ L(S(H)) ∩ RA . Podemos finalmente provar o seguinte: Corolário 4.4 (Stallings 1983) Dado H ≤f.g. FA , o autômato de Stallings S(H) não depende nem da ordem em que as dobragens de arestas são feitas, nem do conjunto finito de geradores de H escolhido. Prova. Pelo Teorema 4.3(ii), L(S(H)) ∩ RA é independente destes dois fatores. Como S(H) é SFG pelo Teorema 4.3(i), segue do Lema 4.2 que L(S(H))∩RA determina S(H) a menos de isomorfismo. Observação 4.5 Por vezes, a construção de Stallings aparece definida de forma um pouco mais geral, admitindo o uso de formas não reduzidas dos geradores na construção do autômato flor F(H). Nesse caso, haveria que acrescentar uma terceira etapa à etapa das dobragens, eliminando sucessivamente todos os vértices diferentes do ponto base que apresentem grau 1 (o grau de um vértice de um autômato é o número de arestas que nele têm origem). 33 Exemplo 4.6 Construção do auômato de Stallings de H = haa−1 b2 , bacaa−1 c−1 bi partindo de formas não reduzidas dos geradores: O autômato flor é /• a • >• ` a b • /• c /• b a / q0 o O b b a • c /• a /• Depois de proceder a todas as dobragens, obtemos •o a •O •O c a a b t <• 3 q0 o / b Eliminando sucessivamente todos os vértices diferentes de q0 que apresentem grau 1, obtemos finalmente o autômato de Stallings a 4.2 <• t b 3 q0 o / b Aplicações A primeira aplicação da construção de Stallings é a solução simples e elegante do chamado problema da palavra generalizado. Para um grupo G, este problema consiste em encontrar um algoritmo que decida, dados g ∈ G e H ≤f.g. G, se g ∈ H ou não. No caso particular H = {1}, permite decidir se g = 1 e logo se g = g 0 para g, g 0 ∈ G (equivalente a g −1 g 0 = 1). Isto explica a terminologia. Teorema 4.7 O problema da palavra generalizado é decidı́vel para FA . Prova. Sejam g ∈ FA e H ≤f.g. FA . Temos L(S(H)) ∩ RA = H pelo Teorema 4.3(ii). Logo, para determinar se g ∈ H, basta construir S(H) e testar se a palavra g é aceite pelo autômato. Exemplo 4.8 Podemos usar o autômato de Stallings construı́do no Exemplo 4.1 para verificar que ba ∈ H = ha2 , ab−1 c, ci mas ab ∈ / H. Os autômatos de Stallings também permitem a construção de bases para subgrupos finitamente gerados, como veremos em seguida. Seja H ≤f.g. FA , e seja m o número de vértices de S(H). Uma árvore geradora T de S(H) consiste em m−1 arestas e suas inversas que, juntas, conectam todos os vértices de S(H). Dado um 34 wp vértice p de S(H), designamos por wp a T -geodésica conectando o ponto base q0 a p, isto é, q0 −→p é o caminho mais curto contido em T ligando q0 a p. Note-se que esta T -geodésica é única, pois caso contrário poderı́amos dispensar uma das m − 1 arestas e continuar ligando todos os vértices, o que é manifestamente impossı́vel com m−2 arestas: se formos colocando as arestas sucessivamente, cada uma ligando a alguma das anteriores, estamos introduzindo dois novos vértices da primeira vez e depois um novo vértice de cada vez! Teorema 4.9 Seja H ≤f.g. FA e seja T uma árvore geradora de S(H) = (Q, q0 , q0 , E). Seja E+ = E ∩ (Q × A × Q). Então Y = {wp awq−1 | (p, a, q) ∈ E+ \ T } é uma base de H. Prova. Note-se que como (p, a, q) ∈ / T , temos Y ⊆ RA . Como Y ⊆ L(S(H)), resulta do Teorema 4.3(ii) que Y ⊆ H. Logo Y ⊆ H no grupo livre. e Pelo Teorema 4.3(ii), existe um Seja agora h = a1 · · · ak ∈ H em forma reduzida (ai ∈ A). caminho bem-sucedido ak a1 a2 q0 −→q 1 −→ · · · −→qk = q0 em S(H). Para cada i = 1, . . . , k, ou wqi−1 ai wq−1 ∈ Y ∪ Y −1 ou wqi−1 ai wq−1 = 1, esta última i i possibilidade ocorrendo se (qi−1 , ai , qi ) ∈ T . Em qualquer caso, obtemos −1 −1 h = a1 · · · ak = (wq0 a1 wq−1 1 )(wq1 a2 wq2 ) · · · (wqk−1 ak wq0 ) ∈ hY i e logo H = hY i. −1 Para mostrar que Y é uma base, sejam y1 , . . . , yk ∈ Y ∪ Y −1 com yi = 6 yi−1 para i = 2, . . . , k. −1 e Seja yi = wpi ai wri , onde ai ∈ A é o rótulo da aresta que não pertence a T . Resulta facilmente de −1 yi 6= yi−1 e da definição de árvore geradora que −1 y1 · · · yk = wp1 a1 wr−1 1 wp2 a2 · · · ak−1 wrk−1 wpk ak wrk , uma palavra reduzida não vazia se k ≥ 1. Logo Y é uma base de H. Como consequência imediata, obtemos: Corolário 4.10 (Nielsen 1921) Todo subgrupo finitamente gerado de FA é livre. Na realidade, todo subgrupo de um grupo livre é livre (Schreier 1926). A versão geral é conhecida como o Teorema de Nielsen-Schreier. Note-se que o Teorema 4.9 mostra também que todo autômato SFG é autômato de Stallings de algum subgrupo finitamente gerado, pois a construção da base Y é válida para todo autômato SFG. Observamos também que diferentes árvores geradoras produzem em geral bases distintas. Exemplo 4.11 Usando o autômato de Stallings do Exemplo 4.1, podemos tomar como árvore geradora a aresta de rótulo b e sua inversa. Logo {ab−1 , ba, c} constitui uma base de H = ha2 , ab−1 c, ci. 35 Uma outra aplicação da construção de Stallings é a identificação de subgrupos de ı́ndice finito: Teorema 4.12 Seja H ≤f.g. FA . Então as condições seguintes ão equivalentes: (i) [FA : H] < ∞; (ii) S(H) é um autômato completo. Prova. (i) ⇒ (ii). Suponhamos que S(H) = (Q, q0 , q0 , E) não é completo. Então existem q ∈ Q e u e tais que (q, a, p) ∈ a∈A / E para todo p ∈ Q. Seja q0 −→q um caminho em S(H). Como S(H) é inverso, podemos assumir que u ∈ RA . Vamos mostrar que Huam 6= Huan se m − n > |u|. (4) De fato, Huam = Huan implica uam−n u−1 ∈ H e logo uam−n u−1 ∈ L(S(H)) pelo Teorema 4.3(ii). Ora como S(H) é inverso temos ua ∈ RA . Como m − n > |u|, resulta que uaam−n−1 u−1 = uam−n u−1 ∈ L(S(H)), pois u−1 não tem comprimento suficiente para apagar todos os a’s. Mas então, como S(H) é determinı́stico, tem que existir uma aresta (q, a, p), contradição. Logo (4) é válida e logo [FA : H] = ∞. wq (ii) ⇒ (i). Para cada q ∈ Q, fixamos uma geodésica q0 −→q (isto é, caminho de comprimento g mı́nimo). Seja g ∈ FA em forma reduzida. Como S(H) é completo, existe um caminho q0 −→q para algum q ∈ Q. Logo gwq−1 ∈ H e portanto g = gwq−1 wq ∈ Hwq . Logo FA = ∪q∈Q (Hwq ) e [FA : H] < ∞. Corolário 4.13 Seja H ≤f.g. FA com ı́ndice finito. Então [FA : H] é o número de vértices de S(H). Prova. Vimos na prova do Teorema 4.12 que FA = ∪q∈Q (Hwq ), logo basta mostrar que as classes Hwq são todas distintas. Suponhamos que Hwp = Hwq para p, q ∈ Q. Então wp wq−1 ∈ H e logo pelo Teorema 4.3(ii) existe um caminho wp wq−1 q0 −−−→q0 em S(H), e logo um caminho wp wq−1 wq q0 −−−−−→q. Como S(H) é inverso e wp wq−1 wq = wp (os rótulos das geodésicas são palavras reduzidas), obtemos wp um caminho q0 −→q. Logo p = q como pretendı́amos. Exemplo 4.14 Como o seu autômato de Stallings não é completo, o subgrupo H = ha−1 ba, ba2 i não tem ı́ndice finito em F2 . Corolário 4.15 Se H ≤f.g. FA tem ı́ndice n, então dim(H) = 1 + n(|A| − 1). Prova. Pelo Teorema 4.12, o autômato S(H) tem n vértices e n|A| arestas positivas. Uma árvore geradora tem n − 1 arestas positivas, logo dim(H) = n|A| − (n − 1) = 1 + n(|A| − 1) pelo Teorema 4.9. 36 Consideramos em seguida a relação de conjugação a nı́vel de subgrupos. Dois subgrupos H, K ≤ G dizem-se conjugados se H = gKg −1 para algum g ∈ G. Seja H ≤f.g. FA e S(H) = (Q, q0 , q0 , E). Como S(H) é um autômato SFG, o ponto base q0 é o único vértice que pode ter grau 1. Seja S0 (H) = (Q, E). Trata-se de um grafo orientado em que e Se q0 tiver grau 6= 1, seja S1 (H) = S0 (H). Se q0 tiver grau 1, S1 (H) as arestas têm rótulos em A. é obtido a partir de S0 (H) eliminando sucessivamente todos os vértices de grau 1. Teorema 4.16 Sejam H, K ≤f.g. FA . As condições seguintes são equivalentes: (i) H e K são conjugados; (ii) S1 (H) ∼ = S1 (K). Prova. Vamos esboçar apenas a prova, apelando à intuição. É fácil compreender que S(H) tem uma das duas formas seguintes: • é S1 (H) com um ponto base designado; u • é obtido a partir de S1 (H) “colando” uma cauda q0 −→q (sendo a colagem feita identificando q com um vértice de S1 (H)) e sendo q0 o ponto base. Esta segunda opção só é possı́vel se S1 (H) tiver mais que um vértice. Consideremos a igualdade K = g −1 Hg. Seja X um subconjunto gerador de H em forma reduzida. Usando a versão mais geral da construção de Stallings referida na Observação 4.5, poderı́amos construir S(K) usando o subconjunto gerador g −1 Xg. Aplicando as dobragens na ordem conveniente, o processo de dobragens seria equivalente a colar a cauda g −1 p0 −−→p em S(H) (sendo a colagem feita identificando p com o ponto-base de S(H)), passando p0 a ser o novo ponto base, e dobrando a cauda se for necessário. Haveria que aplicar em seguida a terceira fase do algoritmo referida na Observação 4.5, o que pode conduzir a várias possibilidades, que criam/alteram/suprimem a cauda e/ou alteram o ponto base (ilustradas no Exemplo 4.17), mas que mantêm S1 (H) inalterado (a menos de isomorfismo). Reciprocamente, S1 (H) ∼ = S1 (K) implica que S(H) e S(K) diferem apenas pela eventual “cauda” e/ou ponto base, e podemos conjugar por um elemento adequado (ver Exemplo 4.17). Exemplo 4.17 Seja H = hab2 ab−1 a−1 i ≤ F2 . Então: O O q0 a /• b /•h b ( • q0 a 37 b /•h b a ( • S(a−1 Ha) S(H) O q0 o O a •o •o a b a •h ( a S(a−3 b−1 a−1 Haba3 ) b b •h q0 a S(b a • a O ) −2 −1 ( S(b−1 a−1 Hab) O •h b q0 i • a ( • / q0 b S(b−3 a−1 Hab3 ) 2 Hab ) Podemos caraterizar facilmente os autômatos de Stallings dos subgrupos normais finitamente gerados: Corolário 4.18 Seja H ≤f.g. FA . Então H E FA se e só se verifica uma das condições seguintes: (i) H = {1}; (ii) [FA : H] < ∞ e S1 (H) é transitivo nos vértices. Prova. Podemos assumir que H 6= {1}. Ora H é normal se e só se S(gHg −1 ) ∼ = S(H) para todo g ∈ FA . Isto não pode acontecer se existir a possibilidade de S(gHg −1 ) ter uma cauda. Logo S(H) é completo e [FA : H] < ∞ pelo Teorema 4.12. Mas então, pelo Teorema 4.16, os autômatos S(gHg −1 ) correspondem a todas as versões de S(H) com o ponto base alterado. Como S(gHg −1 ) ∼ = S(H) se só se S1 (H) admite um automorfismo levando o ponto base q0 em q (onde g −1 q0 −−→q é um caminho em S(H)), isto é equivalente a dizer que S1 (H) é transitivo nos vértices. Vamos agora usar os autômatos de Stallings para dar uma prova simples do Teorema de Howson: Teorema 4.19 (Howson 1954) Sejam H, K ≤f.g. FA . Então H ∩ K ≤f.g. FA . Prova. O produto direto S(H)×S(K) reconhece L(S(H))∩L(S(H)) pela Proposição 2.6. Seja A a componente conexa de S(H)×S(K) contendo o novo ponto base (isto é, removemos todos os vértices e arestas que não estão ligados ao ponto base). Então temos também L(A) = L(S(H)) ∩ L(S(K)). Se removermos de A eventuais vértices de grau 1 que não sejam o ponto base (ver Observação 4.5), obtemos um autômato inverso SFG A0 . Vejamos que A0 ∼ = S(H ∩ K). Pelo Lema 4.2 e pelo Teorema 4.3, basta mostrar que L(A0 )∩RA = H ∩ K. Como L(A0 )∩RA = L(A) ∩ RA e H ∩ K = H ∩ K, isto equivale a mostrar que L(S(H)) ∩ L(S(K)) ∩ RA = H ∩ K, uma consequência imediata do Teorema 4.3(ii). Logo S(H ∩ K) ∼ = A0 , sendo em particular finito. Daqui resulta que H ∩ K é finitamente gerado. 38 O Teorema de Howson está estreitamente ligado ao que foi durante muitos anos um dos mais famosos problemas em aberto da teoria de grupos: a Conjetura de Hanna Neumann. Em 1957, Hanna Neumann provou que dim(H ∩ K) − 1 ≤ 2(dim(H) − 1)(dim(K) − 1) para todos H, K ≤f.g. FA e conjeturou que o fator 2 podia ser removido da desigualdade. A conjetura foi finalmente provada em 2011 por Friedman e Mineyev (de forma independente). 4.3 A métrica profinita Há várias métricas de grande interesse que podem ser definidas em FA . Apresentaremos em seguida a primeira delas, mas primeiro precisamos de provar que FA é residualmente finito. Um grupo G diz-se residualmente finito se ∩{H ≤ G | [G : H] < ∞} = {1}. Proposição 4.20 FA é residualmente finito. e Consideremos o autômato inverso Prova. Seja g ∈ FA \ {1}. Seja g = a1 . . . am com ai ∈ A. o / q0 a1 / q1 a2 / . . . am / qm É fácil verificar que podemos acrescentar arestas a este autômato para obter um autômato inverso completo (e SFG), que será o autômato de Stallings de algum H ≤f.g. FA . Pelo Teorema 4.12, H tem ı́ndice finito, e pelo Teorema 4.3(ii), g ∈ / H. Logo g ∈ / H e portanto FA é residualmente finito. Vamos necessitar também do seguinte lema: Lema 4.21 Sejam H, K ≤ G de ı́ndice finito. Então H ∩ K tem ı́ndice finito. Prova. Suponhamos que G = Ha1 ∩ . . . Ham = Kb1 . . . Kbn . Então G= m [ n [ (Hai ∩ Kbj ). i=1 j=1 Basta-nos mostrar que c ∈ Hai ∩ Kbj ⇒ Hai ∩ Kbj ⊆ (H ∩ K)c. (5) Com efeito, (Hai ∩ Kbj )c−1 ⊆ Hai c−1 ⊆ Hai a−1 i H = H, e analogamente (Hai ∩ Kbj )c−1 ⊆ K. Logo (Hai ∩ Kbj )c−1 ⊆ H ∩ K e (5) é válido como pretendı́amos. 39 Uma métrica (ou distância) num conjunto X é uma função d : X × X → R satisfazendo os axiomas seguintes para todos x, y, z ∈ X: (M1) d(x, y) ≥ 0; (M2) d(x, y) = 0 ⇔ x = y; (M3) d(x, y) = d(y, x); (M4) d(x, z) ≤ d(x, y) + d(x, z). A estrutura (X, d) diz-se então um espaço métrico. Se substituirmos o axioma (M4) pelo axioma mais forte (M4’) d(x, z) ≤ max {d(x, y), d(x, z)}, temos o que se chama de ultramétrica. Definimos uma função d : FA × FA → R do seguinte modo. Sejam g, h ∈ FA . Se g = h, seja d(g, h) = 0. Se g 6= h, seja d(g, h) = 2−k , onde k é o menor número de elementos de um grupo finito F tal que gϕ 6= hϕ para algum homomorfismo ϕ : FA → F . Lema 4.22 A função d é uma ultramétrica em FA . Prova. Primeiro há que mostrar que d está bem definida. Suponhamos que g 6= h. Então gh−1 6= 1 e pela Proposição 4.20 existe H ≤ FA de ı́ndice finito tal que gh−1 ∈ / H. Seja \ K= xHx−1 . x∈G Como xHx−1 = (xH)(Hx−1 ) = (Hx−1 )−1 (Hx−1 ) e [FA : H] < ∞, K é na realidade interseção de um número finito de subgrupos da forma xHx−1 . Cada um deles tem naturalmente ı́ndice finito, logo [FA : H] < ∞ pelo Lema 4.21. É fácil confirmar que K é um subgrupo normal, logo FA /K é um grupo finito. Como gh−1 ∈ /H −1 implica gh ∈ / K, a projeção canónica FA → FA /K envia g e h em elementos distintos de FA /K. Logo d está bem definida. Os axiomas (M1) – (M3) são obviamente satisfeitos. Falta verificar (M4’). Sejam x, y, z ∈ FA . Sem perda de generalidade, podemos assumir que os três elementos são distintos e que max {d(x, y), d(y, z)} = 2−m . Seja ϕ : FA → F um homomorfismo de grupos com |F | < m. Como |F | < d(x, y), temos xϕ = yϕ. Analogamente, yϕ = zϕ. Logo xϕ = zϕ e d(x, z) ≤ 2−m . Logo (M4’) é válido e d é uma ultramétrica. 40 A função d diz-se a métrica profinita. Podemos provar agora o famoso Teorema de Marshall Hall: Teorema 4.23 (Marshall Hall 1950) Seja H ≤f.g. FA . Então H é fechado para a métrica profinita. Prova. Seja g ∈ FA \ H. Pelo Teorema 4.3(ii), g ∈ / L(S(H)). Caso exista um caminho da forma g q0 −→ . . . em S(H), seja A = S(H). Caso contrário, A é o autômato inverso obtido acrescentando g vértices e arestas a S(H) de forma a que passe a existir um caminho q0 −→r (sendo r um novo vértice). Agora, tal como na prova da Proposição 4.20, acrescentamos arestas a A até obter um autômato inverso completo (e SFG), que será o autômato de Stallings de algum K ≤f.g. FA . Pelo Teorema 4.12, K tem ı́ndice finito, e pelo Teorema 4.3(ii), g ∈ / K. Logo g ∈ / K. Seja \ J= xKx−1 . x∈G Tal como na prova do Lema 4.22, temos J E FA e [FA : J] < ∞. Seja π : FA → FA /J a projeção canónica. Suponhamos que gπ = hπ para algum h ∈ H. Então gh−1 ∈ J ⊆ K. Como H ⊆ K, resulta que g ∈ Kh = K, contradição. Logo gπ 6= hπ e portanto d(g, h) ≥ 2−[FA :J] para todo h ∈ H. Designando por Bε (g) a bola aberta de centro g e raio ε no espaço métrico (FA , d), resulta que B2−[FA :J] (g) ⊆ FA \ H e portanto FA \ H é um subconjunto aberto, donde H é um subconjunto fechado de FA . Exemplo 4.24 Consideramos a construção da prova do Teorema 4.23 para H = ha2 i ≤ F2 e g = ab. Obtemos o S(H) : o ) q1 a a / q0 i A: S(K) : a / q0 i ) q1 b /r b ( a a ) / q0 i q1 i M a b o a rp b Logo K tem três conjugados, correspondendo a cada uma das três escolhas possı́veis para ponto base. Utilizando a construção descrita na prova do Teorema 4.19, baseada no produto direto (ver também a Proposição 2.6), acabamos obtendo S(J) : o / q0 o b O /•o a /• O a •o 41 b /•o /• a b 4.4 Exercı́cios (4.1) Para cada um dos seguintes subgrupos de F2 , H1 = ha2 b−1 a−2 , a2 b−2 a−2 i, H2 = ha2 , a−1 baba2 i, H3 = ha3 , ba2 , b−2 , babai, H4 = ha3 , b3 , aba−1 , a(ba)2 , bab−1 , b−1 abi: (a) Construa S(Hi ). (b) Determine quais das palavras a2 b−1 a, a7 bab, a2 b99 a−2 , (ab)100 representam elementos de Hi . (c) Determine uma base de Hi . (d) Calcule [FA : Hi ]. (4.2) Sejam H ≤f.g. FA e g ∈ FA . Mostre que é decidı́vel se xgx−1 ∈ H para algum x ∈ G. (4.3) Sejam H = ha2 , aba, b2 , babi e K = ha2 , b, abai subgrupos de F2 . (a) Construa os autômatos de Stallings de todos os subgrupos conjugados de H e K. (b) Determine se H ou K é subgrupo normal de F2 . (c) Construa S(H ∩ K). (4.4) Seja H um subgrupo de ı́ndice finito de FA . Mostre que existe apenas um número finito de K ≤ FA contendo H. (4.5) Mostre que F2 possui apenas 3 subgrupos de ı́ndice 2. (4.6) Mostre que o produto direto Zn = Z × . . . Z é residualmente finito. (4.7) Seja H = haba−1 i ≤ F2 . Seguindo o algoritmo da prova do Teorema 4.24, construa J E F2 de ı́ndice finito tal que H ≤ J e a2 ∈ / J. (4.8) Sejam g, g 0 , x ∈ FA e H ≤f.g. FA . Mostre que: (a) d(xg, xg 0 ) = d(gx, g 0 x) = d(g, g 0 ); (b) Hg e gH são fechados em (FA , d). 42 5 Bordo de um grupo livre Nesta seção estudamos uma segunda métrica do grupo livre que nos conduz a uma compactificação famosa: o bordo, que pode ser descrito usando palavras infinitas. 5.1 Palavras infinitas Uma palavra infinita no alfabeto A é uma sequência infinita de letras de A do tipo a1 a2 a3 . . .. Designamos por Aω o conjunto de todas as palavras infinitas no alfabeto A e usamos também a notação A∞ = A∗ ∪ Aω . Podemos associar também palavras infinitas a um A-autômato A = (Q, I, T, E). Se (pi−1 , ai , pi ) ∈ E para todo i ≥ 1, temos definido um caminho infinito a a a 1 2 3 p0 −→p 1 −→p2 −→ . . . O seu rótulo é a palavra infinita a1 a2 a3 . . . ∈ Aω . Designamos por Lω (A) o conjunto dos rótulos α de todos os caminhos infinitos da forma I 3 q0 −→ . . . em A. Note-se que os estados terminais não desempenham qualquer papel no cálculo de Lω (A)! Há outras formas de associar uma linguagem de palavras infinitas a A (por exemplo, exigindo uma infinidade de passagens por um estado terminal (Büchi)), mas não nos interessam no presente contexto. Dada L ⊆ A+ , designamos por Lω o conjunto de todas as palavras infinitas da forma u1 u2 u3 . . . (ui ∈ L). Em particular, se a ∈ A, aω designa a palavra infinita aaa . . . Exemplo 5.1 Seja A o autômato a o Então L(A) = a∗ e Lω (A) = aω ∪ c /• b /• a∗ bcω . Não podemos concatenar duas palavras infinitas, mas podemos concatenar u = a1 . . . an e α = b1 b2 b3 . . . (ai , bj ∈ A) por uα = a1 . . . an b1 b2 b3 . . . Dadas u ∈ A∗ e α ∈ Aω , dizemos que: • u é um prefixo de α se α = uβ para alguma β ∈ Aω ; • u é um fator de α se α = vuβ para algumas v ∈ A∗ e β ∈ Aω . Se α = uβ, dizemos também que β é um sufixo de α. Escreveremos u ≤ x para exprimir que u é prefixo de x ∈ A∞ . Designamos por x[n] o prefixo de comprimento n de x (ou a própria x caso |x| < n). 43 5.2 A métrica dos prefixos e o espaço de Cantor A métrica dos prefixos é definida em A∗ do seguinte modo. Dadas u, v ∈ A∗ , seja u ∧ v o mais longo prefixo comum de u e v. Definimos −|u∧v| 2 se u 6= v 0 d (u, v) = 0 se u = v Exemplo 5.2 Sejam u = a3 b, v = a3 b3 e v = b2 . Então d0 (u, v) = 2−4 e d0 (u, w) = d0 (v, w) = 1. Lema 5.3 A função d0 é uma ultramétrica em A∗ . Prova. Os axiomas (M1) – (M3) são obviamente satisfeitos. Falta verificar (M4’) para u, v, w ∈ A∗ . Sem perda de generalidade, podemos assumir que as três palavras são distintas, pelo que nos basta mostrar que |u ∧ w| ≥ min {|u ∧ v|, |v ∧ w|}. Esta desigualdade é válida por transitividade, pois se u e v têm um prefixo comum de comprimento m, e o mesmo se passa com v e w, então u e w vão ter também um prefixo comum de comprimento m. É fácil ver que o espaço métrico (A∗ , d0 ) é discreto, isto é, todo ponto é aberto. Com efeito, dada u ∈ A∗ , temos B2−|u| (u) = {u} : se v ∈ B2−|u| (u) \ {u}, então |u ∧ v| > |u|, absurdo. Isto quer dizer que (A∗ , d0 ) não é muito interessante enquanto espaço métrico. Mas o seu completado vai ser! Uma sucessão (xn )n num espaço métrico (X, d) dix-se de Cauchy se ∀ε > 0 ∃p ∈ N ∀m, n ≥ p d(xm , xn ) < ε. A sucessão diz-se convergente para x ∈ X se ∀ε > 0 ∃p ∈ N ∀n ≥ p d(xn , x) < ε. Dizemos então que x é o limite da sucessão (xn )n . Resultados bem conhecidos da topologia afirmam que o limite de uma sucessão convergente é único e que toda sucessão convergente é de Cauchy. No entanto, o recı́proco não é necessáriamente verdade: por exemplo, a sucessão ( n1 )n é de Cauchy em ]0, +∞[ (para a métrica usual) mas não é convergente. Um espaço métrico em que toda a sucessão de Cauchy é convergente diz-se completo. Suponhamos agora que (X, d) é um espaço métrico mas não é completo. Um outro resultado de topologia afirma que podemos mergulhar (X, d) num espaço métrico completo (Y, d0 ) (com d0 |X×X = d). Se escolhermos Y menor possı́vel (isto é, se todo elemento de Y for limite de alguma sucessão em (X, d)), dizemos que (Y, d0 ) é o completado de (X, d). E um outro resultado de topologia b afirma que o completado é único a menos de homeomorfismo. É designado por X. Por exemplo, para a métrica usual, R é o completado de Q. A construção do completado é em geral técnicamente complicada, mas isso não acontece com o completado de (A∗ , d0 ). Começamos por estender d0 a A∞ com a mesma definição (e a mesma designação d0 !). É fácil ver que d0 é uma ultramétrica em A∞ . Mas há mais: 44 Teorema 5.4 (A∞ , d0 ) é o completado de (A∗ , d0 ). Prova. Seja (αn )n uma sucessão de Cauchy em (A∞ , d0 ). Então ∀k ∈ N ∃pk ∈ N ∀m, n ≥ pk d0 (αm , αn ) < 2−k . Logo [k] ∀k ∈ N ∃pk ∈ N ∀m, n ≥ pk αm = αn[k] . (6) Podemos assumir que a sucessão (pk )k é não decrescente. Daqui resulta facilmente que αp[1]1 ≤ αp[2]2 ≤ αp[3]3 ≤ . . . [k] É claro que existe uma única palavra α ∈ A∞ tal que α[k] = αpk para todo k ∈ N: é finita se a [k] sucessão (αpk )k for estacionária e infinita caso contrário. Vejamos que α = limn→+∞ αn : [k] [k] Seja ε > 0 e seja k ∈ N tal que 2−k < ε. Tomemos n ≥ pk . Por (6), temos αn = αpk . Por [k] [k] outro lado, α[k] = αpk , logo αn = α[k] e portanto d0 (αn , α) ≤ 2−k < ε. Logo α = limn→+∞ αn e portanto (A∞ , d0 ) é completo. Como α = limn→+∞ α[n] para toda α ∈ Aω , (A∞ , d0 ) é o completado de (A∗ , d0 ). Um espaço métrico (X, d) é compacto se toda a sucessão em X admite uma subsucessão convergente. Há muitas outras definições equivalentes. Argumentos ditos de compacidade são usados com grande eficácia em topologia e lógica, e por virtude destas duas disciplinas, na álgebra. Teorema 5.5 (A∞ , d0 ) é compacto. Prova. Seja (αn )n uma sucessão em (A∞ , d0 ). Se existir algum p ∈ N tal que {αn : |αn | ≤ p} seja infinito, então há alguma palavra de comprimento ≤ p a repetir-se infinitamente na sucessão, o que resolve imediatamente a questão. Por isso podemos assumir que {αn : |αn | ≤ p} é finito para todo p ∈ N. [1] Como A é finito, existe algum a1 ∈ A tal que αn = a1 para uma infinidade de n. Mas então [2] existe algum a2 ∈ A tal que αn = a1 a2 para uma infinidade de n, existe algum a3 ∈ A tal que [2] αn = a1 a2 a3 para uma infinidade de n, e assim sucessivamente. Construimos assim uma palavra infinita a1 a2 a3 . . . Consideremos agora a subsucessão (αin )n definida do seguinte modo: seja i1 o [1] [2] primeiro ı́ndice n tal que αn = a1 , seja i2 o primeiro ı́ndice n > i1 tal que αn = a1 a2 , seja i3 [3] o primeiro ı́ndice n > i3 tal que αn = a1 a2 a3 , e assim sucessivamente. É fácil verificar que a subsucessão está bem definida e converge para a1 a2 a3 . . . ∈ Aω . Os espaços métricos (A∞ , d0 ) dizem-se espaços de Cantor. Quem já ouviu falar de conjunto de Cantor pode ficar algo confuso... então o conjunto de Cantor C não é esse conjunto estranho que se obtém removendo o terço interior ] 13 , 23 [ do intervalo [0, 1] e seguindo removendo o terço interior de cada um dos pequenos intervalos que vão aparecendo, até ao infinito? Qual é a relação com (A∞ , d0 )? 45 Há de fato uma relação, pois o conjunto de Cantor descrito acima, com a métrica usual herdada de R, é homeomorfo a (A∞ , d0 ) se |A| = 2. Consideremos os números reais de [0, 1] escritos na base 3. Cada número é uma dı́zima, finita ou infinita, composta pelos algarismos 0, 1, 2. Tal como na base 10, há um pequeno problema de dupla representação. Por exemplo, as dı́zimas 0, 1 e 0, 0222 . . . representam o mesmo número real. Se for possı́vel, optaremos pela dı́zima que não contenha 1. Se não for possı́vel, tanto faz... Tudo isto porque o conjunto de Cantor corresponde precisamente a todas as dı́zimas que não contêm o algarismo 1: eliminar o terço interior de cada intervalo corresponde sempre a eliminar as dı́zimas contendo 1! Logo existe uma bijeção entre C e {0, 2}∞ . E pode verificar-se que é um homeomorfismo (ver o Exercı́cio 5.2). 5.3 Construção do bordo Introduzimos agora uma segunda ultramétrica em FA : a métrica dos prefixos de FA é definida a e∗ por partir da métrica dos prefixos de A d0 (g, h) = d0 (g, h) (g, h ∈ FA ). Resulta imediatamente do Lema 5.3 que Lema 5.6 A função d0 é uma ultramétrica em FA . Analogamente, o espaço métrico (FA , d0 ) é discreto, ao contrário do que acontece com a métrica profinita d. Efetivamente, é fácil confirmar que d(an! , 1) < 2−n para todo n ∈ N: se ϕ : FA → F é um homomorfismo de grupos e |F | ≤ n, então (aϕ)|F | = 1 implica an! ϕ = (aϕ)n! = 1, logo precisamos no mı́nimo de |F | = n + 1 para separar 1 de an! . Logo {1} não é aberto e (FA , d) não é discreto. Qual é o completado de (FA , d0 )? eω sem fatores do tipo aa−1 (a ∈ A) e diz-se uma palavra infinita reduzida. Uma palavra α ∈ A Designamos por ∂FA o conjunto de todas as palavras infinitas reduzidas. Estendemos a ultramétrica cA = FA ∪ ∂FA da forma óbvia, adaptando o que fizemos para A∞ . Os mesmos d0 : FA × FA → R a F argumentos permitem mostrar que: cA , d0 ) é o completado de (FA , d0 ). Teorema 5.7 (F cA , d0 ) é compacto. Teorema 5.8 (F O espaço ∂FA diz-se o bordo de FA . Muitas vezes, o bordo é pensado geometricamente como o conjunto dos raios do grafo de Cayley ΓA (FA ) com origem num determinado vértice. Um raio é uma geodésica infinita, isto é, um caminho infinito em que cada secção finita é uma geodésica. Dado um subconjunto Y de um espaço métrico X, designamos por Fec(Y ) o fecho de Y , que pode ser definido como o menor fechado contendo Y , ou o conjunto dos pontos de X que são limite de sucessões em Y . O resultado seguinte mostra que os autômatos de Stallings podem desempenhar também um papel em relação ao bordo. 46 cA . Então Proposição 5.9 Seja H ≤f.g. FA e seja Fec(H) o fecho de H em F Fec(H) = H ∪ (Lω (S(H)) ∩ ∂FA ). Prova. Como (FA , d0 ) é discreto, temos Fec(H) ∩ FA = H. Seja α ∈ ∂FA . Temos que provar que α ∈ Fec(H) ⇔ α ∈ Lω (S(H)). (7) Suponhamos que α ∈ Fec(H). Então α = limn→+∞ hn para alguma sucessão (hn )n em H. e tais Suponhamos que α ∈ / Lω (S(H)). Então podemos fatorizar α = uaβ com u ∈ A∗ e a ∈ A u a que q0 −→q é um caminho em S(H) mas não existe nenhuma aresta da forma q −→ . . .. Como α = limn→+∞ hn , existe p ∈ N tal que d0 (hn , α) < 2−|u| para todo n ≥ p. Mas então |α ∧ hp | > |u|, a logo ua ≤ hp . Pelo Teorema 4.3(ii), isto implica a existência de uma aresta q −→ . . . em S(H), contradição. Logo α ∈ Lω (S(H)). e Seja m o número de vértices de Reciprocamente, seja α = a1 a2 a3 · · · ∈ Lω (S(H)), com ai ∈ A. S(H). Para cada n ≥ 1, existe alguma palavra wn ∈ RA de comprimento < m tal que a1 · · · an wn ∈ L(S(H)). Logo a1 · · · an wn ∈ L(S(H)) ∩ RA = H pelo Teorema 4.3(ii), e portanto a1 · · · an wn ∈ H. Como |wn | < m, temos |a1 · · · an wn ∧ α| ≥ n − m para todo n ∈ N, logo resulta facilmente que α = limn→+∞ a1 · · · an wn e α ∈ Fec(H). Logo (7) é válido como pretendı́amos. 5.4 Exercı́cios (5.1) Seja A o autômato descrito por b a /•j * • / c Calcule L(A) e Lω (A). (5.2) Seja A = {0, 2} e seja ϕ : A∞ → C a bijeção definida no final da Subsecção 5.2. Mostre que: (a) 3−|α∧β|−1 ≤ |αϕ − βϕ| ≤ 3−|α∧β| para todas α, β ∈ A∞ distintas; (b) ϕ é um homeomeorfismo (para a métrica d0 em A∞ e a métrica usual em C). cA , d0 ), (5.3) No espaço métrico (F (a) calcule d0 (abaω , aba−1 b−1 ); (b) determine B 1 (abaω ). 4 cA , d0 ): (5.4) Calcule os seguintes limites em (F (a) limn→+∞ an b2n ; (b) limn→+∞ (ab2 a−1 )n . 47 (5.5) Calcule Fec(H) para cada um dos seguintes subgrupos de F2 : (a) H = ha, bab−1 i; (b) H = ha, b2 , bab−1 i. (5.6) Seja H ≤f.g. FA e g ∈ G. Mostre que, para a métrica d0 , Fec(Hg) = Hg ∪ (Lω (S(H)) ∩ ∂FA ). 48 6 Pontos fixos de endomorfismos Nesta secção usamos os autômatos para estudar os pontos fixos de um endomorfismo de FA . 6.1 O subgrupo dos pontos fixos Um endomorfismo de um grupo G é um homomorfismo ϕ : G → G. Dizemos que g ∈ G é um ponto fixo de ϕ se gϕ = g. É imediato que o conjunto dos pontos fixos de ϕ constitui um subgrupo de G, que designaremos por Fix(ϕ). Quando definimos um subgrupo através de uma propriedade, a primeira questão que se põe é saber se ele é finitamente gerado ou não, pois nesse caso podemos ambicionar a construção do respetivo autômato de Stallings, com todas as vantagens que lhe estão inerentes. Vamos ver que esse é o caso dos endomorfismos de um grupo livre: Teorema 6.1 (Goldstein e Turner 1986) Seja ϕ um endomorfismo de FA . Então Fix(ϕ) é finitamente gerado. Prova. Para todo g ∈ FA , seja pg = g −1 (gϕ) ∈ FA . Note-se que 1 = p1 e g ∈ Fix(ϕ) se e só se e pg = 1. Definimos um A-autômato A = (P, 1, 1, E) por P = {pg | g ∈ FA }; e E = {(pg , a, pga ) | g ∈ FA , a ∈ A}. Provamos em seguida uma série de lemas intermédios que nos ajudarão a demonstrar o teorema: Lema 6.2 A é um autômato inverso e L(A) = (Fix(ϕ))θ−1 . e Como pgaa−1 = pg , resulta que Prova. É imediato que A é determinı́stico. Sejam g ∈ FA e a ∈ A. −1 (pga , a , pg ) é também uma aresta de A, logo A é involutivo. u e∗ , com ai ∈ A, e existe um caminho (único) do tipo 1−→ Dado u = a1 . . . an ∈ A . . ., a saber: a a a a 1 2 3 n 1 = p1 −→p a1 θ −→p(a1 a2 )θ −→ . . . −→puθ . g g −1 Logo, para todo g ∈ FA , existe um caminho bem-sucedido 1−→pg −−→1 e A é aparado. Finalmente, u ∈ L(A) ⇔ puθ = 1 ⇔ uθ ∈ Fix(ϕ) ⇔ u ∈ (Fix(ϕ))θ−1 . No entanto, o autômato A é infinito caso ϕ 6= 1FA : se aϕ 6= a para algum a ∈ A, então é fácil ver que ak ϕ 6= ak para todo k ∈ N (usando o Lema 3.6), donde resulta que os vértices pak são todos distintos. Como proceder? A estratégia é apontada pelo seguinte lema: Lema 6.3 Se A possuir um subautômato finito A0 tal que Fix(ϕ) ⊆ L(A0 ), então Fix(ϕ) é finitamente gerado. 49 Prova. Se Fix(ϕ) ⊆ L(A0 ), então Fix(ϕ) ⊆ L(A0 ) ⊆ L(A). Pelo Lema 6.2, temos L(A) = (Fix(ϕ))θ−1 = Fix(ϕ), logo Fix(ϕ) ⊆ L(A0 ) ⊆ Fix(ϕ) e portanto L(A0 ) = Fix(ϕ). Daqui resulta que Fix(ϕ) = (L(A0 ))θ. e Como A0 é finito, L(A0 ) é uma A-linguagem racional, e logo Fix(ϕ) é um subconjunto racional de FA pela Proposição 3.13. Logo Fix(ϕ) é finitamente gerado pelo Teorema 3.14. Seja hϕ = max {|aϕ| : a ∈ A} e fixemos P 0 = {pg ∈ P : |pg | ≤ 2hϕ + 1}. Como A é finito, P 0 também o é. No entanto, pode haver uma infinidade de elementos g ∈ FA a dar origem ao mesmo vértice pg . Dado g ∈ FA , seja gι = g [1] . Por outras palavras, gι é a primeira letra de g caso g 6= 1, e é igual a 1 caso contrário. Dizemos que uma aresta (q, a, q 0 ) ∈ E é: • central se q, q 0 ∈ P 0 ; • compatı́vel se não for central e qι = a. O próximo lema recolhe algumas propriedades elementares envolvendo estes conceitos: Lema 6.4 (i) Só existe um número finito de arestas centrais em A. (ii) Se (q, a, q 0 ) ∈ E é não central, então (q, a, q 0 ) ou (q 0 , a−1 , q) é compatı́vel. (iii) Para cada q ∈ P , existe no máximo uma aresta compatı́vel com origem em q. Prova. (i) Porque A e P 0 são ambos finitos. (ii) Suponhamos que (q, a, q 0 ) não é nem central nem compatı́vel. Então podemos escrever e \ {a}. Suponhamos que |q| ≤ hϕ . Então |q 0 | = |a−1 q(aϕ)| ≤ 2hϕ + 1 e (q, a, q 0 ) seria qι = b ∈ A central, absurdo. Logo |q| > hϕ . Escrevendo q = bg, obtemos q 0 = a−1 q(aϕ) = a−1 bg(aϕ). Como b 6= a e |g| ≥ hϕ , obtemos q 0 = a−1 bg(aϕ). Logo q 0 ι = a−1 e (q 0 , a−1 , q) é compatı́vel. (iii) Porque uma aresta compatı́vel com origem em q tem necessariamente rótulo qι, e A é determinı́stico. a a 1 2 Um caminho (possivelmente infinito) q0 −→q 1 −→ . . . em A diz-se: • central se todos os seus vértices estiverem em P 0 ; • compatı́vel se todas as suas arestas forem compatı́veis e nenhum vértice intermédio pertencer a P 0. 50 Lema 6.5 Seja u ∈ Fix(ϕ). Então existe em A um caminho u w−1 v u v v w−1 u 1 n 0 n 0 1 00 2 00 1 0 n 00 1 = q00 −→q 0 −→q1 −→q1 −→q1 −→ . . . −→qn −→qn −→qn = 1 (8) tal que: (i) u = u0 v1 w1−1 u1 . . . vn wn−1 un ; uj (ii) os caminhos qj0 −→qj00 são centrais; vj wj 00 −→q e q 0 −→q são compatı́veis; (iii) os caminhos qj−1 j j j (iv) qj ∈ / P 0 se vj e wj forem ambas 6= 1. Prova. Como 1 ∈ P 0 e u ∈ L(A) pelo Lema 6.2, existe um caminho u x u x x u 0 n 00 1 0 1 00 2 0 n 00 1 = q00 −→q 0 −→q1 −→q1 −→ . . . −→qn −→qn = 1 uj em A tal que u = u0 x1 u1 . . . xn un e os caminhos qj0 −→qj00 (que podem ser triviais!) recolhem todas as ocorrências de vértices em P 0 (sendo consequentemente caminhos centrais). xj 0 00 −→q Pelo Lema 6.4(ii), se uma aresta (r, a, s) ocorre num caminho qj−1 j , então (r, a, s) ou xj 0 −1 00 −→q (s, a , r) é compatı́vel. Por outro lado, como xj é reduzida, resulta do Lema 6.4(iii) que qj−1 j se pode fatorizar como −1 w vj j 00 qj−1 −→qj −→qj0 vj wj 00 −→q e q 0 −→q compatı́veis. Note-se que a condiç ao (iv) é válida porque nenhum vértice com qj−1 j j j x j 00 −→q 0 0 intermédio de qj−1 j pode pertencer a P . a a 1 2 Dizemos que um caminho compatı́vel q0 −→q 1 −→ . . . é maximal se for infinito ou não puder ser prolongado (à direita) continuando compatı́vel. Lema 6.6 Para cada q ∈ P 0 , existe em A um único caminho compatı́vel maximal Mq com origem em q. Prova. É claro que qualquer caminho compatı́vel pode ser estendido a um caminho compatı́vel maximal. A unicidade resulta do Lemma 6.4(iii). Definimos agora P10 = {q ∈ P 0 | Mq só tem um número finito de arestas distintas} e P20 = P 0 \ P10 . Logo Mq não contém ciclos se q ∈ P20 . Pelo Lema 6.6, se os caminhos Mq e Mq0 se intersetarem num vértice rqq0 , então eles vão coincidir a partir de rqq0 . Em particular, se Mq e Mp0 se intersetarem, então q ∈ P10 se e só se q 0 ∈ P10 . Seja Y = {(q, q 0 ) ∈ P20 × P20 | Mq interseta Mq0 }. Para cada (q, q 0 ) ∈ Y , seja Mq \ Mq0 o subcaminho (finito) q−→rqq0 de Mq . Note-se que se q 0 = q, então Mq \ Mq0 é o caminho trivial no vértice q. Seja A0 o subautômato de A contendo: 51 • todos os vértices em P 0 e todas as arestas centrais; • todos os vértices e arestas nos caminhos Mq (q ∈ P10 ) e as respetivas arestas inversas; • todos os vértices e arestas nos caminhos Mq \Mq0 ((q, q 0 ) ∈ Y ) e as respetivas arestas inversas. Segue facilmente do Lema 6.4(i) e das definições de P10 e Mq \ Mq0 que A0 é um subautômato finito de A. Pelo Lema 6.3, basta mostrar que Fix(ϕ) ⊆ L(A0 ). Seja u ∈ Fix(ϕ). Consideremos o caminho fatorizado (8) fornecido pelo Lema 6.5. Como A0 contém todas as arestas centrais de A, basta mostrar que todos os subcaminhos vj wj−1 00 qj−1 −→qj −→qj0 aparecendo em (8) são caminhos em A0 . 00 Se perda de generalidade, podemos assumir que vj 6= 1. Se wj = 1, então qj−1 ∈ P10 e temos o 00 , logo podemos assumir que wj 6= 1 também. Se um pretendido pois A0 contém o caminho Mqj−1 00 , q 0 estiver em P 0 , o outro também está e de novo obtemos o pretendido. Logo dos vértices qj−1 1 j 00 , q 0 ∈ P 0 . podemos assumir que qj−1 2 j −1 00 ,q 0 : como vj w 00 Daqui resulta que qj = rqj−1 ∈ RA , é fácil ver que os caminhos Mqj−1 e Mqj0 j j wj vj 0 00 0 00 não se podem encontrar antes de pj . Logo qj−1 −→qj é precisamente Mqj−1 \ Mqj e qj −→qj é 00 precisamente Mqj0 \ Mqj−1 . Portanto são ambos caminhos em A0 como necessitávamos. Em geral, o problema de construir efetivamente S(Fix(ϕ)) (equivalente a calcular uma base para Fix(ϕ)) é muito difı́cil, mesmo para automorfismos de FA . Maslakova publicou uma prova para automorfismos em 2003, que se descobriu mais tarde conter erros. Recentemente, foram anunciados resultados que cobrem o caso de todos os endomorfismos de FA , mas estão ainda sendo verificados. O exemplo seguinte mostra um caso em que é fácil calcular todos os pontos fixos: Exemplo 6.7 Seja ϕ o automorfismo de F2 definido por aϕ = aba−1 e bϕ = a. Então Fix(ϕ) = habi. Antes de proceder ao cálculo, confirmamos que ϕ é um automorfismo tomando o endomorfismo ψ de F2 definido por aψ = b e bψ = b−1 ab. Como ϕψ = ψϕ = 1, então ϕ e ψ são automorfismos. É imediato que (ab)ϕ = aba−1 a = ab, logo ab ∈ Fix(ϕ) e habi ⊆ Fix(ϕ). Reciprocamente, seja u ∈ Fix(ϕ), digamos u = an0 bm1 an1 bm2 an2 . . . bmk−1 ank−1 bmk ank com k ≥ 0, m1 , . . . , mk , n1 , . . . , nk−1 6= 0. Se k = 0, então u = 1, logo podemos assumir que k > 0 e escrever uϕ = (abn0 a−1 )am1 (abn1 a−1 )am2 (abn2 a−1 ) . . . amk−1 (abnk−1 a−1 )amk (abnk a−1 ) = (abn0 a−1 )am1 +1 bn1 am2 bn2 . . . amk−1 bnk−1 amk −1 (abnk a−1 ). Comparando as séries de b’s em u = uϕ, concluimos que n0 6= 0 = nk ou n0 = 0 6= nk . 52 Suponhamos que n0 6= 0 = nk . Então u = uϕ traduz-se por an0 bm1 an1 bm2 an2 . . . bmk−1 ank−1 bmk = abn0 am1 bn1 am2 bn2 . . . amk−1 bnk−1 amk −1 , logo obtemos sucessivamente 1 = n0 = m1 = n1 = . . . = mk−1 = nk−1 = mk e u = (ab)k ∈ habi. Caso n0 = 0 6= nk , podemos substituir u por u−1 e usar o caso anterior. Logo Fix(ϕ) = habi. 6.2 Pontos fixos no bordo Vamos agora apresentar alguns resultados sobre pontos fixos no bordo, sem demonstração. Como (FA , d0 ) é um espaço métrico discreto, toda função de domı́nio FA é contı́nua. Mas há uma versão mais forte da continuidade que é ainda mais útil, em que as constantes na condição de continuidade não dependem do ponto considerado. Mais precisamente, uma função ϕ : (X, d) → (X 0 , d0 ) entre espaços métricos diz-se uniformemente contı́nua se: ∀ε > 0 ∃δ > 0 ∀x, y ∈ X (d(x, y) < δ ⇒ d(xϕ, yϕ) < ε). A grande vantagem é que se ϕ for uniformente contı́nua, existe uma (única) extensão contı́nua b → Yb de ϕ aos completados de X e Y . A extensão é definida por Φ:X αΦ = lim (xn ϕ), n→+∞ onde (xn )n é uma sucessão de X que converge para α. Nem todos os endomorfismos de FA são uniformente contı́nuos, mas os endomorfismos injetivos têm essa propriedade. Logo todo o endomorfismo injetivo ϕ de FA admite uma única extensão cA → F cA (e por restrição, ao bordo ∂FA ). Os pontos fixos α ∈ Fix(Φ) ∩ ∂FA dizem-se contı́nua Φ : F os pontos fixos infinitos de φ. Exemplo 6.8 Seja ϕ o endomorfismo de F2 definido por aϕ = aba−1 e bϕ = a2 . Então Fix(ϕ) = n n {1} mas α = aba2 b2 a4 b4 . . . a2 b2 . . . ∈ Fix(Φ). Procedendo analogamente ao Exemplo 6.7, mostramos que Fix(ϕ) = {1}. i i Para todo n ∈ N, seja un = Πni=0 a2 b2 . É claro que α = limn→+∞ un , logo uΦ = limn→+∞ (un ϕ). Temos i i i i i i+1 i i+1 (a2 b2 )ϕ = (aba−1 )2 (a2 )2 = (ab2 a−1 )a2 = ab2 a2 −1 , logo un ϕ = n Y i=0 Como un n+1 a2 −1 i ab2 a2 i+1 −1 n n Y Y i i+1 i n+1 n+1 = a( b2 a2 )a−1 = ( a2i b2 )a2 −1 = un a2 −1 . i=0 i=0 ∈ RA , resulta facilmente que n+1 −1 αΦ = lim (un ϕ) = lim un a2 n→+∞ n→+∞ 53 = α, logo α é um ponto fixo infinito de ϕ. Que se pode dizer sobre os pontos fixos infinitos de ϕ? É fácil ver que Fec(Fix(ϕ)) ⊆ Fix(Φ): se α = limn→+∞ (xn ϕ) para alguma sucessão em Fix(ϕ), então αΦ = lim (xn ϕ) = lim xn = α. n→+∞ n→+∞ Tais pontos fixos infinitos dizem-se singulares. Os restantes dizem-se regulares. Seja Fixr (ϕ) o conjunto dos pontos fixos infinitos regulares de ϕ. O resultado seguinte mostra que Fixr (ϕ) é num certo sentido finitamente gerado: Teorema 6.9 (Silva 2010) Seja ϕ um endomorfismo injetivo de FA . Então existem α1 , . . . , αm ∈ Fixr (ϕ) tais que Fixr (ϕ) = Fix(ϕ)α1 ∪ . . . ∪ Fix(ϕ)αm . Este resultado foi provado para automorfismos por Cooper em 1987. cA ), é também possı́vel proceder à Se ϕ for um automorfismo de FA (com extensão contı́nua Φ a F classificação dos pontos fixos infinitos regulares do ponto de vista da teoria dos sistemas dinâmicos. Dizemos que α ∈ Fixr (ϕ) é um: • atrator se cA (d0 (α, β) < ε ⇒ lim (βΦn ) = α); ∃ε > 0 ∀β ∈ F n→+∞ • repulsor se for um atrator para ϕ−1 . Noutros sistemas dinâmicos, podem existir outros tipos (hiperbólico, degenerado), mas não no nosso caso: Teorema 6.10 (Gaboriau, Jaeger, Levitt e Lustig 1998) Seja ϕ um automorfismo de FA . Então todo α ∈ Fixr (ϕ) é atrator ou repulsor. 6.3 Exercı́cios (6.1) Seja ϕ o endomorfismo de F2 definido por aϕ = aba−1 e bϕ = a−1 . Determine os pontos fixos de ϕ de comprimento < 3. (6.2) Seja ϕ o endomorfismo de F2 definido por aϕ = ab2 e bϕ = b−1 . (a) Mostre que {ab, b} é uma base alternativa de FA . (b) Usando a base alternativa, calcule Fix(ϕ). (6.3) Seja ϕ um endomorfismo injetivo de FA com Fix(ϕ) = {1}. Mostre que Fix(Φ) é finito. (6.4) Seja ϕ o endomorfismo de F2 definido por aϕ = a2 e bϕ = b2 . (a) Mostre que ϕ é injetivo. 54 (b) Calcule Fix(Φ). (c) Mostre que os pontos fixos infinitos de ϕ são todos atratores. (6.5) Seja ϕ o endomorfismo de F2 definido por aϕ = ab e bϕ = ba (endomorfismo de Thue-Morse). Mostre que: (a) ϕ é injetivo; (b) Fix(ϕ) = {1}; (c) limn→∞ aϕn ∈ Fixr (ϕ). (6.6) Dado um endomorfismo ϕ de FA , dizemos que h ∈ FA é um ponto periódico se hϕn = h para algum n ≥ 1. Seja A = {a, b, c, d} e seja ϕ o endomorfismo de FA definido por aϕ = b, bϕ = a, cϕ = c2 , Calcule o conjunto dos pontos periódicos de ϕ. 55 dϕ = d2 . 7 Apresentações de grupos Nesta secção deixamos para trás o grupo livre e procuramos ferramentas para lidar com grupos mais gerais. 7.1 Geradores e relatores Dado um grupo G, sabemos pelo Teorema 3.4 que G é isomorfo a algum quociente de um grupo livre FA . Isto equivale a dizer que existe um homomorfismo sobrejetivo ϕ : FA → G. Pelo Teorema 1.5, temos Ker(ϕ) E FA e G ∼ = FA /Ker(ϕ), logo G é determinado por A e Ker(ϕ), a menos de isomorfismo. Como Aϕ gera G, dizemos por extensão que A é um conjunto de geradores de G. Quanto a Ker(ϕ), qual a forma mais simples de descrevê-lo? Na Subsecção 1.4, definimos subgrupo gerado por um subconjunto. De forma análoga, dado um subconjunto X de um grupo G, definimos o subgrupo normal gerado por X como sendo o conjunto dos elementos da forma εn −1 (a1 xε11 a−1 1 ) . . . (an xn an ), onde n ≥ 0, ai ∈ G, xi ∈ X e εi ∈ {1, −1} para i = 1, . . . , n. É fácil verificar que este é efetivamente o menor subgrupo normal de G contendo X, sendo representado por hhXii. Voltando à representação de G ∼ = FA /Ker(ϕ), podemos então descrever Ker(ϕ) através de um subconjunto R tal que Ker(ϕ) = hhRii. A vantagem é que R pode ser muito mais pequeno e fácil de descrever que Ker(ϕ)! Dizemos que um tal R é um conjunto de relatores de G, e a expressão formal hA | Ri diz-se uma apresentação de G. Inversamente, podemos começar com um conjunto A e um subconjunto R ⊆ FA quaisquer. Então hA | Ri constitui uma apresentação de FA /hhRii, bem como de qualquer grupo que lhe seja isomorfo. 7.2 Grupos finitamente apresentáveis Uma apresentação hA | Ri diz-se finita se A e R forem ambos finitos. Um grupo diz-se finitamente apresentável se admitir uma apresentação finita. As apresentações mais simples são as da forma hA | ∅i, que definem os grupos livres FA . O exemplo seguinte envolve uma apresentação com um único relator. Introduzimos a notação [g, h] = ghg −1 h−1 para quaisquer elementos g, h ∈ G. Um elemento desta forma diz-se um comutador de G. Exemplo 7.1 ha, b | [a, b]i é uma apresentação de Z × Z. Para mostrar isto, definimos um homomorfismo ϕ : F2 → Z × Z por aϕ = (1, 0) e bϕ = (0, 1). É claro que ϕ é sobrejetivo e [a, b] ∈ Ker(ϕ). Seja N = hh[a, b]ii. Então N ⊆ Ker(ϕ) e pelo Teorema 1.5 ϕ induz um homomorfismo (sobrejetivo) Φ : F2 /N → Z × Z definido por (aN )Φ = (1, 0) e (bN )Φ = (0, 1). 56 Por outro lado, definimos Ψ : Z × Z → F2 /N por (m, n)Ψ = am bn N . Como abN = baN , resulta facilmente que am bn N = bn am N para todos m, n ∈ Z, e daqui se conclui que Ψ é um homomorfismo. Como (xN )ΦΨ = xN para x ∈ {a, b} e F2 /N é gerado por aN, bN , resulta que ΦΨ = 1F2 /N e logo Φ é injetivo. Logo Φ é um isomorfismo e ha, b | [a, b]i é uma apresentação de Z × Z. Vejamos em seguida que todos os grupos finitos são finitamente apresentáveis: Proposição 7.2 Todo grupo finito é finitamente apresentável. Prova. Seja G um grupo finito. Seja A = {ag | g ∈ G} um alfabeto em bijeção com G e seja R = {ag ah a−1 gh | g, h ∈ G}. Vamos mostrar que hA | Ri é uma apresentação de G. Seja ϕ : FA → G o homomorfismo sobrejetivo definido por ag ϕ = g e seja N = hhRii. Como R ⊆ Ker(ϕ), resulta do Teorema 1.5 que ϕ induz um homomorfismo (sobrejetivo) Φ : FA /N → G definido por (ag N )Φ = g. −1 2 Como a1 a1 a−1 1 ∈ R, obtemos a1 N = a1 N e logo a1 N = N . Por outro lado, como ag ag −1 a1 ∈ R, −1 obtemos a−1 g N = (ag −1 N )(a1 N ) = ag −1 N . Junto com as relações ag ah N = agh N e a1 N = N , isto implica que todo elemento de FA /N se pode escrever na forma ag N para algum g ∈ G. Logo |FA /N | ≤ |A| = |G|. Como Φ é sobrejetivo, resulta que |FA /N | = |G| e logo Φ é um isomorfismo. Mostramos em seguida que a existência de uma apresentação finita é independente do conjunto (finito) de geradores considerado: Proposição 7.3 Seja G um grupo finitamente apresentável e seja ψ : FB → G um homomorfismo sobrejetivo de grupos com B finito. Então G admite uma apresentação finita da forma hB | Si. Prova. Seja hA | Ri uma apresentação finita de G, e seja ϕ : FA → G o correspondente homomorfismo sobrejetivo. Podemos definir um homomorfismo α : FA → FB tal que o diagrama FA α ϕ /G > ψ FB comuta: basta escolher aα ∈ aϕψ −1 para todo a ∈ A e usar a propriedade universal. Analogamente, 57 existe um homomorfismo β : FB → FA tal que o diagrama FOA ϕ β /G > ψ FB comuta. Seja S = Rα ∪ {b−1 (bβα) | b ∈ B} e N = hhSii. Como bN = (bβα)N para todo b ∈ B, resulta facilmente que uN = (uβα)N para todo u ∈ FB . (9) É fácil verificar que S ⊆ Ker(ψ), logo N ⊆ Ker(ψ). Reciprocamente, seja u ∈ Ker(ψ). Como uβϕ = uψ = 1 e Kerϕ = hhRii, obtemos uβα ∈ hhRiiα ⊆ hhRαii ⊆ N. Aplicando (9), resulta que u ∈ N e logo Ker(ψ) ⊆ N . Logo Ker(ψ) = N = hhSii e hB | Si é uma apresentação finita de G. 7.3 Decidibilidade O problema da palavra ganha generalidade no contexto as apresentações: dizemos que a apresentação hA | Ri tem problema da palavra decidı́vel se existir um algoritmo que determine se um elemento arbitrário de FA pertence a N = hhRii. Como uN = vN se e só se u−1 v ∈ N , isto equivale a poder determinar quando dois elementos de FA representam o mesmo elemento de FA /N . Tal como na Proposição 7.3, a decidibilidade do problema da palavra não depende da apresentação considerada para o grupo: Proposição 7.4 Sejam hA | Ri e hB | Si apresentações finitas de um grupo G. Então hA | Ri tem problema da palavra decidı́vel se e só se hB | Si tem problema da palavra decidı́vel. Prova. Suponhamos que hA | Ri tem problema da palavra decidı́vel. Tal como na prova da Proposição 7.3, consideramos o diagrama comutativo FOA β ϕ /G > ψ FB 58 onde ϕ e ψ são sobrejetivos, Ker(ϕ) = hhRii e Ker(ψ) = hhSii. Dado u ∈ FB , temos u ∈ hhSii ⇔ uψ = 1 ⇔ uβϕ = 1 ⇔ uβ ∈ hhRii. Como podemos decidir se uβ ∈ hhRii, então hB | Si tem problema da palavra decidı́vel. Por simetria, obtemos o resultado. Graças à Proposição 7.4, podemos dizer que um grupo finitamente apresentável tem problema da palavra decidı́vel ou indecidı́vel sem especificarmos a apresentação (finita). O resultado seguinte foi demonstrado de forma independente por Novikov e Boone durante a Guerra Fria, numa época em que a matemática produzida em cada um dos blocos era pouco divulgada no outro: Teorema 7.5 (Novikov 1955, Boone 1957) Existem grupos finitamente apresentáveis com problema da palavra indecidı́vel. A prova deste teorema é complexa e pode ser obtida codificando uma das estruturas mais gerais da teoria da computação (a máquina de Turing) através de uma apresentação finita de um grupo! A indecidibilidade do chamado problema da paragem da máquina de Turing implica então a indecidibilidade do problema da palavra do grupo. Como consequência do Teorema 7.5, todos os problemas algébricos não triviais se revelam indecidı́veis para apresentações finitas arbitrárias de grupos. Por exemplo: Teorema 7.6 (Adjan 1955, Rabin 1958) É indecidı́vel se um grupo finitamente apresentável arbitrário é trivial, finito, infinito, livre. 7.4 Diagramas de van Kampen Os diagramas de van Kampen constituem uma das ferramentas geométricas clássicas para estudar apresentações de grupos. Um grafo Γ = (V, E) diz-se planar se puder ser realizado geometricamente num plano, isto é, se pudermos representar V e E como conjuntos de pontos e linhas no plano de forma a que as linhas não se intersetem fora dos vértices. Por exemplo, o grafo completo com 4 vértices (K4 ) é planar pois admite a representação • • • • 59 enquanto K5 constitui o mais pequeno exemplo (em termos de vértices) de grafo não planar • • • • • e o grafo bipartido K3,3 • • • • • • é o grafo não planar com menor número de arestas. O conceito de planaridade estende-se da maneira óbvia a grafos orientados e a A-grafos. Um A-grafo diz-se conexo se for conexo enquanto grafo não orientado. Note-se que um grafo (grafo orientado, A-grafo) planar finito divide o plano num número finito de regiões (incluindo a região exterior). A fronteira de uma região é o conjunto dos vértices e das arestas que lhe são adjacentes. No caso de um A-grafo conexo, o bordo de uma região é uma palavra e∗ obtida lendo sucessivamente o rótulo das arestas da sua fronteira, começando num vértice w∈A qualquer e seguindo o sentido horário ou anti-horário. Para este efeito, lemos o rótulo das arestas como se o autômato fosse involutivo. Note-se que o bordo de uma região pode ser representado por várias palavras, mas cada uma delas será sempre um conjugado cı́clico ou o inverso de um conjugado cı́clico da outra. Exemplo 7.7 Seja A = {a, b} e seja Γ o A-grafo descrito por a •o ?• /•o •_ b a ?• a a b a b • /• a b As 4 regiões interiores de Γ têm bordo a3 (duas vezes), aba−1 b−1 e b3 , enquanto a região exterior tem bordo ba−2 b2 a2 . Seja P = hA | Ri uma apresentação de grupos. É claro que podemos sempre assumir que os relatores de R estão na forma reduzida. Como u = 1 se e só se xux−1 = 1 em qualquer grupo, podemos até assumir que os relatores são palavras ciclicamente reduzidas. Sob esta suposição, definimos diagrama de van Kampen de P como sendo um A-grafo conexo finito em que: • cada região interior admite como bordo um relator de R; 60 • o bordo da região exterior é ciclicamente reduzido. Note-se que, para ler o relator de R, temos o direito de escolher o vértice inicial e o sentido no cálculo do bordo da região interior. O bordo da região exterior diz-se o bordo do diagrama. Mais uma vez, um diagrama pode admitir como bordo várias palavras, mas cada uma delas será sempre um conjugado cı́clico ou o inverso de um conjugado cı́clico da outra. A dimensão do diagrama é o número de regiões interiores. É imediato que o A-grafo do Exemplo 7.7 é um diagrama de van Kampen da apresentação ha, b | a3 , b3 , [a, b]i com bordo ba−2 b2 a2 . O resultado seguinte explica a importância dos diagramas de van Kampen no estudo do problema da palavra. Note-se que para resolver o problema da palavra, basta considerar palavras ciclicamente reduzidas! Teorema 7.8 (van Kampen 1933) Seja P = hA | Ri uma apresentação de grupos com relatores ciclicamente reduzidos e seja w ∈ FA ciclicamente reduzida. Então as condições seguintes são equivalentes: −1 −1 e x ∈ F ; (i) w = (x1 r1 x−1 i A 1 ) . . . (xk rk xk ) para alguns k ≥ 0, ri ∈ R ∪ R (ii) existe um diagrama de van Kampen de P de dimensão k e bordo w. Além disso, se R for finito e M = max {|r| : r ∈ R}, podemos assumir que 1 |xi | ≤ (k|w| + k 2 M ) para i = 1, . . . , k. 2 (10) e Prova. (i) ⇒ (ii). Consideramos o A-grafo involutivo descrito por rk % •o xk • x3 ... E• x1 x2 /•e r1 •Q r2 r3 ao qual removemos em seguida todas as arestas com rótulo em A−1 . Obtemos assim um A-grafo planar conexo com k regiões interiores. O último passo consiste em executar a dobragem sucessiva de arestas da forma • 8• a • a a /• ou • a /& quando não exista nenhuma aresta no meio! Esta versão da dobragem de arestas preserva a planaridade do grafo, a conexidade e o número de regiões interiores, bem como os seus bordos (que permanecem relatores de R). Quando o processo terminar, poderemos ler no bordo a palavra 61 −1 (x1 r1 x−1 1 ) . . . (xk rk xk ), isto é, w. Logo construı́mos um diagrama de van Kampen de P de dimensão k e bordo w. (ii) ⇒ (i). Procedemos por indução sobre a dimensão do diagrama de van Kampen. O único diagrama de dimensão 0 é o diagrama trivial que contém apenas um único vértice e tem como bordo a palavra vazia. Logo a implicação é válida para k = 0. Além disso, se R for finito então (10) é trivialmente verificada. Suponhamos agora que D é um diagrama de dimensão k > 0 e bordo w, e que a implicação (ii) ⇒ (i) é válida para diagramas de dimensão k − 1. Supomos ainda que (10) é verificada para k − 1 quando R é finito. e Para efeitos de representação de rótulos de regiões e caminhos, encaramos D como um A-grafo involutivo. Nesse caso, temos um loop em D pd w que dá origem ao bordo. Entre os vértices deste loop adjacentes a uma região interior, seja q o mais próximo de p. Trocando w por w−1 se necessário, podemos assumir que o loop de rótulo w se fatoriza como pj u *q v com uv = w e |u| ≤ acordo com a figura |w| 2 . Podemos assumir que a região interior I adjacente a q tem bordo v 0 z de p u /qk v0 I + q0 v 00 /p z v0 onde v 0 v 00 = v e q −→q 0 é a parte da fronteira de I contı́gua à região exterior. Seja D0 o A-grafo v0 0 obtido removendo de D as arestas e os vértices intermédios do caminho q −→q . É fácil verificar que D0 é um diagrama de van Kampen de P com bordo uz −1 v 00 se z 6= 1 pois nesse caso uz −1 v 00 é ciclicamente reduzida. E se z = 1? Então pode acontecer que uv 00 não seja reduzida – por exemplo, se D for da forma p q • Nesse caso, se y é o núcleo cı́clico de uv 00 = hyh−1 , eliminamos as arestas de D0 correspondentes ao rótulo h (e que estão totalmente imersas na face exterior do A-grafo). Logo podemos sempre afirmar em qualquer caso que existe um diagrama de van Kampen D00 de P de dimensão k − 1 que tem como bordo o núcleo cı́clico y de uz −1 v 00 = hyh−1 . Note-se que |h| ≤ |w| 2 e |y| ≤ |w| + M . −1 Pela hipótese de indução, podemos escrever y = (x1 r1 x1 ) . . . (xk−1 rk−1 x−1 k−1 ) para alguns ri ∈ R ∪ R−1 e xi ∈ FA . Além disso, se R for finito, temos |xi | ≤ 21 ((k − 1)|y| + (k − 1)2 M ) para i = 1, . . . , k − 1. Logo w = uv = uv 0 v 00 = (u(v 0 z)u−1 )(uz −1 v 00 ) = (u(v 0 z)u−1 )(hyh−1 ) = (u(v 0 z)u−1 )((hx1 )r1 (hx1 )−1 ) . . . ((hxk−1 )rk−1 (hxk−1 )−1 ). Como v 0 z é um conjugado cı́clico de algum r ∈ R ∪ R−1 , (i) é válido. 62 Suponhamos agora que R é finito. Podemos escrever u(v 0 z)u−1 = (ut)r(ut)−1 para algum t ∈ FA tal que |t| ≤ M 2 . Logo |ut| ≤ |u| + |t| ≤ |w| M 1 + ≤ (k|w| + k 2 M ). 2 2 2 Por outro lado, para i = 1, . . . , k − 1, temos 1 2 |hxi | ≤ |h| + |xi | ≤ |w| 2 + 2 ((k − 1)|y| + (k − 1) M ) 1 1 2 2 ≤ |w| 2 + 2 ((k − 1)|w| + (k − 1)M + (k − 1) M ) ≤ 2 (k|w| + k M ). Logo (10) é válido e a prova está completa. 7.5 Funções isoperimétricas Seja P = hA | Ri uma apresentação finita de um grupo G e seja ϕ : FA → G o correspondente homomorfismo sobrejetivo. Dado w ∈ 1ϕ−1 , definimos a área de w como sendo o menor k ≥ 0 tal que −1 w = (x1 r1 x−1 1 ) . . . (xk rk xk ) para alguns ri ∈ R ∪ R−1 e xi ∈ FA . Designamo-la por Area(w). Uma função Iso : N → [0, +∞[ diz-se uma função isoperimétrica para P se Area(w) ≤ Iso(|w|) para todo w ∈ 1ϕ−1 . Certos tipos de funções são particularmente importantes. Dizemos que uma função Iso : N → [0, +∞[ é: • linear se existir K > 0 tal que Iso(n) = Kn para todo n ∈ N; • quadrática se existir K > 0 tal que Iso(n) = Kn2 para todo n ∈ N; • polinomial se existirem K > 0 e m ∈ N tais que Iso(n) = Knm para todo n ∈ N; • exponencial se existir K > 0 tal que Iso(n) = K n para todo n ∈ N; • recursiva se existir um algoritmo que calcula efetivamente Iso(n) para todo n ∈ N. Exemplo 7.9 A apresentação P = ha, b | [a, b]i de Z × Z admite uma função isoperimétrica quadrática. Consideremos o homomorfismo ϕ : F2 → Z × Z definido por aϕ = (1, 0) e bϕ = (0, 1). Sejam 2 Iso(n) = n4 e w ∈ 1ϕ−1 . Vamos mostrar que Area(w) ≤ Iso(w) por indução sobre |w|. Temos Area(w) = 0 quando |w| < 4 pois a única palavra reduzida de comprimento < 4 em 1ϕ−1 é a palavra vazia. Suponhamos agora que |w| = n ≥ 4 e que a desigualdade Area(w0 ) ≤ Iso(w0 ) é válida para elementos w0 ∈ 1ϕ−1 de comprimento < n. 63 Podemos fatorizar w = uaε bm a−ε v (em forma reduzida) para alguns ε ∈ {1, −1} e m 6= 0. Então w = (uaε bm a−ε b−m u−1 )(ubm v). Como ambos os fatores desta fatorização pertencem a 1ϕ−1 , podemos escrever Area(w) ≤ Area(uaε bm a−ε b−m u−1 ) + Area(ubm v). (11) Ora Area(xyx−1 ) = Area(y) para todos x ∈ FA e y ∈ 1ϕ−1 , logo Area(uaε bm a−ε b−m u−1 ) = Area(aε bm a−ε b−m ). Como existe um diagrama de van Kampen •O b a /• O b b b / ... b a a • /• O /• b /• /• O a b / ... b /• de bordo aε bm a−ε b−m e dimensão m, resulta do Teorema 7.8 que Area(aε bm a−ε b−m ) ≤ m < Por outro lado, Area(ubm v) ≤ Area(w) < (n−2)2 4 n 2. por hipótese de indução, logo resulta de (11) que n (n − 2)2 2n + n2 − 4n + 4 n2 − 2n + 4 n2 + = = < 2 4 4 4 4 e portanto Iso é uma função isoperimétrica para P. O seguinte resultado é uma das consequências importantes do Teorema 7.8: Corolário 7.10 Seja P = hA | Ri uma apresentação finita. Então as condições seguintes são equivalentes: (i) P tem problema da palavra decidı́vel; (ii) P admite uma função isoperimétrica recursiva. Prova. (i) ⇒ (ii). Seja Dehn(n) = max ({Area(w) | w ∈ hhRii, |w| = n} ∪ {0}). É claro que a função Dehn constitui uma função isoperimétrica para P, dita função de Dehn de P. Note-se que Dehn(n) ≤ Iso(n) para toda outra função isoperimétrica Iso. Para mostrar que a função Dehn é recursiva, tomamos w ∈ FA com |w| = n. Podemos utilizar (i) para decidir se w pertence ou não a hhRii. Suponhamos que pertence. Agora basta mostrar que Area(w) é computável, para o que utilizamos o seguinte algoritmo: Para k = 0, 1, 2, . . ., vamos testar se Area(w) = k verificando se a igualdade −1 w = (x1 r1 x−1 1 ) . . . (xk rk xk ) 64 (12) é válida em FA para alguma escolha de xi ∈ FA e ri ∈ R ∪ R−1 . Pelo Teorema 7.8, só temos que testar um número finito de xi , e o mesmo acontece com os ri visto que R é finito. Como w ∈ hhRii, acabaremos inevitavelmente por encontrar um valor de k para o qual (12), se verifique. Esse valor é Area(w). Logo a função Dehn é uma função isoperimétrica recursiva para P. (ii) ⇒ (i). Seja Iso uma função isoperimétrica recursiva para P. Seja w ∈ FA . Queremos mostrar que é decidı́vel se w ∈ hhRii. Como Area(w) ≤ Iso(|w|), isto equivale a ter a igualdade (12) para alguns k ≤ Iso(|w|), xi ∈ FA e ri ∈ R ∪ R−1 . Mais uma vez, resulta do Teorema 7.8 que só temos que testar um número finito de xi , e o mesmo acontece com os ri . Logo só temos de testar um número finito de igualdades do tipo (12) em FA , donde resulta a decidibilidade do problema da palavra. Dado um grupo finitamente apresentável, a existência de uma função isoperimétrica de um determinado tipo não depende da apresentação finita escolhida, sendo pois um invariante do grupo: Proposição 7.11 Sejam P = hA | Ri e P 0 = hA0 | R0 i apresentações finitas de um grupo G. Se P admite uma função isoperimétrica recursiva (respetivamente linear, quadrática, polinomial, exponencial), o mesmo acontece com P 0 . Prova. O caso recursivo segue da Proposição 7.4 e do Corolário 7.10. Os restantes casos podem ser demonstrados usando argumentos análogos aos desenvolvidos na prova da Proposição 7.3. 7.6 Exercı́cios (7.1) (a) Mostre que S3 é gerado pelo subconjunto de permutações A = {(123), (12)}. (b) Construa uma apresentação finita de S3 com dois geradores. (7.2) Dados m, n ∈ N, construa uma apresentação finita de Cm × Cn com 3 relatores. (7.3) Dado n ∈ N, construa uma apresentação finita de Z × Cn . (7.4) Mostre que os grafos seguintes são planares: (a) • • • • • (b) • • • • • • 65 (7.5) Para cada uma das apresentações dos grupos S3 , C3 × C3 e Z × C2 construı́das nos Exercı́cios 7.1 – 7.3, construa um diagrama de van Kampen com 5 regiões interiores e calcule o respetivo bordo. (7.6) Seja G o grupo definido pela apresentação P = ha, b, c | a2 c−1 , a2 b−2 i. (a) Mostre que a • c /• b /• a a • c • /• c a • c a b /• b a • b /• /• a é um diagrama de van Kampen de P. (b) Determine se bca−1 cab−2 c−1 ac−2 ab = 1 em G. (7.7) Determine se existe algum diagrama de van Kampen da apresentação ha, b | [a, b]i com bordo aba−1 b−2 . (7.8) Mostre que o grupo cı́clico Cn admite uma função isoperimétrica linear para todo n ≥ 1. 66 8 Produto livre e generalizações As apresentações revelam-se particularmente úteis no estudo de certos operadores, como é o caso do produto livre e suas generalizações, que incluem casos tão importantes como os produtos livres com amalgamação ou os produtos de grafo. 8.1 Produto livre Dizemos que o grupo H é o produto livre dos grupos G1 e G2 se existirem homomorfismos ιi : Gi → H (i = 1, 2) tais que: para todo grupo K e homomorfismos ϕi : Gi → K (i = 1, 2), existe um único homomorfismo Φ : H → K tal que o diagrama G1 ι1 / H o ι2 Φ ϕ1 ~ G2 ϕ2 K comuta. Lema 8.1 Sejam G1 e G2 grupos. O produto livre de G1 e G2 , a existir, é único a menos de isomorfismo. Prova. Suponhamos que H é o produto livre de G1 e G2 para os homomorfismos ιi : Gi → H (i = 1, 2), e H 0 é o produto livre de G1 e G2 para os homomorfismos ι0i : Gi → H 0 (i = 1, 2). Então existem homomorfismos Φ : H → H 0 e Ψ : H 0 → H tais que ιi Φ = ι0i e ι0i Ψ = ιi (i = 1, 2). Mas então ι1 ι2 /Ho G1 G2 ι1 1H ΦΨ ι2 ~ H é um diagrama comutativo. Pela unicidade do homomorfismo na definição de produto direto, obtemos ΦΨ = 1H . Analogamente, ΨΦ = 1H 0 , logo Φ e Ψ são isomorfismos e H ∼ = H 0. Para demonstrar a existência do produto livre, vamos proceder à seguinte construção. Dado um grupo G, seja G̊ = G \ {1}. Fixemos agora grupos G1 e G2 . Construimos um alfabeto AG1 ,G2 = {ag | g ∈ G1 } ∪ {bh | h ∈ G2 } e consideramos o sistema de reescrita RG1 ,G2 = {(ag ag0 , agg0 ) | g, g 0 ∈ G1 } ∪ {(bh bh0 , bhh0 ) | h, h0 ∈ G2 } ∪ {(a1 , 1), (b1 , 1)}. 67 Lema 8.2 Sejam G1 e G2 grupos. Então RG1 ,G2 é um sistema de reescrita redutor e confluente. Prova. É evidente que RG1 ,G2 é redutor, e a confluência prova-se analogamente à demonstração do Lema 3.1: só temos que testar a confluência local para situações do tipo xag ag0 ag00 y / xagg0 ag00 y xag a1 y / xag y xa1 ag y xag ag0 g00 y / xag y xag1 y xa1g y e as versões análogas para G2 , o que se confirma facilmente. Seja G1 ∗ G2 = Irr(RG1 ,G2 ). Então G1 ∗ G2 consiste na palavra vazia e em todas as palavras que alternam letras da forma ag (g ∈ G̊1 ) com letras da forma bh (h ∈ G̊2 ). Definimos uma operação binária ◦ em G1 ∗ G2 do seguinte modo: Dados u, v ∈ G1 ∗ G2 , u ◦ v é a forma reduzida da palavra uv em RG1 ,G2 . A confluência garante que esta operação é associativa, e a palavra vazia é o elemento neutro. É fácil verificar a existência de inversos: por exemplo, (ag1 bh1 . . . agn bhn ) ◦ (bh−1 agn−1 . . . bh−1 ag−1 ) = 1 n 1 1 e todos os outros casos são análogos. Logo (G1 ∗ G2 , ◦) é um grupo. Note-se que existe um homomorfismo injetivo ι1 : G1 → G1 ∗ G2 definido por ag se g 6= 1 gι1 = 1 se g = 1 Analogamente definimos ι2 : G2 → G1 ∗ G2 . Teorema 8.3 Sejam G1 e G2 grupos. Então G1 ∗ G2 é o produto livre de G1 e G2 relativamente aos homomorfismos ιi : Gi → G1 ∗ G2 (i = 1, 2). Prova. Seja A = AG1 ,G2 e R = RG1 ,G2 . Seja K um grupo e seja ϕi : Gi → K um homomorfismo para i = 1, 2. Definimos um homomorfismo ϕ : A∗ → K por ag ϕ = gϕ1 (g ∈ G1 ) e bh ϕ = hϕ2 (h ∈ G2 ). Seja Φ = ϕ |Irr(R) . Para todo g ∈ G̊1 , temos gι1 Φ = ag Φ = gϕ1 . Como 1G1 ι1 Φ = 1Φ = 1 = 1G1 ϕ1 , obtemos ι1 Φ = ϕ1 . Analogamente, ι2 Φ = ϕ2 . Para mostrar que Φ : G1 ∗ G2 → K é um homomorfismo de grupos, temos que provar que (u◦v)Φ = (uΦ)(vΦ) para todos u, v ∈ G1 ∗G2 . Como (uΦ)(vΦ) = (uϕ)(vϕ) = (uv)ϕ, basta verificar que rϕ = sϕ para todo (r, s) ∈ R, o que é obviamente verdade. Logo Φ é um homomorfismo. Finalmente, a unicidade de Φ resulta do fato de X = G1 ι1 ∪ G2 ι2 gerar G1 ∗ G2 , e Φ|X estar univocamente determinado. Habitualmente, simplificamos a representação dos elementos de G1 ∗G2 escrevendo g1 h1 . . . gn hn em vez de ag1 bh1 . . . agn bhn e assim sucessivamente. É a representação do produto livre em forma normal. Podemos afirmar que o produto livre G1 ∗G2 é o maior grupo, gerado por G1 ∪G2 , pois qualquer outro grupo K nestas condiçõs será necessariamente imagem homomorfa de G1 ∗ G2 . Vamos ver em seguida como o produto livre se traduz em termos de apresentações: 68 Teorema 8.4 Seja hAi | Ri i uma apresentação do grupo Gi para i = 1, 2, com A1 ∩ A2 = ∅. Então hA1 ∪ A2 | R1 ∪ R2 i é uma apresentação de G1 ∗ G2 . Prova. Sem perda de generalidade, podemos assumir que Gi = FAi /hhRi ii. Sejam A = A1 ∪ A2 e R = R1 ∪ R2 . Seja H = FA /hhRii. Pelo Teorema 1.5, podemos definir um homomorfismo ιi : Gi → H para i = 1, 2 por (ghhRi ii)ιi = ghhRii. Dado um grupo K e homomorfismos ϕi : Gi → K (i = 1, 2), consideremos os homomorfismos canónicos πi : FAi → Gi . É fácil construir um homomorfismo ϕ : FA → K tal que ϕ|FAi = πi ϕi para i = 1, 2. Ora Ri ⊆ Ker(πi ) ⊆ Ker(ϕ) para i = 1, 2 implica R ⊆ Ker(ϕ), logo pelo Teorema 1.5 existe um homomorfismo Φ : H → K tal que (ghhRii)Φ = gϕ. Para todo g ∈ FAi , temos (ghhRi ii)ιi Φ = (ghhRii)Φ = gϕ = gπi ϕi = (ghhRi ii)ϕi , logo ιi Φ = ϕi para i = 1, 2. A unicidade de Φ resulta do fato de im(ι1 ) ∪ im(ι2 ) gerar H. Logo H é o produto livre de G1 e G2 e portanto hA1 ∪ A2 | R1 ∪ R2 i é uma apresentação de G1 ∗ G2 . 8.2 Generalizações Os produtos livres com amalgamação constituem uma das generalizações mais importantes do produto livre pelo seu significado geométrico. Suponhamos que G1 e G2 são grupos com subgrupos H1 , H2 (respetivamente), e existe um isomorfismo ϕ : H1 → H2 . Seja N = hh(hϕ)h−1 : h ∈ H1 ii E G1 ∗ G2 . O grupo quociente (G1 ∗ G2 )/N diz-se o produto livre com amalgamação de G1 e G2 (relativamente ao isomorfismo ϕ). O produto livre corresponde ao caso particular H1 = H2 = {1}. O produto livre com amalgamação aparece por exemplo no famoso Teorema de van Kampen. Em topologia algébrica, o chamado grupo fundamental é o mais importante dos invariantes topológicos associados a um espaço topológico (isto é, espaços topológicos homeomorfos têm grupos fundamentais isomorfos). Ora no estudo das variedades, as técnicas ditas de cirurgia são muito importantes pois elas permitem decompor/construir variedades mais complexas a partir de variedades mais simples. O Teorema de van Kampen (1933) explica que, nas condições apropriadas, o grupo fundamental da união de duas variedades é um produto livre com amalgamação dos grupos fundamentais das dua variedades mais simples. Esta é mais um resultado brilhante do belga Egbert van Kampen. Infelizmente ele morreu com apenas 33 anos! Outra generalização é o chamado produto de grafo. Suponhamos que G1 , . . . , Gn são grupos e que Γ = (V, E) é um grafo com V = {1, . . . , n}. O Γ-produto de G1 , . . . , Gn pretende ser o maior grupo, gerado por G1 ∪ . . . ∪ Gn , no qual os elementos de Gi comutam com os elementos de Gj quando existe uma aresta i −− j em Γ. Note-se que o produto livre é na realidade uma operação associativa (ver o Exercı́cio 8.2), o que permite falar do produto livre G1 ∗ G2 ∗ . . . ∗ Gn . Formalmente, o Γ-produto de G1 , . . . , Gn é o grupo quociente Γ(G1 , . . . , Gn ) = (G1 ∗ G2 ∗ . . . ∗ Gn )/N, 69 onde N = hh[gi , gj ] : gi ∈ Gi , gj ∈ Gj , (i −− j) ∈ Eii E G1 ∗ . . . ∗ Gn . Se E = ∅, então Γ(G1 , . . . , Gn ) é o produto livre G1 ∗ . . . ∗ Gn . Se Γ for um grafo completo, Γ(G1 , . . . , Gn ) é o produto direto G1 × . . . × Gn . Se Γ for o quadrado 1 2 3 4 é fácil ver que Γ(G1 , G2 , G3 , G4 ) ∼ = (G1 ∗ G4 ) × (G2 ∗ G3 ). Os produtos de grafos permitem assim introduzir elementos de comutatividade parcial num operador tão ferozmente anti-comutativo como o produto livre. Estas ideias de comutatividade parcial são muito importantes também na teoria da computação, onde são usadas na construção de modelos para a computação em paralelo. 8.3 Grupos de grafo Os grupos de grafo são produtos de grafo de grupos cı́clicos infinitos, ou seja, da forma Γ(Z, . . . , Z). Se Γ = (V, E) e V = {1, . . . , n}, resulta que Γ(Z, . . . , Z) admite a apresentação ha1 , . . . , an | [ai , aj ] ((i −− j) ∈ E)i. (13) Se E = ∅, obtemos o grupo livre Fn . Se Γ for um grafo completo, obtemos o grupo abeliano livre Zn (ver o Exercı́cio 3.1). Os grupos de grafo, também chamados de grupos de Artin ortogonais, partilham com os grupos livres muitas das suas boas propriedades. Por exemplo: Teorema 8.5 Todo grupo de grafo tem problema da palavra decidı́vel. Prova. Vamos traçar as linhas gerais da demonstração, omitindo alguns detalhes técnicos. Seja Γ = (V, E) um grafo com V = {1, . . . , n} e seja G o grupo definido pela apresentação (13). e∗ → G a projeção canónica. Seja A = {a1 , . . . , an } e seja ϕ : A e tais que: Designamos por X o conjunto de todos os subconjuntos X de A • X ∩ X −1 = ∅; • se aδi e aεj são elementos distintos de X, então (i −− j) ∈ E. Para simplificar a notação, escreveremos X + a = X ∪ {a}, e para todos X ∈ X e a ∈ A. 70 X − a = X \ {a} Construimos um alfabeto finito B = {bX | X ∈ X } e um sistema de reescrita em B definido por R = {(bX bY , bX−a bY −a−1 ) | X, Y ∈ X ; a ∈ X ∩ Y −1 } ∪ {(bX bY , bX+a bY −a ) | X + a, Y ∈ X ; a ∈ Y \ X} ∪ {(b∅ , 1)}. É fácil ver que R é noetheriano, logo a confluência resultará da confluência local tal como no Lemma 3.1. Limitar-nos-emos a analisar um único caso como exemplo: e são tais que a ∈ X ∩ Y −1 , c ∈ Z \ Y e Suponhamos que w, z ∈ B ∗ , X, Y, Z ∈ X e a, c ∈ A ±1 Y + c ∈ X . É fácil verificar que c 6= a e que podemos completar o diagrama seguinte da forma indicada, / wbX−a b wbX bY bZ z Y −a−1 bZ z / wbX−a b Y −a−1 +c bZ−c z wbX bY +c bZ−c z o que comprova a confluência local para sobreposições deste tipo. Admitida a confluência, resulta da Proposição 2.10 que para cada w ∈ B ∗ existe uma única palavra wη ∈ Irr(R) tal que w−→∗ wη. e∗ → B ∗ o homomorfismo de monóides definido por aα = ba (a ∈ A). e Definimos Seja α : A Q ∗ ∗ e também um homomorfismo de monóides β : B → A por Xβ = a∈X a (X ∈ X ), sendo a ordem e resulta que no produto das letras fixada arbitrariamente. Como aαβ = a para toda a ∈ A, uαβ = u (14) e∗ . para toda u ∈ A Por outro lado, se (r, s) ∈ R, é fácil verificar que rβϕ = sβϕ, logo w−→z implica wβϕ = zβϕ e consequentemente w−→∗ z implica wβϕ = zβϕ (15) para todas w, z ∈ B ∗ . Para provar que o problema da palavra de G é decidı́vel, basta agora mostrar que uϕ = 1 se e só se uαη = 1 e∗ , uma vez que uαη é efetivamente computável. para toda u ∈ A Suponhamos então que uϕ = 1. Então podemos escrever uθ = vθ para alguma palavra εk −1 v = (x1 [ai1 , aj1 ]ε1 x−1 1 ) . . . (xk [aik , ajk ] xk ), 71 (16) e∗ , (it −− jt ) ∈ E, εt = ±1 para t = 1, . . . , k. É fácil verificar que [ait , ajt ]αη = 1 com k ≥ 0 e xt ∈ A f∗ e a ∈ A, e logo para todo t, logo vαη = 1. Por outro lado, (paa−1 q)αη = (pq)αη para todas p, q ∈ A uθ = vθ implica uαη = vαη = 1. Reciprocamente, suponhamos que uαη = 1. Então uα−→∗ 1, logo uαβϕ = 1 por (15). Logo uϕ = 1 por (14) e portanto (16) é válido com pretendı́amos. Mas seria prematuro pensar que todas as boas propriedades dos grupos livres são herdadas pelos grupos de grafo. Por exemplo, mesmo no caso particular do quadrado 1 2 3 4 que define o grupo F2 × F2 , as dificuldades aparecem: Teorema 8.6 (Mihailova 1966) O problema da palavra generalizado é indecidı́vel para F2 × F2 . Pior ainda, Mihailova constrói um certo H ≤f.g. F2 × F2 tal que é indecidı́vel , para g ∈ F2 × F2 arbitrário, se g ∈ H ou não. 8.4 Exercı́cios (8.1) Sejam G e H grupos não triviais. Mostre que: (a) os elementos de ordem finita de G ∗ H são os conjugados dos elementos de ordem finita de G e H; (b) G ∗ H tem elementos de ordem infinita. (8.2) Mostre que o produto livre de grupos é associativo. (8.3) Sejam G e H grupos não triviais e seja K o conjunto dos elementos de G ∗ H da forma g1 h1 . . . gn hn (gi ∈ G \ {1}, hi ∈ H \ {1}). Mostre que: (a) todo elemento de G ∗ H é conjugado de algum elemento de G ou H ou K; (b) os conjugados em K de g1 h1 . . . gn hn ∈ K são da forma gi hi . . . gn hn g1 h1 . . . gi−1 hi−1 ; (c) se G e H têm problema da conjugação decidı́vel, o mesmo acontece com G ∗ H. (8.4) Sejam G1 e G2 grupos. Mostre que o produto direto G1 × G2 é, a menos de isomorfismo, o único grupo H com a seguinte propriedade: existem homomorfismos πi : H → Gi (i = 1, 2) 72 tais que: para todo grupo K e homomorfismos ϕ1 : K → Gi (i = 1, 2), existe um único homomorfismo Φ : K → H tal que o diagrama G1 ` o π1 ϕ1 HO Φ π2 / G2 > ϕ2 K comuta. (8.5) Exprima (Z × Z) ∗ (Z × Z) como um grupo de grafo. (8.6) Mostre que todo grupo de grafo é livre de torsão. [Sugestão: dentro de cada classe de conjugação, trabalhe com o elemento da forma mais conveniente.] 73 9 Grupos hiperbólicos Os grupos hiperbólicos constituem certamente um dos temas mais belos da moderna teoria de grupos, e devem-se a uma ideia revolucionária de Gromov nos anos 80: usar a geometria local do grafo de Cayley para resolver problemas algorı́tmicos. 9.1 Grafos hiperbólicos Seja Γ = (V, E) um grafo conexo. Podemos definir uma métrica d em V do seguinte modo: dados p, q ∈ V , d(p, q) é o comprimento mı́nimo de um caminho ligando p a q em Γ. Um tal caminho diz-se uma geodésica de Γ. Note-se que d está bem definida porque o grafo é conexo, e satisfaz efetivamente os axiomas (M1) – (M4). Diz-se a métrica geodésica de Γ. Dado p ∈ V e W ⊆ V não vazio, escrevemos d(p, W ) = min {d(p, q) | q ∈ W }. Se X ⊆ V ∪ E, escrevemos d(p, X) = d(p, X ∩ V ). Um triângulo geodésico em Γ é um conjunto de 3 geodésicas X : p −− q, Y : q −− r, Z : r −− p formando um triângulo p q r Designamos um tal triângulo geodésico por ∆[XY Z]. Note-se que o triângulo pode ser degenerado, uma vez que um caminho trivial é também uma geodésica. Dada uma constante δ ≥ 0, dizemos que Γ é δ-hiperbólico se, para todo o triângulo geodésico ∆[XY Z] em Γ e todo vértice x em X, se tem d(x, Y ∪ Z) ≤ δ. Dizemos que Γ é hiperbólico se for δ-hiperbólico para algum δ ≥ 0. A designação é inspirada pela natureza dos triângulos no espaço hiperbólico, que têm curvatura negativa: Discutimos em seguida a condição em alguns casos simples. Dado um grafo conexo Γ = (V, E), o seu diâmetro é definido por diam(Γ) = sup{d(p, q) | p, q ∈ V }. 74 Lema 9.1 (i) Se Γ é um grafo conexo finito, então Γ é δ-hiperbólico para δ = diam(Γ). (ii) Se Γ é uma árvore, então Γ é 0-hiperbólico. (iii) Se Γ é o grafo descrito por .. . .. . .. . ... • • • ... ... • • • ... ... • • • ... .. . .. . .. . então Γ não é hiperbólico. Prova. (i) Imediato. (ii) Se ∆[XY Z] é um triângulo geodésico numa árvore Γ, então os vértices de X ocorrem todos em Y ∪ Z. (iii) Vamos identificar os vértices de Gamma com Z × Z da forma óbvia. Para cada n ≥ 1, definimos as geodésicas Xn : (0, 0) −− (0, n), Yn : (0, n) −− (n, n) −− (n, 0), Zn : (n, 0) −− (0, 0) e consideramos o triângulo geodésico ∆[Yn Zn Xn ]. Temos que (n, n) ocorre em Yn e d((n, n), Zn ∪ Xn ) = n. Como n pode ser arbitrariamente grande, concluimos que Γ não é hiperbólico. Vamos agora introduzir o importante conceito de quasi-isometria. Dois espaços métricos (X, d) e (X 0 , d0 ) dizem-se isométricos se existir uma bijeção ϕ : X → X 0 tal que d0 (xϕ, yϕ) = d(x, y) para todos x, y ∈ X. Se aplicarmos este conceito ao espaço dos vértices de um grafo conexo, com a distância geodésica, verificamos facilmente que a isometria corresponde precisamente ao isomorfismo de grafos: se ϕ : V → V 0 é uma bijeção que preserva a distância geodésica, então preserva a relação de adjacência e logo os grafos são isomorfos, e vice-versa. Por isso é muito mais interessante enfraquecer um pouco as exigências. Dois espaços métricos (X, d) e (X 0 , d0 ) dizem-se quase-isométricos se existirem funções ϕ : X → X 0 e ψ : X 0 → X e constantes λ, C ≥ 0 tais que, para todos x, y ∈ X e x0 , y 0 ∈ X 0 . as condições seguintes são verificadas: 75 (Q1) d0 (xϕ, yϕ) ≤ λd(x, y) + C; (Q2) d(x0 ψ, y 0 ψ) ≤ λd0 (x0 , y 0 ) + C; (Q3) d(xϕψ, x) ≤ C; (Q4) d0 (x0 ψϕ, x0 ) ≤ C. Dizemos que dois grafos são quase-isométricos se os respetivos conjuntos de vértices, munidos da distância geodésica, constituem espaços métricos isométricos. Podemos provar o seguinte resultado: Lema 9.2 (i) Todos os grafos conexos de diâmetro finito são quase-isométricos. (ii) Nenhum grafo conexo de diâmetro finito é quase-isométrico a um grafo conexo de diâmetro infinito. Prova. (i) Tomamos C igual ao máximo dos diâmetros dos dois grafos, e λ, ϕ, ψ arbitrários. (ii) Sejam Γ = (V, E), Γ0 = (V 0 , E 0 ) e ϕ : V → V 0 , ψ : V 0 → V funções satisfazendo os axiomas (Q1) – (Q4) para as métricas geodésicas. Suponhamos que Γ tem diâmetro finito M . Para todos x0 , y 0 ∈ V 0 , temos d0 (x0 , y 0 ) ≤ d0 (x0 , x0 ψϕ) + d0 (x0 ψϕ, y 0 ψϕ) + d0 (y 0 ψϕ, y 0 ) ≤ C + λd(x0 ψ, y 0 ψ) + C + C ≤ 3C + λM, logo Γ0 tem diâmetro finito ≤ 3C + λM . O teorema seguinte mostra a robustez do conceito de grafo hiperbólico: Teorema 9.3 Sejam Γ e Γ0 grafos conexos quase-isométricos. Então Γ é hiperbólico se e só se Γ0 é hiperbólico. A demonstração usa argumentos geométricos complexos envolvendo o conceito de quase-geodésica, que não vamos introduzir neste curso. Atenção que as constantes de hiperbolicidade de Γ e Γ0 podem ser muito diferentes! 9.2 Grafos de Cayley hiperbólicos Suponhamos agora que G é um grupo gerado por um subconjunto finito A. O grafo de Cayley e ΓA (G) não é um grafo no sentido formal da palavra, é na realidade um A-grafo (conexo), mas as ideias e os resultados apresentados na subsecção anterior podem ser aplicadas também neste contexto. Como G é o conjunto dos vértices de ΓA (G), podemos em particular definir uma métrica dA e∗ tal que h = gu em G. em G, tal que dA (g, h) é o comprimento da mais curta palavra u ∈ A Dizemosque dA é a métrica geodésica de G (relativamente ao conjunto A de geradores). 76 É fácil verificar que dA (xg, xh) = dA (g, h) para todos g, h, x ∈ G. (17) a Note-se também que, sendo ΓA (G) involutivo (a cada aresta g −→ga corresponde uma aresta ga−→g), a orientação das arestas é irrelevante no cálculo da distância, o que elimina qualquer dúvida sobre a sua simetria... Temos igualmente o conceito de triângulo geodésico e a definição de hiperbolicidade é a mesma. Mas a hiperbolicidade do grafo de Cayley poderá depender do conjunto finito de geradores escolhido? O resultado seguinte mostra que não: a−1 Teorema 9.4 Sejam A e B conjuntos finitos de geradores de um mesmo grupo G. Então os grafos de Cayley ΓA (G) e ΓB (G) são quase-isométricos. Prova. Ambos os grafos têm G como conjunto dos vértices, logo podemos considerar ϕ = ψ = 1G . Fixamos C = 0 e λ = max ({dA (b, 1) | b ∈ B} ∪ {dB (a, 1) | a ∈ A}). É claro que (Q3) e (Q4) são satisfeitos. Sejam g, h ∈ G. Se dA (g, h) = n, então existem a1 , . . . , an ∈ e tais que ga1 . . . an = h. Em virtude de (17), temos dB (ai , 1) = dB (a−1 , 1) e também A i dB (ga1 . . . ai−1 , ga1 . . . ai ) = dB (1, ai ) ≤ λ, logo dB (g, h) ≤ n X dB (ga1 . . . ai−1 , ga1 . . . ai ) ≤ λn = λdA (g, h) i=1 e (Q1) é válido. Por simetria, obtemos também (Q2), logo os dois grafos de Cayley são isométricos. Em consequência, podemos dizer que um grupo finitamente gerado é hiperbólico se ΓA (G) for hiperbólico para algum (qualquer) subconjunto finito A de geradores de G. Teorema 9.5 Seja G um grupo finitamente gerado e seja H um subgrupo de ı́ndice finito de G. Então G é hiperbólico se e só se H é hiperbólico. Prova. Suponhamos que [G : H] = m + 1. Podemos escrever G como uma união disjunta G = Hb0 ∪ Hb1 ∪ . . . ∪ Hbm para alguns b0 , . . . , bm ∈ G. Podemos assumir também que b0 = 1. Seja A = {a1 , . . . , an } um conjunto gerador finito de G. Podemos assumir que A = A ∪ A−1 . Para cada i ∈ {0, . . . , m} e j ∈ {1, . . . , n}, existem wij ∈ H e (i, j)α ∈ {0, . . . , m} únicos tais que bi aj = wij b(i,j)α . Seja W = {wij | i = 0, . . . , m; j = 1, . . . , n}. 77 Seja h ∈ H. Como h ∈ G = hAi, existem i1 , . . . , ik ∈ {1, . . . , n} tais que h = ai1 . . . aik . Seja r0 = 0.Para j = 1, . . . , k, seja rj = (rj−1 , ij )α. Daqui resulta que h = b0 h = br0 ai1 . . . aik = wr0 i1 br1 ai2 . . . aik = wr0 i1 wr1 i2 br2 ai3 . . . aik = . . . = wr0 i1 . . . wrk−1 ik brk . Como h ∈ H, obtemos rk = 0, logo h ∈ hW i e portanto W é um conjunto finito de geradores de H. Além disso, dW (h, 1) ≤ dA (h, 1). (18) Seja B = W ∪ {b1 , . . . , bm }. Então B é também um conjunto finito de geradores de G, e resulta da demonstração do Teorema 9.4 que dA (h, h0 ) ≤ λdB (h, h0 ) para todos h, h0 ∈ H, (19) onde λ = max ({dA (b, 1) | b ∈ B} ∪ {dB (a, 1) | a ∈ A}). Podemos assumir que G é não trivial, logo λ ≥ 1. Seja ϕ : H → G a inclusão e seja ψ : G → H definida por (hbi )ψ = h. Vamos mostrar que ΓA (G) e ΓW (H) são quase-isométricos verificando que os axiomas (Q1) – (Q4) são satisfeitos para C = 2λ. Sejam h, h0 ∈ H e i, j ∈ {0, . . . , m}. Então (19) e W ⊆ B implicam dA (hϕ, h0 ϕ) = dA (h, h0 ) ≤ λdB (h, h0 ) ≤ λdW (h, h0 ) ≤ λdW (h, h0 ) + C. Por outro lado, dW (hϕψ, h) = dW (h, h) = 0 ≤ C, logo (Q1) e (Q3) são válidos. Temos também, graças a (18) e (17), dW ((hbi )ψ, (h0 bj )ψ) = dW (h, h0 ) ≤ dA (h, h0 ) ≤ dA (h, hbi ) + dA (hbi , h0 bj ) + dA (h0 bj , h0 ) = dA (1, bi ) + dA (hbi , h0 bj ) + dA (bj , 1) ≤ λdA (hbi , h0 bj ) + C, e dA ((hbi )ψϕ, hbi ) = dA (h, hbi ) = dA (1, bi ) ≤ λ < C, logo (Q2) e (Q4) são válidos. Concluimos assim que ΓA (G) e ΓW (H) são quase-isométricos e aplicamos o Teorema 9.3. Podemos clarificar agora a questão da hiperbolicidade para várias classes de grupos. Um grupo diz-se virtualmente livre se tiver um subgrupo livre de ı́ndice finito. Por exemplo, Fn × G é virtualmente livre para todo n ≥ 1 e todo grupo finito G. Teorema 9.6 (i) Os grupos finitos são hiperbólicos. (ii) Os grupos livres de dimensão finita são hiperbólicos. (iii) Os grupos virtualmente livres finitamente gerados são hiperbólicos. 78 (iv) O grupo abeliano livre Z × Z não é hiperbólico. Prova. (i) Pelo Lema 9.1(i). (ii) Pelo Lema 9.1(ii). (iii) Pela alı́nea (ii) e pelo Teorema 9.5. (iv) Pelo Lema 9.1(iii). Uma outra classe importante de grupos hiperbólicos é a dos grupos fundamentais de variedades riemannianas compactas com curvatura negativa. Foi esta classe de grupos que motivou Gromov a criar o conceito de grupo hiperbólico. 9.3 Propriedades Num dos resultados mais extraordinários da teoria dos grupos hiperbólicos, geometria e complexidade se encontram de forma inesperada: Teorema 9.7 (Gromov 1987) Seja G um grupo finitamente apresentável. Então as condições seguintes são equivalentes: (i) G é hiperbólico; (ii) G admite uma função isoperimétrica linear; (iii) G admite uma função isoperimétrica subquadrática. Aqui subquadrática significa “melhor que quadrática”! Pelo Corolário 7.10, concluimos que todo grupo hiperbólico finitamente apresentável tem problema da palavra decidı́vel. Veremos na Secção 10 que todo grupo hiperbólico é automático e logo finitamente apresentável, bem como uma solução mais construtiva do problema da palavra. Seja G um grupo hiperbólico gerado pelo conjunto finito A. Isto equivale a considerar um e∗ → G. Designamos por GeoA (G) o conjunto dos homomorfismo involutivo sobrejetivo ϕ : A rótulos de geodésicas em ΓA (G). Note-se que, como ΓA (G) é transitivo nos vértices, todas estas palavras são rótulo de geodésicas iniciando em qualquer vértice. É habitual chamar também de geodésicas as palavras de GeoA (G). e∗ e ε > 0, dizemos que L é ε-lipschitziana (relativamente a ΓA (G)) se, para todas Dados L ⊆ A u, v ∈ L, dA (uϕ, vϕ) ≤ 1 implica dA (u[n] ϕ, v [n] ϕ) ≤ ε para todo n ∈ N. Esta propriedade é também conhecida como a propriedade dos dois viajantes: imaginemos dois viajantes que, partindo do mesmo sı́tio, vão percorrer dois caminhos em ΓA (G) com rótulos u e v, respetivamente. O ritmo é uma aresta por dia! Se eles terminarem seus caminhos a distância ≤ 1, então em cada dia da viagem eles nunca estarão a distância > ε. Dizemos que L é lipschitziana se for ε-lipschitziana para algum ε > 0. 79 e∗ → G um homomorfismo involutivo Teorema 9.8 Seja G um grupo hiperbólico e seja ϕ : A sobrejetivo com A finito. Suponhamos que ΓA (G) é δ-hiperbólico. Então GeoA (G) é (2δ + 2)lipschitziana. Prova. Consideremos um triângulo geodésico 5p u q0 w / q v com |w| ≤ 1 em ΓA (G). Temos que mostrar que dA (u[n] ϕ, v [n] ϕ) ≤ 2δ + 2 para todo n ∈ N. Consideremos as geodésicas no diagrama fatorizadas na forma u[n] v [n] u n q0 −−→pn −→p, v n q0 −−→qn −→q. v w−1 Suponhamos que vn = 1. Como |u| ≤ |v| + 1 (caso contrário q0 −→q −→p seria uma alternativa u mais curta a q0 −→p, absurdo), resulta que dA (u[n] ϕ, uπ) ≤ 1 e logo dA (u[n] ϕ, v [n] ϕ) = dA (u[n] ϕ, vϕ) ≤ dA (u[n] ϕ, uϕ) + dA (uϕ, vϕ) ≤ 2 ≤ 2δ + 2. O caso un = 1 é análogo, logo podemos assumir que un , vn 6= 1. Como ΓA (G) é δ-hiperbólico, z existe algum m ≤ |u| tal que dA (v [n] π, u[m] ) ≤ δ + 1. Logo existe um caminho qn −→pm com |z| ≤ δ + 1. Suponhamos que m > n + δ + 1. Então v [n] z q0 −−→qn −→pm u[m] é uma alternativa mais curta à geodésica q0 −−→pm pois |v [n] | + |z| ≤ n + δ + 1 < m = |u[m] |. Por outro lado, se m < n − δ − 1, então z −1 u[m] q0 −−→pm −−→qn v [n] é uma alternativa mais curta à geodésica q0 −−→qn . Logo |m − n| ≤ δ + 1, pelo que dA (u[n] ϕ, v [n] ϕ) ≤ dA (u[n] ϕ, u[m] ϕ) + dA (u[m] ϕ, v [n] ϕ) ≤ 2δ + 2 e GeoA (G) é (2δ + 2)-lipschitziana. 80 O resultado seguinte mostra que o conjunto das geodésicas dum grupo hiperbólico tem uma estrutura simples: e∗ → G um homomorfismo involutivo Teorema 9.9 Seja G um grupo hiperbólico e seja ϕ : A sobrejetivo com A finito. Então GeoA (G) é uma linguagem racional. Prova. Suponhamos que ΓA (G) é δ-hiperbólico e seja ε = 2δ + 2. Consideremos a bola aberta B = Bε (1) no espaço métrico (G, dA ). Como A é finito, B é finita. Além disso, 1 ∈ B. Definimos e um A-autômato finito A = (Q, {1}, Q, E) por: Q = {X ⊆ B | 1 ∈ X}; e ∪ {1})) ∩ B) | X ∈ Q, a ∈ A e \ (Xϕ−1 )}. E = {(X, a, ((a−1 ϕ)X(Aϕ e ∪ {1}), logo E ⊆ Q × A e × Q e A está bem definido. Note-se que 1 ∈ X implica 1 ∈ (a−1 ϕ)X(Aϕ Além disso, A é determinı́stico. Vamos mostrar que L(A) = GeoA (G). Começamos por mostrar que u e ∪ {1})|u| . se {1}−→X é um caminho em A, então X ⊆ (u−1 ϕ)(Aϕ (20) Usamos indução sobre |u|. O caso u = 1 é trivial. Suponhamos que (20) é válido para u e que u a e Então {1}−→X −→X 0 é um caminho em A com a ∈ A. e ∪ {1}) ⊆ (a−1 ϕ)(u−1 ϕ)(Aϕ e ∪ {1})|u| (Aϕ e ∪ {1}) = (ua)−1 ϕ(Aϕ e ∪ {1})|ua| X 0 ⊆ (a−1 ϕ)X(Aϕ e por indução (20) é válido para todo u. Seja u ∈ GeoA (G). Vamos mostrar que u ∈ L(A) por indução sobre |u|. O caso |u| = 0 é trivial, logo assumimos que |u| > 0 e que a implicação é válida para palavras mais curtas. Seja u = va com v e Como v ∈ GeoA (G), existe um caminho {1}−→X a ∈ A. em A pela hipótese de indução. Temos a que mostrar que existe uma aresta da forma X −→X 0 em A, e para isso basta que aϕ ∈ / X. Suponhamos que aϕ ∈ X. Por (20), temos e ∪ {1})|v| , X ⊆ (v −1 ϕ)(Aϕ logo aϕ = (v −1 ϕ)(wϕ) para alguma palavra w tal que |w| ≤ |v|. Logo uϕ = (va)ϕ = wϕ com |w| < |u|, contradizendo u ∈ GeoA (G). Logo aϕ ∈ / X e portanto u ∈ L(A). Logo GeoA (G) ⊆ L(A). Suponhamos que GeoA (G) ⊂ L(A). Seja u ∈ L(A) \ GeoA (G) de comprimento mı́nimo. Como e Logo v ∈ GeoA (G) por minimalidade 1 ∈ GeoA (G), podemos escrever u = va para alguma a ∈ A. w de u. Como u ∈ / GeoA (G), existe algum caminho 1−→uϕ em ΓA (G) com |w| < |u|. Logo 5 vϕ v 1 w a / uϕ é um triângulo geodésico em ΓA (G). Note-se que |w| = |v| ou |w| = |v| − 1 pois qualquer outra hipótese contradiz |w| < |u| ou v ∈ GeoA (G). 81 v [i] Como v ∈ GeoA (G) ⊆ L(A), existe em A um caminho {1}−−→Xi para i = 0, . . . , |v|. Vamos usar indução sobre i para mostrar que ((v [i] )−1 w[i] )ϕ ∈ Xi (21) para i = 0, . . . , |v|. O caso i = 0 é trivial, logo assumimos que 0 < i ≤ |v| e que (21) é válido para e ∪ {1})) ∩ B, logo i − 1. Seja v [i] = v [i−1] c. Como (Xi−1 , c, Xi ) ∈ E, temos Xi = ((c−1 ϕ)Xi−1 (Aϕ [i−1] −1 [i−1] ((v ) w )ϕ ∈ Xi−1 implica e ∪ {1}) ⊆ (c−1 ϕ)Xi−1 (Aϕ e ∪ {1}). ((v [i] )−1 w[i] )ϕ ∈ (c−1 (v [i−1] )−1 w[i−1] )ϕ(Aϕ Por outro lado, dA (((v [i] )−1 w[i] )ϕ, 1) = dA (w[i] ϕ, v [i] ϕ) ≤ ε pois GeoA (G) é ε-lipschitziana pelo Teorema 9.8. Logo ((v [i] )−1 w[i] )ϕ ∈ B e portanto e ∪ {1})) ∩ B = Xi , ((v [i] )−1 w[i] )ϕ ∈ ((b−1 ϕ)Xi−1 (Aϕ provando (21). Em particular, para i = |v|, obtemos (v −1 w)ϕ ∈ X|v| . Como u = va e uϕ = wϕ, obtemos aϕ = a v (v −1 w)ϕ ∈ X|v| , pelo que não existe nenhuma aresta da forma X|v| −→ . . . em A. Como {1}−→X|v| é um caminho em A e A é determinı́stico, isto contradiz u ∈ L(A). Logo L(A) = GeoA (G) e portanto GeoA (G) é uma linguagem racional. Note-se que, mesmo em casos muito simples, GeoA (G) de modo algum determina G. Por exemplo, se considerarmos o gerador canónico a para os grupos cı́clicos C2 e C3 , com grafos de Cayley ?• a •j a *• a •o a a • obtemos Geoa (C2 ) = {1, a, a−1 } = Geoa (C3 ). 9.4 Exercı́cios (9.1) Mostre que o grafo ... • • • • ... ... • • • • ... ... • • • • ... é 2-hiperbólico. 82 (9.2) Considere o grafo do exercı́cio (9.1) e os grafos • • • • .. . .. . .. . .. . ... • • • • ... ... • • • • ... ... • • • • ... .. . .. . .. . .. . ... ... e Quais destes grafos são quase-isométricos? (9.3) Sejam H um grupo hiperbólico e F um grupo finito. Mostre que H × F é hiperbólico. (9.4) Sejam A = {a, b} e D4 o grupo diedral infinito definido pela apresentação hA | a4 , b2 , bab−1 ai. (a) Construa o grafo de Cayley ΓA (D4 ). (b) Calcule GeoA (D4 ). (9.5) Sejam A = {a, b} e G o grupo fundamental da garrafa de Klein, definido pela apresentação hA | bab−1 ai. (a) Construa o grafo de Cayley ΓA (G). (b) Mostre que G não é hiperbólico. (9.6) Mostre que o grupo C2 ∗ C2 é virtualmente livre. [Sugestão: Considere o subgrupo cı́clico gerado pelo produto ab, onde a (respetivamente b) gera o primeiro (respetivamente segundo) C2 .] (9.7) Mostre que Iso(n) = C2 ∗ C2 . n 2 define uma função isoperimétrica para a apresentação ha, b | a2 , b2 i de (9.8) Seja A = {a, b} o conjunto canónico de geradores de G = Z × Z e considere a linguagem racional [ L= (aδ bε )∗ ((aδ )∗ ∪ (bε )∗ ). δ,ε=±1 Mostre que: 83 (a) L ⊆ GeoA (G); u (b) dado g ∈ G, existe um e um só caminho em ΓA (G) da forma 1−→g (u ∈ L); (c) L é 2-lipschitziana (relativamente a ΓA (G)). 84 10 Grupos automáticos Os grupos automáticos foram oficialmente introduzidos por Cannon, Epstein, Holt, Levy, Paterson e Thurston num livro publicado em 1992! Esta teoria procura descrever a estrutura de um grupo utilizando autômatos finitos, e admite também uma abordagem geométrica que generaliza num certo sentido a teoria dos grupos hiperbólicos. 10.1 Estruturas automáticas Seja A um alfabeto finito e seja ϕ : A∗ → G um homomorfismo sobrejetivo. Isto equivale a dizer que A pode ser visto como um conjunto que gera G enquanto monóide. Uma linguagem L ⊆ A∗ diz-se uma secção de ϕ se Lϕ = G. Se ϕ|L : L → G é bijetiva, L diz-se uma transversal de ϕ. Naturalmente, uma secção não determina a estrutura do grupo. Mas podemos complementar essa informação do modo que passamos a descrever. Dada w ∈ A∗ , estamos interessados em exprimir a relação {(u, v) ∈ L × L | vϕ = (uw)ϕ} sob a forma de uma linguagem. Como proceder? Uma forma simples de o conseguir é usando a convolução. Seja $ um sı́mbolo que assumimos não pertencer a A. Definimos o alfabeto A$ = (A × A) ∪ (A × {$}) ∪ ({$} × A). Dadas u, v ∈ A∗ , a convolução u v é a (única) palavra de A∗$ cuja projeção na primeira (respetivamente segunda) componente pertence a u$∗ (respetivamente v$∗ ). Por exemplo, ab bc = (a, b)(b, c), ab b = (a, b)(b, $), 1 bc = ($, b)($, c). Por outras palavras, as palavras u e v são alinhadas à esquerda para produzir uma palavra de A∗$ e o sı́mbolo $ é usado para compensar a possı́vel diferença de comprimento entre u e v. Para todo w ∈ A∗ , definimos então Lw = {u v | u, v ∈ L, vϕ = (uw)ϕ} ⊆ A∗$ . Dizemos que L ⊆ A∗ é uma estrutura automática para ϕ : A∗ → G se: (E1) L é uma secção racional de ϕ; (E2) La é racional para todo a ∈ A ∪ {1}. Se substituirmos (E1) pela condição mais forte (E1’) L é uma transversal racional de ϕ, 85 dizemos que L é uma estrutura automática com unicidade para ϕ. Logo uma estrutura automática envolve uma coleção (finita) de |A| + 2 autômatos finitos. Se a estrutura tiver unicidade, podemos prescindir do autômato reconhecendo L1 , pois este autômato pode ser facilmente obtido a partir do autômato reconhecendo L substituindo cada rótulo a ∈ A por (a, a). Vamos ver em seguida que a existência de uma estrutura automática implica a existência de uma estrutura automática com unicidade. Mas antes precisamos de introduzir a chamada ordem lexicográfica: Seja A um alfabeto finito que supomos totalmente ordenado por <. Definimos uma relação <l em A∗ do seguinte modo: dados u, v ∈ A∗ , |u| < |v| ou u <l v se |u| = |v| e u = wau0 , v = wbv 0 com a, b ∈ A e a < b É fácil verificar que esta relação é transitiva e tricotômica (isto é, dados u, v ∈ A∗ , ocorre precisamente um dos casos u = v, u <l v ou v <l u). Logo <l é uma ordem total. Como qualquer subconjunto não vazio tem necessariamente um mı́nimo, <l é uma boa ordem. Lema 10.1 Seja A um alfabeto finito totalmente ordenado e seja Ol = {u v | u, v ∈ A∗ , u <l v}. Então Ol é uma linguagem racional. Prova. Seja ∆ = {(a, a) | a ∈ A} e P = {(a, b) ∈ A × A | a <l b}. Verifica-se facilmente que Ol = (A × A)∗ ({$} × A)+ ∪ ∆∗ P (A × A)∗ , logo Ol é racional pelo Teorema 2.8. Necessitamos também provar o seguinte lema: Lema 10.2 Sejam K, L A-linguagens racionais. Então K L = {u v | u ∈ K, v ∈ L} é uma A$ -linguagem racional. Prova. Seja π1 : A∗$ → A∗ o homomorfismo definido por (a, b)π1 = a 1 86 se a ∈ A se a = $ Analogamente definimos o homomorfismo π2 : A∗$ → A∗ considerando a segunda componente. Temos A∗ A∗ = (A × A)∗ ((A × {$})∗ ∪ ({$} × A)∗ ), logo A∗ A∗ é racional. Como K L = Kπ1−1 ∩ Lπ2−1 ∩ (A∗ A∗ ), resulta das Proposições 2.5 e 2.9(ii) que K L é racional. Podemos agora provar o resultado anunciado: Proposição 10.3 Sejam A um alfabeto finito, G um grupo e ϕ : A∗ → G um homomorfismo sobrejetivo. Se existir uma estrutura automática para ϕ, então existe uma estrutura automática com unicidade para ϕ. Prova. Seja L uma estrutura automática para ϕ. Para cada g ∈ G, seja wg o mı́nimo de L ∩ gϕ−1 para a ordem lexicográfica. Definimos W = {wg | g ∈ G}. Vamos mostrar que W é uma estrutura automática com unicidade para ϕ. Seja π2 : A∗$ → A∗ o homomorfismo definido na prova do Lema 10.2. Então (L1 ∩ Ol )π2 é o conjunto de todas as palavras v ∈ L que admitem uma representação alternativa u <l v, logo W = L \ (L1 ∩ Ol )π2 . Como L é uma estrutura automática para ϕ, resulta das Proposições 2.5 e 2.9(i) e do Lema 10.1 que (L1 ∩ Ol )π2 é uma A-linguagem racional. Mas então W = L ∩ (A∗ \ (L1 ∩ Ol )π2 ), e resulta da Proposição 2.5 que W é racional. Resulta da construção de W que W é uma transversal de ϕ. Seja a ∈ A. Temos Wa = {u v | u, v ∈ W, vϕ = (ua)ϕ} = La ∩ (W W ). Pelo Lema 10.2, Wa é racional e logo W é uma estrutura automática com unicidade para ϕ. Tal como em casos anteriores, é possı́vel mostrar que a existência de uma estrutura automática não depende do conjunto de geradores: Teorema 10.4 Seja G um grupo admitindo uma estrutura automática para o homomorfismo sobrejetivo ϕ : A∗ → G, onde A é um alfabeto finito. Seja ψ : B ∗ → G um outro homomorfismo sobrejetivo, onde B é um alfabeto finito. Então G admite uma estrutura automática para ψ. A prova é bastante técnica e não será apresentada aqui. 87 10.2 Caraterização geométrica A parte mais técnica da manipulação dos grupos automáticos envolve naturalmente as linguagens La ⊆ A∗$ . Isso pode ser evitado recorrendo ao grafo de Cayley ΓA (G), através da métrica dA e do conceito de linguagem lipschitziana definida na Subsecção 9.3: Teorema 10.5 Sejam A um alfabeto finito, G um grupo e ϕ : A∗ → G um homomorfismo sobrejetivo. Seja L ⊆ A∗ uma secção racional de ϕ. Então as condições seguintes são equivalentes: (i) L é uma estrutura automática para ϕ; (ii) L é lipschitziana. Prova. (i) ⇒ (ii). Para cada a ∈ A ∪ {1}, seja Aa um A$ -autômato finito reconhecendo La . Seja K o maior número de vértices existente nalgum destes autômatos. Vamos mostrar que L é (2K − 1)-lipschitziana. e Sejam u, v ∈ L tais que dA (uϕ, vϕ) ≤ 1. No grafo de Cayley as arestas têm rótulos em A, mas podemos afirmar que existe a ∈ A tal que vϕ = (ua)ϕ ou uϕ = (va)ϕ. Trocando u com v se necessário, podemos assumir que vϕ = (ua)ϕ, logo u v ∈ La . Logo existe em Aa um caminho bem-sucedido da forma uv → q0 −−−→t → (22) Seja n ∈ N e seja w = u[n] v [n] . Podemos fatorizar (22) como w0 w → q0 −→q −→t → z Seja q −→t uma geodésica de Aa . Então |z| ≤ K − 1. Como z é sufixo de uma palavra em L(Aa ) = La , podemos escrever z = z1 z2 para alguns z1 , z2 ∈ A∗ . Considerando o caminho bem-sucedido w z → q0 −→q −→t → em Aa , resulta facilmente que wz é necessariamente da forma (u[n] z1 ) (v [n] z2 ), logo (u[n] z1 a)ϕ = (v [n] z2 )ϕ e portanto dA (u[n] ϕ, v [n] ϕ) ≤ |z1 az2−1 | ≤ 2K − 1. Logo L é (2K − 1)-lipschitziana. (ii) ⇒ (i). Podemos assumir que L é ε-lipschitziana com ε ≥ 1. Definimos • Q = {g ∈ G | dA (g, 1) ≤ ε}, • E = {(p, x, q) ∈ Q × A$ × Q | q = (xπ1 ϕ)−1 p(xπ2 ϕ)}. Seja a ∈ A e consideremos o A$ -autômato finito (determinı́stico) Aa = (Q, 1, aϕ, E). Vamos mostrar que La = L(Aa ) ∩ (L L). (23) 88 Seja w ∈ La . Então w = u v para alguns u, v ∈ L tais que vϕ = (ua)ϕ, logo w ∈ L L. Para 0 ≤ n ≤ max {|u|, |v|}, seja un a n-ésima letra de u (se n ≤ |u|) ou 1 (se n > |u|). Analogamente, definimos vn . Sejam qn = (u[n] ϕ)−1 (v [n] ϕ) e xn = un vn . Vamos mostrar que x x x 1 2 n q0 −→q 1 −→ . . . −→qn (24) é um caminho em Aa . Como L é ε-lipschitziana, temos qk ∈ Q para todo k. Além disso, se 1 ≤ k ≤ n, então qk = (u[k] ϕ)−1 (v [k] ϕ) = (uk ϕ)−1 (u[k−1] ϕ)−1 (v [k−1] ϕ)(vk ϕ) = (xk π1 ϕ)−1 qk−1 (xk π2 ϕ), logo (qk−1 , xk , qk ) ∈ E e portanto (24) é um caminho em Aa . Como q0 = 1 e qn = (uϕ)−1 (vϕ) = aϕ, resulta que (24) é bem-sucedido e logo x1 x2 . . . xn ∈ L(Aa ), isto é w = u v = x1 x2 . . . xn ∈ L(Aa ). Logo La ⊆ L(Aa ) ∩ (L L). Reciprocamente, seja x ∈ L(Aa ) ∩ (L L). Então temos x = u v para alguns u, v ∈ L e x é o rótulo de um caminho bem-sucedido em Aa da forma (24). Como qk = (xk π1 ϕ)−1 qk−1 (xk π2 ϕ) para k = 1, . . . , n, obtemos aϕ = qn = (xn π1 ϕ)−1 . . . (x1 π1 ϕ)−1 q0 (x1 π2 ϕ) . . . (xn π2 ϕ) = (xπ1 ϕ)−1 (xπ2 ϕ) = (uϕ)−1 (vϕ) e logo (ua)ϕ = vϕ. Resulta que x = u v ∈ La e logo (23) é válido. Pela Proposição 2.5 e pelo Lema 10.2, La é racional e logo L é uma estrutura automática para ϕ. Corolário 10.6 Todo grupo hiperbólico é automático. Prova. Seja G um grupo hiperbólico. Como G é finitamente gerado, podemos tomar um homomorfismo sobrejetivo de monóides ϕ : A∗ → G para algum alfabeto finito A. Podemos estender ϕ e∗ → G, que designamos também por ϕ. a um homomorfismo involutivo (sobrejetivo) A Pelo Teorema 9.9, GeoA (G) é racional, e é obviamente uma secção de ϕ. Por outro lado, o Teorema 9.8 implica que GeoA (G) é lipschitziana. Logo, pelo Teorema 10.5, GeoA (G) é uma estrutura automática para ϕ e portanto G é automático. Usaremos o Teorema 10.5 para provar a existência de grupos automáticos não hiperbólicos. Começamos pelo seguinte lema: Lema 10.7 Sejam A um alfabeto finito, G um grupo e ϕ : A∗ → G um homomorfismo sobrejetivo. Seja L uma estrutura automática com unicidade para ϕ. Então existe K > 0 tal que |u| − |v| ≤ KdA (uϕ, vϕ) para todos u, v ∈ L. 89 Prova. Para cada a ∈ A, seja Aa um A$ -autômato finito reconhecendo La . Seja K o maior número de vértices existente nalgum destes autômatos. Sejam u, v ∈ L. O caso dA (uϕ, vϕ) = 0 é trivial pois a estrutura tem unicidade. Suponhamos que dA (uϕ, vϕ) = 1. Trocando u e v se necessário, podemos assumir que vϕ = (ua)ϕ para algum a ∈ A. Logo u v ∈ L(Aa ). Suponhamos que |v| > |u| + K. Seja v = v 0 v 00 com |v 0 | = |u|. Então temos em Aa um caminho bem-sucedido da forma uv 0 1v 00 → i−−−→q −−−→t → 1v 00 Como |v 00 | > K, existe algum vértice repetido no caminho q −−−→t. Logo podemos eliminar um loop e obter u w ∈ L(Aa ) = La para algum w ∈ L \ {v}. Mas então wϕ = (ua)ϕ = vϕ, contradizendo a unicidade da estrutura. Analogamente se exclui o caso |u| > |v| + K, logo |u| − |v| ≤ K e o resultado é válido quando dA (uϕ, vϕ) = 1. Finalmente, suponhamos que dA (uϕ, vϕ) = n > 1. Então existe uma sucessão w0 , w1 , . . . , wn ∈ L tal que w0 = u, wn = v e dA (wi−1 ϕ, wi ϕ) = 1 para i = 1, . . . , n. Pelo caso anterior, temos |wi−1 | − |wi | ≤ K para i = 1, . . . , n. Pela desigualdade triangular, obtemos n n X X |wi−1 | − |wi | ≤ Kn = KdA (uϕ, vϕ) |u| − |v| = |wi−1 | − |wi | ≤ i=1 i=1 como pretendı́amos. Vamos agora discutir o produto direto: Proposição 10.8 O produto direto de grupos automáticos é um grupo automático. Prova. Para i = 1, 2, seja Li uma estrutura automática com unicidade para o homomorfismo sobrejetivo ϕi : A∗i → Gi , onde Ai é um alfabeto finito e Gi um grupo. Podemos assumir que A1 ∩ A2 = ∅. Seja A = A1 ∪ A2 e ϕ : A∗ → G1 × G2 o homomorfismo (sobrejetivo) definido por ϕ|A∗i = ϕi (i = 1, 2). Vamos mostrar que L1 L2 é uma estrutura automática para ϕ. Pela Proposição 2.7, L1 L2 é racional, e é claro que L1 L2 é uma transversal de ϕ. Logo, pelo Teorema 10.5, basta mostrar que L1 L2 é lipschitziana. Suponhamos que Li é εi -lipschitziana (i = 1, 2) e que K é a constante dada pelo Lema 10.7 para ϕ1 e L1 . Seja ε = max {ε1 + K + 1, ε2 }. Vamos mostrar que L1 L2 é ε-lipschitziana. Sejam ui , vi ∈ Li (i = 1, 2) com dA ((u1 u2 )ϕ, (v1 v2 )ϕ) ≤ 1. Se (u1 u2 )ϕ = (v1 v2 )ϕ, então u1 = v1 e u2 = v2 pois Li é uma estrutura automática com unicidade para i = 1, 2, logo podemos assumir sem perda de generalidade que (v1 v2 )ϕ = (u1 u2 a)ϕ para algum a ∈ A. Suponhamos primeiro que a ∈ A2 . Então (v1 v2 )ϕ = (u1 u2 a)ϕ implica v1 ϕ1 = u1 ϕ1 e v2 ϕ2 = (u2 a)ϕ2 , logo v1 = u1 e u2 v2 ∈ (L2 )a . Logo ( 0 se n ≤ |u1 | [n] [n] dA (((u1 u2 ) )ϕ, ((v1 v2 ) )ϕ) = [n−|u1 |] [n−|u1 |] dA (u2 ϕ, v2 ϕ) ≤ ε2 ≤ ε se n > |u1 | 90 Suponhamos agora que a ∈ A1 . Então (v1 v2 )ϕ = (u1 u2 a)ϕ implica v1 ϕ1 = (u1 a)ϕ1 e v2 ϕ2 = u2 ϕ2 , logo u1 v1 ∈ (L1 )a e v2 = u2 . Temos pois a seguinte situação no grafo de Cayley ΓA (G1 ×G2 ): u2 5• /• u1 • a v1 ··· a ) • a /• v2 =u2 a Se n ≤ |u1 |, |v1 |, então [n] [n] dA (((u1 u2 )[n] )ϕ, ((v1 v2 )[n] )ϕ) = dA (u1 ϕ, v1 ϕ) ≤ ε1 ≤ ε. Por outro lado, se n ≥ |u1 |, |v1 |, então [n−|u |] [n−|v1 |] 1 dA (((u1 u2 )[n] )ϕ, ((v1 v2 )[n] )ϕ) = dA ((u1 u2 )ϕ, (v1 v2 pois |u1 | − |v1 | ≤ K por definição de K e pela figura anterior. Suponhamos agora que |v1 | < n < |u1 |. Então dA (((u1 u2 )[n] )ϕ, ((v1 v2 )[n] )ϕ) = ≤ ≤ < < [n] )ϕ) ≤ K + 1 [n−|v |] 1 dA (u1 ϕ, (v1 v2 )ϕ) [n] [n−|v1 |] dA (u1 ϕ, v1 ϕ) + dA (v1 ϕ, (v1 v2 )ϕ) [n] [n] dA (u1 ϕ, v1 ϕ) + n − |v1 | ε1 + |u1 | − |v1 | ε1 + K < ε. O caso |u1 | < n < |v1 |, é análogo, logo L1 L2 é ε-lipschitziana e G1 × G2 é automático. Corolário 10.9 Todo grupo abeliano livre finitamente gerado Z × . . . × Z é automático. Prova. O grupo livre Z é automático pelo Teorema 9.6 e pelo Corolário 10.6. Aplicando sucessivamente a Proposição 10.8, obtemos o pretendido. Pelo Teorema 9.6(iv), comprovamos que a classe dos grupos automáticos contém estritamente a dos grupos hiperbólicos. 10.3 Propriedades Terminamos estudando algumas propriedades dos grupos automáticos. Começamos pelo problema da palavra: Teorema 10.10 Todo grupo automático tem problema da palavra decidı́vel. 91 Prova. Seja G um grupo e seja L uma estrutura automática para o homomorfismo sobrejetivo e∗ → G, ϕ : A∗ → G, onde A é finito. Estendemos ϕ a um homomorfismo involutivo (sobrejetivo) A ∗ e que designamos ainda por ϕ. Queremos mostrar que é decidı́vel, dado u ∈ A , se uϕ = 1. Suponhamos primeiro que u ∈ A∗ , digamos u = a1 . . . an (ai ∈ A). Tomamos v0 ∈ L qualquer. Para i = 1, . . . , n, determinamos vi ∈ L ∩ (ua1 . . . ai )ϕϕ−1 do seguinte modo: Suponhamos que vi−1 está definido. Usando os homomorfismos πi : A∗$ → A∗ definidos na prova do Lema 10.2, basta tomar vi ∈ (Lai ∩ vi−1 π1−1 )π2 . Pelas Proposições 2.5 e 2.9, (Lai ∩ vi−1 π1−1 )π2 é uma linguagem racional e nós podemos calcular efetivamente um dos seus elementos. Em particular, calculámos vn ∈ L∩(v0 u)ϕ−1 . Agora, para determinar se uϕ = 1, basta verificar se v0 vn ∈ L1 ou não. Para provar o caso geral, temos que saber lidar com letras da forma a−1 (a ∈ A). Para começar, podemos utilizar o caso anterior para determinar w1 ∈ L ∩ 1ϕ−1 : se for necessário, testamos todas as palavras u ∈ L (que é bem ordenado pela ordem lexicográfica) até encontrar a desejada. Agora e∗ é fácil encontrar wa−1 ∈ L ∩ a−1 ϕϕ−1 : basta tomar wa−1 ∈ (Lai ∩ w1 π2−1 )π1 . Assim, dada u ∈ A −1 qualquer, começamos por substituir cada letra a (a ∈ A) em u por wa−1 , obtendo assim uma palavra u0 ∈ A∗ . Como uϕ = u0 ϕ, basta usar o caso anterior para determinar se u0 ϕ = 1. Vamos agora usar a caraterização geométrica para provar o seguinte resultado. A prova é longa e por vezes técnica, mas interessante: Teorema 10.11 Todo grupo automático: (i) é finitamente apresentável; (ii) admite uma função isoperimétrica quadrática. Prova. (i) Seja G um grupo e seja L uma estrutura automática com unicidade para o homomorfismo sobrejetivo ϕ : A∗ → G, onde A é finito. Estendemos ϕ a um homomorfismo involutivo e∗ → G, que designamos ainda por ϕ. Então existe um homomorfismo sobrejetivo (sobrejetivo) A Φ : FA → G tal que o diagrama e∗ ϕ / G A > θ Φ FA e∗ → FA designa a projeção canónica. Para cada g ∈ G, seja wg o único elemento comuta, onde θ : A de L ∩ gϕ−1 . Pelo Teorema 10.5, L é ε-lipschitziana para algum ε > 0. Seja R = {u ∈ 1ϕ−1 |u| ≤ 2ε + 2} ∪ {w1 } e N = hhRθii. É claro que Rθ é um subconjunto finito de Ker(Φ), logo N ⊆ Ker(Φ). Para mostrar que P = hA | Ri é uma apresentação finita de G, basta mostrar que KerΦ ⊆ N . 92 Começamos por fazer um esboço da prova de que u v ∈ La ⇒ (uav −1 )θ ∈ N (25) para todos u, v ∈ L e a ∈ A. zn [n] Seja m = max {|u|, |v|}. Para cada n ∈ {1, . . . , m}, seja u[n] ϕ−→v ϕ uma geodésica em ΓA (G). u v É claro que |zn | ≤ ε para todo n. Usando estas geodésicas e os caminhos 1−→uϕ e 1−→vϕ, podemos construir um diagrama de van Kampen (generalizado) de P de bordo uav −1 . Este diagrama diz-se generalizado porque os relatores de Rθ não são necessariamente palavras ciclicamente reduzidas, e o mesmo acontece com o bordo. Mas a sua existência garante igualmente que a imagem do bordo por θ está em N . Exemplificamos a construção do diagrama para u = a1 a2 a3 e v = b1 b2 b3 b4 : a2 @• a1 1 b1 z1 /• a3 /• z2 b2 /• / uϕ z3 b3 /• z4 b4 ! / vϕ Em geral, cada um dos diagramas interiores tem como bordo uma palavra que é rótulo de um loop em ΓA (G) e tem comprimento ≤ 2ε + 2, logo pertence a R. Logo (25) é válido. Em seguida mostramos que −1 (uwuϕ )θ ∈ N (26) e∗ . Usamos indução sobre |u|. para todo u ∈ A O caso |u| = 0 resulta de w1 ∈ R. Suponhamos então que |u| = n > 0 e que (26) é válido para e Logo palavras mais curtas. Podemos escrever u = vb para algum b ∈ A. −1 −1 −1 −1 )θ = (vwvϕ )θ(wvϕ bwuϕ )θ. (uwuϕ )θ = (vbw(vb)ϕ (27) −1 )θ ∈ N por hipótese de indução, basta mostrar que Como (vwvϕ −1 (wvϕ bwuϕ )θ ∈ N. (28) Se b ∈ A, usamos diretamente (25), logo podemos assumir que b = a−1 para algum a ∈ A, isto −1 )θ ∈ N por (25) e logo é, u = va−1 . Mas então (wuϕ awvϕ −1 −1 (wvϕ bwuϕ )θ = ((wuϕ awvϕ )θ)−1 ∈ N. Concluimos assim que (28) é válido e portanto (26) também. Finalmente, seja g ∈ Ker(Φ). Então (26) e w1 ∈ R implicam −1 −1 g = gθ = (gwgΦ )θ(wgΦ θ) = (gwgϕ )θ(w1 θ) ∈ N, logo Ker(Φ) ⊆ N e P é uma apresentação finita de G. (ii) Mantendo toda a notação de (i), tomamos a constante K > 0 dada pelo Lema 10.7. Começamos por mostrar que −1 Area((uwuϕ )θ) ≤ (K + |w1 | + 1)|u|2 (29) 93 e+ . Usamos indução sobre |u|. para todo u ∈ A Suponhamos que |u| ≥ 1 e (29) é válida para palavras mais curtas. Escrevemos u = vb com e Por (27), temos b ∈ A. −1 −1 −1 (uwuϕ )θ = (vwvϕ )θ(wvϕ bwuϕ )θ. Se v = 1, temos −1 Area((vwvϕ )θ) = Area(w1−1 θ) = 1. Se v 6= 1, obtemos −1 Area((vwvϕ )θ) ≤ (K + |w1 | + 1)|v|2 pela hipótese de indução, logo em qualquer caso −1 −1 Area((uwuϕ )θ) ≤ (K + |w1 | + 1)|v|2 + 1 + Area((wvϕ bwuϕ )θ). (30) −1 por w b−1 w −1 se necessário) que Resulta da prova de (25) (substituindo wvϕ bwuϕ uϕ vϕ −1 Area((wvϕ bwuϕ )θ) ≤ max {|wvϕ |, |wuϕ |}. Como |w1 | − |wuϕ | ≤ KdA (1, uϕ) ≤ K|u| pelo Lema 10.7, obtemos |wuϕ | ≤ K|u| + |w1 |. Analogamente, |wvϕ | ≤ K|v| + |w1 |, logo −1 Area((wvϕ bwuϕ )θ) ≤ K|u| + |w1 | e logo por (30) é fácil verificar que −1 )θ) ≤ (K + |w | + 1)|v|2 + 1 + K|u| + |w | Area((uwuϕ 1 1 ≤ (K + |w1 | + 1)(|u| − 1)2 + (K + |w1 | + 1)|u| ≤ (K + |w1 | + 1)|u|2 . e+ . Logo (29) é válido para todo u ∈ A Seja agora g ∈ Ker(Φ). Se g 6= 1, resulta de (29) que −1 −1 Area(g) = Area((gwgΦ wgΦ )θ) ≤ Area((gwgϕ )θ) + Area(w1 θ) ≤ (K + |w1 | + 1)|g|2 + 1 2 ≤ (K + |w1 | + 2)|g| . Como esta desigualdade é trivialmente válida quando g = 1, então G admite uma função isoperimétrica quadrática. Notamos que, contrariamente ao que acontece com os grupos hiperbólicos, o recı́proco de (ii) não é válido, pois existem grupos não automáticos admitindo uma função isoperimétrica quadrática. De fato, nem tudo são sucessos na teoria dos grupos automáticos... por exemplo, ainda hoje se desconhece se todo grupo automático tem problema da conjugação decidı́vel! Para contornar esse problema, os criadores do conceito de grupo automático inventaram também os grupos biautomáticos. Na versão autômatos, exige-se que as linguagens a L (onde a convolução é feita à direita em vez de ser à esquerda) sejam também racionais. Na versão geométrica, considera-se uma 94 versão da propriedade dos dois viajantes em que os caminhos a percorrer no grafo de Cayley devem começar a distância ≤ 1 e terminar a distância ≤ 1. O problema da conjugação é decidı́vel para todo grupo biautomático... mas ignora-se se os dois conceitos são ou não equivalentes, pois todos os exemplos conhecidos de grupos automáticos são também biautomáticos! Um outro frustrante problema em aberto é o da existência de um recı́proco para a Proposição 10.8: será que G × H automático implica G e H automáticos? 10.4 Exercı́cios (10.1) Construa uma estrutura automática L para Z, produzindo explicitamente autômatos finitos reconhecendo L e as linguagens La . (10.2) Um grupo diz-se de Burnside se for infinito, finitamente gerado e de torsão. Mostre que um grupo de Burnside não pode ser automático. [Sugestão: Considere um loop não trivial num autômato reconhecendo uma estrutura automática de um grupo infinito.] (10.3) Seja L ⊆ A∗ . Dadas X, Y ⊆ L L, seja X ◦ Y = {u v | u w ∈ X, w v para algum w ∈ L}. Mostre que se X e Y são racionais, então X ◦ Y é racional. [Sugestão: Use projeções πij : (A ∪ {$})3 → (A ∪ {$})2 para i, j ∈ {1, 2, 3} distintos.] (10.4) Seja L uma estrutura automática para ϕ : A∗ → G. Mostre que Lw é racional para todo w ∈ A∗ . [Sugestão: Use o Exercı́cio (10.3).] (10.5) Indique uma estrutura automática para Z × Z × C3 . (10.6) Mostre que o produto livre de grupos automáticos é automático. 95 Bibliografia 1. L. Bartholdi e P. V. Silva, Rational subsets of groups, Chapter 23 of the handbook AutoMathA (aguarda publicação), arXiv:1012.1532, 2010. 2. L. Bartholdi e P. V. Silva, Groups defined by automata, Chapter 24 of the handbook AutoMathA (aguarda publicação), arXiv:1012.1531, 2010. 3. G. B. Baumslag, S. M. Gersten, M. Shapiro e H. Short, Automatic groups and amalgams, J. Pure Appl. Algebra 76 (1991), 229–316. 4. J. Berstel, Transductions and Context-free Languages, Teubner, Stuttgart, 1979. 5. R. V. Book e F. Otto, String-Rewriting Systems, Springer-Verlag, New York, 1993. 6. D. B. A. Epstein, J. W. Cannon, D. F. Holt, S. V. F. Levy, M. S. Paterson e W. P. Thurston, Word processing in groups, Jones and Bartlett Publishers, Boston, MA, 1992. 7. E. Ghys e P. de la Harpe (eds), Sur les Groupes Hyperboliques d’après Mikhael Gromov, Birkhauser, Boston, 1990. 8. I. Kapovich e A. Miasnikov, Stallings foldings and subgroups of free groups, J. Algebra 248 (2002), 608–668. 9. R. C. Lyndon e P. E. Schupp, Combinatorial Group Theory, Springer-Verlag, 1977. 10. J. Sakarovitch, Eléments de Théorie des Automates, Vuibert, Paris, 2003. 11. P. V. Silva, Groups and automata: a perfect match, in M. Kutrib, N. Moreira and R. Reis (eds.): Proceedings 14th International Workshop on Descriptional Complexity of Formal Systems (DCFS 2012), volume 7386 of LNCS (2012) 50–63. 96 Índice de conceitos alfabeto, 10 apresentação, 56 finita, 56 área, 63 aresta central, 50 compatı́vel, 50 de um autômato, 12 de um grafo, 11 árvore geradora, 34 atrator, 54 autômato, 12 aparado, 14 com transições-1, 13 completo, 14 de Stallings, 31 determinı́stico, 13 finito, 12 flor, 31 inverso, 27 involutivo, 27 SFG, 32 sobre um monóide M , 26 automorfismo de grafos, 11 de grupos, 6 infinito, 43 não trivial, 12 trivial, 12 completado, 44 composição de relações, 13 comprimento em A∗ , 10 em FA , 22 comutador, 56 concatenação, 10, 43 Conjetura de Hanna Neumann, 39 conjugado, 23 cı́clico, 24 construção de Stallings, 31 convolução, 85 diâmetro, 74 diagrama de van Kampen, 60 bordo de um, 61 diagrama de van Kampen dimensão de um, 61 dimensão de um diagrama de van Kampen, 61 de um grupo livre, 23 base em FA , 23 em A∗ , 10 bordo de um diagrama de van Kampen, 61 de uma região, 60 do grupo livre, 46 endomorfismo, 49 espaço de Cantor, 45 espaço métrico, 40 compacto, 45 completado de um, 44 completo, 44 discreto, 44 estrutura automática, 85 com unicidade, 86 caminho bem-sucedido, 12 central, 50 compatı́vel, 50 maximal, 51 fator em A∗ , 11 em Aω , 43 fecho, 46 função 97 de Dehn, 64 isoperimétrica, 63 exponencial, 63 linear, 63 polinomial, 63 quadrática, 63 recursiva, 63 subquadrática, 79 uniformemente contı́nua, 53 geodésica num autômato, 36 num grafo, 74, 79 numa árvore geradora, 35 grafo, 11 A-, 12 conexo, 60 δ-hiperbólico, 74 bipartido, 60 completo, 59 conexo, 11 de Cayley, 27 diâmetro de um, 74 finito, 11 hiperbólico, 74 orientado, 11 planar, 59 transitivo nos vértices, 28 grupo, 4 cı́clico, 8 de Artin ortogonal, 70 de Burnside, 95 de grafo, 70 de permutações, 4 de torsão, 23 finitamente apresentável, 56 finitamente gerado, 8 fundamental, 69 hiperbólico, 77 livre, 22 livre de torsão, 23 quociente, 6 residualmente finito, 39 simétrico, 4 virtualmente livre, 78 homomorfismo de grupos, 5 de monóides, 6 involutivo, 19 núcleo de um, 7 inverso formal, 19 involução, 19 isometria, 75 isomorfismo de autômatos, 12 de grafos, 11 de grupos, 6 letra, 10 linguagem, 11 ε-lipschitziana, 79 de um autômato, 13 lipschitziana, 79 racional, 13 loop, 13 máquina de Turing, 59 métrica, 40 dos prefixos em A∗ , 44 em FA , 46 geodésica num grafo, 74 num grupo, 76 profinita, 41 monóide, 5 livre, 11 núcleo cı́clico, 23 operadores booleanos, 14 ordem, 8 boa, 86 lexicográfica, 86 total, 86 98 palavra, 10 ciclicamente reduzida, 23 infinita, 43 reduzida, 46 irredutı́vel, 17 reduzida, 20 permutação, 4 ponto base, 27 ponto fixo, 49 infinito, 53 regular, 54 singular, 54 prefixo em A∗ , 11 em Aω , 43 em FA , 22 problema da conjugação, 23 problema da palavra, 23 decidı́vel, 23, 58 generalizado, 34 produto Γ-, 69 de grafo, 69 direto de autômatos, 14 de grupos, 8 livre, 67 com amalgamação, 69 forma normal do, 68 propriedade dos dois viajantes, 79 propriedade universal em A∗ , 10 em FA , 20 quase-isometria de espaços métricos, 75 de grafos, 76 raio, 46 redução, 16 elementar, 16 região, 60 bordo de uma, 60 exterior, 60 fronteira de uma, 60 relator, 56 repulsor, 54 rótulo de um caminho, 12 infinito, 43 de uma aresta, 12 secção, 85 sistema de reescrita, 16 confluente, 17 noetheriano, 16 redutor, 16 subconjunto racional, 26 subgrupo, 5 conjugado, 37 de ı́ndice finito, 7 gerado por um subconjunto, 7 ı́ndice de um, 7 normal, 6 gerado por um subconjunto, 56 sucessão convergente, 44 de Cauchy, 44 limite de uma, 44 sufixo em A∗ , 11 em Aω , 43 Teorema de Benois, 25 de Cayley, 6 de Howson, 38 de Marshall Hall, 41 de Nielsen-Schreier, 35 de van Kampen, 69 transversal, 85 triângulo geodésico, 74 ultramétrica, 40 vértice adjacente, 11 99 de um autômato, 12 de um grafo, 11 inicial, 12 terminal, 12 100