Algebra - Matematica Discreta

Appunti di Algebra (versione provvisoria incompleta) A. Carboni Ottobre 2000 Capitolo 1 Funzioni e Contare 1.1 Funzioni e composizione di funzioni Non definiamo che cosa un insieme, lasciando ad ognuno immaginare e esempi particolari di insiemi: l'insieme dei punti di una retta, l'insieme dei numeri razionali, l'insieme di tutti i movimenti rigidi del piano, l'insieme dei simboli di un linguaggio, e cos via. Indicheremo gli insiemi i con lettere maiuscole A, B, . . . , X, Y , ecc., mentre scriveremo a A, x X, ecc. per indicare che un certo elemento a (risp. x) appartiene all'insieme A (risp. X). La pi importante nozione che si considera per gli insiemi quella u e di funzione (o anche applicazione o morfismo): una funzione da un insieme A ad un insieme B una qualunque legge o regola f che associa e ad ogni elemento di A uno ed un solo elemento di B. Gli insiemi A e B sono chiamati rispettivamente dominio e codominio della funzione f . Per indicare che f una funzione di dominio A e di codominio B, e scriveremo: f : A - B e, se a A, indicheremo con f (a) l'unico elemento di B che f associa ad a. L'elemento f (a) di B si chiama immagine di a nella funzione f o anche valore assunto da f sull'elemento a di A. Per le funzioni vale il seguente Principio di estensionalit: due funzioni f, g: A - B sono uguali se e a solo se per ogni elemento a A si ha f (a) = g(a). 1 2 CAPITOLO 1. FUNZIONI E CONTARE L operazione fondamentale definita per le funzioni la composizione: e se f : A - B , g: B - C sono due funzioni tali che il codominio della prima uguale al dominio e della seconda, allora la regola che consiste nell'associare ad ogni elemento a A l'elemento g(f (a)) di C definisce una funzione gf : A - C che chiamiamo composizione di f e g e che protremo leggere anche come "g segue f ". e Se h: C - D un'altra funzione componibile con g, allora le due composizioni (hg)f e h(gf ) esistono ed il principio di estensionalit a assicura che (hg)f = h(gf ) , poich entrambi i membri valgono h(g(f (a) per ogni a A, cio che e e vale la associativit della composizione di funzioni. a L'altra importante propriet della composizione di funzioni l'esia e stenza della funzione identit, cio per ogni insieme X l'esistenza di a e una funzione: 1X : X - X definita da 1X (x) = x , con la propriet che per ogni funzione f : Y - X e per ogni funzione a g: X - Z si ha: 1X f = f e g1X = g , come si dimostra facilmente, ancora una volta usando il principio di estensionalit per le funzioni. a Si osservi che la funzione identit unica, nel senso che se esistesse ae un'altra funzione 10X con le propriet di identit, allora 1X = 10X ; ina a 0 0 fatti: 1X 1X = 1X , perch 1X identit a sinistra e 1X 10X = 1X , perch e e a e 0 1X identit a destra. e a 1.2. MONO, EPI, ISO, ENDO E AUTO (MORFISMI) 3 1.2 Mono, epi, iso, endo e auto (morfismi) Osserviamo che per dimostrare l'unicit della funzione identit su X a a sarebbe bastato richiedere le propriet di identit solo per le funzioni a a f, g: X - X. Tali Continua »