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 Divisibilita' . . . . . . . . . . . . . . . . . . . . . . . . 31

0.5 Congruenze modulari . . . . . . . . . . . . . . . . . . . . . . . 42

0.6 Gruppo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45

0.6.1 Gruppo quoziente . . . . . . . . . . . . . . . . . . . . . 54

0.6.2 Sottogruppi di e di . . . . . . . . . . . . . . . . . 63

Z Z n

0.7 Permutazioni . . . . . . . . . . . . . . . . . . . . . . . . . . . 67

n (A )

0.7.1 Gruppo alterno su gruppi . . . . . . . . . . . . 77

n

0.8 Anelli . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81

0.8.1 Anelli . . . . . . . . . . . . . . . . . . . . . . . . . 83

Z

n

0.9 Polinomi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90

1

2 INDICE

Algebra I

0.1 Notazioni

SIMBOLI PER I NUMERI: 0

numeri naturali, con anche lo

N −3, −2, −1,

..., 0, 1, 2, 3, ...

numeri interi (interi relativi, relativi)

Z =>

numeri razionali le frazioni

Q numeri relativi, tutti i razionali e gli irrazionali

R 2 −1

a + ıb a, b ı =

numeri complessi con numeri relativi

C

SIMBOLI LOGICI E INSIEMISTICI:

=> implica

<=> equivalenza logica

∃ ne esiste almeno uno

∃! =>

esiste un unico esiste ed è unico

∀ per ogni 3

4 INDICE

0.2 Insiemi

TEORIA INGENUA DEGLI INSIEMI

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

∈ 3

A x A, A x x A

insieme, , è elemento di

6∈ 63

x A A x x A

, , non è elemento di

Un insieme si denota

{2,

A = 3, 5, 7} elenco degli elementi

{1,

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

{x ∈

C = x > 36} specicazione della proprietà

R,

{x, ∈

C = x x > 36}

R,

{x ∈

C = > 36}

R|x

{x ∈ {3,

D = x > 2 e x < 6} = 4, 5}

N,

∧

, e logico, ha lo stesso signicato della virgola e signica che valgono con-

x > 2, x < 6

temporaneamente le proprietà:

{x ∈ 6

E = x > 2 o x = 33}

N,

∨

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

⊆ ∀x ∈ ∈

A, B A B A, x B

Se insiemi, signica:

A B A B

Allora sottoinsieme di , è contenuto in

⊇

B A => B A

Posso scrivere: contiene

⊆ ⊆

A B B A => A = B => A B

e e contengono gli stessi elemen-

0.2 Insiemi 5

ti ⊂ ⊆ 6

A B A B A = B

inclusione stretta cioè e

∩ ∈ ∩ ∈ ∈

A B : A B => x A B <=> x A x B

intersecato e

∪ ∈ ∪ ∈ ∈

A B : A B => x A B <=> x A x B

unione o

∅ ∅ ⊆ ∀

: => => A A

insieme vuoto senza elementi , insieme

Insieme delle parti

A P (A)

di un insieme : è l'insieme denotato con formato da tutti i sott'insie-

A

mi di

Complementare di un insime

A, B insiemi −

B A C B A B

Il complementare di in è l'insieme denotato con o con così

A

denito: − {x ∈ 6∈

A B = A|x B}

⊆ ⊂ ∪ −

B A, A B (A B)

Se si ha

Coppie ordinate a

a b 1 a

Siano e due oggetti, si chiama coppia ordinata di componente e

a

2 b (a, b)

componente , l'insieme denotato con denito così:

{{a}, {a,

(a, b) := b}}

Proprietà fondamentale delle coppie ordinate

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

Due coppie ordinate e sono uguali

Prodotto cartesiano di due insiemi

A B A B

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

× {(a, ∈ ∈

A B := b), a A, b B}

6 INDICE

2

×

A = B A A A

Se il prodotto cartesiano si denota con 2

Il concetto di coppia ordinata e di prodotto cartesiano di insiemi si gene-

3, 4, ...

ralizzano al concetto di terna, quaterna, ... ordinata e di prodotto di

insiemi.

n > 0, n−

Se è un numero naturale si parla di pla ordinata e di prodotto

× ×

n => A ... A

cartesiano di insiemi 1 n

n × ×

A = A = ... = A A = A ... A

Se si scrive

1 2 n

RELAZIONE TRA DUE INSIEMI

A B A B R

Siano e due insiemi, una relazione da e è un sottoinsieme del

×

A B

prodotto cartesiano

⊆ ×

R (A B) ∈

(a, b) R a R b

Se la coppia ordinata diciamo che è in relazione con e scrivo

aRb 6∈ 6

(a, b) R a R b a b

Se scrivo ( non è in relazione con )

APPLICAZIONI (o funzioni)

A B f A B

Siano e due insiemi. Una funzione o applicazione, da a è una

(A, B, F ) F A B

terna ordinata dove è una relazione da a tale che valga la

proprietà seguente: ∀a ∈ ∃!b ∈ ∈

A, B : (a, b) F

−→ ∈

f = (A, B, F ) f : A B (a, b) F

Anzi che scrivere scriviamo e se scrivia-

b = f (a) b f a b

mo e diciamo che è il valore preso da in , allora è l'immagina

a f

di tramite

F è detto graco della funzione.

−→

f : A B A f B

Se è una applicazione, allora è detto dominio di e è

0.2 Insiemi 7

f

detto il codominio. Si chiama immagine di l'insieme:

{f ∈ ⊆

Im f := (a), a A} B

Denizione −→

f : A B su Im f = B

Una applicazione è detta suriettiva, o se (cioè se

∀b ∈ ∈

B∃a A : f (a) = b )

Denizione −→ −

f : A B 1 1,

Una applicazione si dice iniettiva, o se vale la proprietà:

0 0 0

6 6 ∀x, ∈

x = x => f (x) = f (x ) x A

0 0 0

∀x, ∈

f (x) = f (x ) => x = x x A

equivalentemente P => Q Q => P

(stiamo usando l'equivalenza logica di e non non

Denizione −→

f : A B

Una applicazione è detta applicazione biettiva, o corrispon-

−

1 1 su

denza biunivoca, o biezione, se è sia che .

∀b ∈ ∈

B∃!a A : f (a) = b

Questo equivale a dire che vale la proprietà

DEFINIZIONE −→ −→

f : X Y g : Y Z

Date due applicazioni e si chiama funzione compo-

◦ −→ ∀x ∈ ◦

g f : X Z X, (g f )(x) := g(f (x))

sta la funzione tale che

8 INDICE

DEFINIZIONE

−→

f : A B

Sia una applicazione biettiva. Allora è ben denita l'applica-

−1 −→ ∈

f : B A y B x

zione seguente, denotata con e se sia quell'unico

−1

A f (x) = y x := f (y)

elemento di tale che ; poniamo allora

−1 −1

f f

−→ −→ ◦

A B A => f f = id

Se compongo si ha: A

−1 −1

f f

−→ −→ ◦

B A B => f f = id B

−1 −1 −1

◦

(f f )(x) = f (f (x)) = f (y) = x = id (x) y = f (x)

posto

A

−1 −1 −1

◦

(f f )(y) = f (f (y)) = f (x) = y = id (y) x = f (y)

posto

B

PROPOSIZIONE

−→

f : A B

Sia una applicazione di insiemi.

a) f

Sono equivalenti: è biettiva

∃g −→ −→ ◦

b) : B A, h : B A g f = id

applicazioni di insiemi tali che e

A

◦

f h = id B

NOTAZIONI E DEFINIZIONI

−→ ⊆

f : A B S A.

Sia una applicazione di insiemi e sia Si chiama restrizione

f S

di ad l'applicazione: | −→

f : S B

S 7−→

s f (s)

⊆ ⊇

T B T Im f f T

Se tale che , allora si può denire la corestrizione di a

nel modo seguente: T

| −→

f : A T

7−→

a f (a)

0.2 Insiemi 9

DEFINIZIONE

−→ ⊆

f : A B S A.

Sia una applicazione di insiemi e sia Si ponga:

{y|∃x ∈ ⊆

f (S) := S, y = f (x)} B

S f

(immagine di tramite )

⊆

T B, T f A

Sia si chiama controimmagine di tramite il sottoinsieme di :

−1 {x ∈ ∈ } ⊆

f (T ) := A|f (x) T A

Queste sono notazioni universalmente in uso ma ambigue, quindi bisogna fare

−1

f f

attenzione quando si usano. Se è biettiva denota l'applicazione inversa

−1

−→ −→

B A. f P (B) P (A)

Qui invece in realtà indica una applicazione

f

ed non è necessariamente biettiva.

DEFINIZIONE

A B

Se e sono due insiemi, le applicazioni:

× −→ × −→

P : A B A q : A B B

7−→ 7−→

(x, y) x (x, y) y

Sono dette proiezione canonica rispettivamente sul primo e secondo fattore.

FAMIGLIE

−→ ∀i ∈

f : I X I, x := f (i)

Sia una applicazione d'insiemi. Se poniamo i

{x }

f

possiamo dimenticare la funzione e scrivere semplicemente o anche

i i∈I

(x ) x i I

, cioè che varia da a

i i∈I i

10 INDICE

DIAGRAMMI

Un diagramma è una gura dove compaiono lettere che denotano degli insie-

mi e frecce che denotano delle applicazioni.

Un diagramma si chiama commutativo se per ogni coppia d'insiemi che vi

◦ ◦

1 2

compaiono, tutte le applicazioni del nel che si ottengono componendo

le frecce in tutti i modi possibili sono uguali. ≡ .

Per dire che un diagramma è commutativo, si scrive

RELAZIONI DI EQUIVALENZA

R X R

Consideriamo una relazione su un insieme ; è detta:

∀x ∈ X xRx

- riessiva se vale: ,

∀x, ∈

y X (xRy => yRx)

- simmetrica se vale: ,

∀x, ∈

y, z X (xRy yRz => xRz

- transitiva se vale: , e )

R X 3

Una relazione su che ha queste proprietà è detta relazione di equiva-

X

lenza su .

R X xRy

Se è una relazione di equivalenza su scriviamo oltre che o anche

≡

x y mod R x y y R

( ) e leggiamo congruo a o equivalente a , modulo

CLASSI DI EQUIVALENZA

DEFINIZIONE ∈

X R X x X,

Sia un insieme ed una relazione di equivalenza su . Sia si chia-

x [x] [x]

ma classe di equivalenza di e si denota con o con , il sottoinsieme

R

X

di così denito: 0

{x ∈ }

[x] := X|xRx

0.2 Insiemi 11

∈

x [x]

Osserviamo che si ha sempre

LEMMA(ausilio nella dimostrazione di teoremi)

X R X xRy <=>

Sia un insieme ed una relazione di equivalenza su . Allora

[x] = [y] =>

Dimostrazione. ⊆

xRy. [y] [x]

Per ipotesi Facciamo vedere .

∈ ∈

z [y] => yRz => xRz => z [x]

Sia per la proprietà transitiva

⊆

[x] [y] => [x] = [y]

L'altra inclusione segue per la proprietà simmetrica

<= ∈ ∈

[x] = [y] y [y] = [x] => y [x] => xRy

Per ipotesi . Si ha

PARTIZIONI DEGLI INSIEMI

DEFINIZIONE A X P (X)

Una partizione di un insieme è un sottoinsieme di tale che:

∅ 6∈

1) A

∈ ∩ 6 ∅

2) Y, Z A Y Z = => Y = Z

e

S

3) Y = X

∈A

Y

PROPOSIZIONE

12 INDICE

6 ∅

R X =

Sia una relazione di equivalenza su (insiemi ). Allora l'insieme

{[x], ∈

x X} X

delle classi di equivalenza è una partizione di .

{[x], ∈ ⊆

A(R) = x X} P (X)

Dimostrazione.

6 ∅ ∈ ∅ 6∈

1) [x] = x [x] => A(R) =>

perché ha almeno un elemento

∈ 6 ∅. ∃z ∈

2) x, y X [x]∩[y] = [x]∩[y] => zRx, zRy =>

Siano tali che Quindi

xRy => [x] = [y]

per la transitività e simmetricità

3) [ ?

[x] = X

x∈X

[ ⊆

[x] X

x∈X

⊆ ∀x ∈

[x] X X

è vera perché [

⊆

X [x]

x∈X

S

∈ ∈ ⊆

y X => y [y] [x]

è vera, infatti sia x∈X

PROPOSIZIONE

X A

Sia un insieme e la sua partizione. Si può denire una relazione su

X R(A)

, la denotiamo con , nel modo seguente:

∈ ∃B ∈ ∈

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

R(A) X

La relazione è una relazione di equivalenza su le cui classi di equi-

A

valenza sono gli elementi di .

0.2 Insiemi 13

∈ ∈ ∈

x X, 3) B A : x

Dimostrazione. Riessiva: se per la deve esistere un

B => xR(A)x

Simmetrica è vera per denizione. ∃B ∈ ∈ ∃C ∈

xR(A)y => A; x, y B, yR(A)z =>

Transitiva: per ipotesi

∈

A; y, z C

∈ ∩ ∈

y B C => B = C => x, z B => xR(A)z

Allora {y ∈ ∈

[x] = X|xR(A)y} A

R(A) R(A) A

Per costruzione le classi di equivalenza di sono gli elementi di .

OSSERVAZIONI

X R X

Sia insieme, relazione di equivalenza su . Allora la relazione di equi-

R

valenza associata alla partizione data dalle classi di equivalenza di , cioè

R(A(R)), R

è la relazione

A X A(R(A))

Se è una partizione qualsiasi su , e consideriamo cioè la parti-

A A

zione associata alla relazione associata ad , è stessa.

CONCLUSIONE X X

Dare una relazione di equivalenza su o dare una partizione di è la

stessa cosa.

DEFINIZIONE

X R X

Sia un insieme ed una relazione di equivalenza su . La partizione

A(R) R X R

associata alla relazione è detta insieme quoziente di modulo o

X R X R

anche quozientato o anche modulo .

14 INDICE

L'applicazione: X

−→

Π : X R

7−→

x [x]

è suriettiva e viene detta proiezione canonica sul quoziente o proiezione na-

turale sul quoziente.

X {[x], ∈ ⊆

= x X} P (X) (è un insieme di sottoinsieme)

Quindi R

PASSAGGIO AL QUOZIENTE

Denizione - proposizione

−→

f : X Y R

Sia una applicazione di insiemi e sia una relazione di equiva-

X f R f

lenza su . Diciamo che passa al quoziente rispetto ad o anche passa

X −→

R f : Y

al quoziente modulo se esiste una applicazione tale che il

R

seguente diagramma commuti. X

X −→

−→ −→ ,f : Y Π

f : X Y, Π : X , dove è la proiezione canonica sul

R R

quoziente.

f f ([x]) = f (x) f

Se esiste, si ha necessariamente ed viene detta l'applica-

f

zione indotta da sul quoziente. 0 0

f xRx => f (x) = f (x )

La esiste se e solo se vale la: ◦

<=> f Π = f

Dimostrazione. Il diagramma commuta

◦ ∀x ∈

f (f Π)(x) = f (x) X

Quindi se esiste, si deve avere

0 0

f xRx <=> [x] = [x ], f => f ([x]) =

Se esiste allora quindi applicazione

0 0 0

f ([x ]) xRx => f (x) = f (x )

, cioè 0 0

xRx => f (x) = f (x )

Viceversa se vale la proprietà allora basta porre

f ([x]) := f (x)

f è una applicazione ben denita e il diagramma commuta.

0.2 Insiemi 15

PROPOSIZIONE

−→

f : X Y,

Sia una applicazione di insiemi, allora il seguente diagramma è

commutativo: f

−−−→

X Y

x

? ?

? ?

? ?

y i

Π g

X −−−→ Im f

R f

X −→

f : Y

Inoltre R f

Π i

Dove è la proiezione canonica sul quoziente, è l'inclusione

◦ ◦

◦ ◦ f = i g, f = f Π

g([x]) := f (x) f = i g Π,

e

Π i g

e si ha che: è suriettiva, è iniettiva e è una biezione.

f ([x]) = f (x), f

Inoltre e è iniettiva.

Quindi ogni applicazione di insiemi si fattorizza come composizione di una

applicazione suriettiva e di una iniettiva.

RELAZIONE D'ORDINE

DEFINIZIONE

R X R

Se è una relazione in , diciamo che ha la proprietà antisimmetrica

se vale: ∀x, ∈

t X xRy, yRx <=> x = y

DEFINIZIONE ≤ X

Una relazione d'ordine o relazione d'ordine parziale su un insieme (non

16 INDICE

X

vuoto) è una relazione su che sia riessiva, antisimmetrica e transitiva.

≤

Se la relazione d'ordine verica anche la proprietà:

∀x, ∈ ≤ ≤

y X si ha x y oppurey x

allora è detta relazione d'ordine totale.

≤ ≤

X X,

Se è una relazione d'ordine su , ( ) è un insieme (parzialmente)

ordinato.

≤ ≤

X X,

o se è una relazione d'ordine totale su , ( ) è un insieme totalmente

ordinato o catena.

OSSERVAZIONE

≤)

(X,

Sia un insieme ordinato 00 00

<

Allora possiamo denire una relazione così:

≤ 6

x < y <=> x y e x = y

Questa relazione strettamente minore, gode di:

1) x < x non è mai vera (proprietà anti- riessiva)

2) x < y, y < z => x < z (proprietà transitiva)

OSSERVAZIONE

< X 1) 2)

Sia una relazione su un insieme tale che valgano: e allora possiamo

≤ X

denire una relazione su nel modo seguente.

∀x, ∈ ≤

y X, x y <=> x < y o x = y ≤

Si vede facilmente che questa nuova relazione è riessiva, antisimmetrica

e transitiva,