1. Operazioni tra insiemi

In algebra astratta, si comincia spesso parlando dei concetti di insiemistica. Questo perché l’uso di questi concetti permette di effettuare ragionamenti logici e di dimostrare teoremi, astraendo completamente dagli oggetti trattati.

1.1. Nozioni sugli insiemi

Un elemento di un insieme, è una nozione primitiva.

Per elemento si può intendere qualunque entità, considerata non suddivisibile. Una sorta di atomo. E con l’aggettivo qualunque, intendo proprio qualunque: concetti astratti o oggetti concreti. Ovvero ogni cosa vogliamo poter analizzare secondo le regole logiche che ci daremo nel seguito.

Anche il concetto di insieme è una nozione primitiva. È una collezione di elementi. Usualmente si indica con una lettera maiuscola.

Possiamo identificare un insieme elencando i suoi elementi tra parentesi graffe, come ad es. in: \(\{11, 13, 17, 19\}\). Oppure si può identificare tramite una proprietà.

Nota

Ad es., in algebraico, la formula: \(S = \{x | P(x)\}\) indica che l’insieme S è composto da elementi x per i quali vale la proprietà \(P(x)\).

Graficamente, spesso si rappresenta un insieme con un diagramma di Venn, ovvero un elissode che racchiude i suoi elementi. Ad esempio, come nella figura qui sotto, che rappresenta A con un diagramma di Venn.

Un altro concetto intuitivo, molto utilizzato è quello di implicazione logica. La dizione «implica» indica che un fatto ha per conseguenza logica un altro fatto.

Nelle formule si indica, intuitivamente, con una freccia: \(\Rightarrow\). Mentre nel linguaggio parlato usiamo le congiunzioni se … allora …

Ad esempio: «se concluderò in tempo la riunione, allora parteciperò al seminario». In cui i fatti sono:

• «concluderò in tempo la riunione» e

• «parteciperò al seminario»

Nota

Personalmente non trovo molto intuitivo il concetto di implicazione. Consideriamo la sua tavola di verità (V indica Vero, F Falso):

p	q	\(p \Rightarrow q\)
V	V	V
V	F	F
F	V	V
F	F	V

osserviamo che risulta sempre vero, salvo quando esiste una condizione che renda vera p e contemporaneamente falsa q. Questa è l’unica certezza che ci da”: una condizione che avvera p e contemporaneamente rende q falsa afferma che non vi può essere implicazione di p su q. Fatta salva questa condizione, le altre non influiscono sul risultato: qualunque altra coppia di valori di p e q ci danno un risultato vero.

Se il concetto di implicazione vale in entrambi i versi, allora si parla di coimplicazione. In questo caso ognuno dei due fatti ha per conseguenza logica l’altro fatto. Di conseguenza i due fatti si equivalgono logicamente.

Nel linguaggio parlato utilizziamo la frase … se e solo se ….

Nota

Questa la capisco meglio. La sua tavola di verità è (come prima, V indica Vero, F Falso):

p	q	\(p \Leftrightarrow q\)
V	V	V
V	F	F
F	V	F
F	F	V

In questo caso se la verità/falsità di una proposizione, afferma anche la verità/falsità dell’altra, abbiamo la validità della coimplicazione.

Ma torniamo agli insiemi.

Il concetto di appartenenza indica che un elemento appartiene a un insieme.

Nota

L’appartenenza dell’elemento a all’insieme A si scrive \(a \in A\).

I seguenti insiemi sono così rilevanti da essersi guadagnati dei nomi propri:

• i numeri interi positivi: \(\mathit{P}\),

• i numeri interi non negativi: \(\mathit{N}\),

• tutti i numeri interi: \(\mathbb{Z}\),

• tutti i numeri razionali: \(\mathit{Q}\),

• tutti i numeri reali: \(\mathbb{R}\),

• tutti i numeri complessi: \(\mathbb{C}\).

Un insieme particolarmente importante è l’insieme vuoto.

Un insieme è vuoto se non ha elementi.

Nota

L’insieme vuoto si indica con il simbolo \(\phi\).

Altro concetto importante: il concetto di sottoinsieme.

Si chiama sottoinsieme un insieme A che è parte (o tutto) di un insieme B. Si dice A è contenuto in B.

Nota

A è contenuto in B si indica: \(A \subseteq B\).

Nel caso particolare in cui B ha almeno un elemento in più di A, allora A è un sottoinsieme proprio di B. Si indica: \(A \subset B\).

Analizzando i soliti due insiemi A e B. Se osserviamo che ogni elemento di un insieme appartiene anche all’altro, e viceversa, allora diciamo che esiste una relazione di uguaglianza tra i due insiemi.

Nota

La relazione di uguaglianza si indica: \(A = B\).

Consideriamo la possibilità che un insieme A sia contenuto in B e contemporaneamente B sia contenuto in A. Intuitivamente, diremo che ciò è possibile se e solo se i due insiemi sono uguali. Questo è un teorema dimostrabile, e viene usato per dimostrare che due insiemi sono uguali.

Nota

Quanto detto si esprime con la seguente relazione logica:

\[A = B \Leftrightarrow A \subseteq B \: e \: B \subseteq A\]

Consideriamo un ultimo concetto, che ci fa comprendere la flessibilità e genericità di questi strumenti: l'insieme delle parti.

Si dice insieme delle parti un insieme costruito usando come elementi tutti i sottoinsiemi di un insieme dato.

Nota

Se A è l’insieme di riferimento, il suo insieme delle parti è indicato con \(P(A)\).

L’insieme delle parti include l’insieme di riferimento (A) e l'insieme vuoto.

1.2. Operazioni tra insiemi

Dati due (o più) insiemi, è possibile definire delle operazioni tra loro.

Cominciamo con la unione. Si dice unione di due insiemi, l’insieme ottenuto con gli elementi di entrambi 1.

Nota

La unione degli insiemi A e B si scrive \(A \cup B\).

Qui sotto una rappresentazione grafica della operazione di unione tra i due insiemi A e B.

Questa operazione si può generalizzare per più di due insiemi.

Si dice intersezione di due insiemi, l’insieme ottenuto con gli elementi che appartengono ad entrambi 2.

Nota

La intersezione degli insiemi A e B si scrive \(A \cap B\).

Qui sotto una rappresentazione grafica della operazione di intersezione tra i due insiemi A e B.

Anche l’intersezione si può generalizzare per più insiemi.

Usando l’operazione di intersezione, è facile definire due insiemi disgiunti, ovvero che non hanno elementi in comune: «due insiemi sono disgiunti se la loro intersezione è l'insieme vuoto».

Si parla di partizione di un insieme quando, dato un insieme A di partenza, lo si suddivide in sottoinsiemi che non hanno elementi in comune (ovvero: disgiunti due a due).

Nell’immagine che segue, ho partizionato l’insieme A nei sottoinsiemi disgiunti da C1 a C4.

Si dice classe un elemento di una partizione come prima definita. Ovvero un sottoinsieme di A appartenente a una sua partizione.

Indovinate un po” per quale motivo nell’immagine precedente i nomi dei sottoinsiemi iniziano con la lettera C?

Per le operazioni di unione e intersezione valgono le proprietà seguenti (qui le formule ci vogliono, altrimenti non si capisce, quindi, occhio alle note):

• commutativa 3;

• associativa 4;

• distributiva 5;

• esistenza dell’elemento neutro 6;

• idempotenza 7.

Per ricordale si può fare un parallelo con le proprietà delle operazioni di somma, comparata all'unione, e del prodotto, comparata all'intersezione.

Si dice differenza di due insiemi l’insieme ottenuto con gli elementi appartenenti ad A ma non appartenenti a B.

Nota

La differenza di due insiemi A e B si scrive: \(A - B\)

Qui sotto una rappresentazione grafica della operazione di differenza tra i due insiemi A e B.

Intutivamente, unendo gli elementi che appartengono ad entrambi gli insiemi (intersezione), con quelli della differenza, riotteniamo l’insieme originale.

Nota

Quindi vale sempre: \(A = (A \cap B) \cup (A - B )\)

Una immagine vale cento parole:

Se B è un sottoinsieme di A, gli elementi di A non appartenenti a B formano l'insieme complementare di B rispetto A. Si indica con \(B'\).

Graficamene abbiamo:

Una proprietà simpatica, consiste nell’osservare che se un insieme ha un complementare, vale anche il viceversa: se \(B'\) è complementare di B, allora B è complementare di \(B'\).

Nota

Rimanendo nell’ambito del complementare. Se B è sottoinsieme di A, valgono queste proprietà:

• il complementare del complementare è il sottoinsieme iniziale (è l’osservazione precedente); ovvero \((B')' = B\);

• il complementare dell’insieme è l’insieme vuoto; ovvero: \(A' = \phi\);

• l’intersezione del sottoinsieme con il proprio complementare è l’insieme vuoto: \(B \cap B' = \phi\);

• l’unione del sottoinsieme con il proprio complementare è l’insieme: \(B \cup B' = A\).

È più complesso intuire le leggi di Morgan. Ovvero se B e C sono entrambi sottoinsiemi di A, valgono le seguenti:

\[\begin{split}(B \cap C)' = B' \cup C' \\ (B \cup C)' = B' \cap C'\end{split}\]

La seguente rappresentazioe grafica illusta la prima uguaglianza.

A sinistra sono illustrati i due passi (intersezione di B con C, e poi il complemento rispetto A) che formano la parte sinistra dell’uguaglianza.

A destra abbiamo i tre passi della parte destra dell’uguaglianza, ovvero formare i complementi B' e C' e poi farne l’unione.

Confrontanto il risultato a sinistra, con quello a destra, si osserva che le campiture finali coprono le stesse regioni di A.

Come dicevano i prof. dell’università ai miei tempi? Ah, sì: «vi lascio come esercizio la dimostrazione grafica della seconda uguaglianza …» :-)

Dati due insiemi si parla di somma disgiunta (o di differenza simmetrica) prendendo gli elementi che appartengono esclusivamente ad un insieme e non quelli che appartengono ad entrambi. Si indica con il simbolo + (o \(\Delta\)).

Nota

La somma disgiunta di A e B vale: \(A + B = A \cup B - (A \cap B) = (A - B) \cup (B - A)\)

graficamente abbiamo:

1.3. Prodotto cartesiano

Il concetto di prodotto cartesiano è fondamentale. Permette di passare da una dimensione a più dimensioni.

Dati due insiemi, A e B. Formiamo le coppie ordinate usando gli elementi di questi insiemi.

L'insieme di queste coppie ordinate è detto prodotto cartesiano di A per B, e si indica con \(A \times B\) 8. Questa espressione è così comune, che conviene accettarla e metterla nel nostro bagaglio di conoscenze spicciole.

Una coppia ordinata di elementi di A e B si indica con \((a, b)\). Anche questa è una espressione che dobbiamo essere in grado di usare.

Esempio. Supponiamo di avere un insieme di tre maglie come segue: \(A = \{rosso, bianco, verde\}\), e un insieme di modelli: \(B = \{Mario, Luca, Fabio\}\). Il loro prodotto cartesiano è l’insieme \(A \times B = \{(rosso, Mario), (rosso, Luca), (rosso, Fabio), (bianco, Mario), ... (verde, Luca), (verde, Fabio)\}\), e rappresenta tutte le possibili combinazioni tra maglia e modello.

Facciamo un esempio più ortodosso. Dato l’insieme dei numeri reali: \(\mathbb{R}\), il prodotto cartesiano \(\mathbb{R} \times \mathbb{R}\) rappresenta le coordinate cartesiane dei punti di un piano rispetto ad una coppia di assi coordinati.

La definizione di prodotto cartesiano si può estendere ad n insiemi:

\[\mathbb{R}^{n} = \overbrace{\mathbb{R} \times \mathbb{R} \times \dotsc \times \mathbb{R}}^\text{n-volte}\]

1.4. Relazione di equivalenza

Armati del concetto di prodotto cartesiano, passamo ad indagare quello di relazione binaria.

Dati due insiemi, A e B, formiamo l’insieme delle coppie ordinate dei loro elementi. Si dice che esiste una relazione binaria tra i due insiemi, quando esiste una proprietà che è vera per alcune delle coppie.

In pratica questa proprietà lega elementi di A con elementi di B. Di conseguenza, data una qualunque coppia \((a, b)\), è possibile affermare una delle seguenti:

• a é in relazione con b;

• a non è in relazione con b.

Nota

In algebraico, se indichiamo con \(\mathcal{R}\) la relazione, si dice che «l’elemento a è riferito mediante \(\mathcal{R}\) all’elemento b».

È importante notare questo aspetto. Se si prendono tutte le coppie \((a, b)\) per le quali vale «a é in relazione con b» otteniamo sempre un sottoinsieme S di \(A \times B\). Viceversa, dato un sottoinsieme S del prodotto cartesiano \(A \times B\), questo può sempre definire una relazione \(\mathcal{R}\) tra gli elementi di A e B.

Per l’osservazione precedente, si definisce una relazione binaria \(\mathcal{R}\) tra A e B come un sottoinsieme S di \(A \times B\) 9.

Vale la pena sottolineare il fatto che il concetto di relazione binaria è estremamente generale. Qui sotto rappresento graficamente una relazione binaria tra gli insiemi A e B.

Le frecce in questa immagine rappresentano la relazione binaria tra gli elementi dei due insiemi. Vale:

\[\begin{split}\mathcal{R} = \{ &(a1, b1), \\ &(a1, b2), \\ &(a2, b1), \\ &(a3, b3), \}\end{split}\]

Vogliamo vedere le capacità di metaragionamento che questi strumenti ci permettono? Bene. Prendiamo un insieme \(I\) i cui elementi sono insiemi. Possiamo formare il prodotto cartesiano \(I \times I\) che relaziona gli insiemi elementi a due a due.

Per ognuna di queste coppie, possiamo analizzare la rispondenza alla relazione di inclusione: se A è un sottoinsieme di B, rimane definita la relazione di inclusione «A è contenuto in B». Non male, vero? Usare l’insiemistica per ragionare sull’insiemistica.

Ora restringiamo l’attenzione al caso di una relazione binaria tra A e se stesso, ovvero su \(A \times A\).

In queste condizioni si parla di relazione di equivalenza se, per qualunque elemento di A, valgono le seguenti proprietà 10;

• riflessiva: un elemento equivale a se stesso;

• simmetrica: se un elemento a equivale a b, allora b equivale ad a;

• transitiva: se a equivale a b e b equivale a c allora a equivale a c.

Nota

Una relazione di equivalenza si indica con \(\sim\).

Esempio: supponiamo di avere l’insieme dei prodotti disponibili in un grande magazzino di vestiario. Una analisi dei prodotti per tipologia (ovvero: maglione, piuttosto che camicia, piuttosto che pantalone, …) definisce una classe di equivalenza. Se cerco unicamente una camicia (senza preferenze di colore, taglia, …), valgono le proprietà riflessiva (una camicia con serial number 12345678 equivale a se stessa), simmetrica (se la camicia con sn 12345678 equivale a quella con sn 12345679 vale anche il viceversa) e transitiva …

Ed ora l’esempio ortodosso. Dato l’insieme delle rette in un piano, considerando parallele anche due rette coincidenti, la relazione di parallelismo è una relazione di equivalenza.

Ma non finisce qui. Tenetevi forte, perché possiamo definire una relazione d’ordine sugli elementi di \(A \times A\). È una relazione binaria per la quale valgono le proprietà 11:

• riflessiva, la conosciamo: a precede (in senso lato) se stesso;

• antisimmetrica, ovvero se a precede b e b precede a, deduciamo che a è uquale a b;

• transitiva, al solito, se a precede b e b precede c, allora a precede c.

Nota

Abbiamo già usato la terminologia «a precede b», e si scrive: \(a \prec b\).

Esiste anche la relazione inversa: \(a \succ b\): «a segue b».

1.5. Insieme quoziente

Per arrivare al concetto di insieme quoziente, si deve prima capire quello di classe di equivalenza.

Dato un insieme A, e una relazione di equivalenza in essa, possiamo prendere un elemento a dell’insieme e considerare tutti gli altri elementi presenti nell’insieme, per i quali vale la relazione di equivalenza predetta.

L’insieme formato da a e dai sui equivalenti é la classe di equivalenza dell’elemento a di A12.

Nota

La classe di equivalenza dell’elemento a si indica con \([a]\).

Nell’esempio del magazzino di vestiario, se consideriamo la relazione di equivalenza per tipologia di vestiario, tutte le camicie del magazzino formano la classe di equivalenza della camicia.

Nell’esempio delle rette parallele, data una retta, la sua classe di equivalenza individua una direzione.

Il concetto di classe di equivalenza è importante, perché può essere usato per decomporre un insieme in una partizione. A questo riguardo esiste un teorema che afferma proprio questo concetto:

Le classi distinte di equivalenza individuate da una relazione di equivalenza definita in un insieme A vi determinano una partizione.

Viceversa, data una partizione dell’insieme A, si può definire una relazione di equivalenza in A rispetto la quale gli elementi della partizione sono classi distinte di equivalenza.

Riprendendo l’esempio del magazzino. Se considero tutti i diversi tipi di vestiario (camicia, pantalone, gonna, giacca, …), le relative classi di equivalenza mi suddividono il magazzino in sottoinsiemi disgiunti, che lo comprendono interamente: partizionano il magazzino.

Si noti che la seconda parte del teorema afferma anche l’inverso: data una partizione posso definire la relazione di equivalenza che la genera.

Già che ci siamo, cosa ci impedisce di considerare le diverse classi di equivalenza predette come elementi di un insieme?

Bene, dato l’insieme A, e una relazione di equivalenza in esso (che indichiamo con \(\sim\)), consideriamo l’insieme formato da tutte queste diverse classi di equivalenza.

Questo insieme è detto insieme quoziente di A rispetto a \(\sim\) 13.

Nota

L’insieme quoziente di A rispetto a \(\sim\) si indica con: \(A/\sim\).

Per quanto ci siamo detto in questi ultimi paragrafi, l’insieme quoziente è una partizione di A, ovvero una sua suddivisione in sottoinsiemi disgiunti due a due.

1.6. Applicazioni

Chi conosce il concetto di funzione, qui si troverà a proprio agio. Infatti, applicazione e funzione sono termini sinonimi.

E, per capire il loro uso nell’insiemistica, prendiamo due insiemi A e B: una applicazione è una legge che ad un elemento di A associa un unico elemento di B.

Come, ad esempio, nella seguente figura:

Se questo concetto vi suona familiare, non stupitevi. Provate a fare un confronto con il concetto di relazione binaria … la differenza fondamentale sono le paroline unico elemento (di B). Nella relazione binaria non vi è questa limitazione.

Questo concetto è importante, ed è del tutto analogo a quello di funzione per i numeri reali, che possiamo osservare nel seguente esempio grafico.

Nel riquadro a destra la curva traccia una relazione tra la variabile indipendente x e la variabile dipendente y. Ma non è una funzione perché vi sono valori di x cui corrispondono più valori di y. Ad esempio al valore x1 corrispondono tre valori di y: y1, y2 e y3.

Invece nel riquadro a sinistra, la curva è una funzione, in quanto ad un singolo valore di x corrisponde al più un valore di y.

Fatta la presentazione, qui vi è un po' di terminologia da tenere presente.

Per cominciare, l’insieme di partenza, è detto dominio, quello di arrivo è il codominio.

Se l’applicazione é \(f\), e l’elemento di partenza é a, l’elemento di arrivo è detto valore di \(f\) in a, e si indica con \(f(a)\).

Questo grafico indica questi tre termini:

Nota

Formalmente la funzione si indica come \(f : A \rightarrow B\).

O anche come segue per indicare la legge che lega a con b:

\[\begin{split}f\,:\,&\,A \rightarrow B \\ &\,a \mapsto b\end{split}\]

Ad esempio, da numero reale a numero reale, cambiare segno an numero del dominio, è la funzione \(\dotso (-1,1) \dotso (1,-1) \dotso (1.5,-1.5) \dotso\); e si indica:

\[\begin{split}f\,:\,&\,\mathbb{R} \rightarrow \mathbb{R} \\ &\,x \mapsto -x\end{split}\]

L’insieme dei valori assunti da \(f\) al variare di a è detto immagine di \(f\).

Nota

L’immagine di \(f\) si indica con \(Imf\), oppure \(f(A)\). Si noti che nelle parentesi di \(f\), qui è indicato l’intero dominio, non il singolo elemento.

Nella figura precedente, l’immagine della funzione è l’insieme \(Imf = \{f(a1), f(a2), f(a3)\}\).

Si parla di applicazione suriettiva se la funzione ricopre tutto il codominio. Ovvero se ogni elemento di B è immagine di almeno un elemento di A. In questo caso si dice che abbiamo una applicazione \(f\) di A sopra B.

Nella figura precedente l’applicazione non é suriettiva perché vi sono due elementi di B che non sono in relazione con alcun elemento di A. Se B non avesse questi due elementi, allora l’applicazione illustrata sarebbe suriettiva.

Si parla di applicazione iniettiva se elementi distinti del dominio, hanno immagini distinte. Ovvero se un elemento b del codominio é riferito da un solo elemento a del dominio.

Nella figura precedente l’applicazione non é iniettiva perché il valore \(f(a1)\), oltre che da a1 è riferito anche dall’elemento a2. Se l’elemento a2 non facesse riferimento al valore \(f(a1)\), allora l’applicazione sarebbe iniettiva.

Si parla di applicazione biiettiva se è sia suriettiva che iniettiva. In tal caso non solo vi è una relazione uno a uno tra un elemento a e il suo corrispondente b. Inoltre la funzione copre completamente il codominio.

Nota

Una applicazione biiettiva si indica come \(f : A \leftrightarrow B\).

La seguente figura illustra un esempio di funzione biiettiva:

E se volessimo invertire il concetto dell’applicazione, muovendoci dal codominio al dominio?

Bene, facciamolo. Data la funzione \(f\) da A a B, possiamo considerare l’elemento \(b = f(a)\). Per l’elemento b possiamo avere la sua immagine reciproca considerando gli elementi a che lo riferiscono 14.

Nota

L’immagine reciproca di b si indica con \(f^{-1}(b)\), e viene chiamata fibra di \(f\) su b.

Se l’applicazione é suriettiva, tutti gli elementi del codominio sono raggiunti dall’applicazione. Quindi ogni elemento del codominio ha una sua fibra.

Se la funzione é biiettiva, ogni elemento del codominio è raggiungibile dall’applicazione tramite un solo elemento del dominio. In questa condizione la fibra di ogni elemento del codominio è formata da un solo elemento del dominio.

Nel caso di applicazione biiettiva \(f\) tra dominio A e codominio B, comunque prendiamo un elemento b di B, avremo sempre uno e un solo elemento a da cui raggiungerlo. Perciò possiamo definire una applicazione che leghi b con a. Questa è detta applicazione inversa.

Nota

Una applicazione inversa si indica con \(f^{-1}\), e si definisce:

\[\begin{split}f^{-1}\,:\,&\,B \rightarrow A \\ &\,b \mapsto a\end{split}\]

Si dimostra che l’immagine reciproca della unione di due insiemi è uguale alla unione delle loro immagini. Analogamente per l’operazione di intersezione.

Nota

Formalmente, dati due insiemi M e N:

\[\begin{split}f^{-1}( M \cup N) = f^{-1}(M) \cup f^{-1}(N) \\ f^{-1}( M \cap N) = f^{-1}(M) \cap f^{-1}(N)\end{split}\]

Inoltre, si dimostra che l’immagine della unione di due insiemi è uguale alla unione delle loro immagini. Questa proprietà, non vale per l’operazione di intersezione.

Nota

Formalmente, dati due insiemi M e N:

\[f( M \cup N) = f(M) \cup f(N)\]

Concludiamo questo capitolo osservando che è possibile definire una applicazione da A verso B, considerando l’insieme delle sue coppie ordinate \((a, b)\), che formano un sottoinsieme M di \(A \times B\), a patto che ad un valore di a corrisponda un unico valore di b. In tal caso M è il grafico della funzione, e tale grafico definisce la funzione stessa.

1.7. Composizione di applicazioni

Supponiamo di avere due applicazioni. La prima, \(f\), dall’insieme A all’insieme B. E la seconda, \(g\), dall’insieme B all’insieme C.

Inoltre, supponiamo che il dominio di \(g\) in B contenga l’immagine di \(f\).

In queste condizioni, dato un elemento a, possiamo pensare di applicare in sequenza prima \(f\), e sul relativo valore \(f(a)\), applicare \(g\) ottenendo un valore finale \(g(f(a))\) che sarà un elemento dell’insieme C.

Questo giochetto si chiama applicazione composta di \(f\) con \(g\), e nulla ci impedisce di immaginarla come una applicazione da A a C.

Nota

Formalmente una applicazione composta di \(f\) con \(g\) si indica con: \(g \circ f\) 15 ed è chiamata anche applicazione prodotto.

Più estesamente, é:

\[\begin{split}g \circ f \, : \,&\, A \rightarrow C \\ &\, x \mapsto g(f(a)) \quad \forall a \in A\end{split}\]

Da un punto di vista grafico, una applicazione composta può essere rappresentata come segue:

Per le applicazioni composte, si dimostrano le seguenti proprietà:

• vale la proprietà associativa 16,

• esiste l’applicazione identica, ovvero una applicazione che restituisce il suo elemento in ingresso, si indica con \(I_A\), vale \(I_A(a) = a\), e non modifica il valore di qualunque applicazione \(f\) 17,

• l’applicazione composta di due applicazioni iniettive, è iniettiva,

• l’applicazione composta di due applicazioni suriettive, è suriettiva,

1.8. Insiemi equipotenti

Due insiemi si dicono equipotenti se è possibile definire una applicazione biiettiva tra loro.

Come caso particolare di equipotenza, se si può definire una applicazione biiettiva tra un insieme A e quello dei numeri naturali N, allora si dice che A è numerabile.

1.9. Partizione di un insieme e applicazioni

Esiste un rapporto tra il concetto di applicazione e quello di relazione di equivalenza, rapporto che conduce alla seguente interessante, e articolata, osservazione:

1. data una applicazione \(f\) di A in B;

2. definiamo equivalenti gli elementi del dominio di \(f\) che portano allo stesso elemento di codominio; indichiamo con \(\sim\) questa equivalenza;

3. in questo modo abbiamo creato una partizione di A formata dalle classi di equivalenza definite al punto precedente, l’insieme di queste classi di equivalenza è un insieme quoziente; lo indichiamo con \(A/\negthinspace\sim\); possiamo pensare di avere una applicazione (la indichiamo con \(\pi\)) che mette in relazione un qualsiasi elemento del dominio di \(f\) (ovvero A) con la classe di equivalenza cui appartiene, e quindi il suo codominio è \(A/\negthinspace\sim\);

   Nota

   Formalmente, l’applicazione \(\pi\) si definisce con:

   \[\begin{split}\pi : \,& A \rightarrow A/\negthinspace\sim \\ & a \mapsto [a]\end{split}\]

4. a questo punto possiamo chiudere il giro, e pensare di avere una applicazione di \(A/\negthinspace\sim\) in B; ovvero legare una classe di equivalenza di A con il relativo elemento in B: indichiamo questa applicazione come \(f/\negthinspace\sim\).

I punti predetti si sintetizzano con il seguente diagramma commutativo di applicazioni:

in cui osserviamo l’applicazione \(\pi\) che lega gli elementi del dominio di \(f\) agli elementi dell’insieme quoziente \(A /\negthinspace\sim\), e l’applicazione \(f/\negthinspace\sim\) che lega gli elementi dell’insieme quoziente al codominio di \(f\).

Quindi l’uso opportuno della relazione di equivalenza \(\sim\) permette la definizione di una funzione \(f/\negthinspace\sim\) che è sicuramente iniettiva tra insieme quoziente \(A/\negthinspace\sim\) e B.

Inoltre se \(f\) è suriettiva in B, allora \(f/\negthinspace\sim\) è biiettiva.

Si può anche ragionare rispetto una equivalenza definita a priori. Se abbiamo una equivalenza (indicata con \(\sim\)) su un insieme A, possiamo dire che una applicazione \(f\) di A in B è ben definita sullo spazio quoziente se vale il diagramma commutativo precedentemente mostrato.

Nota

Formalmente, l’applicazione \(f : A \rightarrow B\) è ben definita sullo spazio quoziente se:

\[a_1 \sim a_2 \in A / \sim \quad \boldsymbol{\Longrightarrow} \quad f(a_1) = f(a_2)\]

Un’ultima osservazione. Il diagramma commutativo che abbiamo visto ci suggerisce un’altra possibile interpretazione: la funzione \(f : A \rightarrow B\) può essere vista come una funzione composta di \(\pi\) con \(f/\negthinspace\sim\).

Per chiudere questo capitolo, facciamo un esempio di quelli seri. Prendiamo lo spazio euclideo in tre dimensioni e fissiamo in esso un piano bidimensionale (nominiamolo \(\alpha\)).

Come applicazione prendiamo sia una proiezione dello spazio su \(\alpha\) secondo una certa direzione non parallela al piano. Nominiamo \(\pi\) questa applicazione.

\(\pi\) è una applicazione suriettiva dello spazio euclideo su \(\alpha\) (copre tutto il piano), ma non è iniettiva perché ogni punto dello spazio appartenente ad una retta secondo la direzione di proiezione individua lo stesso punto di proiezione sul piano.

Se nello spazio noi definiamo equivalenti due punti che danno la stessa proiezione su \(\alpha\), allora tramite \(\pi\) abbiamo definito una biiezione tra l’insieme quoziente e \(\alpha\).

1.10. Trasformazioni di un insieme

Vediamo un esempio importante di uso dei concetti di insiemistica.

Prendiamo un qualunque insieme A. E chiamiamo trasformazione di A una applicazione biiettiva di A in sè.

In generale saranno possibili più trasformazioni di A. Ognuna di queste può essere considerata un elemento di un nuovo insieme. Tutte le possibili trasformazioni di A formeranno un insieme, che chiamiamo T(A).

Queste trasformazioni sono applicazioni. Quindi esiste la possibilità di comporle formando una applicazione composta.

Si dimostra che esistono le seguenti proprietà:

• date due qualunque trasformazioni di A, la loro composizione è ancora una trasformazione di A 18;

  Nota

  ovvero: \(\rho \circ \sigma \in T(A) \quad \forall \rho , \sigma \in T(A)\);

• nel comporre le trasformazioni, vale la proprietà associativa;

  Nota

  cioè: \(( \rho \circ \sigma ) \circ \tau = \rho \circ ( \sigma \circ \tau ) \quad \forall \rho , \sigma , \tau \in T(A)\);

• esiste una particolare trasformazione, detta identità, che può comporre una qualunque altra trasformazione senza alterarla;

  Nota

  detta i la trasformazione identità, possiamo scrivere: \(i \circ \rho = \rho \circ i = \rho \quad \forall \rho \in T(A)\);

• ogni trasformazione in A ha una sua inversa; se si compone l’inversa con la trasformazione in analisi, si ottiene la trasformazione identità;

  Nota

  indicando con \(\rho^{-1}\) l’inversa della trasformazione \(\rho\), abbiamo: “” \(\rho^{-1} \circ \rho = \rho \circ \rho^{-1} = i \quad \forall \rho \in T(A)\).

Premesso che, quando abbiamo un insieme e delle operazioni su di esso, diciamo di avere definito una struttura algebrica; in questo caso, considerando l’insieme T(A) e la legge di composizione ora vista, abbiamo una particolare struttura algebrica, detta struttura di gruppo.

1.11. Leggi di composizione

Facciamo un salto indietro, e dimentichiamo temporaneamente il concetto di applicazione.

Prendiamo un insieme A. Supponiamo sia possibile legare a delle coppie di elementi di A un terzo elemento, sempre appartenente ad A. In questo caso si dice di avere una legge di composizione interna.

Se a, b e c sono i tre elementi predetti, si dice che «c è il prodotto di a per b».

Avvertimento

Attenzione a non applicare la precedente frase alla lettera. Una legge di composizione non deve essere necessariamente un prodotto in senso letterale. Piuttosto, è un concetto di operazione binaria del tutto generica.

Nota

Formalmente una legge di composizione si indica con il simbolo \(\circ\), che rappresenta una operazione generica: \(c = a \circ b\).

Essendo una operazione generica, spesso la legge di composizione è indicata con un simbolo più specifico, relativo alla particolare operazione considerata. O, addirittura, si può non indicare, dandolo per sottinteso.

L’insieme A, munito della legge di composizione, si indica con \((A, \circ)\). Come già indicato in questa premessa, questa è una struttura algebrica.

Adesso ricordiamo la definizione di applicazione. Utilizzando questa per analizzare il concetto di legge di composizione, possiamo anche dire che:

una legge di composizione è una applicazione definita su \(A \times A\), o un suo sottinsieme, con valori in A.

Esempi di leggi di composizione: l’operazione di addizione nell’insieme dei numeri naturali. Questa legge è definita per qualunque coppia di numeri naturali.

Altro esempio: l’operazione di sottrazione nell’insieme dei numeri naturali, In questo caso l’operazione è definita solo se il minuendo è maggiore o uguale del sottraendo.

Quando si definisce una legge di composizione su un insieme A, varranno (o non varranno) determinate proprietà.

Bene: le diverse strutture algebriche sono classificate secondo le proprietà soddisfatte dalla relativa legge di composizione.

Le proprietà da considerare sono le seguenti.

1. Proprietà associativa. Se, dati tre elementi composti tra loro, non è influente la precedenza con cui si esegue la prima composizione rispetto la seconda.

   Nota

   Formalmente: \((a \circ b) \circ c = a \circ (b \circ c) \quad \forall a, b, c \in A\).

   Un insieme non vuoto tra i cui elementi sia definita una legge di composizione che gode della proprietà associativa si dice semigruppo.

2. Proprietà commutativa. Se, dati due elementi, l’ordine di composizione è ininfluente.

   Nota

   Ovvero: \(a \circ b = b \circ a \quad \forall a, b \in A\).

   Nota

   Di solito una legge di composizione commutativa si indica con il simbolo \(+\).

3. Esistenza di un elemento neutro. Quando esiste un elemento che composto con qualunque altro elemento restituisce sempre il secondo elemento. In questo ambito deve valere la legge commutativa.

   Nota

   Ovvero, detto \(e\) l’elemento neutro, vale: \(e \circ a = a \circ e = a\).

   Ad esempio, lo zero è l’elemento neutro per l’operazione di addizione nell’insieme dei numeri naturali. Mentre l’1 è l’elemento neutro per la legge di composizione di moltiplicazione, sempre nell’insieme dei naturali.

   Si noti che non è detto che l’elemento neutro debba esistere. Ad esempio si prenda l’insieme dei numeri naturali pari. E come legge di composizione si consideri la moltiplicazione. In questo caso l’elemento neutro non esiste.

   Mentre si può dimostrare che se esiste un elemento neutro, questo è unico.

4. Elementi simmetrici. Se esiste l’elemento neutro per una legge di composizione, dato un elemento \(a\), si dice che ha un elemento simmetrico \(a'\) se la loro composizione rende l’elemento neutro.

   Nota

   Cioè: \(a \circ a' = a' \circ a = e\).

   Se esiste il simmetrico di un elemento, non è detto sia unico. A meno che la legge di composizione sia associativa, in tal caso si dimostra l’univocità del simmetrico.

Quando su un insieme esistono più leggi di composizione, allora si possono avere dei rapporti tra queste leggi. Ad esempio si pensi alla proprietà distributiva della moltiplicazione rispetto l’addizione nell’insieme dei numeri reali.

Se si considerano due diversi insiemi A e B, è possibile considerare una legge di composizione tra elementi del prodotto cartesiano \(B \times A\) verso un elemento di A. In questo caso si parla di legge di composizione esterna.

Un esempio di composizione esterna è il prodotto di uno scalare \(k\) appartenente all’insieme dei numeri reali, per un vettore \(\overrightarrow{v}\). Questo prodotto rende un nuovo vettore, che ha la stessa direzione di \(\overrightarrow{v}\), un modulo pari a \(| k |\) volte il modulo di \(\overrightarrow{v}\), e un verso uguale a quello di \(\overrightarrow{v}\) se \(k > 0\), oppure opposto se \(k < 0\)

1.12. Struttura algebrica di un insieme

Come ci siamo detti già un paio di volte: un insieme e una legge di composizione sui suoi elementi definisce quella che chiamiamo una struttura algebrica.

Uno stesso insieme può avere diverse strutture algebriche: dipende da quale (o quali: può essere più di una) legge di composizione stiamo considerando.

Ad esempio, prendiamo i numeri reali. Se la legge di composizione è l’addizione, allora avremo una struttura di gruppo. Se sullo stesso insieme consideriamo le leggi di moltiplicazione e addizione, allora abbiamo una struttura di campo.

Ora facciamo una considerazione rilevante. Se abbiamo insiemi diversi, su cui sono definite leggi di composizione (ovvero: operazioni) con le stesse proprietà, allora tutti i teoremi basati su queste proprietà rimangono validi per ciascuno degli insiemi in questione.

Ad esempio. In questo capitolo stiamo parlando di insiemistica. Dato un insieme U su cui sono definiti unione, intersezione e complementazione; l’insieme delle sue parti e le relative operazioni \((P(U), \cup, \cap, ')\) hanno una serie di proprietà definite nella seguente nota 19. Se si considera un nuovo insieme, formato da due elementi \(I=\{0,1\}\), e tre operazioni or, and, not come definite in nota 20, si dimostra che per questa struttura algebrica 21, valgono le stesse proprietà della struttura algebrica \((P(U), \cup, \cap, ')\).

La considerazione precedente è importante sia perchè, in base ad essa, basta dimostrare un teorema in un contesto per ritenerlo poi valido in tutti i contesti con la stessa struttura algebrica, ottenendo una notevole economia di pensiero. Sia perché può mettere in evidenza fatti essenziali da cui dipendono vari teoremi.

---

1

Esempio di unione tra due insiemi:

\[\begin{split}& A = \{1,2,3\} \\ & B = \{3,4,5\} \\ & A \cup B = \{1,2,3,4,5\}\end{split}\]

2

Esempio di intersezione tra due insiemi:

\[\begin{split}& A = \{1,2,3\} \\ & B = \{3,4,5\} \\ & A \cap B = \{3\}\end{split}\]

3

Unione e intersezione, proprietà commutativa:

\[\begin{split}A \cup B = B \cup A \\ A \cap B = B \cap A\end{split}\]

4

Unione e intersezione, proprietà associativa:

\[\begin{split}(A \cup B) \cup C = A \cup (B \cup C) \\ (A \cap B) \cap C = A \cap (B \cap C)\end{split}\]

5

Unione e intersezione, proprietà distributiva:

\[\begin{split}A \cup (B \cap C) = (A \cup B) \cap (A \cup C) \\ A \cap (B \cup C) = (A \cap B) \cup (A \cap C)\end{split}\]

6

Unione e intersezione con l’insieme vuoto:

\[\begin{split}A \cup \phi = A \\ A \cap \phi = \phi\end{split}\]

7

Unione e intersezione, proprietà di idempotenza:

\[\begin{split}A \cup A = A \\ A \cap A = A\end{split}\]

8

In sintesi, il prodotto cartesiano è:

\[A \times B = \{(a, b) | a \in A, b \in B\}\]

9

Una relazione binaria, se \(S \subseteq A \times B\), si esprime con:

\[a \mathcal{R} b \Leftrightarrow (a,b) \in S\]

10

In algebraico, per la relazione di equivalenza, valgono le proprietà:

\[\begin{split}& a \sim a \quad\text{riflessiva}\\ & a \sim b \Rightarrow b \sim a \quad\text{simmetrica}\\ & a \sim b, b \sim c \Rightarrow a \sim c \quad\text{distributiva}\end{split}\]

11

Proprietà per la relazione d’ordine:

\[\begin{split}& a \mathcal{R} a \quad\text{riflessiva} \\ & a \mathcal{R} b, b \mathcal{R} a \Rightarrow a = b \quad\text{antisimmetrica} \\ & a \mathcal{R} b, b \mathcal{R} c \Rightarrow a \mathcal{R} c \quad\text{transitiva}\end{split}\]

12

Classe di equivalenza, dato l’insieme A:

\[[a] = \{x \in A | x \sim a\}\]

13

Perché parliamo di quoziente?

Prendiamo la solita cassetta con 100 mele, e dividiamola in 20 gruppi uguali di 5 mele ciascuno. Cominciamo a vedere l’analogia?

La cassetta è l’insieme A. Ogni gruppo di 5 mele è una diversa classe di equivalenza. I 20 gruppi sono il quoziente, ottenuto dividendo 100 per 5.

Abbiamo partizionato la cassetta in 20 insiemi tra loro disgiunti, formati ciascuno a 5 mele.

14

Occhio al plurale. In generale è possibile che un singolo elemento b sia riferito da più elementi di A.

15

Notare la sequenza delle lettere nella formula: g viene prima di f, a differenza della locuzione nel linguaggio parlato, in cui l’ordine è invertito.

16

Ovvero \((h \circ g) \circ f = h \circ (g \circ f)\)

17

Infatti vale: \((f \circ I_A) (a) = f(I_A(a)) = f(a) = f\).

Inoltre vale \(I_B \circ f = f(a) = f\).

18

Questa proprietà si esprime anche dicendo che l’insieme delle trasformazioni T(A) è chiuso rispetto il prodotto \(\rho \circ \sigma\).

19

proprietà dell’insiemistica, \(\forall A, B, C \in P(U)\)

\[\begin{split}& B_1 : A\cup B = B \cup A \\ & B_{1'} : A\cap B = B \cap A \\ & B_{2} : A\cup \phi = A \\ & B_{2'} : A\cap U = A \\ & B_{3} : A\cap (B \cup C) = (A\cap B) \cup (A \cap C) \\ & B_{3'} : A\cup (B \cap C) = (A\cup B) \cap (A \cup C) \\ & B_{4} : A\cap A' = \phi \\ & B_{4'} : A\cup A' = U\end{split}\]

20

Operazioni; or:

\[\begin{split}\begin{matrix} + & 0 & 1 \\ 0 & 0 & 1 \\ 1 & 1 & 1 \end{matrix}\end{split}\]

and:

\[\begin{split}\begin{matrix} \circ & 0 & 1 \\ 0 & 0 & 0 \\ 1 & 0 & 1 \end{matrix}\end{split}\]

not:

\[\begin{split}\begin{matrix} ' & \\ 0 & 1 \\ 1 & 0 \end{matrix}\end{split}\]

21

Detta Algebra di Boole.