Algebra 1 - Appunti

Indice

• 0.1 Notazioni 3
• 0.2 Insiemi 4
• 0.3 Numeri naturali 18
• 0.4 Interi e naturali 24
• 0.4.1 Numeri di Fibonacci 25
• 0.4.2 Divisibilità 31
• 0.5 Congruenze modulari 42
• 0.6 Gruppo 45
• 0.6.1 Gruppo quoziente 54
• 0.6.2 Sottogruppi di Z e di Z_n 63
• 0.7 Permutazioni 67
• 0.7.1 Gruppo alterno su gruppi A_n 77
• 0.8 Anelli 81
• 0.8.1 Anelli Z_n 83
• 0.9 Polinomi 90

Algebra I

0.1 Notazioni

Simboli per i numeri

N numeri naturali, con anche lo 0

Z = −3, −2, −1, ..., 0, 1, 2, 3, ... numeri interi (interi relativi, relativi)

Q numeri razionali, le frazioni

R numeri relativi, tutti i razionali e gli irrazionali

C numeri complessi con a, b numeri relativi, a + ıb, ı² = −1

Simboli logici e insiemistici

=> implica

<=> equivalenza logica

∃ ne esiste almeno uno

∃! => esiste un unico, esiste ed è unico

∀ per ogni

0.2 Insiemi

Teoria ingenua degli insiemi

Prendiamo come primitivi i concetti d'insieme, elemento, appartenenza.

∈ A x A, A x x A, insieme, è elemento di

6∈ A x A, A x x A, non è elemento di

A = {2, 3, 5, 7} elenco degli elementi

B = {1, 2, 3, 4, ...} vuol dire che si va avanti così

C = {x ∈ R, x > 36} specificazione della proprietà

C = {x ∈ R, x | x > 36}

C = {x ∈ R | x > 36}

D = {x ∈ N, x > 2 e x < 6} = {3, 4, 5}

∧, e logico, ha lo stesso significato della virgola e significa che valgono contemporaneamente le proprietà: x > 2, x < 6

E = {x ∈ N, x > 2 o x = 33}

∨, o logico, o vale la prima o la seconda o entrambe contemporaneamente

A ⊆ B <=> ∀x ∈ A, x ∈ B. Se A, B insiemi, significa: A è sottoinsieme di B, A è contenuto in B.

B ⊇ A => B contiene A. Posso scrivere:

A ⊆ B e B ⊆ A => A = B => A e B contengono gli stessi elementi.

A ⊂ B <=> A ⊆ B e A 6= B, inclusione stretta cioè A è contenuto strettamente in B.

A ∩ B := {x ∈ A ∩ B <=> x ∈ A, x ∈ B} intersecato

A ∪ B := {x ∈ A ∪ B <=> x ∈ A, x ∈ B} unione o

∅ insieme vuoto senza elementi, ∅ ⊆ A ∀ insieme A.

Insieme delle parti

P(A) di un insieme A: è l'insieme denotato con A formato da tutti i sott'insiemi di A.

Complementare di un insieme

A, B insiemi. Il complementare di B in A è l'insieme denotato con A − B o con C_AB così definito:

A − B = {x ∈ A | x 6∈ B}

Se si ha B ⊆ A, A ⊂ B, (A − B) ∪ B.

Coppie ordinate

Siano a e b due oggetti, si chiama coppia ordinata di componente a e componente b, l'insieme denotato con (a, b) definito così:

(a, b) := {{a}, {a, b}}

Proprietà fondamentale delle coppie ordinate:

(a, b) = (x, y) <=> a = x, b = y

Due coppie ordinate sono uguali.

Prodotto cartesiano di due insiemi

Siano A e B insiemi, si chiama prodotto cartesiano di A e B l'insieme:

A × B := {(a, b), a ∈ A, b ∈ B}

Se il prodotto cartesiano si denota con A² = A × A.

Il concetto di coppia ordinata e di prodotto cartesiano di insiemi si generalizzano al concetto di terna, quaterna, ... ordinata e di prodotto di insiemi.

Se n > 0, n ∈ N − si parla di n-pla ordinata e di prodotto cartesiano di n insiemi A₁ × ... × A_n.

Se si scrive Aⁿ = A × ... × A = A₁ × ... × A_n.

Relazione tra due insiemi

Siano A e B due insiemi, una relazione da A e B è un sottoinsieme del prodotto cartesiano A × B.

R ⊆ (A × B). Se la coppia ordinata (a, b) ∈ R diciamo che a è in relazione con b e scrivo aRb.

Se scrivo (a, b) 6∈ R, a non è in relazione con b.

Applicazioni (o funzioni)

Siano A e B due insiemi. Una funzione o applicazione, da A a B è una terna ordinata (A, B, F) dove F è una relazione da A a B tale che valga la proprietà seguente:

∀a ∈ A, ∃!b ∈ B : (a, b) ∈ F

Anziché scrivere f = (A, B, F) scriviamo f : A −→ B e se scriviamo b = f(a) e diciamo che b è il valore preso da a in f, allora b è l'immagine di a tramite f.

F è detto grafico della funzione.

Se f : A −→ B è una applicazione, allora A è detto dominio di f e B è detto il codominio. Si chiama immagine di f l'insieme:

Im f := {f(a), a ∈ A} ⊆ B

Definizione

Una applicazione f : A −→ B è detta suriettiva, o su, se Im f = B, cioè se ∀b ∈ B ∃a ∈ A : f(a) = b.

Una applicazione f : A −→ B si dice iniettiva, o 1-1, se vale la proprietà:

∀x, x' ∈ A, f(x) = f(x') => x = x'

Equivalentemente x = x' => f(x) = f(x') e f(x) = f(x') => x = x', stiamo usando l'equivalenza logica di P => Q e Q => P, non non.

Una applicazione f : A −→ B è detta applicazione biettiva, o corrispondenza biunivoca, o biezione, se è sia 1-1 che su.

∀b ∈ B ∃!a ∈ A : f(a) = b. Questo equivale a dire che vale la proprietà.

Definizione

Date due applicazioni f : X −→ Y e g : Y −→ Z si chiama funzione composta la funzione g ◦ f : X −→ Z tale che ∀x ∈ X, (g ◦ f)(x) := g(f(x)).

Definizione

Sia f : A −→ B una applicazione biettiva. Allora è ben definita l'applicazione seguente, denotata con f⁻¹ : B −→ A e se y ∈ B sia quell'unico elemento x di A tale che f(x) = y; poniamo allora x := f⁻¹(y).

Se compongo f : A −→ B e f⁻¹ : B −→ A si ha: f⁻¹ ◦ f = id_A.

f ◦ f⁻¹ = id_B.

(f⁻¹ ◦ f)(x) = f⁻¹(f(x)) = f⁻¹(y) = x = id_A(x), posto y = f(x).

(f ◦ f⁻¹)(y) = f(f⁻¹(y)) = f(x) = y = id_B(y), posto x = f⁻¹(y).

Proposizione

Sia f : A −→ B una applicazione di insiemi.

Sono equivalenti: f è biettiva.

∃g : B −→ A, h : B −→ A applicazioni di insiemi tali che g ◦ f = id_A e f ◦ h = id_B.

Notazioni e definizioni

Sia f : A −→ B una applicazione di insiemi e sia S ⊆ A. Si chiama restrizione di f ad S l'applicazione:

f|_S : S −→ B, s 7−→ f(s)

Se T ⊆ B, T ⊇ Im f, allora si può definire la corestrizione di f a T nel modo seguente:

f|^T : A −→ T, a 7−→ f(a)

Definizione

Sia f : A −→ B una applicazione di insiemi e sia S ⊆ A. Si ponga:

f(S) := {y | ∃x ∈ S, y = f(x)} ⊆ B, immagine di S tramite f.

Sia T ⊆ B, si chiama controimmagine di T tramite f il sottoinsieme di A:

f⁻¹(T) := {x ∈ A | f(x) ∈ T} ⊆ A

Queste sono notazioni universalmente in uso ma ambigue, quindi bisogna fare attenzione quando si usano. Se f è biettiva f⁻¹ denota l'applicazione inversa B −→ A. Qui invece f⁻¹ : P(B) −→ P(A) indica una applicazione ed f non è necessariamente biettiva.

Definizione

Se A e B sono due insiemi, le applicazioni:

P : A × B −→ A, (x, y) 7−→ x

q : A × B −→ B, (x, y) 7−→ y

Sono dette proiezione canonica rispettivamente sul primo e secondo fattore.

Famiglie

Sia f : I −→ X una applicazione d'insiemi. Se poniamo x_i := f(i), ∀i ∈ I, possiamo dimenticare la funzione f e scrivere semplicemente {x_i}_{i ∈ I} o anche (x_i)_{i ∈ I}, cioè x_i con i ∈ I, cioè che varia da i a I.

Diagrammi

Un diagramma è una figura dove compaiono lettere che denotano degli insiemi e frecce che denotano delle applicazioni.

Un diagramma si chiama commutativo se per ogni coppia d'insiemi che vi compaiono, tutte le applicazioni del nel che si ottengono componendole frecce in tutti i modi possibili sono uguali. Per dire che un diagramma è commutativo, si scrive ◦₁ ≡ ◦₂.

Relazioni di equivalenza

Consideriamo una relazione R su un insieme X; R è detta:

Riflessiva se vale: ∀x ∈ X, xRx.

Simmetrica se vale: ∀x, y ∈ X, (xRy => yRx).

Transitiva se vale: ∀x, y, z ∈ X (xRy e yRz => xRz).

Una relazione R su X che ha queste proprietà è detta relazione di equivalenza su X.

Se R è una relazione di equivalenza su X scriviamo oltre che xRy o anche x ≡ y mod R e leggiamo congruo a y o equivalente a y, modulo R.

Classi di equivalenza

Definizione. Sia X un insieme ed una relazione di equivalenza R su X. Sia x ∈ X, si chiama classe di equivalenza di x e si denota con x/R o con [x], il sottoinsieme di X così definito:

[x] := {x' ∈ X | xRx'}

Osserviamo che x ∈ [x] si ha sempre.

Lemma

Ausilio nella dimostrazione di teoremi. Sia X un insieme ed una relazione di equivalenza R su X. Allora xRy <=> [x] = [y].

Dimostrazione. => Per ipotesi xRy. Facciamo vedere [y] ⊆ [x]. Sia z ∈ [y] => yRz => xRz => z ∈ [x] per la proprietà transitiva.

[x] ⊆ [y] segue per la proprietà simmetrica => [x] = [y].

<= Per ipotesi [x] = [y]. Si ha y ∈ [y] = [x] => y ∈ [x] => xRy.

Partizioni degli insiemi

Definizione. Una partizione A di un insieme X è un sottoinsieme di P(X) tale che:

∅ 6∈ A.

Y, Z ∈ A, Y ∩ Z 6= ∅ => Y = Z.

&bigcup;_{Y ∈ A} Y = X.

Proposizione

Sia R una relazione di equivalenza su X (insiemi 6= ∅). Allora l'insieme {[x], x ∈ X} delle classi di equivalenza è una partizione di X.

A(R) = {[x], x ∈ X} ⊆ P(X).

Dimostrazione.

1) [x] 6= ∅ perché x ∈ [x] => A(R) 6= ∅ perché ha almeno un elemento.

2) Siano x, y ∈ X tali che [x] ∩ [y] 6= ∅. Quindi ∃z ∈ [x] ∩ [y] => zRx, zRy => xRy => [x] = [y] per la transitività e simmetricità.

3) &bigcup;_{x ∈ X} [x] = X. &bigcup;_{x ∈ X} [x] ⊆ X è vera perché [x] ⊆ X. X ⊆ &bigcup;_{x ∈ X} [x] è vera, infatti sia y ∈ X => y ∈ [y] ⊆ [x].

Proposizione

Sia X un insieme e A la sua partizione. Si può definire una relazione su X, la denotiamo con R(A), nel modo seguente:

x, y ∈ X, xR(A)y <=> ∃B ∈ A : x, y ∈ B

La relazione R(A) è una relazione di equivalenza su X le cui classi di equivalenza sono gli elementi di A.

Dimostrazione. Riflessiva: se x ∈ X, per la 3) deve esistere un B ∈ A : x ∈ B => xR(A)x.

Simmetrica è vera per definizione.

Transitiva: per ipotesi xR(A)y => ∃B ∈ A; x, y ∈ B, yR(A)z => ∃C ∈ A; y, z ∈ C. Allora y ∈ B ∩ C => B = C => x, z ∈ B => xR(A)z.

[x]_R(A) = {y ∈ X | xR(A)y} ∈ A. Per costruzione le classi di equivalenza di R(A) sono gli elementi di A.

Osservazioni

Sia X insieme, R relazione di equivalenza su X. Allora la relazione di equivalenza associata alla partizione data dalle classi di equivalenza di R, cioè R(A(R)), è la relazione R.

Se A è una partizione qualsiasi su X, e consideriamo A(R(A)), cioè la partizione associata alla relazione associata ad A, è stessa.

Conclusione

Dare una relazione di equivalenza su X o dare una partizione di X è la stessa cosa.

Definizione

Sia X un insieme ed una relazione di equivalenza R su X. La partizione A(R) associata alla relazione R è detta insieme quoziente di X modulo R o anche X quozientato o anche X modulo R.

L'applicazione:

Π : X −→ X/R, x 7−→ [x]

è suriettiva e viene detta proiezione canonica sul quoziente o proiezione naturale sul quoziente.

X/R = {[x], x ∈ X} ⊆ P(X), è un insieme di sottoinsieme.

Passaggio al quoziente

Definizione - proposizione. Sia f : X −→ Y una applicazione di insiemi e sia R una relazione di equivalenza su X. Diciamo che f passa al quoziente rispetto ad R o anche passa al quoziente modulo R se esiste una applicazione f : X/R −→ Y tale che il seguente diagramma commuti.

X −→ X/R −→ Y, f : X −→ Y, Π : X −→ X/R, dove Π è la proiezione canonica sul quoziente.

Se esiste, si ha necessariamente f([x]) = f(x) ed f viene detta l'applicazione indotta da f sul quoziente.

f esiste se e solo se vale la: xRx' => f(x) = f(x').

Dimostrazione. Il diagramma commuta <=> f ◦ Π = f. Quindi se f esiste, si deve avere ∀x ∈ X, (f ◦ Π)(x) = f(x).

Se f esiste allora xRx' <=> [x] = [x'], f applicazione => f([x]) = f([x']) => xRx' => f(x) = f(x').

Viceversa se vale la proprietà allora basta porre f([x]) := f(x). f è una applicazione ben definita e il diagramma commuta.

Proposizione

Sia f : X −→ Y una applicazione di insiemi, allora il seguente diagramma è commutativo:

X −−−→ Y
x ? ?? ?? ? y
Π X/R −−−→ Im f
g

Inoltre f : X −→ Y, dove Π è la proiezione canonica sul quoziente, i è l'inclusione e f = i ◦ g, f = f ◦ Π.

g([x]) := f(x), e si ha che: Π è suriettiva, i è iniettiva e g è una biezione.

Inoltre f([x]) = f(x), f è iniettiva.

Quindi ogni applicazione di insiemi si fattorizza come composizione di una applicazione suriettiva e di una iniettiva.

Relazione d'ordine

Definizione. Se R è una relazione in X, diciamo che ha la proprietà antisimmetrica se vale:

∀x, t ∈ X, xRy, yRx <=> x = y

Definizione. Una relazione d'ordine o relazione d'ordine parziale su un insieme X (non vuoto) è una relazione su X che sia riflessiva, antisimmetrica e transitiva.

Se la relazione d'ordine ≤ verifica anche la proprietà:

∀x, y ∈ X si ha x ≤ y oppure y ≤ x

allora è detta relazione d'ordine totale.

Se ≤ è una relazione d'ordine su X, (X, ≤) è un insieme (parzialmente) ordinato.

O se ≤ è una relazione d'ordine totale su X, (X, ≤) è un insieme totalmente ordinato o catena.

Osservazione

Sia (X, ≤) un insieme ordinato. Allora possiamo definire una relazione < così:

x < y <=> x ≤ y e x 6= y

Questa relazione strettamente minore, gode di:

X < x non è mai vera, proprietà anti-riflessiva.

X < y, y < z => x < z, proprietà transitiva.

Osservazione

Sia < una relazione su un insieme X tale che valgano: 1) e 2) e allora possiamo definire una relazione ≤ su X nel modo seguente.

∀x, y ∈ X, x ≤ y <=> x < y o x = y.

Si vede facilmente che questa nuova relazione è riflessiva, antisimmetrica e transitiva.