Definibilità in algebra e teoria dei numer
5. Definibilità in algebra e in combinatorica
5.A. Gruppi.
5.A.1. Linguaggi e assiomatizzazioni per i gruppi. Per studiare la teoria del prim’ordine dei gruppi possiamo utilizzare il linguaggio Lgruppi introdotto a pagina 38. Una Lgruppi-struttura è un gruppo se e solo se soddisfa gli assiomi (3.8).
La scelta del linguaggio per formalizzare la nozione di gruppo è ben lungi dall’essere unica: se si rimuove il simbolo di inverso si ottiene il linguaggio
Lmonoidi; una struttura per questo linguaggio è un monoide se soddisfa (3.8a)
e (3.8b), ed è un gruppo se soddisfa anche
∀x∃y (x · y = 1 ∧ y · x = 1) .
I termini e le formule di Lmonoidi sono termini e formule di Lgruppi, ma non viceversa. Volendo essere ancora più parsimoniosi, potremmo rinunciare anche alla costante 1 limitandoci al linguaggio Lsemigruppi che ha un solo simbolo · di operazione binaria (Esercizio 5.28).
Nel caso dei gruppi abeliani si usa di solito la notazione additiva al posto di quella moltiplicativa e si utilizza il linguaggio Lgruppi a. introdotto a pagina 40.
In algebra una Lsemigruppi-struttura si dice magma; si tratta cioè di un insieme non vuoto dotato di un’operazione binaria. La nozione di magma è troppo generale per essere di qualche utilità. Per ottenere strutture matema- ticamente più interessanti dobbiamo imporre delle condizioni sull’operazione. 73
magma quasigruppo loop gruppo monoide semigruppo divisibilità identità associatività associatività identità invertibilità
Figura 1. Alcune strutture algebriche con una operazione binaria
Ecco una breve lista delle strutture più comuni: un quasigruppo è una magma divisibile, cioè soddisfa ∀x, y∃z(y · z = x) e ∀x, y∃z(z · y = x), un quasigruppo con identità è un loop, un loop associativo è un gruppo. Alter- nativamente: una magma associativa è un semigruppo, un semigruppo con identità è un monoide, e un monoide che ammetta inversi, cioè che soddisfi ∀x∃y(x · y = 1) e ∀x∃y(x · y = 1), è un gruppo (Figura 1).
5.A.2. Assiomatizzazioni equazionali*. La teoria dei gruppi è equazionale ed è finitamente assiomatizzabile, quindi è assiomatizzabile mediante un unico assioma. Infatti questo assioma può essere un’equazione. Una teoria equazionale che sia assiomatizzabile mediante un’unica equazione si dice 1-basata.
È stato dimostrato che l’equazione nel linguaggio Lgruppi ((z · (x · y)−1)−1· (z · y−1)) · (y−1· y)−1= x,
definisce un gruppo, mentre se vogliamo assiomatizzare i gruppi abeliani si può usare
((x + y) + z) + (−(x + z)) = y
dove − è il simbolo dell’operazione unaria di opposto additivo. Se invece usiamo − per denotare il simbolo di operazione binaria per la differenza, un singolo assioma per i gruppi abeliani è dato da
x − (y − (z − (x − y))) = z,
mentre un’assiomatizzazione dei gruppi mediante il simbolo / per la divisione, dove x/y sta per x · y−1, è dato dal singolo assioma
x/ (((x/x)/y)/z)/(((x/x)/x)/z)
5.A.3. Sottogruppi. Per parlare di sottogruppi possiamo utilizzare il seguente trucco. Aggiungiamo un nuovo simbolo di predicato unario H al linguaggio dei gruppi, ottenendo così un linguaggio LH. Le LH-strutture hanno la forma (G, ·,−1, 1, H): se queste soddisfano gli assiomi per i gruppi e anche
l’enunciato
H(1) ∧ ∀x, yH(x) ∧ H(y) ⇒ H(x · y−1)
allora stiamo considerando dei gruppi dotati di un sottogruppo privilegiato. Se vogliamo dire che questo sottogruppo è normale e non banale utilizziamo l’enunciato
∀x, yH(x) ⇒ H(y · x · y−1)∧ ∃x (x 6= 1 ∧ H(x)) ∧ ∃x¬H(x). Un gruppo G si dice semplice se non ha sottogruppi normali propri, cioè se
∀H (H sottogruppo normale ∧ ∃x (H(x) ∧ x 6= 1) ⇒ ∀x H(x)) . Questa è una formula della logica del second’ordine (vedi l’Osservazione 3.7) dato che si quantifica su sottoinsiemi e quindi viene relegata nel limbo delle pseudo-formule. Infatti non c’è nessun sistema di assiomi del prim’ordine i cui modelli siano tutti e soli i gruppi semplici (Esercizio 32.24, della Sezione 32). 5.A.4. Definibilità. Un elemento g di un gruppo G ha torsione se gn = 1 per qualche n > 0 e il più piccolo n siffatto si dice ordine di g e si indica con o(g). Se g non ha torsione, si dice che g ha ordine infinito, o(g) = ∞.
Vediamo qualche esempio di formula e suo significato: La formula. . . significa che. . .
∃z (z · x = y · z) x e y sono coniugati
xn= 1 o(x) divide n
∀x (xn= 1) l’ordine di un qualsiasi elemento divide n.
Esempi di sottoinsiemi definibili senza parametri sono:
• il centro C(G), definito dalla formula ϕ(x): ∀y(y · x = x · y). Più in generale, se A ⊆ G è definibile in G con parametri p1, . . . , pn, allora il suo
centralizzante CG(A)
def
= {g ∈ G | ∀x ∈ A (g · x = x · g)} è definibile in G con parametri p1, . . . , pn;
• il sottogruppo banale {1}, definito dalla formula ϕ(x): x = x · x, • il grafo della funzione inversa
(x, y) | y = x−1
, definito dalla formula ϕ(x, y): y · x = (y · x) · (y · x).
Vediamo due esempi di insiemi non definibili. 5.A.5. Torsione. L’espressione
∃n ∈ N (xn= 1)
che afferma che x ha torsione finita, è una pseudo-formula, e non è una formula del nostro linguaggio, per via della quantificazione sui naturali. Se
tentassimo di sostituire ∃n ∈ N con una disgiunzione del tipo
x2= 1∨x3 = 1∨ . . .
otterremmo una stringa infinita di simboli, che non può essere una formula. A questo punto non possiamo ancora concludere che
Tor(G) = {x ∈ G | ∃n ∈ N (xn= 1)} ,
l’insieme degli elementi di torsione di G, sia indefinibile nel nostro linguaggio. L’Esercizio 32.32(i) del Capitolo VI mostra che le cose stanno proprio così. 5.A.6. Divisibilità. La parte n-divisibile di un gruppo è l’insieme degli ele- menti della forma yn, ed è definita dalla formula ∃y (x = yn). Nel caso dei gruppi abeliani si utilizza solitamente la notazione additiva (G, +) e la parte
n-divisibile
nG = {nx | x ∈ G}
è un sottogruppo. Un gruppo abeliano si dice n-divisibile (n ≥ 2) se coincide con la sua parte n-divisibile, cioè se G = nG. Una Lgruppi a.- struttura (G, +, −, 0) è un gruppo n-divisibile (n ≥ 2) se e solo se soddisfa Σgruppi a.(vedi pagina 40) e l’enunciato
(δn) ∀x∃y ny = x.
La parte divisibile di un gruppo abeliano è il sottogruppo ottenuto interse- cando tutte le sue parti n-divisibili o, equivalentemente, tutte le sue parti
pk-divisibili, con p primo. Un gruppo abeliano è divisibile se e solo se coincide con la sua parte divisibile. Esempi di gruppi abeliani n-divisibili sono
Z[1/n] =
n
x ∈ Q | ∃k(nkx ∈ Z)o
e Z[1/n]/Z, che può essere identificato con un sottogruppo del gruppo moltiplicativo {z ∈ C | |z| = 1} ∼= R/Z. Esempi di gruppi abeliani divisibili sono Q =S
n≥1Z[1/n], R, Q/Z e R/Z.
L’espressione
∀n > 0 ∃y ny = x
non è una formula e quindi non può esser usata per definire la parte divisibile di un gruppo. Infatti non c’è nessuna formula ϕ(x) che definisca la parte divisibile di un gruppo abeliano (Capitolo VI Esercizio 32.32(ii)).
5.B. Esempi di teorie del prim’ordine dei gruppi. I gruppi abeliani divisibili sono caratterizzabili mediante enunciati del nostro linguaggio: basta aggiungere agli usuali assiomi per i gruppi abeliani Σgruppi a. gli enunciati δn per ogni n ≥ 2. Fissato n prendiamo un primo p sufficientemente grande, diciamo n! < p. Il gruppo Z[1/n!] è k-divisibile, per ogni k ≤ n, ma non è