Note e osservazioni Le prime assiomatizzazioni dei gruppi (abeliani e no) mediante una singola equazione, come
Proposizione 6.18. Sia T una teoria del prim’ordine nel linguaggio L con
costanti. Supponiamo che per ogni coppia M, N di modelli di T e per ogni isomorfismo F : M0 → N0 dove M0 è una sottostruttura di M e N0 è una
sottostruttura di N ,
M ∃yϕ[a1, . . . , an] ⇔ N ∃yϕ[F (a1), . . . , F (an)],
dove ϕ(y, x1, . . . , xn) è congiunzione di formule che sono atomiche o nega-
Allora T ammette l’eliminazione debole dei quantificatori.
Ci sono teorie T che non hanno costanti e che tuttavia ammettono l’eliminazione dei quantificatori per formule che non sono enunciati, cioè ad ogni formula ϕ non chiusa possiamo associare una formula ϕ0 priva di quantificatori e con le medesime variabili libere, così che ϕ e ϕ0 sono logicamente equivalenti modulo T . In questo caso diremo che T ammette l’eliminazione dei quantificatori per formule non chiuse e la Proposizione 6.18 qui sopra continua a valere in questo caso.
Oltre a Σ(N,S), ci sono altre teorie che ammettono l’eliminazione dei quantificatori:
• la teoria dei naturali con l’ordinamento (Esercizio 6.48) o con la somma (pag. 114),
• la teoria degli ordini lineari densi senza primo o ultimo elemento (Eserci- zio 6.67),
• la teoria dei campi algebricamente chiusi di caratteristica fissata (Teore- ma 6.42),
• la teoria dei campi reali chiusi (Sezione 6.D.1).
6.A.3. L’ordinamento. Consideriamo i numeri naturali N con l’ordinamento — cioè la struttura (N, <). La funzione successore è definibile mediante la
formula
(σ(x, y)) x < y ∧ ¬∃z (x < z ∧ z < y) ,
quindi gli insiemi definibili in (N, <) sono esattamente quelli di (N, <, S, 0). La teoria Σ(N,<,S,0)è ottenuta aggiungendo a Σ(N,S,0)gli enunciati che asseriscono che < è un ordine stretto
¬∃x (x < x) (6.5a) ∀x, y, z (x < y ∧ y < z ⇒ x < z) (6.5b) ∀x, y (x < y ·∨ x = y ·∨ y < x) , (6.5c)
dove ·∨ è la disgiunzione esclusiva (vedi pag. 6), e l’enunciato che asserisce che S(x) è il successore immediato di x
(6.5d) ∀x, y (x < S(x) ∧ ¬ (x < y ∧ y < S(x))) .
Gli enunciati ∀x(S(n)(x) 6= x) sono conseguenza della transitività dell’ordi- namento, quindi Σ(N,<,S,0) è finitamente assiomatizzabile. La teoria Σ(N,<) ammette l’eliminazione dei quantificatori (Esercizio 6.48): ne segue che Σ(N,<) e Σ(N,<,S,0) sono teorie complete e decidibili. Anche in questo caso, gli unici sottoinsiemi di N definibili in (N, <, S, 0) o, equivalentemente in (N, <), sono
quelli finiti e quelli cofiniti. La formula x < y può essere descritta tramite S dalle espressioni
∃k y = S(S(k)(x))
oppure da
y = S(x) ∨ y = S(S(x)) ∨ y = S(S(S(x))) ∨ . . . ,
ma in entrambi i casi si tratta di pseudo-formule e quindi non possiamo con- cludere che l’ordinamento sia definibile in (N, S). Infatti per l’Esercizio 6.16 l’ordinamento < non è definibile in (N, S).
Mediante un’immediata generalizzazione della dimostrazione della Pro- posizione 6.2 si ottiene:
Proposizione 6.19. I modelli non-standard (M, SM) di Σ(N,<) sono, a meno di isomorfismo, della forma
M = N ·∪ (I × Z)
con (I, ≺) un insieme arbitrario linearmente ordinato, e <M è l’ordinamento solito su N, ogni n ∈ N precede ogni (i, a) ∈ I × Z, e
(i, a) <M (j, b) ⇔ i ≺ j ∨ [i = j ∧ a < b].
Dato che ogni insieme I può essere linearmente ordinato,6 ogni modello di Σ(N,S) può essere trasformato in un modello di Σ(N,<).
6.A.4. L’addizione. Consideriamo ora la struttura (N, +). L’ordinamento
x < y è definito dalla formula
x 6= y ∧ ∃z (x + z = y) ,
quindi gli insiemi definibili nella struttura (N, +, <, S, 0) sono quelli nella struttura (N, +). Per ogni n ≥ 2, la relazione ≡n di congruenza modulo n è
definibile in (N, +) mediante la formula (χn(x, y)) ∃z x + z + · · · + z | {z } n = y ∨ y + z + · · · + z | {z } n = x ,
quindi gli insiemi definibili nella struttura (N, +, <, S, 0, ≡2, ≡3, . . . ) sono
quelli definibili in (N, +).
Definizione 6.20. L’aritmetica di Presburger è la teoria Σ(N,+,<,S,0) nel linguaggio con i simboli +, <, S, 0 e che ha per assiomi:
• gli assiomi per gli ordini lineari (gli enunciati (6.5) di pagina 112), • gli assiomi per i monoidi commutativi (gli enunciati (3.9a), (3.9b), (3.9c)
di pagina 38)
• ∀x, y, z (x + z = y + z ⇒ x = y) (legge di cancellazione)
• ∀x, y (x + y = 0 ⇒ x = 0 ∧ y = 0) (legge di positività)
• ∀x, y (x < y ⇔ x 6= y ∧ ∃z (x + z = y)) (legge di compatibilità) • gli infiniti enunciati
(π0n) ∀x∃!y χn(x, y) ∧ y < S(n)(0)
per ogni n ≤ 2.
Osserviamo che l’assioma π0n può essere riscritto come ∀x∃!y ∃!z x =
nz + y ∧ y < S(n)(0)
, e che è l’assioma πn per gli Z-gruppi (vedi pag. 78)
riformulato per la struttura (N, +, <, S, 0, ≡2, ≡3, . . . ).
La teoria Σ(N,+,S,0) non ammette l’eliminazione dei quantificatori, dato che la formula χn(x, y) non è equivalente ad una qualche formula aperta con
variabili libere x e y. In un certo senso queste sono le uniche ostruzioni per l’eliminazione dei quantificatori. Sia Σ(N,+,≡) la teoria (che continuiamo a chiamare aritmetica di Presburger) nel linguaggio esteso mediante infiniti nuovi simboli di relazione binaria ≡n(n ≥ 2) e che ha per assiomi gli assiomi di Σ(N,+) più gli infiniti enunciati
∀x, y (x ≡ny ⇔ χn(x, y))
per ogni n ≤ 2. Allora Σ(N,+,≡) ammette l’eliminazione dei quantificatori e ogni enunciato atomico è decidibile [End01, pag. 197–201]. Quindi le teorie Σ(N,+,≡) e Σ(N,+) sono complete e decidibili.
Ogni sottoinsieme finito o cofinito di N è definibile in (N, +), dato che ogni insieme definibile in (N, <) è anche definibile in (N, +). Oltre ai sottoinsiemi finiti e cofiniti è anche possibile definire ogni insieme periodico, cioè ogni progressione aritmetica. Infatti {a · n + b | n ∈ N} è definito da
x ≡aS(b)(0).
Dato che la famiglia dei sottoinsiemi definibili è chiusa per differenze simme- triche, ogni sottoinsieme di N che sia definitivamente periodico è definibile in (N, +). Mediante il metodo dell’eliminazione dei quantificatori si dimostra che gli insiemi definibili in (N, +) di rango 1, sono esattamente i sottoinsiemi di N definitivamente periodici e i loro complementi. L’addizione non è definibile né in (N, <) né in (N, S): se lo fosse, allora l’insieme dei numeri pari sarebbe definibile in queste strutture, contrariamente al fatto che i sottoinsiemi di N definibili in (N, <) o in (N, S) sono gli insiemi finiti e i cofiniti.
Analizziamo ora i modelli nonstandard di Σ(N,+). Per le leggi di positi- vità e compatibilità 0 è il minimo di (M, <), per la legge di cancellazione l’elemento z di cui si asserisce l’esistenza nella legge di compatibilità è unico. Proposizione 6.21. M Σ(N,+,≡) se e solo se (M, +) è (isomorfo a)
dove G è uno Z-gruppo.
Dimostrazione. Sia (M, +, <, S, 0, ≡2, ≡3, . . . ) un modello di Σ(N,+,≡), e
supponiamo che F : M \ {0} → M0 sia una biezione e che M0 sia un insieme disgiunto da M . Allora mediante F si possono definire + e < su M0 ponendo
∀x, y ∈ M \ {0} [F (x) + F (y) = F (x + y) ∧ (F (x) < F (y) ⇔ y < x)] . L’ordinamento < può essere esteso ad un ordine totale su G def= M ∪ M0 stabilendo che gli elementi di M0 vengano prima degli elementi in M . Per definire + su G è sufficiente definire x + y quando x ∈ M0 e y ∈ M o quando
x ∈ M e y ∈ M0. Se imponiamo che x + y = y + x possiamo ricondurci al caso in cui x ∈ M0 e y ∈ M . Se F−1(x) = y, allora poniamo x + y = 0, quindi possiamo supporre che F−1(x) < y oppure che y < F−1(x). Se vale il primo caso allora F−1(x) + z = y per un unico z ∈ M \ {0}, e poniamo
x + y = z; se vale il secondo caso allora y + z = F−1(x) per un unico z > 0, e poniamo x + y = F (z). È facile verificare che (G, +, <) è uno Z-gruppo.
L’altra direzione, che G+ è un modello dell’aritmetica di Presburger per
ogni Z-gruppo G, è lasciata al lettore.
Se G è uno Z-gruppo e Z = {k1G | k ∈ Z}, il quoziente (G/Z, <) è un
ordine lineare denso privo del primo e ultimo elemento, quindi l’ordinamento in un modello non standard dell’aritmetica di Presburger è della forma N ·∪ L × Z, con L ordine lineare denso privo del primo e ultimo elemento. Un esempio concreto di modello non standard dell’aritmetica di Presburger è N ·∪ Q × Z con l’operazione di addizione definita da n + (q, z) = (q, z + n) e (q1, z1) + (q2, z2) = (q1+ q2, z1+ z2) (Esercizio 6.46).
6.A.5. Moltiplicazione, divisibilità e coprimalità. Consideriamo le strutture (N, ⊥), (N, |) e (N, ·), dove ⊥ è il predicato binario di coprimalità, cioè
x ⊥ y ⇔ ∀z (z | x ∧ z | y ⇒ z = 1)
e | è il predicato di divisibilità. Chiaramente la relazione | è definibile in (N, ·), mentre la definibilità della relazione ⊥ in (N, |) segue dalla definibilità del numero 1 nella struttura (N, |) (Esercizio 3.55). Il viceversa non vale, cioè | non è definibile in (N, ⊥) (Esercizio 6.45) e · non è definibile in (N, |) (Sezione 32.C.1).
Anche per la struttura (N, ·) si può trovare un sistema di assiomi com- pleto, noto come aritmetica di Skolem, che ammette l’eliminazione dei quantificatori [Smo91].
Per l’Esercizio 3.55 l’insieme dei numeri primi è definibile in (N, |) e quindi in (N, ·). L’insieme dei numeri primi non è definitivamente periodico, quindi non è definibile in (N, +).