ELEMENTI DI MATEMATICA E LOGICA
MATEMATICA DISCRETA STRUTTURE ALGEBRICHE
Operazioni in un insieme Operazioni in un insiemeOperazioni in un insieme
Sia A un insieme non vuoto; una funzione f : A × A −→ A si dice operazione binaria (o semplicemente operazione), oppure legge di composizione interna.
Per definizione di funzione, un’operazione associa a ogni coppia ordinata (a, b) ∈ A × A un elemento diA, se indichiamo con ∗ tale operazione, invece di ∗((a, b)) scriveremo a ∗ b, cio`e: ∗ : A × A −→ A (a, b) −→ a ∗ b Un’operazione ∗ si dice: associativa se (a ∗ b) ∗ c = a ∗ (b ∗ c) ∀ a, b, c ∈ A commutativa se a ∗ b = b ∗ a ∀ a, b ∈ A Esempi:
1. L’addizione + e la moltiplicazione · sono operazioni nell’insieme dei numeri interi asso-ciative e commutative.
2. La composizione di applicazioni ◦ , nell’insieme delle applicazioni da un insieme A in se stesso, `e associativa.
3. La composizione di applicazioni ◦ , nell’insieme delle applicazioni da N in se stesso, non `e commutativa. Per esempio siano f : N −→ N e g : N −→ N cos´i definite: f (n) = n2, g(n) = n + 1; allora (f ◦ g)(n) = (n + 1)2 = n2+ 2n + 1 6= (g ◦ f )(n) = n2+ 1.
4. La sottrazione − nell’insieme dei numeri interi non `e n´e associativa n´e commutativa, infatti per esempio (5 − 3) − 1 = 1 6= 5 − (3 − 1) = 3 e 5 − 1 = 4 6= 1 − 5 = −4.
Un insieme A nel quale siano definite una o pi´u operazioni si dice struttura algebrica. GruppiGruppiGruppi
Un insieme G con una operazione ∗ : G × G −→ G si dice gruppo se: (1) ∗ `e associativa;
(2) c’`e un elemento neutro e per ∗, cio`e ∃ e ∈ G tale che g ∗ e = e ∗ g = g, ∀ g ∈ G;
(3) ogni elemento ha un inverso (opposto se l’operazione `e l’addizione), cio`e ∀ g ∈ G ∃ g0 ∈ G tale che g ∗ g0 = g0 ∗ g = e. 1
Un gruppo si dice commutativo (o abeliano) se l’operazione `e commutativa. Propriet`a:
1. Vale la legge di cancellazione (o regola di semplificazione), cio`e: a ∗ b = a ∗ c =⇒ b = c Infatti poich´e ∃ a0 tale che a0 ∗ a = e, moltiplicando per a0 si ottiene a0 ∗ (a ∗ b) = a0 ∗ (a ∗ c) e per la propriet`a associativa si ha (a0
∗ a) ∗ b = (a0 ∗ a) ∗ c, cio`e b = e ∗ b = e ∗ c = c. 2. L’inverso `e unico. Infatti se a ∗ a0 = a0 ∗ a = e e a ∗ b = b ∗ a = e, si ha b = b ∗ e = b ∗ (a ∗ a0 ) = (b ∗ a) ∗ a0 = e ∗ a0 = a0 . 3. L’inverso dell’inverso di a `e a.
Infatti a `e l’unico elemento tale che a0
∗ a = a ∗ a0
= e, quindi (a0
)0
= a.
Queste regole ci dicono che in un gruppo ogni equazione di primo grado a ∗ x = b oppure x ∗ a = b ha soluzione Se il gruppo non `e commutativo a ∗ x = b e x ∗ a = b possono avere soluzioni diverse. Infatti moltiplicando per l’inverso a0
di a si ottiene nel primo caso x = a0
∗ b, nel secondo x = b ∗ a0
.
Da tutto ci`o risulta che nella tabellina del gruppo su ogni riga e colonna devono comparire tutti gli elementi del gruppo e una volta sola. Si vede quindi facilmente che (a meno di scambiare il nome degli elementi) per i gruppi di 2 o 3 elementi c’e‘ una sola tabellina possibile, mentre per quelli di 4 elementi ce ne sono due.
Esempi:
1. L’insieme dei numeri naturali N con l’addizione + non `e un gruppo, infatti + `e associativa e commutativa, 0 `e l’elemento neutro, ma ∀ n > 0 non c’`e l’opposto. Analogamente N con la moltiplicazione non `e un gruppo perch`e · `e associativa e commutativa, 1 `e l’elemento neutro, ma ∀ n 6= 1 non c’`e l’inverso.
2. L’insieme dei numeri interi Z con l’addizione + `e un gruppo commutativo, infatti + `e associativa e commutativa, 0 `e l’elemento neutro e ∀ a ∈ Z ∃ − a tale che a + (−a) = (−a) + a = 0. Invece Z con la moltiplicazione · non `e un gruppo perch`e · `e associativa e commutativa, 1 `e l’elemento neutro, ma gli unici elementi che hanno inverso sono −1 e 1. 3. L’insieme {−1, 1} ⊆ Z con la moltiplicazione · `e un gruppo commutativo, infatti · `e associativa e commutativa, 1 `e l’elemento neutro e ogni elemento `e l’inverso di se stesso. 4. L’insieme Q∗
= Q\{0} con la moltiplicazione · `e un gruppo commutativo, infatti · `e associativa e commutativa, 1 `e l’elemento neutro e ∀ a
b ∈ Q ∗ ∃ b a tale che a b · b a = 1.
5. Sia A = {1, 2, 3}. L’insieme S3 delle applicazioni bigettive di A in A con la composizione
di applicazioni `e un gruppo con 6 elementi, detto gruppo delle permutazioni di 3 elementi:
i : A −→ A σ : A −→ A σ2 : A −→ A 1 −→ 1 1 −→ 2 1 −→ 3 2 −→ 2 2 −→ 3 2 −→ 1 3 −→ 3 3 −→ 1 3 −→ 2 τ1 : A −→ A τ2 : A −→ A τ3 : A −→ A 1 −→ 1 1 −→ 3 1 −→ 2 2 −→ 3 2 −→ 2 2 −→ 1 3 −→ 2 3 −→ 1 3 −→ 3
Infatti ◦ `e associativa, l’elemento neutro `e f1, l’inversa di f4 `e f6 e f1, f2, f3, f5 sono ognuna
l’inversa di se stessa. S3 non `e commutativo perch´e f2 ◦ f3 6= f3◦ f2, infatti f2(f3(1)) =
f2(2) = 3, mentre f3(f2(1)) = f3(1) = 2.
Una permutazione f pu`o anche essere denotata 1 2 3 f (1) f (2) f (3) , per esempio σ = 1 2 3 2 3 1 .
Se G con l’operazione ∗ , L con l’operazione • sono due gruppi, il prodotto cartesiano G × L con l’operazione definita da (a, b) (c, d) = (a ∗ c, b • d) `e un gruppo con elemento neutro (eG, eL). Infatti si vede facilmente che `e associativa e che ogni elemento (a, b) ha
inverso (a, b)0
= (a0
, b0
) dove 0
si denota l’inverso nel rispettivo gruppo. In particolare se L = G il gruppo G × G si denota G2. Analogamente si definiscono G3 e pi´u in generale Gn.
Un gruppo G si dice ciclico se esiste un suo elemento g tale che ∀ x ∈ G ∃ n ∈ Z tale che x = g∗n
, dove con g∗n
si intende g ∗ g ∗ · · · ∗ g n volte se n ≥ 0 oppure g0
∗ g0
∗ · · · ∗ g0
−n volte se n < 0. Tale g si dice generatore di G. Per esempio Z `e ciclico generato da 1, infatti ogni numero intero n `e somma di |n| copie di 1 o di −1 a seconda del segno di n. Z2
non `e ciclico, infatti comunque scegliamo un elemento (a, b) esso non pu`o generare tutti gli elementi di Z2 perch´e per esempio l’elemento (a, −b) 6= n(a, b) ∀n ∈ Z, a meno che a = 0
oppure b = 0, ma allora non si ottengono gli elementi con entrambe le componenti non nulle. SottogruppiSottogruppiSottogruppi
Un sottoinsieme H del gruppo G si dir`a un sottogruppo di G se H `e un gruppo rispetto all’operazione (che chiameremo ancora * ) indotta su H da quella di G. Ci`o significa che e ∈ H, a ∗ b ∈ H ∀ a, b ∈ H, a0
∈ H ∀ a ∈ H o equivalentemente a ∗ b0
∈ H ∀ a, b ∈ H. Esempi:
1. L’insieme dei numeri pari P = {2n | n ∈ Z } `e un sottogruppo di Z. Infatti 2n − 2m = 2(n − m) ∈ P , mentre l’insieme dei numeri dispari D = {2n + 1 | n ∈ Z } non `e un sottogruppo di Z. Infatti 2n + 1 − (2m + 1) = 2(n − m) /∈ D.
2. Z `e un sottogruppo di Q.
3. L’insieme {1, −1} `e un sottogruppo del gruppo moltiplicativo Q∗
. 4. L’insieme {i, σ, σ2} `e un sottogruppo ciclico di S
3, e anche gli insiemi {i, τ1}, {i, τ2}, {i, τ3},
mentre non sono sottogruppi gli insiemi {τ1, τ2} (perch´e non contiene l’elemento neutro i)
e {i, τ1, τ2} (perch´e τ1 ◦ τ2 = σ /∈ {i, τ1, τ2}). Scrivere per esercizio le tabelline di questi
sottogruppi. Esercizi:
1. Dire quali dei seguenti sottoinsiemi di Z2 sono sottogruppi:
H1 = {(x, y) | x + y = 1} H2 = {(x, y) | x + y = 0}
H3 = {(x, y) | xy = 0} H4 = {(t, t) |t ∈ Z} H5 = {(t, t2) |t ∈ Z}.
2. Sia S4 il gruppo delle permutazioni di 4 elementi e siano i l’applicazione identica,
σ = 1 2 3 4 2 3 4 1
. Provare che {i, σ} non `e un sottogruppo di S4 e determinare il pi´u
piccolo sottogruppo H tale che σ ∈ H, calcolarne l’ordine e scriverne la tabella moltiplicativa. 3. Sia S4 il gruppo delle permutazioni di 4 elementi e siano i l’applicazione identica,
τ1 = 1 2 3 4 2 1 4 3 , τ2 = 1 2 3 4 3 4 1 2 , τ3 = 1 2 3 4 4 3 2 1 .
Provare che L = {i, τ1, τ2, τ3} `e un sottogruppo di S4 e scriverne la tabellina.
4. Siano g un gruppo e H e K due suoi sottogruppi. Provare che H ∩ K `e un sottogruppo, mentre H ∪ K lo `e solo se uno dei due sottogruppi `e contenuto nell’altro.
Omomorfismi di gruppiOmomorfismi di gruppiOmomorfismi di gruppi
Se G, ∗, e e L, •, u sono due gruppi diciamo che una applicazione f : G → L
`e un omomorfismo di gruppi) se rispetta le operazioni, cio`e se f (a1∗ a2) = f (a1) • f (a2),
∀a1, a2 ∈ G.
Se inoltre f `e bigettiva, f si dice isomorfismo, G e L si dicono isomorfi e si scrive G ' L.
Si vede facilmente che:
a) f (e) = u, infatti ∀ a ∈ G si ha f (e) • f (a) = f (e ∗ a) = f (a) = u • f (a), da cui per la legge di cancellazione in L si ottiene f (e) = u.
b) f (a0
) = f (a)0
, ∀a ∈ G. Infatti f (a) • f (a0
) = f (a ∗ a0
) − f (e) = u e analogamente f (a0
) • f (a) = u e dunque la tesi. Esempi:
1. L’applicazione f : G → L definita da f (a) = u, ∀ a ∈ G `e un omomorfismo di gruppi, mentre se si fissa un elemento b0 6= u di L e si definisce h(a) = b0, ∀ a ∈ G, questo non `e un
omomorfismo perch`e h(e) 6= u.
2. L’applicazione identica iG : G → G `e un isomorfismo di gruppi.
3. f : Z → Z definita da f (a) = 3a `e un isomorfismo di gruppi.
Infatti f (a + b) = 3(a + b) = 3a + 3b = f (a) + f (b). Si vede facilmente che f `e bigettivo. 4. f : Z → Z definita da f (a) = 3a+1 non `e un omomorfismo di gruppi perch´e f (0) = 1 6= 0. 5. f : Z → Z definita da f (a) = a2 non `e un omomorfismo di gruppi perch´e
f (1 + 1) = f (2) = 4 6= f (1) + f (1) = 2.
6. Sia G il gruppo moltiplicativo {e = (1, 1), g1 = (1, −1), g2 = (−1, 1), g3 = (−1, −1)}.
Allora G `e isomorfo al sottoguppo di S4 visto nell’esercizio 3 precedente:
L = i = 1 2 3 4 1 2 3 4 , τ1 = 1 2 3 4 2 1 4 3 , τ2 = 1 2 3 4 3 4 1 2 , τ3 = 1 2 3 4 4 3 2 1 . Basta infatti porre f (e) = i, f (gj) = τj ∀ j = 1, 2, 3.
Data f : G → L abbiamo gi`a definito l’immagine di f come l’insieme: Imf = f (G) = {y ∈ L | ∃x ∈ G, f (x) = y}.
Se f `e un omomorfismo, Imf `e un sottogruppo di G (infatti comunque si scelgano due elementi y1 = f (x1), y2 = f (x2) in Imf si ha y1•y2 = f (x1)•f (x2) = f (x1∗x2) ∈ Imf ).
Ricordiamo che f `e surgettiva se e solo se Imf = L.
Se f : G → L `e un omomorfismo, definiamo nucleo di f , l’insieme degli elementi con-troimmagine di u:
Kerf = f−1(u) = {x ∈ G | f (x) = u}. `
E chiaro che e ∈ Kerf , inoltre Kerf `e un sottogruppo di G perch´e se a, b ∈ Kerf allora f (a ∗ b0
) = f (a) • f (b)0
= u • u = u e quindi a ∗ b0
Teorema. Un omomorfismo f : G → L `e iniettivo se e solo se Kerf = {e}.
Dimostrazione. Se f `e iniettiva allora Kerf = {e}, altrimenti due elementi distinti avreb-bero immagine u.
Viceversa se Kerf = {e} e se f (x1) = f (x2), allora u = f (x1) • f (x2) 0
= f (x1 ∗ x 0 2) e
quindi x1∗ x02 ∈ Kerf = {e}, da cui x1∗ x02 = e, quindi x1 = x2 e dunque f `e iniettiva.
Proposizione. Se f : G → L `e un omomorfismo e se y0 ∈ L e x0 ∈ G sono tali che
f (x0) = y0 allora:
f−1
(y0) = x0∗ Kerf = {x0∗ z | z ∈ Kerf }.
Dimostrazione. `E immediato che f−1(y
0) ⊇ x0∗Kerf . Infatti comunque si scelga z ∈ Kerf
si ha f (x0∗ z) = f (x0) • f (z) = y0• u = y0 .
Viceversa se t ∈ f−1
(y0) allora f (t) = y0, cio`e f (t) = f (x0), da cui si ottiene
u = f (x0)0• f (t) = f (x00 ∗ t) e quindi x 0
0 ∗ t = z ∈ Kerf , ossia t = x0 ∗ z e dunque
f−1(y
0) ⊆ x0∗ Kerf .
Esempi:
1. Sia f : Z2 → Z definita da f (a, b) = a. Poich´e f (a, b) + f (c, d) = a + c = f (a + c, b + d)
si ha che f `e un omomorfismo di gruppi additivi. Kerf = {(a, b) ∈ Z2
| f (a, b) = 0} = {(0, b) | b ∈ Z}. Se vogliamo calcolare f−1(2), sapendo che f (2, 0) = 2 otteniamo
f−1(2) = (2, 0) + Kerf = {(2, b) | b ∈ Z}.
2. Sia f : Z → Z2 definita da f (a) = (a, 0). Verificare per esercizio che f `e un omomorfismo
di gruppi additivi. Kerf = {a ∈ Z | f (a) = (0, 0)} = {0}, quindi f `e iniettivo. 3. Sia f : Q∗
→ Q∗
definito da f (x) = |x|, dove con |x| si indica il valore assoluto di x. Poich`e |xy| = |x||y| si ha che f `e un omomorfismo di gruppi moltiplicativi. Risulta Kerf = {x ∈ Q∗
| f (x) = 1} = {1, −1}. AnelliAnelliAnelli
Un insieme A con due operazioni + e · si dice anello se: (1) A con la somma + `e un gruppo commutativo;
(2) Il prodotto · `e associativo;
(3) vale la propriet`a distributiva della somma rispetto al prodotto, cio`e (a + b)c = ac + bc e a(b + c) = ab + ac
Inoltre A si dice anello commutativo se il prodotto · `e commutativo; A si dice anello con identit`a (o con 1) se in A c’`e un’identit`a moltiplicativa, che denoteremo appunto 1 (o 1A in caso di ambiguit`a).
Propriet`a: 1. a0 = 0b = 0.
Infatti a + a0 = a(1 + 0) = a1 = a + 0 e per la legge di cancellazione a0 = 0; il caso 0b=0 `e analogo.
2. (−a)b = −ab = a(−b)
Infatti (−a)b + ab = (−a + a)b = 0b = 0 e a(−b) + ab = a(b − b) = a0 = 0. 3. (−a)(−b) = ab
Infatti (−a)(−b) = −(a(−b)) = −(−ab) = ab.
Non `e detto che se ab = 0 allora a = 0 oppure b = 0. Un anello A si dice integro se ab = 0 ⇐⇒ a = 0 oppure b = 0.
Esempi:
1. L’insieme dei numeri interi Z con l’addizione e la moltiplicazione `e un anello commutativo con identit`a, integro.
2. Se A `e un anello, l’insieme FA = {f : A −→ A} delle funzioni di A in A con le
operazioni + e · cos´i definite : (f + g)(x) = f (x) + g(x) e (f g)(x) = f (x)g(x) `e un anello commutativo con identit`a, non integro.
Verificare che FA con la somma definita sopra e con la composizione di funzioni come
moltiplicazione non `e un anello perch´e non vale la propriet`a distributiva. 3. Se A `e un anello, possiamo considerare l’insieme A[X] dei polinomi
f (X) = a0+ a1X + a2X2+ · · · + anXn
dove a0, a1, . . . , an ∈ A sono detti coefficienti del polinomio e X ’indeterminata. Se
an 6= 0 si dice che il polinomio f (X) ha grado n e si scrive δf (X) = n, in tal caso an si dice
coefficiente direttivo di f (X).
Dati due polinomi a coefficienti in un anello A, f (X) = a0+ a1X + a2X2+ · · · + anXn
e g(X) = b0 + b1X + b2X2+ · · · + bsXs, possiamo definire una somma e un prodotto nel
modo seguente: f (X) + g(X) = (a0+ b0) + (a1+ b1)X + (a2+ b2)X2+ · · · + (ai+ bi)Xi+ . . .
f (X)g(X) = a0b0+ (a0b1+ a1b0)X + (a0b2+ a1b1+ a2b0)X2+ · · · + (
Pi
j=0ajbi−j)Xi+ . . .
Con tali operazioni A[X] diventa un anello, integro se A `e integro.
Osserviamo che il grado della somma di due polinomi `e minore o uguale al massimo tra i due gradi. Il grado pu`o diminuire se f e g hanno lo stesso grado e coefficienti direttivi opposti, per esempio f = 1+2X −3X3, g = 2+X2+3X3 hanno grado 3, mentre f +g = 3+2X +X2
ha grado 2.
Se A `e integro il prodotto di due polinomi ha come grado la somma dei gradi, infatti se δf = n e δg = s il termine di grado massimo di f g `e anbsXn+s, quindi δ(f g) = n + s.
4. Se A, B sono due anelli, sul gruppo additivo A × B si pu`o definire oltre alla somma (a, b) + (c, d) = (a + c, b + d) anche un prodotto (a, b) · (c, d) = (ac, bd). Con queste due operazioni A × B `e un anello con 1A×B = (1, 1), commutativo se A e B lo sono, ma non
integro anche se A e B lo sono, perch´e per esempio (1, 0) · (0, 1) = (0, 0).
5. Vedremo in seguito che l’anello delle matrici `e un anello non commutativo con identit`a, non integro.
