Indice

1 Insiemi, relazioni, funzioni 3

1.1 Insiemi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2 Relazioni ed funzioni . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.2.1 Funzioni . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.2.2 Relazioni d’equivalenza . . . . . . . . . . . . . . . . . . . 13
1.2.3 Cardinalità . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.2.4 Relazioni d’ordine . . . . . . . . . . . . . . . . . . . . . . 22
1.3 Calcolo combinatorio . . . . . . . . . . . . . . . . . . . . . . . . . 26

2 Strutture algebriche 30
2.1 Monoidi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
2.2 Stringhe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40

3 Algebra Lineare 44
3.1 Vettori e matrici . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
3.2 Il determinante di una matrice quadrata . . . . . . . . . . . . . . 50
3.3 Metodo di Gauss . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
3.4 Sistemi lineari . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
3.5 Vettori linearmente indipendenti e basi . . . . . . . . . . . . . . 65
3.6 I sottospazi di uno spazio vettoriale . . . . . . . . . . . . . . . . 67
3.7 I vettori geometrici . . . . . . . . . . . . . . . . . . . . . . . . . . 70
3.8 Il prodotto scalare su Rn . . . . . . . . . . . . . . . . . . . . . . . 72
3.9 Il prodotto vettoriale in R3 . . . . . . . . . . . . . . . . . . . . . . 75

4 Grafi 79

5 Algebre eterogenee 81

A Aritmetica 82
A.1 Definizioni di base . . . . . . . . . . . . . . . . . . . . . . . . . . 82
A.2 Algoritmo euclideo in Z . . . . . . . . . . . . . . . . . . . . . . . 83

1
A.3 I numeri primi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90

2
Capitolo 1

Insiemi, relazioni, funzioni

Nota. Questo primo capitolo riassume sinteticamente il contenuto dell’Appendice

A, dell’Appendice B e del Capitolo 2 delle dispense:

G. Rosolini, R. Pagnan: Elementi di Logica Matematica, Genova (2016),

che verranno indicate nel prosieguo con R-P. Il Lettore è vivamente consigliato
di consultare e studiare tali dispense.

1.1 Insiemi
Notazioni. Se A è un insieme e x un elemento di A scriveremo x ∈ A; se
l’elemento x non appartiene ad A scriveremo x < A.
Con U indicheremo il superinsieme di tutti gli elementi e con I il superinsieme
i cui elementi sono tutti gli insiemi (vedere R-P, Osservazione A.1.4 p.60).
Sia P un’affermazione. Scriveremo P(x) per affermare che per l’elemento
x vale l’affermazione P. Ad esempio se P è “essere un numero intero pari”
allora scriveremo P(x) per dire che x è un numero intero pari. La scrittura

{x ∈ A | P(x)}

sta ad indicare l’insieme degli elementi di A per cui vale P.

Un insieme A costituito da un solo elemento (cioè A = {x} dove x ∈ U) sarà
chiamato singoletto.
Utilizzeremo nel seguito le seguenti notazioni.

• N = {0, 1, 2, 3, 4, . . . }, l’insieme dei numeri naturali.

• N∗ = {1, 2, 3, 4, . . . }, l’insieme dei numeri interi positivi.

3
 • Z = {. . . , −3, −2, −1, 0, 1, 2, 3, 4, . . . }, l’insieme dei numeri interi.
m
 
• Q = | m, n sono numeri interi primi tra di loro e n > 0 , l’insieme dei
n
numeri razionali.
• R l’insieme dei numeri reali.
• C l’insieme dei numeri complessi.
Ad esempio
2 √ 1 √
3 ∈ N∗ , ∈ Q, 3 ∈ R, < Z, 2 < Q, π < Q.
3 5
Definizione 1.1.1 (Connettivi). Siano P e Q due affermazioni.
• Congiunzione di P e Q: P ∧ Q. Significato: P e Q cioè sia P che Q.
• Disgiunzione di P e Q: P ∨ Q. Significato: P o Q cioè P oppure Q.
• Negazione di P: ¬P. Significato: non si ha P o che P è falsa.
• Implicazione: P implica Q: P ⇒ Q. Significato: se P allora Q.
• Equivalenza di P e Q: P ⇔ Q. Significato: P se e solo se Q.
Ad esempio se P è l’affermazione “essere triangolo” e Q è l’affermazione
“essere poligono regolare” allora P ∧ Q è l’affermazione “essere triangolo
equilatero”.
Se P è l’affermazione “essere un quadrato” e Q è l’affermazione “essere un
quadrilatero non regolare” allora P ∨ Q è l’affermazione “essere un quadri-
latero”.
• Due altri simboli: vero >; falso ⊥.
Definizione 1.1.2 (Quantificatori). Siano A un insieme e P un’affermazione.
• Quantificatore universale ∀: scriveremo
∀ x ∈ A.P(x)
volendo dire che per tutti gli elementi x di A si ha P(x)
• Quantificatore esistenziale ∃: scriveremo
∃ x ∈ A.P(x)
volendo dire che esiste un elemento x di A per cui si ha P(x). Con il
simbolo ∃! intendiamo affermare l’esistenza e l’unicità.

4
•• Vedere R-P, A.4: Negare un’affermazione, pp. 67-69.

Definizione 1.1.3. Siano A e B due insiemi. Diremo che A è contenuto in B o che

A è un sottoinsieme di B, in simboli A ⊂ B se

∀ x ∈ A.x ∈ B.

Diremo anche che B contiene A, in simboli B ⊃ A. Altre notazioni usate sono

A ⊆ B e B ⊇ A. Se vogliamo indicare che A è strettamente contenuto in B cioè

(∀ x ∈ A.x ∈ B) ∧ (∃ y ∈ B.y < A)

scriveremo A ( B o B ) A. Ad esempio

N ⊂ Z ⊂ Q ⊂ R.

Più precisamente
N ( Z ( Q ( R.
Il principio di estensionalità afferma

(A ⊂ B ∧ B ⊂ A) ⇒ A = B.
df
• L’insieme vuoto: ∅ = {x ∈ U | x , x} è l’insieme privo di elementi. Per ogni
insieme A ∈ I si ha che ∅ ⊂ A.
• Sia A un insieme. L’insieme delle parti P(A) di A è l’insieme i cui elementi sono
i sottoinsiemi di A:
df
P(A) = {x ∈ I | x ⊂ A}.

Definizione 1.1.4. Siano A e B due insiemi.

• L’intersezione di A e B:
df
A ∩ B = {x ∈ A | x ∈ B} = {x ∈ B | x ∈ A} = {x ∈ U | x ∈ A ∧ x ∈ B}.

Gli insiemi A e B sono disgiunti se A ∩ B = ∅.

df
• L’unione di A e B: A ∪ B = {x ∈ U | x ∈ A ∨ x ∈ B}.
df
• La differenza di A da B: B r A = {x ∈ B | x < A} = {x ∈ U | x ∈ B ∧ x < A}.
Se A ⊂ B chiameremo la differenza B r A il complementare di A in B, in
simboli {B (A).

5
Proposizione 1.1.5. Siano A, B e C sottoinsiemi di X. Allora
(A ∩ B) ∩ C =A ∩ (B ∩ C), Proprietà associativa dell’intersezione.
A∩B =B ∩ A, Proprietà commutativa dell’intersezione.
(A ∪ B) ∪ C =A ∪ (B ∪ C), Proprietà associativa dell’unione.
A∪B =B ∪ A, Proprietà commutativa dell’unione.
A ∩ (B ∪ C) =(A ∩ B) ∪ (A ∩ C), Proprietà distributiva dell’intersezione
rispetto all’unione.
A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C), Proprietà distributiva dell’unione
rispetto all’intersezione.
Valgono inoltre le formule di De Morgan

{X (A ∩ B) = {X (A) ∪ {X (B), {X (A ∪ B) = {X (A) ∩ {X (B).

Dimostrazione. Lasciata come esercizio per il Lettore. 

Definizione 1.1.6. Assumiamo come ben definito il concetto di coppia (a, b),
tripla (a, b, c) e, in generale, di n-upla (a1 , . . . , an ) come sequenza ordinata di
elementi. Tali elementi vengono detti componenti.
Siano A e B insiemi. Il prodotto cartesiano A × B di A e B è definito da
df
A × B = {(a, b) | a ∈ A ∧ b ∈ B}.

Si ha la relazione
A×B=∅ ⇔ A = ∅ ∨ B = ∅.
• Per tre insiemi A, B, C si pone
df
A × B × C = {(a, b, c) | a ∈ A ∧ b ∈ B ∧ c ∈ C}.

• In generale se si hanno n insiemi A1 , A2 , . . . , An poniamo

df
A1 × A2 × · · · An = {(a1 , a2 , . . . , an ) | ∀ i ∈ {1, . . . , n}.ai ∈ Ai }.

Useremo anche la notazione

n
Y
Ai
i=1

al posto di A1 × A2 × · · · An .

6
 Quando i fattori sono tutti uguali (cioè A1 = A2 = A3 = · · · ) si usano le
“potenze”
df
A2 = A × A, coppie
df
A3 = A × A2 , triple
.. ..
. .
n df
A = A × An−1 , n-uple
.. ..
. .

Pertanto
An = {(x1 , . . . , xn ) | ∀ i ∈ {1, . . . , n}.xi ∈ A}.
df
Si pone, infine, A1 = A (interpretando gli elementi x ∈ A come 1-uple (x)) e
df
A0 = {( )} “0-upla senza componenti”o anche A0 = {∅}, il singoletto che ha
come elemento l’insieme vuoto.

1.2 Relazioni ed funzioni

Definizione 1.2.1. Siano A e B insiemi. Un sottoinsieme R ⊂ A × B si dice
relazione da A in B. Per indicare che (x, y) ∈ R useremo anche la notazione x R y.
Una relazione R ⊂ A × A si dice totale se R = A × A. La relazione R = {(x, y) ∈
A × A | x = y} si dice relazione diagonale.
Sia R ⊂ A × B una relazione. La relazione opposta è l’insieme
df
R◦ = {(y, x) ∈ B × A | x R y}.

1.2.1 Funzioni
Definizione 1.2.2. Siano A e B insiemi. Una relazione f ⊂ A × B si dice funzione
o applicazione o, ancora, mappa da A a B e si scrive

f: A→B

se
∀ x ∈ A.∃! y ∈ B.(x, y) ∈ f.
Useremo per lo più la notazione di Eulero y = f (x), per cui

(x, y) ∈ f ⇔ y = f (x).

7
Se (x, y) ∈ f , chiameremo x argomento di f e y valore di f sull’argomento x o
immagine di x mediante f . La scrittura Euleriana di una funzione f : A → B,
y = f (x) ci porta a definire grafico di f l’insieme

{(x, y) ∈ A × B | y = f (x)},

che null’altro è che la definizione di f come relazione.

L’insieme A (cioè l’insieme degli argomenti) viene detto dominio di f e B
codominio. L’insieme dei valori di f è detto l’immagine di f ed indicato con f (A):
df
f (A) = {y ∈ B | ∃ x ∈ A.y = f (x)} = { f (x) ∈ B | x ∈ A}.

Più in generale se C è un sottoinsieme del dominio A l’immagine di C mediante

f è l’insieme
df
f (C) = {y ∈ B | ∃ x ∈ C.y = f (x)} = { f (x) ∈ B | x ∈ C}.

Scriveremo sempre f (x) per indicare f ({x}).

Se D è un sottoinsieme del codominio B la controimmagine di D è l’insieme
df
f −1 (D) = {x ∈ A | ∃ y ∈ D. f (x) = y} = {x ∈ A | f (x) ∈ D}.

In particolare se D è un singoletto {y} allora useremo la notazione f −1 (y) al

posto di f −1 ({y}).

Definizione 1.2.3. Una funzione f : A → B è iniettiva se

∀ x ∈ A.∀ x0 ∈ A.( f (x) = f (x0 ) ⇒ x = x0 ).

Una funzione f : A → B è surgettiva o suriettiva se

∀ y ∈ B.∃ x ∈ A.y = f (x).

Una funzione sia iniettiva che surgettiva è detta bigettiva o biiezione o corrispon-
denza biunivoca. Intal caso si ha

∀ y ∈ B.∃! x ∈ A.y = f (x).

Una funzione f : A → B è costante se f (A) è un singoletto cioè f (A) = {b} per un

b ∈ B; in altre parole
∃! b ∈ B.∀ x ∈ A. f (x) = b.

8
Definizione 1.2.4. Dato un insieme A la funzione idA identità di A è la relazione
diagonale su A ossia
idA = {(x, y) ∈ A × A | x = y}.
Con la simbologia Euleriana idA : A → A, ∀ x ∈ [Link] (x) = x. L’identità idA è
chiaramente una funzione bigettiva.
Siano dati una funzione f : A → B e un sottoinsieme D ⊂ A. Chiameremo
restrizione di f a D la funzione f |D : D → B definita da
∀ x ∈ D. f |D (x) = f (x).
Si può considerare la restrizione all’immagine di f , cioè pensare f : A → f (A); in
tal caso f diventa ovviamente surgettiva.
Se A è un sottoinsieme di B la funzione i : A → B, i(x) = x, è detta inclusione
di A in B. Questa funzione è iniettiva ma non surgettiva a meno che che
A = B, nel qual caso è idA . Spesso indicheremo l’inclusione di A in B scrivendo
semplicemente A ,→ B.
Esempio 1.2.5. Consideriamo la funzione parte intera p.i. : R → R (più spesso
useremo la notazione [x] per indicare p.i.(x)) definita da
∀ x ∈ R.∀ n ∈ Z.n ≤ x ⇒ n ≤ p.i.(x),
ossia p.i.(x) è il più grande intero ≤ x. Allora p.i.(R) = Z, p.i.|Z = idZ e
p.i. : R → Z è surgettiva.
Osservazione 1.2.6. Siano A, B e C tre insiemi. Si possono considerare il
prodotti
X = A × B × C, Y = (A × B) × C, Z = A × (B × C).
Gli insiemi X, Y e Z sono tre insiemi distinti, infatti
A × B × C = {(a, b, c) | a ∈ A ∧ b ∈ B ∧ c ∈ C}
(A × B) × C = {((a, b), c) | (a, b) ∈ A × B ∧ c ∈ C}
A × (B × C) = {(a, (b, c)) | a ∈ A ∧ (b, c) ∈ B × C}.
D’altronde le mappe
f : A × B × C → (A × B) × C, f (a, b, c) = ((a, b), c)
g : A × B × C → A × (B × C), f (a, b, c) = (a, (b, c))
h : (A × B) × C → A × (B × C), h((a, b), c) = (a, (b, c)),
sono bigettive. Queste considerazioni si estendono facilmente al prodotto di un
numero arbitrario di insiemi. Quindi “a meno di spostamento, eliminazione
o aggiunta di parentesi” il prodotto di insiemi è associativo.

9
• Siano A e B sono due insiemi allora i prodotti A × B e B × A sono insiemi
distinti, infatti

A × B = {(a, b) | a ∈ A ∧ b ∈ B}
B × A = {(b, a) | b ∈ B ∧ a ∈ A}.

D’altronde la mappa

f : A × B → B × A, f (a, b) = (b, a)

è bigettiva. Queste considerazioni si estendono facilmente al prodotto di un

numero arbitrario di insiemi. Quindi “a meno di scambio di posizione delle
componenti” il prodotto di insiemi è commutativo.

Esempio 1.2.7. Sia A un insieme e {∗} un singoletto. Allora le mappe

prA : A × {∗} → A, prA (a, ∗) = a

prA : {∗} × A → A, prA (∗, a) = a
i∗ : A → A × {∗} i∗ (a) = (a, ∗),
i∗ : A → {∗} × A i∗ (a) = (∗, a),

sono bigettive.

Definizione 1.2.8. Dati due insiemi A e B le relazioni

df
prA = {(x, y, z) ∈ (A × B) × A | z = x}
df
prB = {(x, y, z) ∈ (A × B) × B | z = y}

sono funzioni; chiamiamo prA proiezione sul primo fattore e prB proiezione sul
secondo fattore. Con la simbologia Euleriana

prA : A × B → A, ∀ (x, y) ∈ A × [Link] (x, y) = x,

prB : A × B → B, ∀ (x, y) ∈ A × [Link] (x, y) = y.

Le proiezioni sono funzioni surgettive ma, in generale non iniettive (a meno

che A o B non siano singoletti, cfr. Esempio 4)).
• Dati due insiemi A e B. Per ogni b ∈ B definiamo le relazioni

ib = {(x, y, z) ∈ A × (A × B) | x = y ∧ z = b}.

10
Tali relazioni sono funzioni: ib : A → A×B, ∀ x ∈ [Link] (x) = (x, b). Analogamente,
per ogni a ∈ A si hanno le funzioni

ia : B → A × B, ∀ y ∈ [Link] (y) = (a, y).

Tali mappe sono iniettive ma in generale non surgettive (a meno che A o B non
siano singoletti, cfr. Esempio 4)).
• Sia A un insieme. La diagonale di A è il sottoinsieme

∆A = {(x, y) ∈ A × A | a = b}.

La funzione i∆A : A → A × A, ∀ x ∈ A.i∆A (x) = (x, x) è detta immersione diagonale.

È iniettiva ma non surgettiva (a meno che A non sia un singoletto).
• Siano f : A → B e g : C → D due applicazioni. Definiamo il prodotto f × g
come la mappa

f × g : A × C → B × D, ( f × g)(x, y) = ( f (x), g(y)).

È facile (esercizio per il Lettore) provare le seguenti implicazioni:

• Se f e g sono iniettive allora f × g è iniettiva.

• Se f e g sono surgettive allora f × g è surgettiva.

• Se f e g sono bigettive allora f × g è bigettiva.

Definizione 1.2.9. Siano I e X due insiemi non vuoti. “Etichettare” degli

elementi di X mediante gli elementi di I significa dare una funzione f : I → X,
non necessariamente iniettiva o surgettiva nel senso che possiamo dare più
“etichette” a uno stesso elemento di X e non dare alcuna etichetta a qualche
elemento di X. Con questa accezione si suole indicare l’immagine f (i) per ogni
i ∈ I con xi .
• Se I = N una funzione f : N → X o ( f : N∗ → X) viene detta semplicemente
successione in X e quasi√sempre denotata l’immagine
√ f (n) con xn . Ad esempio
se X = R e f (n) = 2 + n, scriveremo xn = 2 + n e avremo
n n

√ √
x0 = 1, x1 = 3, x2 = 4 + 2, x3 = 8 + 3, . . . ,

o √ √
x1 = 3, x2 = 4 + 2, x3 = 8 + 3, . . . ,
se f : N∗ → R.

11
• Un insieme di insiemi A può essere descritto come una famiglia di insiemi
indiciati su un insieme I se diamo una funzione surgettiva f : I → A. Allora ogni
elemento A di A verrà indicato con Ai se f (i) = A. Porremo quindi

A = {Ai }i∈I

• Generalizziamo la Definizione 1.1.4 alla famiglia A:

\ df
Ai = {x ∈ U | ∀ i ∈ I.x ∈ Ai }, intersezione della famiglia A.
i∈I
[ df
Ai = {x ∈ U | ∃ i ∈ I.x ∈ Ai }, unione della famiglia A.
i∈I

Ad esempio sia, per k ∈ N, k ≥ 2, Ak = {nk | n ∈ N∗ }, ossia A2 è [

l’insieme
dei quadrati dei numeri naturali, A3 dei cubi e cosı̀ via. Allora Ak è
k≥2,k∈N
∗
un
\sottoinsieme proprio di N (l’insieme non contiene alcun numero primo) e
Ak = ∅. Vedremo più avanti le stringhe che sono un esempio importante
k≥2,k∈N
di unioni di insiemi indiciati sui numeri naturali.

Definizione 1.2.10. Siano date due funzioni f : A → B e g : B → C. La compo-

sizione di f e g è la relazione

g ◦ f = {(x, z) ∈ A × C | ∃ y ∈ B.[(x, y) ∈ f ∧ (y, z) ∈ g]}.

Si verifica subito che g ◦ f è una funzione A → C e che ∀ a ∈ A si ha

(g ◦ f )(a) = g( f (a)).

f g
A / B /7 C

g◦ f

È facile (esercizio per il Lettore) provare le seguenti implicazioni:

• Se f e g sono iniettive allora g ◦ f è iniettiva.

• Se f e g sono surgettive allora g ◦ f è surgettiva.

• Se f e g sono bigettive allora g ◦ f è bigettiva.

Proposizione 1.2.11. Sia f : A → B una funzione. Sono equivalenti i seguenti fatti.

12
 i) f è bigettiva.

ii) Esiste una ed una sola funzione g : B → A tale che g ◦ f = idA e f ◦ g = idB .

La funzione g : B → A è detta la funzione inversa di f e viene indicata con f −1 .

Reciprocamente, f è la funzione inversa di g.

Dimostrazione. Se f è bigettiva defineremo, per ogni b ∈ B, g(b) = a dove

f (a) = b. Allora g è una funzione B → A e

– ∀ a ∈ A.(g ◦ f )(a) = g( f (a)) = a,

– ∀ b ∈ B.( f ◦ g)(b) = f (g(b)) = f (a) = b.

Pertanto g è univocamente definita. Viceversa supponiamo che esista una

funzione g : B → A tale che g ◦ f = idA e f ◦ g = idB . Proviamo che f è iniettiva:
se, per a, a0 ∈ A si ha f (a) = f (a0 ) allora a = g( f (a)) = g( f (a0 )) = a0 da cui a = a0 .
Proviamo che f è surgettiva: ∀ b ∈ B si ha f (g(b)) = b ossia f −1 (b) , ∅. 

1.2.2 Relazioni d’equivalenza

Definizione 1.2.12. Una relazione R ⊂ A × A si dice di equivalenza se è:

• riflessiva, cioè ∀ a ∈ A.(a, a) ∈ R;

• simmetrica, cioè ∀ (a, b) ∈ R ⇒ (b, a) ∈ R;

• transitiva, cioè ∀ (a, b) ∈ R ∧ ∀ (b, c) ∈ R ⇒ (a, c) ∈ R.

La relazione totale e la relazione diagonale sono relazioni d’equivalenza. Gen-

eralmente, per le relazioni d’equivalenza, si usa il simbolo ∼ al posto di R per
cui porremo
a ∼ b ⇔ a R b.
Per ogni a ∈ A definiamo la classe di equivalenza di a come il sottoinsieme [a] di
A definito da
[a] = {b ∈ A | b ∼ a}.
Per la proprietà transitiva due classi di equivalenza o coincidono o sono dis-
giunte. Le classi di equivalenza di una relazione d’equivalenza costituiscono
quindi una partizione dell’insieme A nel senso che
[
A= [a]
a∈A

13
e le classi distinte sono tra loro tutte disgiunte.
L’insieme i cui elementi sono le classi d’equivalenza di una relazione d’equivalenza
R è detto insieme quoziente e verrà denotato con A/R (o con A/ ∼ se usiamo ∼ al
posto di R). Ogni elemento di una classe di equivalenza è detto rappresentante
della classe.

Osservazione 1.2.13 (Importante). Ogni affermazione relativa ad un insieme

quoziente A/ ∼ enunciata mediante gli elementi di A deve essere indipendente
dalla scelta dei rappresentanti delle classi. Vedremo nella Definizione 2.1.11
un esempio in tal senso.

Esempio 1.2.14. Sia n un intero ≥ 1 fissato. La relazione ∼ su Z definita da:

∀ x, y ∈ Z.x ∼ y ⇔ ∃ k ∈ Z.x − y = kn,

è una relazione d’equivalenza. Se n = 1 la relazione è quella totale. Se n ≥ 2

l’insieme Z è unione di n classi di equivalenza distinte:

Z = [0] ∪ [1] ∪ · · · ∪ [n − 1],

poichè ogni intero x è equivalente al resto della divisione di x per n, pertanto

le classi [0], [1], . . . , [n − 1] sono dette le classi di resto modulo n.
L’insieme quoziente Z/ ∼ viene più spesso denotato con Zn , per cui

Zn = {[0], [1], . . . , [n − 1]}.

Per questa relazione d’equivalenza si suole usare la notazione

x ≡ y (mod q)

al posto di x ∼ y.

Esempio 1.2.15. Sull’insieme Z × (Z r {0}) definiamo la relazione

(x, y) ∼ (z, t) ⇐⇒ xt = yz.

Tale relazione è d’equivalenza.

• è riflessiva: (x, y) ∼ (x, y) poichè xy = yx;

• è simmetrica: se (x, y) ∼ (z, t) allora xt = yz, quindi zy = tx cioè (z, t) =

(x, y);

14
 • è transitiva: se (x, y) ∼ (z, t) e (z, t) = (u, v) allora xt = yz e zv = tu. Se
x , 0 allora z , 0 e u , 0 (y, t e v sono non nulli per ipotesi), pertanto
moltiplicando ambo i membri dell’uguaglianza xt = yz per uv (che è , 0)
otteniamo xtuv = yzuv ossia (xv)(tu) = (yu)(zv). Poichè tu = zv si ha
xv = yu cioè (x, y) ∼ (u, v). Se x = 0 allora z = 0 e u = 0 e certamente
xv = 0 = yu per cui ancora si ha (x, y) ∼ (u, v).

È allora immediato vedere che la mappa

x
φ : ([Z × (Z r {0})]/ ∼) → Q, φ([(x, y)]) =
y

è bigettiva.

1.2.3 Cardinalità
Definizione 1.2.16. Diremo che due insiemi A e B sono equipotenti, se esiste una
funzione f : A → B bigettiva o, equivalentemente per la Proposizione 1.2.11, se
esiste una funzione g : B → A bigettiva. Se non vogliamo specificare la funzione
bigettiva ma dire semplicemente che A e B sono equipotenti scriveremo

A ←→ B. (1.2.1)

La relazione di equipotenza è una relazione di equivalenza su I. Infatti

• ogni insieme A è equipotente a se stesso mediante l’identità idA ;

• Se A è equipotente a B allora B è equipotente ad A per la Proposizione

1.2.11;

• Se A è equipotente a B mediante una mappa bigettiva f : A → B e B

è equipotente a C mediante una mappa bigettiva g : B → C allora A è
equipotente a C mediante la mappa bigettiva g ◦ f : A → C.

Se due insiemi A e B sono equipotenti cioè stanno nella stessa classe di

equivalenza rispetto alla relazione di equipotenza scriveremo, in alternativa
alla (1.2.1),
](A) = ](B)
e chiameremo il simbolo ](A) il numero cardinale di A. Il numero cardinale ](A)
è “l’etichetta” che individua la classe di equipotenza di A. Il numero cardinale
](N) di N viene solitamente indicato con ℵ0 .

15
Notazioni. Sia n ∈ N, definiamo per ogni n ≥ 1
df
n = {m ∈ N : m < n} = {0, 1, . . . , n − 1}.

Inoltre poniamo 0 = ∅.

Definizione 1.2.17. Diremo che un insieme A è infinito se esiste un sottoinsieme

proprio B ( A equipotente ad A. Diremo che un insieme A è finito se non è
infinito. Chiameremo numerabile un insieme A tale che ](A) = ℵ0 . Un insieme
infinito non numerabile sarà detto più che numerabile. Tale locuzione deriva dal
fatto che “N è l’insieme infinito più piccolo” nel senso che può provare che
ogni insieme infinito X contiene strettamente un sottoinsieme numerabile.

I sottoinsiemi finiti sono caratterizzati dalle seguente

Proposizione 1.2.18. Un insieme A è un finito se e solo se è equipotente a n per solo

n ∈ N e siffatto numero naturale n è unico. In tal caso poniamo

](A) = n “il numero degli elementi di A”.

In particolare ](∅) = 0. Pertanto se A e B sono insiemi finiti, ](A) = n e ](B) = m,

allora ](A) = ](B) se e solo se n = m.

Dimostrazione. Si veda R-P, Lemma A.7.1 (pp. 73-74) che utilizza il principio
d’induzione qui sotto enunciato) per l’unicità. 
Enunciamo in tre forme equivalenti la proprietà fondamentale dei numeri
naturali (vedere R-P, A.7, pp. 73-76).

Proposizione 1.2.19. Sono equivalenti le seguenti affermazioni.

Principio d’induzione. Sia A ⊂ N (rispettivamente A ⊂ N∗ ) un insieme di numeri
naturali tale che

• 0 ∈ A (rispettivamente 1 ∈ A)

• se n ∈ A allora n + 1 ∈ A.

Allora A = N (rispettivamente A = N∗ ).
Principio della discesa infinita. Sia A ⊂ N (rispettivamente A ⊂ N∗ ) un insieme
di numeri naturali tale che

• 0 < A (rispettivamente 1 < A)

• se n ∈ A allora esiste k ∈ A tale che k < n.

16
Allora A = ∅.
Principio del minimo. Sia A ⊂ N (rispettivamente A ⊂ N∗ ) un sottoinsieme non
vuoto di numeri naturali. Allora A ha un elemento minimo cioè

∃ k ∈ A.∀x ∈ A.k ≤ x.

Esempio 1.2.20. 1) L’applicazione f : N → N∗ , f (n) = n + 1 è bigettiva, pertanto

N e N∗ sono equipotenti. Più in generale se k è un numero naturale fissato la
mappa g : N → {m ∈ N | m ≥ k}, g(n) = n + k è bigettiva.
2) L’applicazione α : N∗ → Z definita da
(
n/2 se n è pari
α(n) =
−(n − 1)/2 se n è dispari

è bigettiva quindi Z è equipotente a N∗ . Pertanto la mappa α ◦ f : N → Z è

bigettiva, pertanto N e Z sono equipotenti.
Esempio 1.2.21. L’applicazione ϕ : N∗ × N∗ → N∗
1
ϕ(n, m) = n + (n + m − 1)(n + m − 2)
2
è bigettiva. Dalla Definizione 1.2.8 si ha che l’applicazione ψ : N × N → N
1
ψ(n, m) = n + (n + m + 1)(n + m)
2
è bigettiva.
Dimostrazione. Utilizzando il principio d’induzione si ha subito che ϕ è
surgettiva. Infatti 1 = ϕ(1, 1) e 2 = ϕ(1, 2). Se m ≥ 2 e ϕ(n, m) = k allora
k + 1 = ϕ(n + 1, m − 1). Se k = ϕ(n, 1) allora k + 1 = ϕ(1, n + 1).
L’iniettività si verifica direttamente. Analizziamo i tre casi possibili.
Primo caso: n1 ≤ n2 e m1 < m2 . Allora

(n1 + m1 − 1)(n1 + m1 − 2) < (n2 + m2 − 1)(n2 + m2 − 2)

da cui ϕ(n1 , m1 ) < ϕ(n2 , m2 ).

Secondo caso: n1 < n2 e m1 ≤ m2 . Allora

(n1 + m1 − 1)(n1 + m1 − 2) < (n2 + m2 − 1)(n2 + m2 − 2)

da cui
1 1
n1 + (n1 + m1 − 1)(n1 + m1 − 2) < n2 + (n2 + m2 − 1)(n2 + m2 − 2)
2 2

17
cioè ϕ(n1 , m1 ) < ϕ(n2 , m2 ).
Rimangono due casi: n1 < n2 , m1 > m2 e n1 > n2 , m1 < m2 . Procediamo per
assurdo e supponiamo che ϕ(n1 , m1 ) = ϕ(n2 , m2 ) cioè

1 1
n1 + (n1 + m1 − 1)(n1 + m1 − 2) = n2 + (n2 + m2 − 1)(n2 + m2 − 2) (1.2.2)
2 2
Terzo caso: n1 < n2 e m1 > m2 . Posto n2 = n1 + a con a ∈ N∗ e m1 = m2 + b con
b ∈ N∗ da (1.2.2) ne deriva

1 1
n1 + (n1 + m2 + b − 1)(n1 + m2 + b − 2) = n1 + a + (n1 + m2 + a − 1)(n1 + m2 + a − 2)
2 2
e quindi

(n1 + m2 + b − 1)(n1 + m2 + b − 2) = 2a + (n1 + m2 + a − 1)(n1 + m2 + a − 2), (1.2.3)

palesemente assurda se a ≥ b. Se a < b allora b = a + c con c ∈ N∗ . Posto per

comodità di scrittura k = n1 + m2 > 1 da (1.2.3) otteniamo

2ck = 3c − c2 − 2ac + 2a. (1.2.4)

Se c = 1 si ha 2k = 2 e quindi k = 1 che è assurdo. Se c ≥ 2 allora il membro a

sinistra di (1.2.4) è > 0 mentre quello a destra è ≤ 0: assurdo.
Quarto caso: n1 > n2 , m1 < m2 . Posto n1 = n2 + a con a ∈ N∗ e m2 = m1 + b con
b ∈ N∗ da (1.2.2) avremo

2a + (n2 + m1 + a − 1)(n2 + m1 + a − 2) = (n2 + m1 + b − 1)(n2 + m1 + b − 2)

e procedendo come per (1.2.3) si arriva ancora ad un assurdo. 

Osservazione 1.2.22. Dall’Esempio 1.2.21 si può dedurre che l’insieme dei

numeri razionali Q è equipotente a N cioè che Q è numerabile. Per tale
scopo si può utilizzare il seguente fondamentale teorema la cui dimostrazione
omettiamo perchè è assai complicata:

Teorema 1.2.23 (Cantor-Bernstein). Siano A e B due insiemi. Se esistono due mappe

iniettive f : A → B e g : B → A allora esiste una mappa bigettiva h : A → B, cioè A e
B sono equipotenti.

Osservazione 1.2.24. In riferimento all’Esempio 1.2.21 si osservi che se A e B

sono insiemi finiti, ](A) = n e ](B) = m, allora ](A × B) = nm, quindi a meno che
A o B non sia un singoletto, A × B non è equipotente nà ad A nè a B.

18
Definizione 1.2.25. Siano A e B due insiemi. Denoteremo l’insieme delle funzioni
da A in B con BA :
df
BA = { f ∈ P(A × B) | ∀ x ∈ A.∃ b ∈ B.[x f y ∧ ∀ z ∈ B.(x f z ⇒ y = z)]}
= { f : A → B}.

Se B = {0, 1} si è soliti indicare con 2X l’insieme {0, 1}A = { f : X → {0, 1}}.

Proposizione 1.2.26. Se X è un insieme non vuoto non esiste alcuna mappa surgettiva
f : X → P(X). In particolare X e P(X) non sono equipotenti.
Dimostrazione. Supponiamo per assurdo che esista un’applicazione surget-
tiva f : X → P(X). Sia
S = {x ∈ X : x < f (x)}.
L’insieme S può essere anche vuoto. Sia s ∈ X tale che f (s) = S. Se s ∈ S
allora s < f (s) = S. Se s < S = f (s) allora s ∈ f (s) = S. In ogni caso si ha una
contraddizione. 
Proposizione 1.2.27. Siano X un insieme. Allora P(X) è equipotente a 2X .
Dimostrazione. Sia ϕ : 2X → P(X) definita da ϕ( f ) = f −1 (1). L’applicazione
ϕ è surgettiva infatti se A ⊂ X e

1 se x ∈ A

χA (x) = 

0 se x < A


è la funzione caratteristica di A, allora ϕ(χA ) = A. L’applicazione ϕ è iniettiva

infatti se f , g allora esiste x ∈ X tale che f (x) , g(x). Pertanto x apparterrà
solo ad uno dei due insiemi f −1 (1), g−1 (1). 
Lemma 1.2.28. Siano A = {a1 , . . . , an } un insieme con n elementi e B un insieme
finito. Allora la corrispondenza

ϕ : BA → B × B × · · · × B, ϕ( f ) = ( f (a1 ), f (a2 ), . . . , f (an ))

| {z }
n volte

è biunivoca. In particolare gli insiemi Bn = { f : n → B} e Bn sono equipotenti.

Dimostrazione. Esercizio per il Lettore. 
Corollario 1.2.29. Se A e B sono insiemi finiti allora A × B e BA sono insiemi finiti e

](A × B) = ](A) · ](B), ](BA ) = (](B))](A) .

19
Dimostrazione. Basta provare, per il Lemma 1.2.28, che ](A × B) = ](A) · ](B)
ma ciò è evidente. 

Corollario 1.2.30. Sia X un insieme di cardinalità ](X) = n ∈ N, allora

](P(X)) = 2n .

Dimostrazione. Segue subito dalla Proposizione 1.2.27 e dal Lemma 1.2.29.



Proposizione 1.2.31. L’insieme R dei numeri reali è più che numerabile.

Dimostrazione. Assumiamo il seguente fatto: R è in corrispondenza biuni-

voca con P(N) (corrispondenza fornita dalla rappresentazione decimale dei
numeri reali). Allora, per la Proposizione 1.2.26, R non può essere equipotente
a N. 

Figura 1.1:

b• y= b−a
2
x + b+a
2

•a
• • x
−1 1

20
Proposizione 1.2.32. Ogni intervallo non ridotto ad un punto di R è equipotente a
R.
Dimostrazione. Siano a e b due numeri reali tali che a < b. La funzione
f : R → R definita da
b−a b+a
f (x) = x+
2 2
è bigettiva. La funzione f induce una corrispondenza biunivoca tra (Figura
1.1)
• l’intervallo aperto (−1, 1) e l’intervallo aperto (a, b);
• l’intervallo chiuso [−1, 1] e l’intervallo chiuso [a, b];
• l’intervallo semiaperto [−1, 1) e l’intervallo semiaperto [a, b);
• l’intervallo semiaperto (−1, 1] e l’intervallo semiaperto (a, b];
• l’intervallo illimitato aperto (−1, +∞) e l’intervallo illimitato aperto (a, +∞);
• l’intervallo illimitato aperto (−∞, 1) e l’intervallo illimitato aperto (−∞, b);
• l’intervallo illimitato chiuso [−1, +∞) e l’intervallo illimitato chiuso [a, +∞);
• l’intervallo illimitato chiuso (−∞, 1] e l’intervallo illimitato chiuso (−∞, b].
La mappa g : R → R, g(x) = −x, è bigettiva e induce una corrispondenza
biunivoca tra gli intervalli
• [−1, 1) e (−1, 1],
• (−1, +∞) e (−∞, 1),
• [−1, +∞) e (−∞, 1].
Utilizzando il teorema di Cantor Bernstein per le inclusioni (−1, 1) ,→ [−1, 1],
[−1, 1) ,→ [−1, 1], (−1, 1] ,→ [−1, 1] e (−1, 1) ,→ (−2, 2) e già sapendo che (−1, 1)
è equipotente a (−2, 2), otteniamo l’equipollenza tra gli intervalli

(−1, 1), [−1, 1], [−1, 1), (−1, 1].

Infine la mappa h : R → (−1, 1) data da

x
h(x) =
1 + |x|
è bigettiva. La tesi segue subito per la transitività dell’equipotenza. 

21
1.2.4 Relazioni d’ordine
Definizione 1.2.33. Sia X un insieme. Una relazione R su X è detta preordine se

i) ∀ x ∈ X.x R x, cioè R è riflessiva,

ii) ∀ x.y, z ∈ X.(x R y ∧ y R z ⇒ x R z), cioè R è transitiva.

Per le relazioni di preordine useremo la notazione x J y al posto di x R e diremo

che x precede y o che y segue x. Un insieme X è preordinato se è dotato di un
definito preordine J; in tal caso scriveremo (X, J).
• Un preordine J in X è detto ordine parziale se

∀ x, y ∈ X.(x J y ∧ y J x ⇒ x = y), cioè R è antisimmetrica.

Un insieme X è parzialmente ordinato (in inglese “poset”) se è dotato di un

definito ordine parziale. Due elementi x, y ∈ X sono confrontabili se x J y∨y J x.
• Un ordine parziale J in X è detto ordine totale (o anche ordine lineare) se tutti
gli elementi sono confrontabili cioè se

∀ x, y ∈ X.(x J y ∨ y J x).

Un insieme X è totalmente ordinato se è dotato di un definito ordine totale.

Esempi 1.2.34. 1) La relazione “minore o uguale” x ≤ y sui numeri reali è un

ordine totale. Osserviamo che la relazione “minore (stretto) ” x < y sui numeri
reali non è un preordine in quanto non riflessiva.
2) La relazione diagonale su un insieme X è un ordine parziale ma non totale.
3) La relazione su C: z J w se e solo se |z| ≤ |w| è un preordine ma non è un
ordine parziale.
4) Sia X un insieme. La relazione su P(X): A J B se e solo se A ⊂ X è un ordine
parziale ma non totale (a meno che X non sia un singoletto).
5) La relazione su N∗ : n J m se e solo se n | m è un ordine parziale ma non
totale.

Definizione 1.2.35. Siano dati n insiemi parzialmente ordinati

(A1 , J1 ), . . . , (An , Jn ).

Sul prodotto cartesiano A1 × · · · × An è definito l’ordine lessicografico lex ;


a1 J1 b1 a1 , b1

(a1 , . . . , an ) lex (b1 , . . . , bn ) ⇐⇒ 

ak+1 Jk+1 bk+1 a j = b j , j = 1, . . . , k.


22
Se tutti gli insiemi Ai sono totalmente ordinati allora (A1 × · · · × An , lex ) è
totalmente ordinato.
Sul prodotto cartesiano A1 × · · · × An è definito altresı̀ l’ordine prodotto Jpr :

(a1 , . . . , an ) Jpr (b1 , . . . , bn ) ⇐⇒ ai Ji bi , i = 1, . . . , n.

Definizione 1.2.36. Sia (X, J) un insieme parzialmente ordinato e sia Y ⊂ X. Se

poniamo, per ogni a, b ∈ Y

a JY b ⇐⇒ a J b

allora JY è un ordine parziale su Y detto l’ordine indotto su Y. Diremo che Y è

una catena se JY è un ordine totale.
Ad esempio sia X = N∗ con l’ordine parziale n J m se e solo se n | m. Per
ogni a ∈ N∗ il sottoinsieme

Ya = {ak : k ∈ N}

è una catena.

Definizione 1.2.37. Sia (X, J) un insieme parzialmente ordinato e sia Y ⊂ X

non vuoto.

• Un elemento y è il minimo di Y se ∀ x ∈ Y.y J x; scriveremo y = min Y.

• Un elemento y è il massimo di Y se ∀ x ∈ Y.x J y; scriveremo y = max Y.

• Un elemento y è minimale di Y se ∀ x ∈ Y.(x J y ⇒ x = y).

• Un elemento y è il massimale di Y se ∀ x ∈ Y.(y J x ⇒ x = y).

Valgono i seguentii fatti

• Gli elementi minimo e massimo, se esistono, sono unici.

• Se esiste il minimo ogni elemento minimale coincide con il minimo.

Analogamente se esiste il massimo ogni elemento massimale coincide
con il massimo.

• Se J è un ordine totale esiste un elemento minimale se e solo se esiste il

minimo ed esiste un elemento massimale se e solo se esiste il massimo.

23
1) In (N, ≤) l’elemento minimo di N è 0 e non esiste l’elemento massimo.
Essendo ≤ un ordine totale non esistono elementi massimali.
2) In (Z<0 , ≤) l’elemento massimo di Z<0 è 0 e non esiste l’elemento minimo.
Essendo ≤ un ordine totale non esistono elementi minimali.
3) In (Z, ≤) non esiste nè massimo nè minimo di Z. Essendo ≤ un ordine totale
non esistono elementi minimali nè massimali.
4) In (P(X), ⊂) l’insieme vuoto ∅ è il minimo di P(X) e X è il massimo di P(X). Se
considero il sottoinsieme Y di P(X) costituito dai singoletti allora ogni elemento
di Y è sia minimale che massimale ma Y non ha nè massimo nè minimo.
5) Consideriamo la famiglia X = {An | n ∈ N, n ≥ 2} dei sottoinsiemi di Z

An = {m ∈ Z | m = nk, per un k ∈ Z}.

Allora (X, J), dove A J B ⇐⇒ A ⊂ B, è un insieme parzialmente ordinato.

Poichè se n e q sono interi ≥ 2

An ⊂ Aq ⇐⇒ q | n,

gli elementi An con n numero primo sono massimali di X. Non vi sono elementi
minimali. Non vi è l’elemento massimo, nè minimo.
5) Sia (X, J) un insieme parzialmente ordinato e finito, allora ogni Y ⊂ X ha
elementi massimali e minimali. Si consideri il seguente esempio:

X = {0, 1, 2, 3, ω}; 0 J 1 J 2 J 3, ω J ω.

Allora (X, J) è poset ma Y = {0, ω} non ha nè massimo nè minimo ma 0 è

minimale e massimale e ω è minimale e massimale.
• Sia (X, J) un insieme parzialmente ordinato. L’ordine opposto J◦ a J è definito
da
∀ a, b ∈ X.(a J◦ b ⇐⇒ b J a).
È immediato verificare che J◦ è un ordine parziale. Gli eventuali massimali (il
massimo) per J diventano minimali (il minimo) per J◦ e viceversa.
Definizione 1.2.38. Sia (X, J) un insieme parzialmente ordinato e sia Y ⊂ X un
suo sottoinsieme.
• Un elemento z ∈ X è un minorante di Y se ∀ x ∈ Y.z J x.
• Un elemento z ∈ X è un maggiorante di Y se ∀ x ∈ Y.x J z.
• Un minorante z di Y è l’estremo inferiore di Y se l’insieme dei minoranti di
Y è non vuoto e z è il massimo dell’insieme dei minoranti di Y, se esiste;
scriveremo z = inf Y.

24
 • Un maggiorante z di Y è l’estremo superiore di Y se l’insieme dei maggio-
ranti di Y è non vuoto e z è il minimo dell’insieme dei maggioranti di Y,
se esiste; scriveremo z = sup Y.

È immediato notare che se inf Y ∈ Y allora inf Y = min Y. Parimenti se sup Y ∈ Y

allora sup Y = max Y.

Esempi 1.2.39. 1) In (R, ≤) l’intervallo Y = (0, 1) non ha massimo nè minimo;

l’insieme dei minoranti di Y è l’intervallo (−∞, 0] e l’insieme dei maggioranti
di Y è [1, +∞) per cui 0 = inf Y e 1 = sup Y.
2) In (R, ≤) l’intervallo Y = [0, 1] ha massimo 1 e minimo 0; l’insieme dei mino-
ranti di Y è l’intervallo (−∞, 0] e l’insieme dei maggioranti di Y è [1, +∞).
3) In (R r {0, 1}, ≤) sia Y l’intervallo (0, 1); l’insieme dei minoranti di Y è
l’intervallo (−∞, 0) e l’insieme dei maggioranti di Y è (1, +∞) per cui non
esistono nè inf Y nè sup Y.

Definizione 1.2.40. Sia (X, J) un insieme parzialmente ordinato. Diremo che

X è ben fondato se ogni sottoinsieme non vuoto di X ha un elemento minimale.
Non è difficile provare la seguente affermazione:

L’insieme (X, J) è ben fondato se e solo se non esiste una successione xn di

elementi di X tali che

∀ n ∈ N∗ .xn+1 J xn ∧ xn+1 , xn .

L’ insieme (N, +, 0) è ben fondato per la Proposizione 1.2.19.

Il seguente risultato, che enunciamo ma non dimostriamo, è il principio di

induzione strutturale o anche detto di induzione completa. Un caso particolare di
questo teorema è la Proposizione 1.2.19.

Teorema 1.2.41. Sia (X, J) un insieme ben fondato. Se ∀ x ∈ X

se x è minimale o se ∀ y J x.P(y) =⇒ P(x)

allora
∀ z ∈ X.P(z).
In altre parole per provare che una proprietà P vale per tutti gli x ∈ X basta provare
che P vale per ogni x ∈ X minimale e che, se P vale per ogni y J x, allora vale per x.

25
1.3 Calcolo combinatorio
• In questa sezione X indicherà un insieme finito con ](X) = n, un intero ≥ 1.
Definizione 1.3.1 (Permutazioni). Una permutazione di X è un’applicazione
bigettiva p : {1, 2, · · · , n} → X. Osservando che 1 ha n possibili immagini p(1)
e che fissato p(1) all’elemento 2 rimangono n − 1 scelte e cosı̀ via si conclude
facilmente che il numero delle permutazioni di X è
n(n − 1)(n − 2) · · · 2 · 1 (1.3.1)
questo numero viene indicato con n! e chiamato fattoriale di n o n fattoriale. Si
noti che sussiste la relazione
n! = n(n − 1)! (1.3.2)
valida per n > 1. Dato che il membro a sinistra di (1.3.2) ha senso anche per
n = 1 per rendere valida (1.3.2) anche per n = 1 si pone 0! = 1.
Indicheremo con Pn l’insieme delle permutazioni di un insieme di n ele-
menti.
Definizione 1.3.2 (Disposizioni). Sia k ≤ n. Chiameremo disposizione di classe
k di X un’applicazione iniettiva Dk : {1, 2, · · · , k} → X. Partendo da 1 che ha n
possibili immagini, fissato Dk (1) l’elemento 2 ha n − 1 scelte fino ad arrivare a
k che ha n − k + 1 scelte, quindi il numero delle disposizioni Dk è
n(n − 1) · · · (n − k + 1). (1.3.3)
Se k = n ovviamente le disposizioni Dk altro non sono che le permutazioni.
Indicheremo con Dn,k l’insieme delle disposizioni di classe k di un insieme
di n elementi.
Definizione 1.3.3 (Combinazioni). Sia k ≤ n. Chiameremo combinazione di
classe k di X ogni sottoinsieme Ck di X costituito da k elementi. Fissiamo
una combinazione Ck cioé un sottoinsieme di X costituito da k elementi. Il
numero delle permutazioni di Ck vale k!, quindi, se m è il numero di tutte le
combinazioni Ck il prodotto mk! fornisce tutte le disposizioni Dk di X. Pertanto
avremo mk! = n(n − 1) · · · (n − k + 1) da cui
n(n − 1) · · · (n − k + 1)
m= . (1.3.4)
k!
Il numero m viene indicato col simbolo
!
n
k

26
e chiamato, per ragioni che vedremo piú avanti, coefficiente binomiale o simbolo
binomiale. È immediato verificare che esiste la relazione seguente
!
n n!
= (1.3.5)
k k!(n − k)!
valida per tutti gli interi 1 ≤ k ≤ n. Tuttavia, poichè il membro di destra di
(1.3.5) ha significato anche per k = 0, per via della convenzione 0! = 1, e vale 1,
porremo !
n
= 1.
0
Il simbolo binomiale gode della seguente simmetria
! !
n n
= . (1.3.6)
k n−k
Indicheremo con Cn,k l’insieme delle combinazioni di classe k di un insieme
di n elementi.
Teorema 1.3.4 (Il teorema binomiale). Sia A un anello commutativo con identità.
Allora per ogni a, b ∈ A e per ogni n ∈ N∗ si ha
n !
X n n−k k
(a + b) =
n
a b.
k
k=0

Dimostrazione. È immediato osservare che il termine an−k bk si ottiene tante

volte quante sono le possibilità di scegliere k fattori nel prodotto
(a + b)(a + b) · · · (a + b);
| {z }
n volte
n

tale numero è, come sopra visto, k
. 
Corollario 1.3.5. Sia X un insieme di cardinalità ](X) = n, allora
](P(X)) = 2n .
Dimostrazione. Siano k ≤ h due numeri naturali. L’insieme dei sottoinsiemi !
h
di k elementi di un insieme di h elementi è dato dal coefficiente binomiale .
k
Pertanto se ](X) = n ∈ N avremo
n !
X n
](P(X)) = = (1 + 1)n = 2n
k
k=0

per il teorema binomiale. 

27
Definizione 1.3.6 (Disposizioni con ripetizione). Sia k ∈ N. Chiameremo dis-
posizione con ripetizione di classe k di X un’applicazione Drk : {1, 2, · · · , k} → X.
È immediato notare che il loro numero è nk in quanto ognuno dei k elementi
{1, 2, · · · , k} ha n possibili immagini.
Indicheremo con Dn,k r
l’insieme delle disposizioni con ripetizione di classe k
di un insieme di n elementi.
Definizione 1.3.7 (Combinazioni con ripetizione). Sia k ∈ N. Chiameremo com-
binazione con ripetizione di classe k di X = {a1 , a2 , . . . , an } un elemento (ai1 , ai2 , · · · , aik )
di Xk = X × X × · · · × X tale che i1 ≤ i2 ≤ · · · ≤ ik .
| {z }
k volte
Indicheremo con Cn,kr
l’insieme delle combinazioni con ripetizione di classe
k di un insieme di n elementi.
Proposizione 1.3.8. Il numero delle combinazioni con ripetizione di classe k di n
elementi è
n+k−1
!
.
k
Dimostrazione. La proposizione è vera per k = 1 qualunque sia n. Proce-
diamo per induzione su k. Supponendo vera la proposizione per k provi-
amo che le combinazioni con ripetizione di classe k + 1 sono n+k


k+1
. Suddi-
vidiamo l’insieme Ck+1,n r
delle combinazioni con ripetizione di classe k + 1 di
X = {a1 , a2 , · · · , an } in n sottinsiemi disgiunti.

A1 = {C ∈ Ck+1,n r
| C 3 a1 },
A2 = {C ∈ Ck+1,n r
| C 3 a2 , C = a1 },
A3 = {C ∈ Ck+1,n | C 3 a3 , C = a1 , a2 },
r

.. .. ..
. . .
An = {{an , . . . , an }}.
| {z }
k+1 volte

Le combinazioni di A1 si ottengono aggregando ad a1 una qualunque combi-

nazione con ripetizione di classe k degli elementi a1 , a2 , · · · , an . Pertanto il loro
n+k−1
!
numero è, per l’ipotesi induttiva, . Le combinazioni di A2 si otten-
k
gono aggregando ad a2 una qualunque combinazione con ripetizione di classe
k degli elementi a2 , a3 , · · · , an . Pertanto il loro numero è, per l’ipotesi induttiva,
n+k−2
! !
k
e cosı̀ via fino ad An che ha 1 = elementi. Quindi il numero
k k

28
complessivo delle combinazioni di classe k + 1 è

n+k−1 n+k−2 n+k

! ! ! !
k
+ + ··· + = .
k k k k+1 

Teorema 1.3.9 (Il teorema multinomiale). Sia A un anello commutativo con iden-
tità. Se a1 , · · · , ar ∈ A e n ∈ N allora
X n!
(a1 + a2 + · · · + ar )n = ak1 ak2 · · · akr r .
k1 !k2 ! · · · kr ! 1 2
k1 +k2 +···+kr =n

Dimostrazione. Osserviamo che le possibilità di ottenere il termine ak11 ak22 · · · akr r

dove k1 + k2 + · · · + kr = n sviluppando il prodotto

(a1 + a2 + · · · + ar ) · · · (a1 + a2 + · · · + ar )
| {z }
n volte

sono
! ! ! !
n n − k1 n − k1 − k2 n − k1 − k2 − · · · − kr−2 n!
··· = .
k1 k2 k3 kr−1 k1 !k2 ! · · · kr !

Osserviamo che il numero degli addendi distinti nella sommatoria è dato

dal numero delle combinazioni con ripetizione di classe n degli elementi
r+n−1
!
a1 , a2 , · · · , ar e cioè . 
n

29
Capitolo 2

Strutture algebriche

2.1 Monoidi
Definizione 2.1.1. Sia M un insieme. Una operazione (o legge di composizione) su
M è una funzione ? : M × M → M. Useremo la notazione x ? y per indicare
l’immagine ?(x, y), per x, y ∈ M. Una operazione ? si dice

• associativa se ∀ x, y, z ∈ M.x ? (y ? z) = (x ? y) ? z;

• commutativa se ∀ x, y ∈ M.x ? y = y ? x.

Definizione 2.1.2. Un monoide è una tripla (M, ?, λ) dove M è un insieme, ? è

una operazione su M e λ è un elemento di M tali che

(i) ∀ x, y, z ∈ M vale la proprietà associativa

x ? (y ? z) = (x ? y) ? z;

(ii) ∀ x ∈ M si ha
x = x ? λ = λ ? x.

L’insieme M viene detto sostegno del monoide, l’applicazione ? è detta op-

erazione, l’elemento λ è detto elemento neutro dell’operazione ?. Osserviamo
subito che se esistesse un elemento µ ∈ M tale che ∀ x ∈ M.x = x ? µ = µ ? x
allora avremmo
µ = µ ? λ = λ.
Quindi l’elemento neutro di un monoide è unico. Se ∀ x, y ∈ M si ha

x?y= y?x

30
il monoide viene detto commutativo o abeliano.
• Un semigruppo è una coppia (M, ?) dove M è un insieme e ? è una operazione
associativa su M. Ovviamente ogni monoide è un semigruppo ma non vale il
viceversa: (N∗ , +) è un semigruppo ma non un monoide.
df df
Poniamo R>0 = {x ∈ R | x > 0} e Q>0 = {x ∈ Q | x > 0}.
• (N, +, 0), (N, ·, 1) e (N∗ , ·, 1) sono monoidi commutativi.
• (Z, +, 0) e (Z, ·, 1) sono monoidi commutativi.
• (Q, +, 0), (Q, ·, 1) e (Q>0 , ·, 1) sono monoidi commutativi.
• (R, +, 0), (R, ·, 1) e (R>0 , ·, 1) sono monoidi commutativi.
• (C, +, 0) e (C, ·, 1) sono monoidi commutativi.
df
• Sia S1 = {z ∈ C | |z| = 1}, allora (S2 , ·, 1) è un monoide commutativo.
• (P(X), ∩, X) e (P(X), ∪, ∅) sono monoidi commutativi.
• (XX , ◦, idX ) è un monoide non commutativo a meno che X = ∅ o X singo-
letto.
• L’insieme dei numeri irrazionali R r Q non è un semigruppo rispetto nè
a + nè a ·.
• ({−1, 0, 1}, ·, 1), ({0, 1}, ·, 1), ({−1, 1}, ·, 1) sono monoidi commutativi.
df
• La tripla ({0, 1}, , 1), dove n  m = 1 − n − m + 2mn, è un monoide com-
mutativo;
1  1 = 1, 0  0 = 1, 1  0 = 0  1 = 0.

• Siano a, b ∈ N indichiamo il massimo comun divisore di a e b con il

simbolo a u b se a e , 0; poniamo inoltre 0 u a = a u 0 = a per ogni a ∈ N.
Allora la tripla (N, u, 0) è un monoide commutativo.
Definizione 2.1.3. Sia (M, ?, λ) un monoide e siano a e b due elementi di M. Se
a?b=λ
diremo che a è inverso sinistro di b e b è inverso destro di a. Un elemento che ha
un inverso sinistro (destro) è detto invertibile a sinistra (a destra). Se un elemento
a ∈ M ha sia inverso sinistro che inverso destro si dice semplicemente che a è
invertibile o che a ha inverso,. Indicheremo l’inverso di a con a−1 utilizzando la
notazione moltiplicativa.

31
Proposizione 2.1.4. Sia (M, ?, λ) un monoide.

(i) λ è inverso sinistro e destro di se stesso.

(ii) Se a è inverso sinistro di b e c inverso destro di b allora a = c. Pertanto se un

elemento ha un inverso allora l’inverso è unico.

(iii) Se a è inverso sinistro di b e c inverso sinistro di d allora c ? a è inverso sinistro

di b ? d.

(iv) Se a è inverso destro di b e c inverso destro di d allora c ? a è inverso destro di

b ? d.

(v) Se (M, ?, λ) è commutativo un elemento ha inverso destro se e solo se ha inverso

sinistro.

Dimostrazione. (i) Si ha infatti λ ? λ = λ.

(ii) Poichè a ? b = λ e b ? c = λ, per la proprietà associativa si ha

a = a ? λ = a ? (b ? c) = (a ? b) ? c = λ ? c = c.

(iii) Sfruttando l’associatività e le ipotesi si ha

(c ? a) ? (b ? d) = c ? (a ? b) ? d = c ? d = λ.

(iv) Analogamente si ha

(b ? d) ? (c ? a) = b ? (d ? c) ? ad = b ? a = λ.

(v) Per la commutatività a ? b = λ se e solo se b ? a = λ. 

Esempi 2.1.5. 1) In (Z, +, 0), (Q, +, 0), (R, +, 0) e (C, +, 0) ogni elemento ha in-
verso.
2) In (Z, ·, 1) i soli elementi invertibili sono 1 e −1; in (N, ·, 1) e (N∗ , ·, 1) il solo
elemento invertibile è 1.
3) In (Q, ·, 1), (R, ·, 1) e (C, ·, 1) tutti gli elementi , 0 sono invertibili.
4) In (P(X), ∩, X) e (P(X), ∪, ∅) i soli elementi invertibili sono X e ∅, rispettiva-
mente.
5) In ({0, 1}, , 1) ogni elemento è inverso di se stesso.
6) In (N, u, 0) il solo elemento invertibile è 0.

Proposizione 2.1.6. Sia X un insieme con almeno 2 elementi. Proviamo i seguenti

fatti relativi al monoide (XX , ◦, idX ).

32
 Figura 2.1:

y = f (x)
x −> x
−> •
• •
• −> m
Z •
f gm
X −−−−−−−−−−−−−−−−−−→ X −−−−−−−−−−−−−−−−−−→ X

Figura 2.2:

y
x −> x
−> •
• •
f −1 (x)

g f
X −−−−−−−−−−−−−−−−−−→ X −−−−−−−−−−−−−−−−−−→ X

(i) f ∈ XX ha inverso sinistro se e solo se è iniettiva.

(ii) f ∈ XX ha inverso destro se e solo se è surgettiva.
(iii) f ∈ XX ha inverso se e solo se è bigettiva.
Dimostrazione. (i) Supponiamo che f abbia un inverso sinistro, cioè che
esista g ∈ XX tale che g ◦ f = idX . Allora se f (x) = f (x0 ) avremo
x = g( f (x)) = g( f (x0 )) = x0
per cui f è iniettiva. Viceversa sia f è iniettiva ma non surgettiva e sia Z =
X r f (X). Per ogni m ∈ X considero la funzione (Figura 2.1)

x se f (x) = y

gm (y) = 

m se y ∈ Z.


Allora per ogni x ∈ X si ha gm ( f (x)) = x ossia gm ◦ f = idX . Osserviamo che

f , iniettiva ma non surgettiva, ha tanti inversi sinistri almeno quanti sono gli
elementi di X.

33
(ii) Supponiamo che f abbia un inverso destro, cioè che esista g ∈ XX tale che
f ◦ g = idX . Allora per ogni x ∈ X si ha f (g(x)) = x, quindi f è surgettiva.
Viceversa se f è surgettiva, per ogni x ∈ X, f −1 (x) , ∅, pertanto definiamo

g(x) = y dove y ∈ f −1 (x).

Osserviamo che f , surgettiva ma non iniettiva, ha più inversi destri corrispon-

denti alle scelte di y ∈ f −1 (x).
(iii) Se f è bigettiva la funzione inversa f −1 : X → X è l’inverso di f nel monoide
(XX , ◦, idX ). Se f ha l’inverso g nel monoide (XX , ◦, idX ) allora g ◦ f = f ◦ g = idX
e quindi, per la Proposizione 1.2.11, f è bigettiva. 
Definizione 2.1.7. Sia (M, ?, λ) un monoide. Sia x ∈ M, per ogni numero
naturale n ∈ N definiamo la potenza n-esima di x



 x ? x ? · · · ? x se n > 0,
df
x =
n
|
 {z }
 n volte
λ se n = 0.



Se x è un elemento invertibile allora possiamo definire le potenze negative di x

df
xn = (x−1 )n , ∀ n ∈ Z, n < 0.

Per ogni n ∈ N (o n ∈ Z se x è invertibile)

xn ? xm = xn+m , (xn )m = xnm .

• Si osservi che se il monoide non è commutativo allora, in generale,

(x ? y)n , xn ? yn .

Definizione 2.1.8. Un monoide (abeliano) (M, ?, λ) tale che ogni suo elemento
ha inverso è detto gruppo (abeliano).
Esempi 2.1.9. 1) I monoidi (Z, +, 0), (Q, +, 0), (R, +, 0) e (C, +, 0) sono gruppi
commutativi.
2) I monoidi (Q r {0}, ·, 1), (Q>0 , ·, 1). (R r {0}, ·, 1), (R>0 , ·, 1) e (C r {0}, ·, 1) sono
gruppi commutativi.
3) Il monoide (S1 , ·, 1) è un gruppo commutativo.
df
4) Siano X un insieme e G(X) = { f ∈ XX | f bigettiva}. Allora (G(X), ◦, idX ) è
un gruppo (non commutativo a meno che X abbia al più due soli elementi).
L’inverso di f ∈ G(X) altro non è che l’applicazione inversa f −1 .
5) Il monoide ({0, 1}, , 1) è un gruppo commutativo.

34
Definizione 2.1.10. Introduciamo la funzione ϕ : N∗ → N∗ di Eulero definita da
df
ϕ(n) = ]({m ∈ N∗ | MCD(m, n) = 1}),
ossia ϕ(n) è il numero dei naturali positivi che sono primi con n. Ad esempio
ϕ(1) = 1, ϕ(2) = 1, ϕ(3) = 2, ϕ(4) = 2, ϕ(5) = 4, ϕ(6) = 2, . . . .
Se n è un numero primo allora è immediato vedere che ϕ(n) = n − 1.
Definizione 2.1.11 (Operazioni in Zn ). Sull’insieme quoziente Zn (Vedere Es-
empio 1.2.14) possiamo introdurre le operazioni
df df
∀ [r], [s] ∈ Zn , [r] + [s] = [r + s], [r] · [s] = [rs].
Queste operazioni sono ben definite infatti se u ∼ r e v ∼ s allora u − r = kn e
v − s = hn pertanto
u + v = r + kn + s + hn = r + s + (k + h)n ossia [u + v] = [r + s].
Analogamente
uv = (r + kn)(s + hn) = rs + (rh + sk)n ossia [uv] = [rs].
Segue subito dalla definizione di prodotto che [r]k = [r] · · · · [r] = [rk ] per ogni
| {z }
k volte
classe [r] ∈ Zn e per ogni intero k ≥ 0.
La terna (Zn , +, [0]) è un gruppo commutativo, infatti ogni classe [r] ha
come inverso [−r]. La terna (Zn , ·, [1]) è un monoide commutativo ma, in
generale, non è un gruppo. In Z6 la classe [5] ha come inverso se stessa:
[5] · [5] = [25] = [1], mentre [2] non ha inverso infatti [2] · [r] = [1] implica la
relazione 2r − 1 = 6k che è impossibile. Si può però provare che:
Proposizione 2.1.12. Una classe [r] ∈ Zn , [r] , [0], ha inverso se e solo se
MCD(r, n) = 1. In particolare se n è un numero primo allora ogni classe non nulla di
Zn ha inverso.
La Proposizione 2.1.12 deriva subito dalla Proposizione A.2.11.
Teorema 2.1.13 (Piccolo teorema di Fermat). Sia n un intero > 1. Sia x ∈ Z primo
con n. Allora
xϕ(n) ≡ 1 (mod n), (2.1.1)
ossia [x]ϕ(n) = [1] in Zn . In particolare la (2.1.1) fornisce subito l’inverso [x]−1 di [x]:
[x]−1 = [x]ϕ(n)−1 .

35
Dimostrazione. Sappiamo dalla Proposizione 2.1.12 che gli elementi invert-
ibili di Zn sono le ϕ(n) classi [a] con 1 ≤ a < n e MCD(a, n) = 1. Indichiamo
queste classi con [a1 ], [a2 ], . . . , [aϕ(n) ]. Pertanto
ai . a j (mod n), se i , j.
Sia x un intero primo con n allora per ogni i = 1, . . . , ϕ(n), MCD(xai , n) = 1,
quindi
ai x ≡ a j per un opportuno indice j che dipende da x e da ai .
Moltiplicando tra loro [a1 x], . . . , [aϕ(n) x] avremo

[a1 ] · · · [aϕ(n) ] = [a1 x] · · · [aϕ(n) x] = [a1 ] · · · [aϕ(n) ][x]ϕ(n) .

Moltiplicando ambo i membri per [aϕ(n) ]−1 · · · [a1 ]−1 otteniamo

[1] = [x]ϕ(n)
cioè la tesi. 
Definizione 2.1.14. Sia (M, ?, λ) un monoide. Un sottoinsieme L ⊂ M è un
sottomonoide di M se
(i) λ ∈ L;
(ii) ∀ a, b ∈ L ⇒ a ? b ∈ L.
Pertanto la funzione ? : M × M → M si restringe alla funzione ?L : L × L → L,
definita a ?L b = a ? b, quindi (L, ?L , λ) è un monoide.
Se (M, ?, λ) è un gruppo e (L, ?L , λ) un suo sottomonoide. Se ∀ a ∈ L ⇒
a−1 ∈ L, L si dice sottogruppo di M.
• Sia (M, ?, λ) un monoide. Allora l’insieme
df
M◦ = {m ∈ M | m invertibile}
è un sottomonoide di M ed è un gruppo. Infatti se x e y ∈ M sono invertibili
allora x ? y e y ? x sono invertibili: per la Proposizione 2.1.4 si ha
(x ? y)−1 = y−1 ? x−1 , (y ? x)−1 = x−1 ? y−1 .
Nel caso del monoide (Zn , ·, [1]) si ha
Z◦n = {[x] ∈ Zn | MCD(x, n) = 1}.
Per la Proposizione 2.1.12 avremo che
](Z◦n ) = ϕ(n).

36
Esempi 2.1.15. 1) (N, +, 0) è un sottomonoide di (Z, +, 0); (Z, +, 0) è un sot-
togruppo di (Q, +, 0); (Q, +, 0); è un sottogruppo di (R, +, 0); (R, +, 0) è un
sottogruppo di (C, +, 0); (S1 , ·, 1) è un sottogruppo di (C r {0}, ·, 1).
2) (N∗ , ·, 1) è un sottomonoide di (N, ·, 1); (N, ·, 1) è un sottomonoide di (Z, ·, 1);
(Z, ·, 1) è un sottomonoide di (Q, ·, 1); (Q, ·, 1) è un sottomonoide di (R, ·, 1);
(R, ·, 1) è un sottomonoide di (C, ·, 1).
3) (G(X), ◦, idX ) è un sottomonoide di (XX , ◦, idX ).

Definizione 2.1.16. Siano (M, ?, λ) e (L, ∇, η) due monoidi. Una funzione

f : M → L è un omomorfismo di monoidi se

(i) f (λ) = η;

(ii) ∀ a, b ∈ M ⇒ f (a ? b) = f (a) ∇ f (b).

Se (M, ?, λ) e (L, ∇, η) sono due gruppi allora un omomorfismo di monoidi

f : M → L è chiamato omomorfismo di gruppi.

Esempi 2.1.17. 1) La funzione f : Z → Q, f (n) = 2n , è un omomorfismo di

monoidi (anzi di gruppi) dal monoide (Z, +, 0) al monoide (Q>0 , ·, 1).
2) Le funzioni
x
f : (R r {0}, ·, 1) → ({−1, 1}, ·, 1), f (x) = ,
|x|
z
f : (C r {0}, ·, 1) → (S1 , ·, 1), f (z) = ,
|z|
f : (R>0 , ·, 1) → (R, +, 0), f (x) = log x,

sono omomorfismi di monoidi (anzi di gruppi).

3) Le funzioni

1
 se n è pari
f : (N, +, 0) → ({0, 1}, , 1), f (n) = 

0
 se n è dispari,

1
 se n = 1
f (n) = 

f : ({−1, 1}, ·, 1) → ({0, 1}, , 1),
0
 se n = −1,

1
 se 3 | n
f (n) = 

f : (N, u, 0) → ({0, 1}, ·, 1),
0
 altrimenti,

sono omomorfismi di monoidi (nell’ultimo esempio si osservi che 3 | (n u m) ⇔

3 | n ∧ 3 | m).

37
4) Sia X un insieme. La funzione f : P(X) → P(X), f (A) = X r A è un omo-
morfismo dal monoide (P(X), ∪, ∅) nel monoide (P(X), ∩, X) e, viceversa dal
monoide (P(X), ∩, X) nel monoide (P(X), ∪, ∅).
5) Sia (M, ?, λ) un monoide e sia m ∈ M un elemento fissato. La funzione
fm : M → M, fm (x) = m ? x (o fm (x) = x ? m) non è un omomorfismo di monomi
(a meno che m = λ, nel qual caso fm = idM ), infatti f (λ) = m e

fm (x ? y) = m ? (x ? y) , (m ? x) ? (m ? y) = fm (x) ? fm (y).

Ad esempio se (M, ?, λ) = (N, +, 0) allora fm : N → N, fm (x) = m + x.

La funzione

ϕ : (M, ?, λ) → (MM , ◦, idM ), ϕ(m) = fm ∈ MM ,

è un omomorfismo di monoidi. Si ha infatti ϕ(λ) = fλ = idM . Inoltre ϕ(m?m0 ) =

ϕ(m) ◦ ϕ(m0 ), infatti, Poichè ∀ x ∈ M si ha

fm?m0 = (m ? m0 ) ? x = m ? (m0 ? x) = fm ( fm0 (x))

allora
ϕ(m ? m0 ) = fm?m0 = fm ◦ fm0 = ϕ(m) ◦ ϕ(m0 ).

Proposizione 2.1.18. Sia f : (M, ?, λ) → (L, ∇, η) un omomorfismo di monoidi. La

restrizione di f a M◦ induce un omomorfismo di gruppi

f |M◦ : M◦ → L◦ .

Inoltre per ogni x ∈ M◦ si ha

f (x−1 ) = [ f (x)]−1 .

Dimostrazione. Basta provare che se x ∈ M◦ allora f (x) ∈ L◦ . Poichè x è

invertibile si ha
f (x ? x−1 ) = f (x−1 ? x) = f (λ) = µ.
Poichè
f (x ? x−1 ) = f (x)∇ f (x−1 ), f (x−1 ? x) = f (x−1 )∇ f (x)
avremo
f (x)∇ f (x−1 ) = f (x−1 )∇ f (x) = µ
cioè f (x) ∈ L◦ e f (x−1 ) = [ f (x)]−1 . 

Proposizione 2.1.19. Sia (M, ?, λ) un monoide.

38
 (i) La funzione idM : M → M è un omomorfismo di monoidi.

(ii) Se f : (M, ?, λ) → (L, ∇, η) e g : (L, ∇, η) → (P,
, ν) sono omomorfismi di

monoidi, allora la composizione g ◦ f : (M, ?, λ) → (P,
, ν) è un omomorfismo
di monoidi.

(iii) Se f : (M, ?, λ) → (L, ∇, η) è un omomorfismo di monoidi e una funzione biget-

tiva allora la funzione inversa f −1 : (L, ∇, η) → (M, ?, λ) è un omomorfismo di
monoidi e f viene detto isomorfismo di monoidi.

Dimostrazione. (i) Per ogni x, y ∈ M si ha idM (x ? y) = x ? y = idM (x) ? idM (y).

(ii) Siano x, y ∈ M allora

(g ◦ f )(x ? y) = g( f (x ? y))
= g( f (x)∇ f (y))
= g( f (x))
g( f (y))
= (g ◦ f )(x)
(g ◦ f )(y).

(iii) Osserviamo innanzitutto che, essendo f (λ) = η, allora f −1 (η) = λ. Siamo

poi m, m0 elementi qualsiasi di M, allora n = f (m) e n0 = f (m0 ) sono elementi
arbitrari di L poichè f è una bigezione. Allora si ha

f (m ? m0 ) = f (m)∇ f (m0 ) = n∇n0 .

Pertanto
f −1 (n∇n0 ) = m ? m0 = f −1 (n) ? f −1 (n0 )
da cui segue la tesi. 

39
2.2 Stringhe
Definizione 2.2.1. Sia A un insieme. Poniamo
df
[
SA = An .
n∈N

In R-P si usa la notazione A∗ al posto di SA . Chiameremo stringa un qualsiasi

elemento di SA e l’insieme A alfabeto. Pertanto se α ∈ SA allora α ∈ An per un
n ∈ N; tale n è la lunghezza della stringa α; diremo anche che α è una n-stringa.
È definita pertanto la funzione lunghezza di una stringa

ln : SA → N, ln(α) = n, se α ∈ An . (2.2.1)

Ricordiamo che 
n df {( )}
 se n = 0
A =

A × Am
 se n = m + 1.
In particolare ln(( )) = 0.
Possiamo vedere una stringa come una parola composta con le lettere
dell’alfabeto A
α = (a1 , . . . , an ) ←→ a1 a2 . . . an .
Definiamo ora l’operazione cons : A × SA → SA

(a, α) = (a, a1 , . . . , an ) ∈ An+1 se α = (a1 , . . . , an ) ∈ An

cons(a, α) = 

(a)
 se α = ( ).

La funzione cons soddisfa le seguenti proprietà:

• è iniettiva:

∀ x ∈ A.∀ y ∈ A.∀ α ∈ SA .∀ β ∈ SA .(cons(x, α) = cons(y, β) ⇒ (x = y∧α = β)).

• ( ) < cons(A × SA );

• vale il principio di induzione strutturale:

∀X ∈ P(SA ).[[( ) ∈ X∧∀ x ∈ A.∀ α ∈ SA .(α ∈ X ⇒ cons(x, α) ∈ X)] ⇒ X = SA ].

Definizione 2.2.2. La funzione @ : SA × SA → SA definita da


β se α = ( )
df 
α@β =  (2.2.2)

cons(a, (γ @ β)) se α = cons(a, γ),


40
è detta concatenazione. Più esplicitamente se α = (a1 , . . . , an ) e β = (b1 , . . . , bm )
allora
α @ β = (a1 , . . . , an , b1 , . . . , bm ). (2.2.3)
In particolare, se a ∈ A allora
cons(a, α) = (a) @ α.
Proposizione 2.2.3. Sia A un insieme. La tripla (SA , @, ( )) è un monoide.
Dimostrazione. La tesi è evidente dalla (2.2.3). Per una dimostrazione for-
male basata sulla (2.2.2) e sul principio di induzione strutturale si può procedere
come segue. Dalla (2.2.2) si ha subito che per ogni stringa α si ha ( ) @ α = α.
Usando il principio di induzione strutturale proviamo che α @ ( ) = α. Sempre
dalla (2.2.2) abbiamo ( ) @ ( ) = ( ). Supponiamo che α @ ( ) = α, allora
cons(a, α) @ ( ) = cons(a, (α @ ( )) = cons(a, α).
Quindi ( ) è l’elemento neutro. Proviamo ora l’associatività. Utilizziamo
l’induzione strutturale.
• ( ) @ (α @ β) = (α @ β) = (( ) @ α @ )β.
• Supponiamo che α @ (β @ γ) = (α @ β) @ γ; allora
cons(a, α) @ (β @ γ) = cons(a, (α @ (β @ γ))
= cons(a, ((α @ β) @ γ))
= cons(a, (α @ (β)) @ γ
= (cons(a, α) @ β) @ γ.

Pertanto cons(a, ((α @ β) @ γ)) = (cons(a, α) @ β) @ γ e l’associatività è provata.

Osserviamo esplicitamente che l’unico elemento invertibile (invertibile a
destra o a sinistra) di SA è l’elemento neutro ( ). 
Definizione 2.2.4. Data una stringa α diremo che una stringa β è un prefisso o
una testa di α se esiste una stringa γ tale che
α = β @ γ.
Una stringa β è un suffisso o una coda di α se esiste una stringa δ tale che
α = δ @ β.
Una stringa β è una sottostringa di α se esistono due stringhe ε e η tali che
α = ε @ β @ η.
Un prefisso β (suffisso, sottostringa) di α è proprio se α , β.

41
Definizione 2.2.5. Poniamo su SA il seguente ordine parziale

∀ α, β ∈ SA .α J β ⇐⇒ ∃ δ ∈ SA .δ @ α = β. (2.2.4)

La riflessività è ovvia in quanto α = ( ) @ α implica che α J α. Proviamo la

transitività: se α J β e β J γ allora esistono δ, δ0 ∈ SA tali che

δ @ α = β, δ0 @ β = γ.

Allora (δ0 @ δ) @ α = γ cioè α J γ. Proviamo ora l’antisimmetria: sia α J β e

β J α, allora esistono δ, δ0 ∈ SA tali che

δ @ α = β, δ0 @ β = α.

Allora (δ0 @ δ) @ α = α da cui segue che δ0 @ δ = ( ), ossia δ0 = δ = ( ) e α = β.

• Osserviamo che ∀ α ∈ SA .∀ a ∈ A.α J cons(a, α).
• La stringa ( ) è ovviamente il minimo di (SA , J).

Osservazione 2.2.6. Osserviamo esplicitamente quanto segue: dato α ∈ SA i

soli elementi che precedono α sono le code di α cioè

( ) J (an ) J (an−1 , an ) J (an−2 , an−1 , an ) J · · · J (a2 , . . . , an ) J (a1 , . . . , an ).

I soli elementi che seguono α sono le stringhe di cui α è una coda.

Osservazione 2.2.7. Il principio di induzione strutturale è conseguenza del

Teorema 1.2.41 se si pone su SA l’ordine (2.2.4). Infatti (SA , J) è ben fondato.
Sia S ⊂ SA e α = (a1 , . . . , an ) ∈ S un elemento di S. Per l’Osservazione 2.2.6 α ha
un numero finito di elementi che lo precedono e quindi il minore tra questi che
sta in S è minimale per S.

Osservazione 2.2.8. Se l’insieme A è un poset allora su SA vengono messi altri

ordinamenti.

Proposizione 2.2.9 (Proprietà universale). Sia A un insieme e (M, ?, λ) un monoide.

Per ogni funzione f : A → M esiste uno ed un solo omomorfismo di monoidi

f : (SA , @, ( )) → (M, ?, λ)

tale che per ogni a ∈ A si abbia

f (cons(a, ( )) = f (a).

42
In altre parole esiste uno ed un solo omomorfismo di monoidi f : (SA , @, ( )) → (M, ?, λ)
che rende commutativo il diagramma

A
cons / SA
f
f 
M

Si suole anche dire che (SA , @, ( )) è il monoide libero generato dall’insieme A.

Dimostrazione. Ci limitiamo a definire l’omomorfismo f utilizzando la (2.2.3):


λ se α = ( )

f (α) = 

 f (a1 ) ? f (a2 ) ? · · · ? f (an ) se α = (a1 , . . . , an ).


Rimandiamo a R-P, p. 85 per la dimostrazione completa. 

Osservazione 2.2.10. Se nella Proposizione 2.2.9 prendiamo A = M e f = idM

allora avremo
f ((a1 , . . . , an )) = a1 ? a2 ? · · · ? an .

Corollario 2.2.11. Sia A un insieme. La “funzione lunghezza di una stringa con

caratteri in A” ln : SA → N, definita in (2.2.1), è l’unico omomorfismo di monoidi
(SA , @, ( )) → (N, +, 0) tale che ln(cons(a, ( ))) = 1.

Dimostrazione. L’omomorfismo lunghezza di una stringa altro non è che f

dove f : A → N, f (a) = 1 per ogni a ∈ A. 

43
Capitolo 3

Algebra Lineare

3.1 Vettori e matrici

Sia
Rn = {(x1 , x2 , . . . , xn ) | xi ∈ R, 1 ≤ i ≤ n}
l’insieme delle n-uple ordinate di numeri reali. Un elemento v = (x1 , x2 , . . . , xn )
di Rn è chiamato vettore (o talvolta n-vettore) e i numeri reali xi sono detti
componenti di v. Gli elementi di R sono detti anche scalari. Indicheremo con 0n
la n-upla (0, 0, . . . , 0) che chiameremo vettore nullo. Su Rn definiamo le seguenti
operazioni.

• La somma u + v di u = (x1 , x2 , . . . , xn ) e v = (y1 , y2 , . . . , yn ),

u + v := (x1 + y1 , x2 + y2 , . . . , xn + yn ).

• Il prodotto di u = (x1 , x2 , . . . , xn ) per lo scalare λ ∈ R,

λu := (λx1 , λx2 , . . . , λxn ).

Le operazioni ora definite godono delle seguenti proprietà: siano u, v e w ∈ Rn

e λ, µ ∈ R, allora

• u + v = v + u, proprietà commutativa

• u + (v + w) = (u + v) + w, proprietà associativa

• λ(u + v) = λu + λv, proprietà distributiva

• (λ + µ)u = λu + µu, proprietà distributiva

44
 • λ(µu) = (λµ)u, omogeneità
• u + 0n = u,
• 1u = u.
• Osserviamo esplicitamente che (Rn , +, 0n ) è un gruppo commutativo.
Definizione 3.1.1. Una matrice reale m × n è una tabella ordinata
 a11 a12 . . . a1n 
 
 21 a22 . . . a2n 
 a 
A =  ..
 .. .. ..  (3.1.1)
 .
 . . . 
am1 am2 · · · amn


dove ai j ∈ R, i = 1, . . . , m, j = 1, . . . , n. I numeri reali ai j sono detti componenti o

entrate della matrice.
Indicheremo con Mm,n (R) l’insieme delle matrici m × n a elementi in R; se
m = n scriveremo più semplicemente Mn (R). Al posto della tabella (3.1.1)
scriveremo, piú brevemente, A = (ai j )i, j ∈ Mm,n (R).
L’insieme Rn si identifica con M1,n (R), l’insieme delle matrici 1 × n dette vettori
riga, e con Mn,1 (R), l’insieme delle matrici n × 1 dette vettori colonna
 
x1 
←→  ... 
 
(x1 , . . . , xn ) ←→ x1 . . . xn
 
 
xn
D’altronde Mm,n (R) si può identificare con Rmn “mettendo in fila le righe”(o
“mettendo in colonna” le colonne)
 a11 a12 . . . a1n 
 
 21 a22 . . . a2n 
 a 
 .
 .. .. ... ..  ←→ (a11 , . . . a1n , a21 , . . . , a2n , . . . , am1 , . . . , amn ).
 . . 
am1 am2 · · · amn
 

Scriveremo Mm,n (R)  Rmn . Sia A = (ai j )i,j ∈ Mm,n (R), l’i-esima riga di A è il
vettore riga
A(i) = (ai1 ai2 · · · ain ), i = 1, · · · , m
e la j-esima colonna di A è il vettore colonna

 a1j 
 
 a2j 
A(j) =  ..  , j = 1, . . . , n.
 
 . 
 
am j

45
Pertanto l’elemento ai j di A sta sulla i-esima riga e sulla j-esima colonna e la
matrice A si dice a m righe e n colonne.
Con 0m,n indicheremo la matrice nulla di Mm,n (R) cioè quella avente tutti i suoi
elementi uguali a 0.
Se A = (ai j )i, j ∈ Mm,n (R) la matrice (a ji ) j,i ∈ Mn,m (R) si chiama trasposta di A
e viene indicata con t A. La matrice t A è quindi ottenuta da A scambiando
ordinatamente le righe con le colonne. Notiamo che la trasposta di un vettore
riga è un vettore colonna e viceversa.
Esempio 3.1.2. Se !
1 0 3
A=
2 −1 0
avremo
1 2 
 
t
A = 0 −1
 
3 0
 

Definizione 3.1.3. Le matrici A = (ai j )i,j ∈ Mn (R), cioè aventi ugual numero di
righe e di colonne, sono dette matrici quadrate. Gli elementi a11 , a22 , . . . , ann di
una matrice quadrata A ∈ Mn (R) costituiscono la diagonale principale di A.
• Se ai j = 0 per i , j la matrice A = (ai j )i, j=1,...,n si dice diagonale; se

λ se i = j

ai j = 

0 se i , j,


la matrice A si dice scalare e viene indicata con D(λ). La matrice scalare

D(1) si indica con In ed è chiamata matrice unità.

• Una matrice A ∈ Mn (R) si dice triangolare superiore se tutti le entrate sotto

la diagonale principale sono nulle cioè se ai j = 0 per i > j; analogamente
chiameremo A matrice triangolare inferiore se tutti le entrate sopra la diag-
onale principale sono nulle cioè se ai j = 0 per i < j.

• Una matrice quadrata A si dice simmetrica se A = t A.

Definizione 3.1.4. Su Mm,n (R) è definita la somma: se A = (ai j )i,j , B = (bi j )i, j ∈
Mm,n (R)
A + B = (ai j + bi j )i, j ∈ Mm,n (R)
e la moltiplicazione di uno scalare: k ∈ R per una matrice A = (ai j )i,j ∈ Mm,n (R)

kA = (kai j )i,j ∈ Mm,n (R)

46
 Facilmente si verificano le seguenti proprietá: A, B, C ∈ Mm,n (R), h, k ∈ R

1) A+B=B+A proprietà commutativa

2) A + (B + C) = (A + B) + C proprietà associativa
3) k(hA) = (kh)A proprietà associativa
4) k(A + B) = kA + kB proprietà distributiva
5) (k + h)A = kA + hA proprietà distributiva
6) 0m,n + A = A elemento neutro
7) 1A = A (1 ∈ R) unitarietà
8) A + (−A) = 0m,n dove −A = −1A elemento opposto
9) 0A = 0m,n , (0 ∈ R) k0m,n = 0m,n
10) (A + B) = A + B.
t t t

Definizione 3.1.5. Siano dati i vettori u1 , . . . um di Rn e gli scalari λ1 , . . . , λm ∈ R.

La combinazione lineare di u1 , . . . um con coefficienti λ1 , . . . , λm ∈ R è il vettore
m
X
λi ui := λ1 u1 + λ2 u2 + · · · + λm um .
i=1

Si considerino in R3 i seguenti vettori

u1 = (1, 0, 1), u2 = (0, 2, 1), u3 = (−1, 1, 1), u4 = (−2, 1, 2),

e gli scalari
λ1 = 4, λ2 = −2, λ3 = −1, λ4 = 5.
La combinazione lineare di u1 , . . . u4 con coefficienti λ1 , . . . , λ4 è il vettore
4
X
λi ui = 4(1, 0, 1) − 2(0, 2, 1) − (−1, 1, 1) + 5(−2, 1, 2) = (−5, 0, 11).
i=1

Definizione 3.1.6. Sia A = (ai j )i, j ∈ Mm,n (R) e B = (b jk )i,j ∈ Mn,p (R). Il prodotto
righe per colonne tra A e B è la matrice A · B = (cik )i,k ∈ Mm,p (R) dove
n
X
cik = ai j b jk i = 1, . . . , m, k = 1, . . . , p.
j=1

Eviteremo, se non necessario, di indicare il puntino · scrivendo AB invece che

A · B.

47
Esempio 3.1.7. Siano date le matrici

 1 3 2 −1
 
 
 
1 3 0
!  1 
B =  0 −4 2 −5
 
A= , 
−4 −5 3  
 
 3 
−2 1 0
 
5
allora se AB = (cik ), 1 ≤ i ≤ 2, 1 ≤ k ≤ 4, si ha
3
c11 = 1 × 1 + 3 × 0 + 0 × (−2); c12 = 1 × 3 + 3 × (−4) + 0 ×
5
1
c13 = 1 × 2 + 3 × + 0 × 1; c14 == 1 × (−1) + 3 × (−5) + 0 × 0
2
3
c21 = −4 × 1 + (−5) × 0 + 3 × (−2); c22 = −4 × 3 + (−5) × (−4) + 3 ×
5
1
c23 = −4 × 2 + (−5) × + 3 × 1; c24 = −4 × (−1) + (−5) × (−5) + 3 × 0,
2
per cui

 1 −9 7 
−16 
 2 
AB =   .
 


 49 15 
−10 − 29 

5 2
Osservazione 3.1.8. Il prodotto suddetto è definito se il numero delle colonne
del primo fattore è uguale al numero delle righe del secondo fattore, pertanto
sull’insieme Mn (R) risulta sempre definito il prodotto. Si noti peró che siffatto
prodotto in generale non è commutativo: ad esempio
! ! !
1 1 1 0 2 0
=
0 1 1 0 1 0
mentre ! ! !
1 0 1 1 1 1
= .
1 0 0 1 1 1
Osservazione 3.1.9. In Mn (K) esistono i cosidetti 0-divisori cioè matrici A,B con
A, B , 0n,n tali che AB = 0n,n . Ad esempio per n = 2
! ! !
1 0 0 0 0 0
A= , B= , AB =
0 0 0 1 0 0

48
 Elenchiamo le proprietà delle operazioni sopra definite.
Proposizione 3.1.10. Siano A, B ∈ Mm,n (R) e C, D ∈ Mn,p (R), k ∈ R, allora
1) (A + B)C = AC + BC: proprietà distributiva.
2) A(C + D) = AC + AD: proprietà distributiva.
3) A(kC) = k(AC) = (kA)C: omogeneità.
4) AIn = A, In C = C: unitarietà.
Se A ∈ Mm,n (R), B ∈ Mn,p (R) e C ∈ Mp,s (R) allora
5) (AB)C = A(BC): proprietà associativa.
6) t (AB) = t Bt A.
Dimostrazione. I punti 1), 2), 5), 6) sono di laboriosa verifica mentre le altre
sono facili e vengono lasciate al Lettore. 
Definizione 3.1.11. Una matrice quadrata A ∈ Mn (R) si dice invertibile se esiste
una matrice B ∈ Mn (R) tale che
AB = BA = In .
Siffatta matrice B, che è unica, viene indicata con A−1 ed è detta la matrice
inversa di A. Vedremo piú avanti come determinare la matrice inversa di una
data matrice. Definiamo
GLn (R) = Mn (R)◦ ,
il sottogruppo delle matrici invertibili di Mn (R).
Corollario 3.1.12. La terna (Mn (R), ·, In ) è un monoide non commutativo. Inoltre la
funzione
T : Mn (R) → Mn (R), T(A) = t A
è un omomorfismo di monoidi che induce un omomorfismo di gruppi
T|GLn (R) : GLn (R) → GLn (R).
Valgono cioè i seguenti fatti:
1) Se A è una matrice invertibile allora t A è invertibile.
2) (A−1 )−1 = A.
3) (AB)−1 = B−1 A−1 .
4) t (A−1 ) = (t A)−1 .

49
3.2 Il determinante di una matrice quadrata
Definizione 3.2.1. Sia !
a a
A = 11 12
a21 a22
una matrice 2 × 2. Definiamo determinante di A il numero reale

det(A) := a11 a22 − a12 a21 .

Il determinante di una matrice quadrata n × n con n ≥ 2 viene definito indutti-

vamente. Sia data una matrice A = (ai j )i, j ∈ Mn (R),

a11 . . . a1n 
 
 . . ..  .
 .. . . . 

an1 . . . ann
 

Per ogni 1 ≤ i ≤ n, 1 ≤ j ≤ n sia A(b ij) la sottomatrice quadrata di ordine

n − 1 ottenuta cancellando la i-esima riga e la j-esima colonna. Il complemento
algebrico dell’elemento ai j di A è

Ai j = (−1)i+j det(A(b
ij)).

Definiamo allora
ai1 Ai1 + ai2 Ai2 + . . . + ain Ain , (3.2.1)
lo sviluppo secondo la i-esima riga, oppure

a1j A1j + a2j A2j + . . . + an j An j , (3.2.2)

lo sviluppo secondo la j-esima colonna.

• I numeri definiti dalle (3.2.1) e (3.2.2) sono uguali per ogni i e j = 1, . . . , n.
Possiamo allora definire

det(A) := ai1 Ai1 + ai2 Ai2 + . . . + ain Ain = a1j A1j + a2j A2j + . . . + an j An j .

Per indicare il determinante di A useremo anche la notazione

a11 . . . a1n
.. . . .. .
. . .
an1 . . . ann3

50
Consideriamo il caso di una matrice 3 × 3
a11 a12 a13 
 
A = a21 a22 a23  .
 
a31 a32 a33
 

Sviluppando il det(A) secondo la prima riga otteniamo

a22 a23 a a a a
det(A) = a11 − a12 21 23 + a13 21 22
a32 a33 a31 a33 a31 a32
= a11 a22 a33 − a11 a23 a32 − (a12 a21 a33 − a12 a23 a31 ) + a13 a21 a32 − a13 a22 a31 .
Se sviluppiamo il det(A) secondo la seconda colonna otteniamo
a21 a23 a a a a
det(A) = −a12 + a22 11 13 − a32 11 13
a31 a33 a31 a33 a21 a23
= −(a12 a21 a33 − a12 a23 a31 ) + a11 a22 a33 − a13 a22 a31 − (a11 a23 a32 − a13 a21 a32 ).
Come facilmente si verifica i due sviluppi danno lo stesso risultato.

• Un metodo un po’ più veloce per calcolare il determinante di una matrice 3×3
è la cosidetta regola di Sarrus che è in realtà la vera definizione di determinante.
Scriviamo la matrice A senza parentesi e affianchiamole le due prime colonne
a11 a12 a13 a11 a12
a21 a22 a23 a21 a22 .
a31 a32 a33 a31 a32
Sommiamo i prodotti degli elementi sulle tre diagonali da sinistra a destra
a11 a22 a33 + a12 a23 a31 + a13 a21 a32
e sommiamo i prodotti degli elementi sulle tre diagonali da destra a sinistra
a13 a22 a31 + a11 a23 a32 + a12 a21 a33 .
Allora si ha
det(A) = a11 a22 a33 + a12 a23 a31 + a13 a21 a32 − (a13 a22 a31 + a11 a23 a32 + a12 a21 a33 ).
Esempio 3.2.2. Calcoliamo il determinante della seguente matrice

1 −2 1 0 
 
2 1 −2 0 
A = 
 
0 −3 1 4 

 
0 −1 2 −1

51
E’ opportuno sviluppare il determinante secondo la prima colonna in quanto
la presenza di due zeri accorcia i calcoli.

1 −2 0 −2 1 0
det(A) = −3 1 4 − 2 −3 1 4
−1 2 −1 −1 2 −1

= (−1 + 8 − 8 + 6) − 2(2 − 4 + 16 − 3) = −17.

Calcoliamo ora questo determinante fissando la 3◦ e 4◦ riga. Dei 6 addendi
3 contengono come fattori determinanti con una colonna nulla e quindi sono
nulli. Pertanto avremo

−3 1 1 0 −3 4 1 1
det(A) = (−1)3+4+2+3 + (−1)3+4+2+4
−1 2 2 0 −1 −1 2 −2
1 4 1 −2
+ (−1)3+4+3+4 = −17.
2 −1 2 1

Elenchiamo alcune proprietà fondamentali del determinante.

Proposizione 3.2.3. Siano A e B matrici n × n allora

1. Se k ∈ R allora det(kA) = kn det(A).

2. det(t A) = det(A).

3. det(AB) = det(A) det(B).

4. Se A è matrice triangolare superiore o inferiore (in particolare se è diagonale)

allora det(A) = a11 a22 . . . ann e quindi det(In ) = 1.

5. La funzione det : (Mn (R), ·, In ) → (R, ·, 1), A → det(A), è un omomorfismo di

monoidi.

6. A è invertibile se e solo se det(A) , 0 nel qual caso si ha

1
det(A−1 ) = .
det(A)

7. Se una matrice ha una riga o una colonna nulla (cioè formata di soli zeri) il suo
determinante è nullo.

8. Se in una matrice A si scambiano tra loro 2 righe o 2 colonne, chiamando A0 la

matrice cosı̀ ottenuta, si ha det(A0 ) = − det(A).

52
 9. Se ad una riga o ad una colonna di una matrice si aggiunge una combinazione
lineare di altre righe o di altre colonne, rispettivamente, il determinante della
matrice cosı̀ ottenuta è uguale a quello della matrice originaria.

10. Una matrice ha una riga o una colonna che è combinazione lineare di altre
righe o di altre colonne, rispettivamente, se e solo se il suo determinante è nullo.
In particolare se una matrice ha due righe o due colonne proporzionali il suo
determinante è zero.

Esempio 3.2.4. Sia data la matrice

 2 −3 1 0 
 
−1 2 4 −6
A = 

−3 5 0 −2

 
8 −13 1 4

essendo la quarta riga combinazione lineare della prima e della terza, cioè
(8, −13, 1, 4) = (2, −3, 1, 0) − 2(−3, 5, 0, −2) il determinante di A è nullo.

Definizione 3.2.5. La matrice cofattore di A è

cof(A) = (Ai j )i, j ∈ Mn (R)

cioè la matrice avente per elementi i complementi algebrici degli elementi di

A.

Possiamo ora ottenere la forma della matrice inversa di una matrice A con
det(A) , 0.

Proposizione 3.2.6. Sia A ∈ Mn (R) tale che det(A) , 0. Allora

1
A−1 = t
cof(A).
det(A)

• Nel caso delle matrici 2 × 2 si determina facilmente l’inversa:

! !
a11 a12 1 a22 −a12
se A = allora A =
−1
.
a21 a22 det(A) −a21 a11

Esempio 3.2.7. Sia A la matrice

 1 2 5
 
−3 1 4
 
−1 2 2
 

53
il cui determinante è −27. Calcoliamo la matrice cof(A)

1 4 −3 4
A11 = = −6, A12 = − =2
2 2 −1 2

−3 1 2 5
A13 = = −5, A21 = − =6
−1 2 2 2
1 5 1 2
A22 = = 7, A23 = − = −4
−1 2 −1 2
2 5 1 5
A31 = = 3, A32 = − = −19
1 4 −3 4
1 2
A33 = =7
−3 1
e quindi
−6 2 −5
 
cof(A) =  6 7 −4

3 −19 7
 

pertanto
−6 6 3 
 
1 

A−1 =−

 2 7 −19
27 −5 −4 7 


Definizione 3.2.8. Sia ora A = (ai j )i,j ∈ Mm,n (R). Fissiamo p righe i1 , i2 , · · · , ip
e p colonne j1 , j2 , · · · , jp . Consideriamo la sottomatrice p × p di A ottenuta
prendendo gli elementi che appartengono contemporaneamente ad una delle
righe e ad una delle colonne fissate. Il determinante di questa sottomatrice p×p
di A si chiama minore di ordine p di A. Ad esempio i singoli elementi ai j sono
i minori di ordine 1 di A. Ovviamente si potranno considerare minori di A di
ordine p ≤ min {m, n}. E’ immediato osservare, dal calcolo combinatorio, che il
numero delle sottomatrici (e quindi dei minori) di A di ordine p è

m(m − 1) · · · (m − p + 1) n(n − 1) · · · (n − p + 1)
! !
m n
= · .
p p p(p − 1)(p − 2) · · · 2 · 1 p(p − 1)(p − 2) · · · 2 · 1

Ad esempio una matrice 3 × 4 ha

! !
3 4 3·2 4·3
= · = 18
2 2 2·1 2·1

54
sottomatrici 2 × 2 e ! !
3 4 3·2·1 4·3·2
= · =4
3 3 3·2·1 3·2·1
sottomatrici 3 × 3.

• Chiameremo caratteristica di A il massimo degli ordini dei minori non nulli e

la indicheremo con rk(A). Pertanto A ha caratteristica rk(A) se

1. esiste un minore non nullo di ordine rk(A),

2. tutti i minori di ordine rk(A) + 1 sono nulli.

• Sia A una matrice m × n allora

rk(t A) = rk(A).

Esempio 3.2.9. Consideriamo la matrice A

!
2 5 0
.
−1 0 7

La caratteristica di A è almeno 1 in quanto vi sono elementi non nulli in A. Un

minore di ordine 2 non nullo è
2 5
=5
−1 0

quindi r(A) = 2.

Risulta utile per il calcolo della caratteristica di una matrice la seguente

Teorema 3.2.10 (Regola di Kronecker). Sia A ∈ Mm,n (R). Supponiamo che la

sottomatrice B = (ai j ) 1≤i≤p con p < min {m, n} abbia determinante non nullo, se tutte
1≤ j≤p
le sottomatrici (p + 1) × (p + 1) di A che si ottengono ”orlando” B (cioè aggiungendo
a B una delle righe ed una delle colonne restanti) hanno determinante nullo, allora
rk(A) = p.

Osservazione 3.2.11. L’ipotesi fatta nel teorema di Kronecker non è restrittiva

poichè la caratteristica di una matrice non cambia scambiando tra loro righe (o
colonne) poichè, con questa operazione, i minori della matrice cambiano al piú
segno.

55
Esempio 3.2.12. Si consideri la matrice

 1 2 −3 5 0 
 
A = −2 0 3 4 −3
 
3 0 −1 2 −5
 

poichè
1 2
,0
−2 0
per calcolarne la caratteristica basterà prendere in considerazione i 3 minori
ottenuti orlando !
1 2
−2 0
e quindi
1 2 −3 1 2 5 1 2 0
−2 0 3 , −2 0 4 , −2 0 −3
3 0 −1 3 0 2 3 0 −5
invece di tutti i 10 minori di ordine 3. Risulta che rk(A) = 3.
Terminiamo dando due relazioni relative alla caratteristica di una matrice.
1. Siano A una matrice m × n e B una matrice n × p, allora

rk(AB) ≤ min{rk(A), rk(B)}.

2. Siano A e B matrici m × n, allora

rk(A + B) ≤ rk(A) + rk(B).

3.3 Metodo di Gauss

Definizione 3.3.1. Una matrice A ∈ Mm,n (R) si dice ridotta per righe se il primo
elemento non nullo di ogni riga si trova su di una colonna più a sinistra del
primo elemento non nullo della riga successiva ossia se ai j , 0 e aik = 0 per ogni
k < j allora ahk = 0 per ogni h ≥ i e per k ≤ j.
Se una matrice quadrata è ridotta per righe allora è triangolare superiore.
La matrice
2 −3 1 0 
 
0 −1 4 −6
A = 
 
0 0 0 −2

 
0 0 0 4

56
è triangolare superiore ma non ridotta.
Una matrice A = (ai j ) ∈ Mm,n (R) si dice ridotta per colonne se t A è ridotta
per righe. Se una matrice quadrata è ridotta per colonne allora è triangolare
inferiore.

Definizione 3.3.2. Si chiamano trasformazioni o operazioni elementari sulle righe

(o sulle colonne) di una matrice A ∈ Mm,n (R) le seguenti operazioni:

(a) Scambiare due righe (o due colonne).

(b) Moltiplicare una riga (o una colonna) per un numero λ , 0.

(c) Sommare ad una riga un multiplo di un’altra riga (sommare ad una

colonna un multiplo di un’altra colonna).

Si ha il seguente risultato:

• Ogni matrice A ∈ Mm,n (R) si può trasformare in una matrice ridotta

per righe RA mediante una serie di operazioni elementari sulle righe.
Chiameremo RA una riduzione per righe di A.

• Ogni matrice A ∈ Mm,n (R) si può trasformare in una matrice ridotta per
colonne CA mediante una serie di operazioni elementari sulle colonne.
Chiameremo CA una riduzione per colonne di A.

Va notato che le riduzioni RA e CA di una matrice A non sono uniche dipendendo

queste dal tipo di operazioni usate. Ad esempio sia

0 −3 1 0 
 
1 −1 4 −6
.
 
2 0 1 −2

 
3 −2 0 4

Posso partire in tre modi scambiando la prima riga con la seconda, la terza e la
quarta

1 −1 4 −6 2 0 1 −2 3 −2 0 4 

     
0 −3 1 0  1 −1 4 −6 1 −1 4 −6
, , .
     
2 0 1 −2 0 −3 1 0  2 0 1 −2
  
     
3 −2 0 4 3 −2 0 4 0 −3 1 0

Otterrò tre matrici ridotte distinte.

57
Definizione 3.3.3. La caratteristica per righe di una matrice ridotta per righe A
è il numero delle righe di A non nulle. Analogamente definiamo caratteristica
per colonne di una matrice ridotta per colonne A è il numero delle colonne di A
non nulle.
Vale il seguente fatto fondamentale:
• La caratteristica di una matrice A coincide con la la caratteristica per righe
di una sua qualsiasi riduzione RA e con la caratteristica per colonne di una sua
qualsiasi riduzione CA .

• Utilizziamo la riduzione gaussiana per ottenere l’inversa di una matrice. Sia

 1 0 1 
 
A = −3 1 2 
 
−1 2 −3
 

Mediante una sequenza di operazioni elementari dobbiamo trasformare la

matrice
 1 0 1 1 0 0 
 
 −3 1 2 0 1 0 

−1 2 −3 0 0 1
 

in una matrice avente a sinistra la matrice identica I3 . Allora a destra comparrà

58
l’inversa A−1 .
 1 0 1 1 0 0
 

R2 + 3R1 −→  0 1
 5 3 1 0 

R3 + R1 0 2 −2 1 0 1
 

 1 0 1 1 0 0 
 
 
 
−→  0 1 5 3 1 0 

 
1  1 1 
R3  0 1 −1 0
2 2 2
 1 0 1 1 0 0 
 
 
 
−→  0 1 5 3 1 0 

 
R3 − R2
 5 1 
 0 0 −6 − −1
 2 2
 
 1 0 1 1 0 0 

 
 
−→  0 1 5 3 1 0 

 
1

5 1 1 
 
− R3  0 0 1 −
6 12 6 12
 
 7 1 1 
 1 0 0 − 
R1 − R3

 12 6 12 

11 1 5
 
R2 − 5R3 −→  0 1 0



 12 6 12 

 5 1 1 
0 0 1 −
 
12 6 12
Allora  
 7 1 1 
 12 − 6 12 
 
 
11 1 5
 
A = 
−1   .

 12 6 12 
 
 5 1 1 
−

12 6 12
Definizione 3.3.4 (Matrici elementari). Le operazioni elementari della Definizione
3.3.2 su una matrice A possono vedersi come il risultato della moltiplicazione
di A per opportune matrici dette “matrici elementari”. Le matrici elementari di
ordine n sono:

59
 1. la matrice identica In ;

2. la matrice Ei j con 1 ≤ i, j ≤ n e i , j, ottenuta da In scambiando la riga Ri

con la riga R j o, che è lo stesso, scambiando la colonna Ci con la colonna
C j;

3. la matrice Ei (λ) con λ ∈ R, λ , 0, ottenuta da In sostituendo l’1 della riga

Ri con λ;

4. la matrice Ei j (λ) con λ ∈ R, λ , 0, 1 ≤ i, j ≤ n e i , j, ottenuta da In

sostituendo lo 0 di posto (i, j) con λ.

Alcuni esempi con n = 4:

1 0 0 0 1 0 0 0

   
0 0 0 1 0 0 1 0
E24 =  , E23 =  .
 
0 0 1 0 0 1 0 0
   
0 1 0 0 0 0 0 1

1 0 0 0 1 0 −5 0

   
0 −3 0 0 0 1 0 0
E2 (−3) =  , E13 (−5) =  .
  
0 0 1 0 0 0 1 0
   
0 0 0 1 0 0 0 1
Le matrici elementari sono tutte invertibili. Precisamente si ha

det(Ei j )) = −1 i j = Ei j
E−1
1
det(Ei (λ)) = λ Ei (λ)−1 = Ei ( )
λ
det(Ei j (λ)) = 1 Ei j (λ)−1 = Ei j (−λ).

Sia ora A una matrice m × n. Le matrici elementari di ordine m operano con

la moltiplicazione a sinistra sulla matrice A nei seguenti modi:

1. Ei j A è la matrice ottenuta da A scambiando la riga Ri di A con la riga R j

di A;

2. Ei (λ)A è la matrice ottenuta da A moltiplicando per λ ogni elemento della

riga Ri di A;

3. Ei j (λ)A è la matrice ottenuta da A sostituendo la riga Ri con Ri + λR j .

Analogamente le matrici elementari di ordine n operano con la moltiplicazione

a destra sulla matrice A nei seguenti modi:

60
 1. AEi j è la matrice ottenuta da A scambiando la colonna Ci di A con la
colonna C j di A;
2. AEi (λ) è la matrice ottenuta da A moltiplicando per λ ogni elemento della
colonna Ci di A;
3. AEi j (λ) è la matrice ottenuta da A sostituendo la colonna C j con C j + λCi .

3.4 Sistemi lineari

Definizione 3.4.1. Consideriamo il sistema di m equazioni lineari in n incognite
x1 , x2 , . . . , xn a coefficienti in R
a11 x1 + a12 x2 + · · · + a1n xn = b1


.. ..



. . (3.4.1)




a x + a x + · · · + a x = b

m1 1 m2 2 mn n m

Una soluzione di tale sistema è un vettore riga (c1 , c2 , . . . , cn ) tale che sostituendo
nelle equazioni del sistema xi con ci , 1 ≤ i ≤ n si ottengano m identità.
Al sistema (3.4.1) vengono associate due matrici:

 a11 a12 . . . a1n 

 
 a21 a22 · · · a2n 
A =  .. .. .. .. 
 
 .
 . . . 
am1 am2 · · · amn


detta matrice dei coefficienti, o incompleta e

 a11 a12 ... a1n b1 

 
 a
 21 a22 ... a2n b2 
(A, b) =  .. .. .. .. .. 
 . . . . . 
...

am1 am2 amn bm


detta matrice completa. Poichè A è una sottomatrice di (A, b) si ha

rk(A) ≤ rk(A, b).
Sussiste il seguente teorema fondamentale
Teorema 3.4.2 (Rouchè - Capelli). Il sistema lineare (3.4.1) ha soluzioni se e solo se
la matrice completa e quella incompleta hanno la stessa caratteristica.
Inoltre se k = rk(A) = rk(A, b) allora il sistema ha ∞n−k soluzioni, con la conven-
zione che ∞0 = 1.

61
• Riducendo per righe con il metodo di Gauss la matrice completa (A, b) ot-
teniamo una matrice a cui è associato un sistema equivalente al sistema dato.
Vediamo due esempi.
Consideriamo il sistema



 2x1 − 2x2 − 7x3 + 4x4 = 2
x1 − x2 − 4x3 + 2x4 =1




−x1 + x2 + 3x3 − 2x4 = −1.



Riduciamo per righe la matrice completa

 2 −2 −7 4 2
 

 1 −1 −4 2 1 
 
−1 1 3 −2 −1
 

Con le operazioni elementari R2 −→ R2 + R3 e R3 −→ R3 + R2 e, infine, R3 −→

R3 − R2 otteniamo la matrice ridotta che ha caratteristica 2

 2 −2 −7 4 2 
 
 0 0 −1 0 0 
 
0 0 0 0 0
 

a cui è associato il sistema equivalente


2x1 − 2x2 − 7x3 + 4x4 =2


= 0,

−x3


ossia 
x 1

 = x2 − 2x4 + 1
= 0.

x 3


Le ∞2 soluzioni del sistema sono {(x2 − 2x4 + 1, x2 , 0, x4 ) : x2 , x4 ∈ R}.

Consideriamo il sistema



 −x1 − x2 + 2x3 = 1
x − 2x2 + x3 =1


 1


3x1 − 3x3 = 0.


Riduciamo per righe la matrice completa

 −1 −1 2 1 
 
 1 −2 1 1  .
 
3 0 −3 0

62
Con le operazioni elementari R2 −→ R2 + R1 e R3 −→ R3 + 3R1 e, infine,
R3 −→ R3 − R2 otteniamo la matrice ridotta
 −1 −1 2 1 
 
 0 −3 3 2  .
 
0 0 0 1
La matrice incompleta A ha una riga nulla e quindi rk(A) = 2 mentre la matrice
completa (A, b) non ha righe nulle quindi rk(A) = 3. Pertanto il sistema è
impossibile.
Teorema 3.4.3 (Cramer). Se, nel sistema (3.4.1), il numero delle equazioni è uguale
a quello delle incognite, cioè m = n, e se rk(A) = n ossia se
a11 a12 . . . a1n
a21 a22 . . . a2n
.. .. .. . ,0
. . . ..
an1 am2 . . . ann
allora il sistema (3.4.1) ha una ed una sola soluzione rappresentata dalla n-upla
(x1 , x2 , . . . , xn ) dove
a11 . . . b1 . . . a1n
.. .. ..
. . .
an1 . . . bn . . . ann
xj = 1≤ j≤n
a11 . . . a1n
.. ..
. .
an1 . . . ann
dove la colonna  
b1 
 . 
 .. 
 
bn
 

sosituisce la j-esima colonna  

a1j 
 .. 
 .  .
 
an j
Esempio 3.4.4. Consideriamo ll sistema di 3 equazioni in 3 incognite



 −x1 − 3x2 + 2x3 = 1
=1

2x1 − x3



x1 + x2 − 2x3 = 0.



63
Poichè
−1 −3 2
2 0 −1 = −6
1 1 −2
il sistema è di Cramer. L’unica soluzione è data dalla terna (x1 , x2 , x3 ) dove

1 −3 2
1 0 −1
0 1 −2 −3 1
x1 = = = ,
−6 −6 2
−1 1 2
2 1 −1
1 0 −2 3 1
x2 = = =−
−6 −6 2
−1 −3 1
2 0 1
1 1 0
x3 = = 0.
−6
Esempio 3.4.5. Si consideri il sistema omogeneo n × n + 1

a11 x1 + a12 x2 + · · · + a1n+1 xn+1 =0



.. ..



. .




a x + a x + · · · + a

=0
n1 1 n2 2 nn+1 xn+1

tale che la caratteristica della matrice incompleta sia massima cioè n. Per i
teoremi di Rouchè-Capelli e Cramer il sistema ha ∞1 soluzioni (x1 , . . . , xn+1 ) tali
che
a11 · · · ab1i · · · a1n+1
xi = (−1)i+1 k ... ..
.
..
. i = 1, . . . , n + 1
an1 · · · abni · · · ann+1
dove k ∈ R è una costante di proporzionalità e il cappuccio sugli elementi
della colonna i-esima vuole indicare che siffatta colonna non è presente nel
determinante. In particolare si consideri il sistema omogeneo 2 × 3

a11 x1 + a12 x2 + a13 x3 = 0


a21 x1 + a22 x2 + a23 x3 = 0



64
avente la matrice incompleta di caratteristica 2, allora le ∞1 soluzioni del sis-
tema sono !
a12 a13 a11 a13 a11 a12
k, − k, k
a22 a23 a21 a23 a21 a22
essendo k ∈ R.

3.5 Vettori linearmente indipendenti e basi

Definizione 3.5.1. Diremo che i vettori u1 , . . . um sono linearmente indipendenti o
che l’insieme {u1 , . . . um } è libero se
m
X
λi ui = 0 =⇒ λ1 = λ2 = · · · = λm = 0.
i=1

Diremo che i vettori u1 , . . . um sono linearmente dipendenti se non sono linear-

mente indipendenti.
• Siano dati i vettori u1 , . . . um di Rn . Se due o più tra questi vettori sono tra loro
proporzionali cioè se ui = µu j per due indici i e j e per un µ ∈ R allora u1 , . . . um
sono linearmente dipendenti. In particolare se due vettori tra gli u1 , . . . um sono
uguali o se un vettore tra essi è il vettore nullo allora u1 , . . . um sono linearmente
dipendenti.
• Sia S un insieme finito e libero di vettori di Rn , allora ogni sottoinsieme di S
è libero.
Definizione 3.5.2. Siano dati i vettori u1 , . . . um di Rn . Diremo che {u1 , . . . um } è un
insieme di generatori di Rn se per ogni u ∈ Rn esistono degli scalari λ1 , . . . , λm ∈ R
tali che
Xm
u= λi ui .
i=1
n
• Se S è un insieme di generatori di R e T ⊃ S allora T è un insieme di generatori
di Rn .
Definizione 3.5.3. Una base per lo spazio vettoriale Rn è un insieme libero di
generatori. I vettori
e1 = (1, 0, . . . , 0), e2 = (0, 1, 0 . . . , 0), e3 = (0, 0, 1, 0 . . . , 0), · · · en = (0, 0, . . . , 1),
costituiscono la base canonica di Rn . Sia infatti u = (x1 , x2 , . . . , xn ) un vettore di
Rn allora si vede immediatamente che
Xn
u= xi ei .
i=1

65
Quindi {e1 , . . . en } è un insieme di generatori di Rn . Sia
n
X
λi ei = 0.
i=1

Ciò vuol dire che (λ1 , . . . , λn ) = (0, 0, . . . , 0) da cui segue che λ1 = λ2 = · · · =

λn = 0. Quindi {e1 , . . . en } è un insieme libero.
Puntualizziamo alcuni fatti fondamentali (cfr. l’Osservazionee 3.5.5):
Proposizione 3.5.4. 1. Un sottoinsieme libero di Rn ha al più n elementi distinti.

2. Un insieme di generatori di Rn ha almeno n elementi.

3. Una base di Rn ha esattamente n elementi distinti. Quindi tutte le basi hanno lo

stesso numero di elementi.

4. Un insieme libero di Rn avente esattamente n elementi distinti è una base di Rn .

5. Ogni insieme libero può essere completato in modo da formare una base.

6. Ogni insieme di generatori contiene una base.

Osservazione 3.5.5. Dati m vettori in Rn

u1 = (a11 , . . . , an1 ), u2 = (a12 , . . . , an2 ), . . . , um = (a1m , . . . , anm )

Consideriamo la matrice avente come righe i vettori u1 , . . . , um :

a11 . . . a1m 
 

A =  ... ..  .


. 
an1 . . . anm
 

Allora k vettori tra essi sono linearmente indipendenti se e solo se la caratter-

istica della matrice è k. I k vettori linearmente indipendenti sono tutti e soli
quelli che “incrociano” un minore di A di ordine k non nullo. Ad esempio i
vettori di R4

u1 = (1, 2, 0, 1), u2 = (2, 1, 1, 0), u3 = (3, 0, −1, 1)

sono linearmente indipendenti. poichè la matrice

1 2 0 1
 
2 1 1 0
 
3 0 −1 1

66
ha caratteristica 3. In R4 i vettori

u1 = (1, 2, 0, 1), u2 = (2, 1, 1, 0), u3 = (3, 3, 1, 1),

u4 = (1, −4, 2, −3), u5 = (0, −6, 2, −4)

non sono linearmente indipendenti. La matrice
 
1 2 0 1 
2 1 1 0 
 
3 3 1 1 
 
 
1 −4 2 −3
 
0 −6 2 −4

ha caratteristica 2 e un minore di ordine 2 è

1 2
= −3 , 0
2 1

i vettori u1 , u2 sono linearmente indipendenti mentre ogni sottoinsieme di

{u1 , u2 , u3 , u4 , u5 }

che contiene strettamente u1 e u2 non è libero.

3.6 I sottospazi di uno spazio vettoriale

Definizione 3.6.1. Diremo che un sottinsieme W di Rn è un sottospazio vettoriale
di Rn se

1. Se u, v ∈ W allora u + v ∈ W.

2. Se u ∈ W allora per ogni λ ∈ R si ha λu ∈ W.

Quindi W con le operazioni indotte da Rn è esso stesso uno spazio vettoriale

su R. L’insieme {0n } è il sottospazio nullo di Rn .
• Poichè se u ∈ W anche −u ∈ W segue da 1) che 0n ∈ W.
2
In Mn (R)  Rn il sottinsieme delle matrici simmetriche è un sottospazio
vettoriale di Mn (R): se A = (ai j ) e B = (bi j ) sono simmetriche allora A + B =
(ai j + bi j ) è simmetrica e cosı̀ pure λA = (λai j ), ∀ λ ∈ R. Il sottinsieme delle
matrici invertibili di Mn (R) non è un sottospazio come si evince dall’esempio:

67
Definizione 3.6.2. Sia dato in Rn un insieme S formato da m vettori u1 , . . . , um .
Il sottinsieme
m
X
L(S) = {w ∈ R : w =
n
λi ui , λi ∈ R, i = 1, . . . m}
i=1

dicesi sottospazio generato dai vettori u1 , . . . , um .

E’ immediato verificare che L(S) è un sottospazio vettoriale di Rn . Se i vettori

di S sono linearmente indipendenti e dimK (V) = n allora necessariamente m ≤ n
e m sará la dimensione del sottospazio. Essi formano una base per L(U). Se
n = m allora L(S) = V.
Se i vettori non sono linearmente indipendenti allora dimK (W) = p dove p è il
numero massimo di vettori linearmente indipendenti contenuti in S. Se S0 è un
sottinsieme massimale di S costituito di vettori indipendenti allora

L(S) = L(S0 ).

Esempio 3.6.3. In R4 consideriamo l’insieme S vettori

u1 = (1, 2, 0, 1), u2 = (3, 0, 1, 0), u3 = (4, 2, 1, 1), u4 = (2, 4, 0, 2)

Poichè la matrice
1 3 4 2
 
2 0 2 4

0 1 1 0
 
 
1 0 1 2
ha caratteristica 2. Posto S0 = {u1 , u2 } allora L(S) = L(S0 ).

Proposizione 3.6.4. Dato un sistema lineare omogeneo

a11 x1 + a12 x2 + · · · + a1n xn =0



.. ..



. .




a x + a x + · · · + a x

=0
m1 1 m2 2 mn n

tale che la matrice completa abbia caratteristica p allora l’insieme delle soluzioni forma
un sottospazio di Rn di dimensione n − p. Viceversa, se V è un sottospazio di Rn di
dimensione k, allora V è l’insieme delle soluzioni di un sistema lineare omogeneo in n
incognite la cui matrice completa ha caratteristica n − k.

68
Esempio 3.6.5. 1) Dato il sistema lineare

2x1 − 3x2 + x4 =0


x1 + x3 =0



2 1
 
le soluzioni sono rappresentate dai vettori −x3 , − x3 + x4 , x3 , x4 dove x3 ,
3 3
x4 ∈ R. Ora
2 1 2 1
     
−x3 , − x3 + x4 , x3 , x4 = x3 −1, − , 1, 0 + x4 0, , 0, 1
3 3 3 3
quindi il sottospazio associato al sistema ha come base
2 1
   
−1, − , 1, 0 , 0, , 0, 1 .
3 3
2) Sia dato S = {u1 , u2 } dove u1 = (1, 2, 1, 0) e u2 = (3, 0, 0, 1). Il sottospazio L(S)
ha come base S. Sia u = (x1 , x2 , x2 , x4 ) il vettore generico appartenente a L(S)
allora la matrice
x1 1 3
 
x2 2 0
 
x3 1 0
 
x4 0 1
deve avere caratteristica 2 e quindi tutti i minori di ordine 3 devono essere
nulli. Allora, applicando la regola di Kronecker, basta provare che sono nulli i
minori di ordine 3 ottenuti orlando la matrice 2 × 2 situata in basso a destra
!
1 0
0 1

Quindi avremo
x2 2 0 x1 1 3
x3 1 0 = 0, x3 1 0 = 0
x4 0 1 x4 0 1
e quindi otterremo il sistema lineare

x1 − x3 − 3x4 = 0


x2 − 2x3 = 0



Definizione 3.6.6. Siano dati V1 , . . . , Vm sottospazi di V. Il sottospazio inter-

sezione V1 ∩ · · · ∩ Vm ha dimensione ≤ min(d1 , . . . , dm ) dove di = dimK (Vi ),
i = 1, . . . , m.

69
Esempio 3.6.7. Sia V1 il sottospazio di R4 associato al sistema lineare

x1 − x3 − 3x4 = 0


=0

x2 − 2x3


e V2 il sottospazio di R4 associato al sistema lineare


2x1 − 3x2 + x4 = 0


x1 + x3 =0



allora il sottospazio V1 ∩ V2 è associato al sistema


2x1 − 3x2 + x4 = 0



x1 + x3 =0



=0




 x1 − x3 − 3x4
=0

x2 − 2x3


Quindi V1 ∩ V2 = {0}.

3.7 I vettori geometrici

Definizione 3.7.1 (Vettori geometrici). Un vettore geometrico u applicato nel punto
−−→
O del piano (o dello spazio tridimensionale) è un segmento orientato OP avente
come primo estremo il punto O, detto punto di applicazione, e come secondo estremo
il punto P (Figura 3.1). La direzione del vettore u è data dalla retta OP su cui il
vettore giace; il modulo kuk di u è la lunghezza del segmento OP; il verso di u è
indicato dalla freccia sul secondo estremo. Indicheremo con V2O l’insieme dei
vettori del piano con punto di applicazione O e con V3O l’insieme dei vettori
−−→
dello spazio con punto di applicazione O. Il vettore OO è il vettore nullo che ha
modulo 0 e a cui non si attribuisce nè direzione nè verso.
−−→ −−→
La somma di due vettori entrambi non nulli u = OP e v = OQ non aventi
la stessa direzione è il vettore, con punto di applicazione O, diagonale del
parallelogramma individuato da u e v (Figura 3.2). Se u e v hanno la stessa
direzione allora u + v ha la stessa direzione di u e v e

kuk + kvk se u e v hanno lo stesso verso

ku + vk = 

|kuk − kvk| se u e v hanno verso opposto.


70
 Figura 3.1:

u
•
O

Figura 3.2:

v u+v
P
H
u

Il verso di u + v, se non nullo, è quello del vettore avente modulo maggiore. Se

−−→ −−→
u = OO è il vettore nullo e v = OQ allora u + v = v.
−−→
Il prodotto λu di uno scalare λ , 0 per un vettore u = OP è il vettore, con punto
di applicazione O tale che

kλuk = |λ|kuk, (dove |λ| è il valore assoluto di λ),

la cui direzione è quella di u e il cui verso è quello di u se λ > 0 e opposto a

−−→
quello di u se λ < 0. Se λ = 0 allora λu è il vettore nullo OO.
Osservazione 3.7.2. Fissiamo nel piano (o nello spazio) un sistema di coor-
dinate cartesiane ortogonali Oxy (o Oxyz) cioè una coppia di rette ortogonali
orientate¿ Ad ogni punto P del piano (o dello spazio) è biunivocamente asso-
ciata la coppia (x, y) (o la terna (x, y, z)) delle sue coordinate. Pertanto vi sono

71
le corrispondenze biunivoche
−−→
OP ←→ P ←→ (x, y), V2O ←→ R2 ,
−−→
OP ←→ P ←→ (x, y, z), V3O ←→ R3 .

Tali corrispondenze “rispettano le operazioni”:

−−→ −−→
se OP ←→ (x, y) e OQ ←→ (x0 , y0 ) allora
−−→ −−→
OP + OQ ←→ (x + x0 , y + y0 )
−−→
λOP ←→ (λx, λy).
−−→ −−→
Analogamente se OP ←→ (x, y, z) e OQ ←→ (x0 , y0 , z0 ) allora
−−→ −−→
OP + OQ ←→ (x + x0 , y + y0 , z + z0 )
−−→
λOP ←→ (λx, λy, λz).

Osservazione 3.7.3. I sottospazi di dimensione 1 del piano o dello spazio sono

le rette passanti per l’origine. I sottospazi di dimensione 2 dello spazio sono i
piani passanti per l’origine.

3.8 Il prodotto scalare su Rn

Definizione 3.8.1. Siano u = (x1 , x2 , . . . , xn ) e v = (y1 , y2 , . . . , yn ) due vettori in
Rn . Il prodotto scalare di u e v il numero reale definito da

u · v = x1 y1 + x2 y2 + · · · xn yn .

Il prodotto scalare gode delle seguenti proprietá: siano u, v e w ∈ Rn e λ ∈ R,

allora

1. u · v = v · u (proprietà commutativa).

2. u · (v + w) = u · v + u · w (proprietà distributiva).

3. λ(u · v) = (λu) · v = u · (λv) (omogeneità).

• Consideriamo ora i “casi geometrici”: il piano R2 e lo spazio R3 . Indichiamo

con O l’origine (cioè il vettore 0). Dati due vettori u = P − O, v = Q − O che
non stanno su una stessa retta, l’angolo u,cv da essi formato è l’angolo POQ
b ed

72
 Figura 3.3:

v
P

O
O u
P
v

è sempre minore di π (vedere Figura 3.3). Se appartengono alla stessa retta ed

hanno lo stesso verso allora u, cv = 0, se hanno verso opposto u, cv = π.
Si consideri ora il triangolo di vertici O, P, Q. Il teorema di Carnot afferma
che
2 2 2
PQ = OP + OQ − 2OP OQ cos(u, cv)
poichè u − v è il vettore P − Q si ha che
ku − vk2 = kuk2 + kvk2 − 2kukkvk cos(u,
cv).
Se u = (a1 , a2 , a3 ), v = (b1 , b2 , b3 ) allora P − Q = (a1 − b1 , a2 − b2 , a3 − b3 ) pertanto
(a1 − b1 )2 + (a2 − b2 )2 + (a3 − b3 )2 = a21 + a22 + a23 + b21 + b22 + b23
q q
−2 a1 + a2 + a3 b21 + b22 + b23 cos(u,
2 2 2 cv),
da cui, con facili calcoli, si ottiene
a1 b1 + a2 b2 + a3 b3
cv) = q
cos(u, q .
a1 + a2 + a3 b1 + b2 + b3
2 2 2 2 2 2

73
Le suddette considerazioni valgono ovviamente nel piano e conducono alla
seguente
a b +a b
cv) = q 1 1 q2 2
cos(u,
a21 + a22 b21 + b22
dove u = (a1 , a2 ), v = (b1 , b2 ). Pertanto

u · v = kukkvk cos(u,
cv).

• Notiamo esplicitamente che u · v = 0 se e solo se u e v sono ortogonali cioè

giacciono su rette perpendicolari fra loro.
• Chiamiamo versore del vettore u il vettore
1
vers(u) = u.
kuk
• Il vettore
u·v
Pv (u) = v
kvk2
è detto proiezione ortogonale di u su v.

• Una base {u1 , u2 , u3 } di R3 è ortogonale se ui · u j = 0 se i , j, ortonormale se è

ortogonale e kui k = 1, 1 ≤ i ≤ 3. La base canonica è ortonormale. Definizioni
identiche si danno nel piano.
• Una base ordinata di R3 {u1 , u2 , u3 }, con u1 = (u11 , u21 , u31 ), u2 = (u12 , u22 , u32 ),
u3 = (u13 , u23 , u33 ), si dirà destrorsa o positiva (sinistrorsa o negativa) se u3 vede u1
sovrapporsi su u2 ruotando in senso antiorario (orario) di un angolo minore di
π. E’ immediato notare che la base canonica è destrorsa. Per ragioni legate alla
continuità della funzione determinante che non approfondiamo in questa sede
la base {u1 , u2 , u3 } è destrorsa se e solo se
u11 u12 u13
u21 u22 u23 > 0.
u31 u32 u33
Nel piano una base ordinata {u1 , u2 }, dove u1 = (u11 , u21 ), u2 = (u12 , u22 ), si dirà
destrorsa o positiva (sinistrorsa o negativa) se u1 si sovrappone a u2 ruotando in
senso antiorario (orario) di un angolo minore di π. E’ immediato notare che la
base canonica è destrorsa. Una base ordinata {u1 , u2 }, dove u1 = (u11 , u21 ), u2 =
(u12 , u22 ), è destrorsa se e solo se
u11 u12
> 0.
u21 u22

74
3.9 Il prodotto vettoriale in R3
Definizione 3.9.1. Siano dati due vettori u, v nello spazio. Il prodotto vettoriale
u ∧ v di u e v è il vettore avente le seguenti proprietà:

i) ku ∧ vk = kukkvk sin(u,
cv)

ii) u ∧ v · u = u ∧ v · v = 0

iii) la terna {u, v, u ∧ v} è destrorsa (se non è degenere).

• Il modulo del prodotto vettoriale ku ∧ vk rappresenta l’area A del parallelo-

gramma individuato dai vettori u e v. Infatti (vedere Figura 3.4)

A = OP · QH = kuk · kvk sin(u,

cv).

Figura 3.4:

v
P
H
u

Sia {u, v, w} una base ortonormale ordinata, essa è destrorsa se e solo se

u ∧ v = w, v ∧ w = u, w ∧ u = v.

Se u = (a, b, c), v = (a0 , b0 , c0 ) allora

!
b c a c a b
u ∧ v = 0 0 ,− 0 0 , 0 0
b c a c a b

75
Infatti è soddisfatta i)
2 2 2
b c a c a b a2 + b2 + c2 aa0 + bb0 + cc0
0 + 0 0 + 0 0 =
0
b c a c a b aa0 + bb0 + cc0 a02 + b02 + c02

kuk2 u · v
= = kuk2 kvk2 − (u · v)2 = kuk2 kvk2 (1 − cos2 (u,
cv)) = ku ∧ vk2 ,
u · v kvk2
ii)
a b c
b c a c a b
w·u=a 0 0 −b 0 0 +c 0 0 = a b c =0
b c a c a b
a0 b0 c0
a0 b0 c0
b c a c a b
w · v = a0 0 0 − b0 0 0 + c0 0 0 = a b c = 0
b c a c a b
a0 b0 c0
e iii)
a b c
a0 b0 c0
> 0.
b c a c a b
− 0 0
b0 c0 a c a0 b0
Il prodotto vettoriale gode delle proprietà:
1. u ∧ v = −v ∧ u (anticommutatività).

2. (u + v) ∧ w = u ∧ w + v ∧ w (distributività).

3. (ku) ∧ v = u ∧ (kv) = k(u ∧ v) (omogeneità).

4. u ∧ (v ∧ w) = (u · w)v − (u · v)w.

5. (u ∧ v) ∧ w = (u · w)v − (v · w)u.

6. u ∧ v = 0 se e solo se u e v sono linearmente dipendenti.

Per 4) e 5) il prodotto vettoriale non è associativo.
• Per quanto visto sopra l’operazione ∧ : R3 × R3 → R3 non è associativa nè
commutativa e non ha elemento neutro.
Esempio 3.9.2 (Proiezione ortogonale di un vettore su un piano). Siano u, v e
w tre vettori linearmente indipendenti di R3 . Determiniamo il vettore Pu,v (w)
proiezione ortogonale di w sul piano individuato dai vettori u e v. Il vettore
Pu,v (w) è la proiezione ortogonale di w su un vettore k ortogonale al vettore u ∧ v
(poichè sta sul piano individuato da u e v) e ortogonale al vettore un qualsiasi

76
 Figura 3.5:

w
u∧v v • P
K
H
u

−−→
OK = Pu,v (w)
(u ∧ v) ∧ w

vettore ortoganale al piano individuato da w e da u ∧ v. Pertanto possiamo

prendere (Figura 3.5)
k = (u ∧ v) ∧ ((u ∧ v) ∧ w).
Allora
Pu,v (w) = Pk (w).
Definizione 3.9.3. Dati tre vettori u = (a, b, c), v = (a0 , b0 , c0 ), w = (a00 , b00 , c00 ) si ha
che
u · v ∧ w = u ∧ v · w.
Il prodotto misto [u, v, w] dei vettori u, v, w è uno dei due membri di (1). Si ha che

a b c
u · v ∧ w = 0 b0 c0 .
a
a00 b00 c00
• Il valore assoluto |u · v ∧ w| rappresenta il volume del parallelepipedo che ha
come spigoli u, v, w (vedere Figura 3.6). Infatti

|u ∧ v · w| = ku ∧ vkkwk|cos(u [
∧ v, w)| = ku ∧ vkkwk sin(ROK)
b = Ah

77
dove A = ku ∧ vk è l’area di base (il parallelogramma individuato da u e v) e
h = kwk sin(ROK)
b è l’altezza RK del parallelepipedo relativa al vertice R.

Figura 3.6:

w
u∧v v • P
K
H
u

Il prodotto misto ha le seguenti proprietà:

i) [u, v, w] = 0 se e solo se i tre vettori sono linearmente dipendenti.

ii) [u, v, w] > 0 se la terna ordinata {u, v, w} è concorde con la base canonica.e

iii) [u, v, w] = [v, w, u] = [w, u, v] = −[u, w, v] = −[w, v, u] = −[v, u, w].

iv) Il prodotto misto è lineare rispetto ai tre vettori u, v, w, cioè

[λu+µu0 , v, w] = λ[u, v, w]+µ[u0 , v, w], [u, λv+µv0 , w] = λ[u, v, w]+µ[u, v0 , w],

[u, v, λw + µw0 ] = λ[u, v, w] + µ[u, v, w0 ].

78
Capitolo 4

Grafi

Definizione 4.0.4. Un grafo è una quadrupla Γ = (V, A, ∂0 , ∂1 ) dove V e A sono

insiemi e ∂0 : A → V, ∂1 : A → V sono funzioni. Gli elementi di V sono detti
vertici o nodi di Γ e gli elementi di A sono gli archi di Γ. Dato un arco a ∈ A i
valori ∂0 (a) e ∂1 (a) sono detti partenza e arrivo di a, rispettivamente.
• Dato un grafo Γ = (V, A, ∂0 , ∂1 ), un cammino da v a w di lunghezza n è una tripla
(v, (a1 , . . . , an ), w) dove v, w ∈ V e a1 , . . . , an ∈ A tali che

v = ∂0 (a1 ), ∂1 (a1 ) = ∂0 (a2 ), . . . , ∂1 (an ) = w.

Considereremo cammino anche una tripla (v, ( ), v) di lunghezza 0.

• Un cappio o laccio in un grafo è un arco a tale che ∂0 (a) = ∂1 (a).

• Due archi a e b in un grafo tali che ∂0 (a) = ∂0 (b) e ∂1 (a) = ∂1 (b) si dicono
paralleli.

• Un circuito è un cammino da un vertice a sé dove tutti gli archi sono

distinti.

• Il grado d’ingresso di un vertice è il numero degli archi che arrivano nel

vertice.

• Il grado d’uscita di un vertice è il numero degli archi che partono dal

vertice.

• Un grafo è orientato se, presi comuque due vertici v e w cè al massimo un

arco da v a w.

• Un grafo è semplice se è orientato e dove, per ogni coppia di vertici v e w,

se cè un arco da v a w allora cè un arco da w a v.

79
 • Un grafo completo è un grafo semplice dove cè un arco per ogni coppia di
vertici distinti.

• Un grafo è connesso se presi comunque due vertici v e w esiste un cammino

da v a w.

• Un ciclo in un grafo è un cammino da un vertice a sé dove tutti i vertici,

escluso l’ultimo, sono a due a due distinti; in particolare un ciclo è un
circuito.

Definizione 4.0.5. Un grafo non-orientato è una quintupla Γ = (V, A, ∂0 , ∂1 , j)

dove (V, A, ∂0 , ∂1 ) è un grafo e j : A → A è una funzione sugli archi tale che, per
ogni a ∈ A si abbia

∂0 ( j(a)) = ∂1 (a), ∂1 (j(a)) = ∂0 (a), j( j(a)) = a.

80
Capitolo 5

Algebre eterogenee

81
Appendice A

Aritmetica

A.1 Definizioni di base

La teoria dei numeri nasce come teoria sistematica con Euclide (Alessandria
d’Egitto, 300 a.C.). I libri aritmetici degli Elementi, il VII, l’VIII e il IX libro
forniscono le definizioni e i teoremi fondamentali dell’aritmetica.

Definizione A.1.1. Nel VII Libro vi sono 22 definizioni tra cui:

i) Un intero a è sottomultiplo o divisore di un intero b (detto a sua volta multiplo

di a) se esiste un intero k tale che b = ka; in simboli a | b. Se a non divide b
scriveremo a - b.

ii) Un intero a è pari se 2 | a, dispari se 2 - a.

iii) Un intero a > 1 è un numero primo se i suoi soli divisori sono 1 e a. Numeri
primi sono: 2, 3, 5, 7, 11, 13, . . . . Un intero positivo è un numero composto
se non è primo.

iv) Il massimo comun divisore MCD(a, b) di 2 numeri interi non nulli a e b è il

più grande divisore positivo comune di quei numeri. Quindi MCD(a, b) =
MCD(|a|, |b|). Poniamo inoltre MCD(a, 0) = |a| per ogni intero a , 0.

v) Due interi a e b sono primi tra di loro se MCD(a, b) = 1.

vi) Il minimo comune multiplo mcm(a, b) di 2 numeri interi non nulli a e b

è il più piccolo multiplo positivo di quei numeri. Quindi mcm(a, b) =
mcm(|a|, |b|).

82
A.2 Algoritmo euclideo in Z
Proposizione A.2.1 (Algoritmo di divisione: Proposizione I del Libro VII).
Siano a, b ∈ Z, a , 0, allora esiste un unico q ∈ Z e un unico intero r, 0 ≤ r < |a|, tale
che
b = aq + r.
L’intero q è il quoziente della divisione di b per a e r è il resto.

Dimostrazione. Sia qa il più grande multiplo di a tale che qa ≤ b. Posto

r = b − qa si ha r ≥ 0. Se per assurdo fosse r = b − qa ≥ |a|, allora avremmo

b − qa ≥ a =⇒ qa < (q + 1)a ≤ b, se a > 0;

b − qa ≥ −a =⇒ qa < (q − 1)a ≤ b, se a < 0,

contro l’ipotesi che qa sia il più grande multiplo di a tale che qa ≤ b. Quindi
r < |a|. Proviamo ora l’unicità. Supponiamo ora che b = aq1 + r1 = aq2 + r2 con
0 ≤ r1 , r2 < |a| allora a(q1 − q2 ) = r2 − r1 . Ovviamente r1 , r2 se e solo se q1 , q2 .
Supponiamo r2 > r1 : allora
se a > 0 allora q1 − q2 > 0 e (q1 − q2 )a ≤ r1 + (q1 − q2 )a = r2 < a che è assurdo;
se a < 0 allora q1 − q2 < 0 e (−a)(q2 − q1 ) ≤ r1 + (−a)(q2 − q1 ) = r2 < −a che è ancora
un assurdo. 

Esempio A.2.2. Se b = 24 e a = 13 allora q = 1, r = 11 e 24 = 13 · 1 + 11.

Se b = −11 e a = 5 allora q = −3, r = 4 e −11 = 5 · (−3) + 4 (la decomposizione
−11 = 5·(−2)−1 non è quella della Proposizione A.2.1 perchè il resto è negativo).

Corollario A.2.3. Sia a un intero positivo e b un intero > 1. Allora esistono degli
interi non negativi n, c0 , . . . , cn tali che 0 ≤ ci < b, 0 ≤ i ≤ n con cn > 0 tali che

a = cn bn + · · · + c1 b + c0 .

Inoltre siffatta rappresentazione è unica. Diremo quindi che a ha in base b la rappre-

sentazione
(a)b = cn cn−1 · · · c1 c0 . (A.2.1)

Esempio A.2.4. Per determinare la (A.2.1) si cerca il multiplo della massima

potenza di b, kbn con k < b, tale che kbn ≤ a; poi si cerca il multiplo della massima
potenza di b, hbm con h < b, tale che hbm ≤ a − kbn e cosı̀ via. Vediamo alcune
rappresentazioni:

- Poichè 2301 = 2 · 103 + 3 · 102 + 0 · 10 + 1, (2301)10 = 2301.

83
 - Poichè 2301 = 1 · 211 + 1 · 27 + 1 · 26 + 1 · 25 + 1 · 24 + 1 · 23 + 1 · 22 + 1,
(2301)2 = 100011111101.

- Poichè 2301 = 3 · 54 + 3 · 53 + 2 · 52 + 1, (2301)5 = 33201.

Introduciamo 6 nuove cifre: a per 10, b per 11, c per 12, d per 13, e per 14 e f per
15. In base 16 (la base esadecimale) avremo

2301 = 8 · 162 + 15 · 16 + 13 =⇒ (2301)16 = 8 f d.

Algoritmo euclideo: Proposizione II del Libro VII. Siano a, b ∈ N? . Iterando

la Proposizione A.2.1 si ha

b = q1 a + r1 0 ≤ r1 < a
a = q2 r1 + r2 0 ≤ r2 < r1
r1 = q3 r2 + r3 0 ≤ r3 < r2
..
.
ri−1 = qi+1 ri + ri+1 0 ≤ ri+1 < ri (A.2.2)
..
.
rn−3 = qn−1 rn−2 + rn−1 0 ≤ rn−1 < rn−2
rn−2 = qn rn−1 + rn 0 ≤ rn < rn−1
rn−1 = qn+1 rn .

La sequenza di divisioni deve terminare dopo un numero finito di passi ≤ a

poichè i resti ri decrescono e sono non negativi. Allora

MCD(a, b) = rn = ultimo resto non nullo.

Esempio A.2.5. Determiniamo MCD(963, 657).

963 = 657 · 1 + 306

657 = 306 · 2 + 45
306 = 45 · 6 + 36 (A.2.3)
45 = 36 · 1 + 9
36 = 9 · 4.

Quindi MCD(963, 657) = 9.

Proposizione A.2.6 (Identità di Bézout). Siano a, b ∈ Z. Allora esistono x, y ∈ Z

tali che
MCD(a, b) = ax + by. (A.2.4)

84
Esempio A.2.7. Illustriamo la Proposizione A.2.6 con un esempio. Determini-
amo x e y tali che MCD(963, 657) = 963x + 657y. Dall’Esempio A.2.5 sappiamo
che MCD(963, 657) = 9. Ripercorriamo al contrario la (A.2.3). Avremo

9 = 45 − 36
= 45 − (306 − 45 · 6)
= −306 + 45 · 7
= −306 + (657 − 306 · 2) · 7
= 657 − 963 + [657 − (963 − 657) · 2] · 7
= 657 − 963 + 657 · 7 − 963 · 14 + 657 · 14
= 657 · (22) + 963 · (−15).

Pertanto x = −15, y = 22 e

MCD(963, 657) = 963 · (−15) + 657 · (22).

Definizione A.2.8. Siano a1 , . . . , an ∈ Z, tutti non nulli. Il massimo comun

divisore MCD(a1 , . . . , an ) di a1 , . . . , an è il più grande divisore positivo dei numeri
a1 , . . . , an . Il minimo comun multiplo mcm(a1 , . . . , an ) di a1 , . . . , an è il più piccolo
multiplo positivo dei numeri a1 , . . . , an . Osserviamo che

MCD(a1 , . . . , an ) = MCD(|a1 |, . . . , |an |).

Inoltre
MCD(0, a1 , . . . , an ) = MCD(a1 , . . . , an ).
Il massimo comun divisore e il minimo comun multiplo possono essere calcolati
ricorsivamente. Infatti

MCD(a1 , . . . , an ) = MCD(a1 , MCD(a2 , . . . , an )),

mcm(a1 , . . . , an ) = mcm(a1 , mcm(a2 , . . . , an )).

Osservazione A.2.9. Dovendo calcolare MCD(a1 , . . . , an ) si può procedere come

segue. Supponiamo che a1 ≤ ai per ogni i ≥ 2; allora

MCD(a1 , . . . , an ) = MCD(a1 , r2 , . . . , rn )

dove, se i ≥ 2, ri è il resto della divisione ai = a1 qi + ri . Procedendo in questo

modo si otterranno degli zeri e si ridurrà quindi progressivamente fino a 2 il
numero n degli elementi di cui si vuol calcolare il massimo comun divisore.

85
Esempio A.2.10. Calcoliamo MCD(81719, 52003, 33649, 30107). Avremo

MCD(81719, 52003, 33649, 30107) = MCD(21505, 21896, 3542, 30107)

= MCD(253, 644, 3542, 1771)
= MCD(253, 138, 0, 0)
= MCD(253, 138)
= 23.

Proposizione A.2.11 (Equazione diofantea di 1◦ grado). Siano a, b, n interi.

L’equazione
ax + by = n (A.2.5)
ammette soluzioni (x, y) ∈ Z × Z se e solo se MCD(a, b) | n. In particolare se i
coefficienti di x e y, a e b, sono primi tra di loro la (A.2.5) ha soluzioni.

Dimostrazione. La condizione è ovviamente necessaria dato che

MCD(a, b) | a ∧ MCD(a, b) | b =⇒ MCD(a, b) | n.

Vediamo ora come la condizione sia anche sufficiente. Innanzitutto determini-

amo una soluzione particolare della (A.2.5). La (A.2.5) è equivalente (cioè ha
le stesse soluzioni dell’equazione

a1 x + b1 y = c (A.2.6)

dove
a b n
a1 = , b1 = , c= . (A.2.7)
MCD(a, b) MCD(a, b) MCD(a, b)

Per la Proposizione A.2.6 esistono x1 e y1 ∈ Z tali che

a1 x1 + b1 y1 = MCD(a1 , b1 ) = 1. (A.2.8)

Allora prendendo
x0 = cx1 , y0 = cy1 , (A.2.9)
otteniamo
a1 x0 + b1 y0 = a1 cx1 + b1 cy1 = c(a1 x1 + b1 y1 ) = c,
quindi (x0 , y0 ) è soluzione di (A.2.6). Consideriamo ora l’equazione omogenea

a1 x + b1 y = 0. (A.2.10)

86
Tutte e sole le soluzioni di (A.2.10) sono della forma

(x, y) = (kb1 , −ka1 ), k∈Z

Tutte e sole le infinite soluzioni di (A.2.6) sono allora della forma (x, y) dove

x = x0 + kb1 , y = y0 − ka1 , k ∈ Z.

Infatti
a1 (x0 + kb1 ) + b1 (y0 − ka1 ) = a1 x0 + b1 y0 = c.


Esempio A.2.12. Troviamo, se esistono, le soluzioni intere dell’equazione 728x+

329y = 2. Poichè 2 - 329 l’equazione non ha soluzioni intere.

Esempio A.2.13. Troviamo, se esistono, le soluzioni intere dell’equazione 175x+

77y = 329. Innanzitutto calcoliamo MCD(175, 77). Mediante l’algoritmo eu-
clideo abbiamo

175 = 2 · 77 + 21
77 = 3 · 21 + 14
21 = 1 · 14 + 7
14 = 2 · 7 + 0,

quindi MCD(175, 77) = 7. Poichè 7 | 329 = 7 · 47 l’equazione ha soluzioni intere

ed è equivalente all’equazione

25x + 11y = 47.

Determiniamo ora degli interi x1 e y1 tali che valga l’identità di Bézout (A.2.4)

25x1 + 11y1 = 1.

Mediante l’algoritmo euclideo abbiamo

25 = 2 · 11 + 3
11 = 3·3+2
3 = 1·2+1
2 = 1 · 2 + 0.

87
 Andando a ritroso da sopra otteniamo

1 = 3−2
= 3 − (11 − 3 · 3)
= 4 · 3 − 11
= 4(25 − 2 · 11) − 11
= 4 · 25 + (−9) · 11,

per cui
1 = 4 · 25 + (−9) · 11.
Con le notazioni delle (A.2.8) e (A.2.9) avremo x1 = 4, x2 = −9, c = 47 per cui
una soluzione particolare è

x0 = 47 · 4 = 188, y0 = 47 · (−9) = −423.

Tutte le soluzioni della nostra equazione sono allora

x = 188 + 11k, y = −423 − 25k, k ∈ Z,

ossia
(x, y) ∈ {(188 + 11k, −423 − 25k) : k ∈ Z}.
Quanto visto per l’equazione in due incognite (A.2.5) si generalizza ad una
equazione in n incognite.
Proposizione A.2.14. Siano a1 , . . . , an , b interi non tutti nulli. Allora esistono degli
interi x1 , . . . , xn tali che
a1 x1 + · · · + an xn = b
se e solo se MCD(a1 , . . . , an ) | b.
• Infine un rapido cenno per quanto riguarda i sistemi lineari a coefficienti
interi. Consideriamo il sistema lineare
a11 x1 + · · · a1n xn = b1


.. ..



. . ai j ∈ Z, bi ∈ Z, (A.2.11)




a x + · · · a x = b

m1 1 mn n m

e poniamo
   
 a11 · · · a1n   a11 · · · a1n b1 
A =  ... ..  , (A, b) =  ... ..  .
 
 .   . 
am1 · · · amn am1 · · · amn bm
 

88
Un sistema come (A.2.11), che ha i coefficienti interi, ha tutte le soluzioni
razionali cioè se la n-upla (x1 , . . . , xn ) risolve il sistema (A.2.11) allora

(x1 , . . . , xn ) ∈ Qn .

Chiameremo soluzione intera di (A.2.11) ogni (x1 , . . . , xn ) ∈ Zn che risolve (A.2.11).

Vale in proposito la seguente
Proposizione A.2.15. Il sistema lineare (A.2.11) ha almeno una soluzione intera se
e solo se
i) rk(A) = rk(A, b) = k;

ii) il massimo comun divisore dei minori di ordine k di A coincide con il massimo
comun divisore dei minori di ordine k di (A, b).
Esempio A.2.16. Consideriamo il sistema

6x + 24y − 41z = 91


2x − 3y + 7z = 2.



Avremo ! !
6 24 −41 6 24 −41 91
A= , (A, b) = .
2 −3 7 2 −3 7 2
Poichè
6 24 6 −41 24 −41
= −66, = 124, = 45,
2 −3 2 7 −3 7
si ha MCD(−66, 124, 45) = 1; d’altronde

6 91 24 91 −41 91
= −170, = 321 = −719,
2 2 −3 2 7 2
e
MCD(−66, 124, 45, −170, 321, −719) = 1,
le condizioni di risolubilità della Proposizione A.2.15 sono soddisfatte e quindi
il sistema ha soluzioni intere.
Esempio A.2.17. Il sistema

2x + 2z = 1


x − y + 2z = 1.



non ha soluzioni intere.

89
A.3 I numeri primi
Proposizione A.3.1. Siano a, b ∈ Z e p un numero primo tale che p | ab. Allora p | a
o p | b.

Dimostrazione. Sopponiamo che p non divida a e proviamo che p | b. Per la

Proposizione A.2.6 esistono x, y ∈ Z tali che ax + py = 1 e quindi, moltiplicando
ambo i membri per b, si ha abx + pby = b. Per l’ipotesi esiste k ∈ Z tale che
ab = kp, pertanto

b = abx + pby = kpx + pby = p(kx + by),

ossia p | b. 

Teorema A.3.2. Ogni intero n > 1 si fattorizza in modo unico, a meno dell’ordine,
come prodotto di potenze di numeri primi, ossia per ogni n > 1 esistono r numeri primi
p1 , . . . , pr e degli interi positivi n1 , . . . , nr tali che

n = pr11 · · · pnr r .

Se n ∈ Z e n < −1 allora avremo

n = −pr11 · · · pnr r .

Osservazione A.3.3. Siamo n e m due interi > 1. Allora MCD(n, m) è il prodotto

dei fattori primi comuni di n e m presi con il minimo esponente. Il mcm(n, m) è
il prodotto dei fattori primi comuni ad n e m presi con il massimo esponente e
dei primi non comuni presi con il loro esponente. Ad esempio siano 304920 =
23 · 32 · 5 · 7 · 112 e 5642 = 2 · 7 · 13 · 31; allora

MCD(304920, 5642) = 2 · 7 = 14,

mentre

mcm(304920, 5642) = 23 · 32 · 5 · 7 · 112 · 13 · 31 = 122882760.

Proposizione A.3.4 (Prop. XX del IX libro). L’insieme dei numeri primi è infinito.

Dimostrazione. Se p1 , . . . , pN fossero tutti e soli i primi allora il numero

M = p1 · · · pN + 1

non sarebbe primo nè diviso dai primi p1 , . . . , pN . 

90
Osservazione A.3.5. Il problema di trovare numeri primi sempre più grandi è
divenuto centrale per la crittografia. Bisogna risalire ad Euclide per trovare le
radici
Un numero perfetto è un intero positivo n che è uguale alla somma dei suoi
divisori < n. Ad esempio sono perfetti n = 6, n = 28.
Proposizione A.3.6 (XXXVI del IX libro). Sia p un numero primo tale che 2p − 1 è
primo. Allora n = 2p−1 (2p − 1) è un numero perfetto.
L. Euler (Basilea 1707, Pietroburgo 1783) prova, nel 1750, la proposizione
inversa di quella di Euclide sui numeri perfetti.
Proposizione A.3.7. Sia n un numero perfetto pari, allora esiste un primo p tale che
n = 2p−1 (2p − 1) e 2p − 1 è primo.
I primi della forma 2p − 1 si dicono primi di Mersenne (monaco francese
(1588-1648)) e forniscono tutti i numeri primi più grandi finora trovati. Sono
primi i numeri 2p − 1 con
p = 2, 3, 5, 7, 13, 17, 19, 31, 127,
ma
267 − 1 = 193707721 · 761838257287
non è primo. Quindi, ad esempio, 8128 = 26 (27 − 1) è perfetto.
• Non è nota l’esistenza di numeri perfetti dispari. Citiamo il seguente risultato
(A. Grytczuk, M. Wojtowicz - 1999):
Se N è un numero perfetto dispari allora N ha almeno 420 fattori
primi distinti e
N > 1, 9 × 102550
cioè ha almeno 2551 cifre decimali.

La distribuzione dei numeri primi

Osserviamo due fenomeni antitetici:
1. Esistono sequenze comunque lunghe di numeri consecutivi non primi:
n! + 2, n! + 3, . . . , n! + n ha n − 1 termini consecutivi non primi se n ≥ 2.
Se n è un intero non negativo il fattoriale di n è l’intero n! = 1 · 2 · 3 · · · n, ad es.
5! = 1 · 2 · 3 · 4 · 5 = 120.
2. Esistono primi gemelli, cioè coppie di primi del tipo p e p + 2 (ad es. 11 e 13,
17 e 19). I più grandi primi gemelli finora trovati sono
2996863034895 · 21290000 ± 1.
L’esistenza di infiniti primi gemelli è un problema ancora aperto.

91
Teorema A.3.8 (Il teorema dei numeri primi). Sia x un numero reale positivo e
π(x) il numero dei numeri primi ≤ x. Allora
x
π(x) ∼ , x → +∞.
log x

Se vogliamo trovare numeri primi vicini a x basta spostarsi da x di log x.

Ad esempio se x = 10100 , log x = 100 log 10 < 250; ora 10100 ha 101 cifre, si
tratta quindi di alterare le sue ultime 3 cifre e usare criteri di primalità su 4 · 102
numeri.

92