Sia G un gruppo finitamente generato con generatori x1, . . . , xn e relatori r1, . . . , rk. Il problema della parola `e detto risolubile per una presentazione se esiste un algoritmo che, data una parola w nelle xi, permetta di stabilire se que- sta sia o no la parola vuota w = 1. Questo problema `e equivalente a quello dell’uguaglianza: date due parole w1, w2 ∈ G, esiste un algoritmo che permetta di stabilire se w1 = w2, ovvero se w1w2−1 = 1.
Tale problema `e indipendente dalla presentazione finita considerata, e riguarda invece il gruppo G. Possiamo dire che per un gruppo G il problema della parola `e risolubile se lo `e per una certa presentazione finita di G (e quindi per tutte le sue presentazioni).
Ricordiamo alcune definizioni della teoria della ricorsivit`a. Un insieme S di ele- menti si dice ricorsivo se esiste un algoritmo capace di stabilire se un elemento appartiene o no all’insieme. Si dice ricorsivamente enumerabile se esiste un al- goritmo che permetta di disporre in una lista gli oggetti di S. Ogni insieme S ricorsivo `e ricorsivamente enumerabile, e S `e ricorsivo se sia S che il suo comple- mentare sono ricorsivamente enumerabili. Per un insieme ricorsivo non c’`e quindi mai un’attesa infinita: facendo girare contemporaneamente i due algoritmi che danno le liste degli elementi di S e del suo complementare S0, un dato elemento apparir`a, prima o poi, in una delle due liste. Si dimostra per`o che esistono insiemi di interi positivi ricorsivamente enumerabili ma non ricorsivi, e questo fatto `e, in un certo senso, la fonte di tutti i problemi di indecidibilit`a in matematica.
Si pu`o fare una lista delle parole su un alfabeto finito X ∪ X−1 come si fa per un dizionario: la parola vuota 1 ha lunghezza 0; le parole di lunghezza 1 sono gli elementi x o x−1 ordinate per esempio come
x1, x−11 , x2, x−12 , . . . , xn, x−1n , quelle di lunghezza 2 nell’ordine lessicografico
24 CAPITOLO 4. IL PROBLEMA DELLA PAROLA
x1x1, x1x−11 , x1x2, . . . , x−1n x−1n ,
ecc. Usando la lista w0, w1, w2, . . . possiamo formare una lista delle parole uguali a 1 in G.
Teorema 4.1. Se G `e finitamente presentato, G = hX|Ri e Ω `e l’insieme delle parole su X, allora l’insieme
W = {w ∈ Ω|w = 1 ∈ G} `e ricorsivamente enumerabile.
Dimostrazione. Usando la lista w0, w1, w2, . . . delle parole nelle xi, disponiamo in una lista ρ0, ρ1, ρ2, . . . le parole nelle ri, cio`e le parole di W , nello stesso modo in cui si ottiene una enumerazione dei numeri razionali:
w0−1ρ0w0 w−10 ρ1w0 //w0−1ρ2w0 ww w−10 ρ3w0 //. . . w1−1ρ0w1 77 w−11 ρ1w1 ww w1−1ρ2w1. . . 77 w2−1ρ0w2 w−12 ρ1. . . 77 w−13 ρ0w3. . . 77 .. .
Allora, poich´e per un gruppo finitamente presentato G l’insieme W `e ricorsi- vamente enumerabile, il problema della parola per G `e risolubile se anche
{w ∈ Ω|w 6= 1} `e ricorsivamente enumerabile.
Nota. Un gruppo finitamente generato si dice ricorsivamente presentato se l’in- sieme delle relazioni `e ricorsivamente enumerabile. Il problema della parola si definisce per questi gruppi come nel caso dei gruppi finitamente presentati, ed `e anch’esso un problema ricorsivamente enumerabile.
25
`
E chiaro che per il gruppo libero il problema della parola `e risolubile: data una parola w l’algoritmo richiesto consiste nel procedimento di riduzione. Una parola nelle xi `e una parola w = 1 nel gruppo libero se dopo la cancellazione di lettere adiacenti della forma xix−1i o x
−1
i xi si arriva alla parola vuota; altrimenti w 6= 1. Consideriamo ora la nozione di gruppo semplice nel contesto dei gruppi dati con generatori e relazioni.
Definizione 4.1. Un gruppo G si dice semplice se N G ⇒ N = {1} oppure N = G.
Si dimostra il seguente:
Teorema 4.2. Sia G = hX|Ri un gruppo dato con generatori e relazioni. Allora G `e un gruppo semplice ⇔ ogniqualvolta si aggiunge a R una parola w che non `e uguale a 1 in G si ottiene il gruppo identico:
G1 = hX|R, wi = {1}.
Teorema 4.3. Per un gruppo semplice G = hX|Ri finitamente presentato il proble- ma della parola `e risolubile.
Dimostrazione. Sia w ∈ G. Se G = 1 non c’`e niente da dimostrare. Sia allora G 6= 1, x 6= 1 un fissato elemento di G, e Gw = hX|R, wi. Se w = 1 ∈ G, allora ovviamente G ' Gw. Se w 6= 1 allora, essendo G semplice, per il Teor. 3.2 si ha Gw = {1}. Ne segue x = 1 in Gw se e solo se w 6= 1 in G. Il gruppo Gw `e anch’esso finitamente presentato. Data la parola w di G, possiamo allora formare simultaneamente due liste:
- parole uguali a 1 in G; - parole uguali a 1 in Gw. Allora:
- se w = 1 in G, w compare nella prima lista; - se w 6= 1 in G, x compare nella seconda lista.
Basta allora aspettare e vedere quale dei due fatti si verifica.
Definizione 4.2. Sia G un gruppo, ρ una relazione tra elementi e sottoinsiemi defi- nita su G e sulle sue immagini omomorfe, e sia P una propriet`a di gruppi (ovvero tale che se G1 ' G e G ha la propriet`a P, allora anche G1ha la propriet`a P). Si dice allora che G ha residualmente la propriet`a P rispetto a ρ, o che G `e residualmente P, se per ogni coppia di elementi x, y che non sono tra loro nella relazione ρ esiste un omomorfismo suriettivo φ di G in un gruppo K che ha la propriet`a P e tale che φ(x) 6= φ(y).
26 CAPITOLO 4. IL PROBLEMA DELLA PAROLA Esempio 4.1. Sia ρ la relazione di uguaglianza. Allora G `e residualmente P se per ogni coppia di elementi distinti x e y esiste un omomorfismo di G in un gruppo K che ha la propriet`a P e tale che le immagini sono anch’esse distinte. Poich´e x = y `e equivalente a xy−1 6= 1, quanto detto `e equivalente ad affermare che un elemento di G diverso da 1 resta diverso da 1 in un gruppo che ha la propriet`a P. La cosa si pu`o esprimere dicendo che G `e residualmente P se, per ogni g 6= 1, esiste N G, dove N dipende da x, tale che g 6∈ N e G/N ha la propriet`a P (la propriet`a `e dunque ”residua” nel senso che di essa gode il gruppo che resta quando si ”toglie” il sottogruppo N ).
Esempio 4.2. Gli interi sono un gruppo residualmente finito (se non si specifica la relazione ρ si intende la relazione di uguaglianza). Infatti, dati due interi n e m, con m che non divide n, n non appartiene ad hmi, e il quoziente Z/hmi `e finito. Questo fatto vale in generale per tutti i gruppi liberi.
Teorema 4.4. Un gruppo libero `e residualmente finito.
Teorema 4.5. Per un gruppo G finitamente presentato e residualmente finito il problema della parola `e risolubile.
Dimostrazione. Sia F libero di rango n, R finitamente generato e G = F/R. Sia w una parola di F ; dobbiamo decidere se w ∈ R o no. Cominciamo allora due procedure: con la prima enumeriamo effettivamente gli elementi di R; con la seconda facciamo una lista delle tavole di moltiplicazione dei quozienti finiti di F/R. Allora basta aspettare perch´e necessariamente o w compare nella prima enumerazione, e quindi w ∈ R, oppure, se w 6∈ R `e wR 6= R, e dunque, essendo F/R residualmente finito, esiste H/R F/R tale che (F/R)/(H/R) `e finito e wR 6∈ H/R, e pertanto wR comparir`a nella lista dei quozienti finiti di F/R.
Conclusione
Un gioco con lettere ”come pedine” e con regole di formaione, che ci ha con- sentito di costruire semplici esempi di monoidi o gruppi finiti, si `e rapidamente rivelato come la ”punta di un iceberg” di una parte essenziale della teoria dei grup- pi, con complicazioni insospettabili che riguardano sia aspetti tecnici (trovare una presentazione ”minimale” in qualche senso di un gruppo finito, oppure data una presentazione elencare gli elementi del gruppo con algoritmi opportuni) sia aspetti logigi, come la decidibilit`a o meno del problema della parola o dell’isomorfismo per classi di gruppi.
Bibliografia
[V] L.Verardi, Dispense del corso di Algebra da un Punto di Vista Superiore, a.a. 2013-2014
[A] M.Artin, Algebra, Bollati-Boringhieri,1997
[R] D.J.S.Robinson, A Course in the Theory of Groups, Springer-Verlag, New York,1996
[M] A.Mach`ı, Gruppi: Una introduzione a idee e metodi della Teoria dei Gruppi, Springer-Verlag, Milano, 2007