Teoria degli Insiemi

Teoria degli Insiemi

Definizioni e proprietà

Generalità

Un insieme è un raggruppamento, una classe o una collezione di oggetti, detti elementi dell'insieme.
Sia un insieme ed un suo elemento; per indicare che è un elemento di , si scrive e si legge appartenente ad , oppure appartiene ad . Invece la scrittura indica che non appartiene ad , non è un elemento di .


Un insieme privo di elementi si dice insieme vuoto e si denota con .



Nella teoria degli insiemi, solitamente, sono usati tre tipi di rappresentazione:

1. tabulare, che consiste nell'elencare, quando è possibile, tutti gli elementi di un insieme, entro parentesi graffe: ad esempio, consideriamo l'insieme composto dalle prime lettere dell'alfabeto allora posso scrivere
   
2. grafica, che consiste nel rappresentare gli elementi di un insieme con punti interni ad una linea piana, chiusa e non intrecciata (diagrammi Eulero-Venn): di seguito è riportata la rappresentazione grafica
   dell'insieme delle prime tre lettere dell'alfabeto
   
3. caratteristica, che consiste nello specificare un certo numero di proprietà che servono a decidere, in modo inequivocabile, quali elementi appartengono all'insieme considerato e quali non vi appartengono: ad esempio, possiamo caratterizzare l'insieme come l'insieme delle prime cinque lettere dell'alfabeto che siano consonanti, cioè
   

Esempio 1: Sia . L'ordine degli elementi è irrilevante. Per verificare se un elemento appartiene ad si procede per "scorrimento", cioè si controllano tutti gli elementi di , verificando se è presente quello desiderato; in particolare notiamo che la lettera "" non appartiene ad (perchè non coincide con , nè con , nè con , nè con ), mentre appartiene ad
Osserviamo che tale insieme non può essere dato assegnando una proprietà


.
Esempio 2: Sia " è una vocale" L'insieme è definito attraverso una proprietà; osserviamo che



Esempio 3: Rappresentiamo graficamente con un diagramma di Eulero-Venn la classificazione dei triangoli rispetto ai lati:
Sia un insieme, una proprietà si dice definita in se è possibile stabilire che ogni elemento di gode oppure no di tale proprietà.
Per dire che un elemento gode (risp. non gode) di una certa proprietà si dice anche che la suddetta proprietà è vera (risp. è falsa) per .

Sottoinsiemi e relazione di inclusione

Dato un insieme, sia un insieme tale che "ogni elemento di è anche elemento di ", si dice che è incluso in , o che include e si scrive Il simbolo è detto inclusione e si definisce sottoinsieme di
Le scritture indicano che non include .



Se e , allora vuol dire che esiste almeno un elemento di che non appartiene ad , pertanto si dice che è incluso propriamente in o che è sottoinsieme proprio di e si indica con

Osserviamo che per ogni insieme si ha che:


In particolare se è un insieme e una proprietà vera per qualche elemento di , l'insieme costituito dagli elementi di che verificano si indica con

si dice parte di individuata dalla proprietà o sottoinsieme di individuato dalla proprietà .

Simboli logici

Allo scopo di una maggiore concisione è opportuno adoperare alcuni simboli per sintetizzare frasi di uso corrente. In particolare, l'espressione Esiste almeno un tale che si indica con analogamente, per dire Esistono almeno ed tali che , è sufficiente scrivere Il simbolo è detto quantificatore esistenziale.
Le frasi Per ogni , Qualunque sia si rappresentano con
Analogamente le frasi Per ogni ed e Qualunque siano ed si indicano con Il simbolo è detto Quantificatore universale.

Siano e due proposizioni o affermazioni definite in . Si dice che in implica o che consegue da , e si scrive se è verificata da ogni elemento di che verifichi anche . Quando si dice anche che il verificarsi di è condizione sufficiente per il verificarsi di o, analogamente, che il verificarsi di è condizione necessaria per il verificarsi di
Se e si dice che le proprietà e sono equivalenti in e si scrive Quando si dice anche che il verificarsi di è condizione necessaria e sufficiente per il verificarsi di o che è vera se e solo se è vera
Le scritture sono le negazioni delle affermazioni precedenti.



Esempio 4: Sia l'insieme costituito da tutti i diplomati:
=" ha conseguito il diploma di maturità"
=" è iscritto all'Università degli Studi di Salerno".

Chiaramente ma poichè potrebbero esserci dei diplomati che non sono iscritti all'Università Invece le proposizioni:

=" ha conseguito il diploma di maturità"
=" ha superato l'esame di stato per conseguire il diploma"




sono fra loro equivalenti, cioè poichè non è possibile conseguire il diploma di maturità senza sostenere l'esame di stato.





Esempio 5: Siano l'insieme delle provincie italiane e siano
contiene almeno una vocale
inizia con la lettera a
L'insieme è parte di individuato dalla proprietà " inizia con la lettera a".
Inoltre se e sono due proprietà definite in , risulta:




Esempio 6: Sia l'insieme costituito da tutti gli studenti iscritti al corso di Laurea in Ingegneria Informatica dell'Università di Salerno. I sottoinsiemi e sono tali che infatti, dette e risulta

Insieme delle parti

L'insieme di tutti i sottoinsiemi di un insieme si denota con e si chiama insieme delle parti di
Va osservato che gli insiemi e


e vengono denominati sottoinsiemi impropri o banali.

Esempio 3: Sia l'insime costituito da tutte le lettere della parola dado. Essendo , i suoi sottoinsiemi propri sono:
.
mentre i sottoinsiemi impropri (o banali) sono:
e .
Pertanto, l'insieme delle parti di è dato:
 
Esempio 4: Si consideri l'insieme

è ovvio che e quindi

Un insieme formato da un solo elemento si chiama singleton. è il singleton di cioè l'insieme costituito dal solo elemento ; cioè un insieme formato da un solo elemento non si identifica con tale elemento; infatti ed sono oggetti di diverso tipo: il primo è un insieme, il secondo è un elemento, pertanto non sono confrontabili.
Sia un insieme costituito da elementi. Si dimostra che il numero di elementi di


è pari a .




Esempio 5: Si consideri un insieme costituito da elementi




Gli elementi dell'insieme delle parti


sono pari a




Esempio 6: Si consideri un insieme costituito da elementi




Allora l'insieme delle parti


è costituito da elementi, come già mostrato nell'esempio precedente.

 

Operazioni su insiemi: unione, intersezione e complemento

Sia un insieme e siano e due sottoinsiemi di . Il sottoinsieme di costituito dagli elementi che appartengono ad oppure (senza esclusività) ad si dice unione di e e si indica con , cioè





Esempio Sia l'insieme costituito daille lettere dell'alfabeto. Siano e si vede che




L'operazione di unione soddisfa le seguenti proprietà: È banale verificare che e che Più in generale, detti sottoinsiemi di (non necessariamente distinti), si dice unione di essi, il sottoinsieme di : che è costituito dagli elementi di ognuno dei quali gode della proprietà di appartenere ad almeno uno degli insiemi dati.
La nozione di unione di insiemi è ulteriormente generalizzabile. Sia una famiglia di indici ed una famiglia di sottoinsiemi di , si definisce unione della famiglia , il sottoinsieme di costituito dagli elementi di ognuno dei quali gode della proprietà di appartenere ad almeno un .




Sia un insieme ed ed due suoi sottoinsiemi. Si definisce intersezione di e e si denota con il sottoinsieme di costituito dagli elementi che appartengono sia ad che a , cioè




Esempio Sia l'insieme costituito dagli animali da cortile e siano e Risulta




E' immediato verificare che l'operazione di intersazione verifica le seguenti proprietà:




Inoltre, è banale provare che Più in generale, detti sottoinsiemi di (non necessariamente distinti), si dice intersezione di essi, il sottoinsieme di : che è costituito dagli elementi di ognuno dei quali gode della propietà di appartenere a ciascuno degli insiemi dati.
La nozione di intersezione di insiemi è ulteriormente generalizzabile. Sia una famiglia di indici ed una famiglia di sottoinsiemi di , si definisce intersezione della famiglia , il sottoinsieme di costituito dagli elementi di ognuno dei quali gode della proprietà di appartenere a ciascun .




Due sottoinsiemi si dicono poi disgiunti quando non esiste alcun elemento appartenente ad entrambi,cioè:



Esempio Sia è l'insieme delle lettere dell'alfabeto e siano ed due sottoinsiemi di definiti nel seguente modo

È banale osservare che risulta .




Sia un sottoinsieme di , si definisce complemento di in il sottoinsieme di costituito dagli elementi di che non appartengono ad e si denota con
Chiaramente e
Sono verificate, inoltre, le seguenti relazioni




Siano ed sono due sottoinsiemi di , si dice complemento di rispetto ad il sottoinsieme di costituito dagli elementi di che appartengono a B e non appartengono ad A e si denota con

Inoltre, si verifica che:

Esempio Siano ed
Il complementare di rispetto ad sarà dato da:

Proprietà distributiva dell'unione e dell'intersezione

Sia un insieme ed , e tre suoi sottoinsiemi, è facile verificare che vale la proprietà distributiva dell'unione rispetto all'intersezione

e la proprietà distributiva dell'intersezione rispetto all'unione

Queste relazioni si estendono a collezioni qualsiasi di sottoinsiemi di , risulta, infatti, che se e sono sottoinsiemi di , allora: e




Esempio Siano , e , allora
Inoltre e

Relazioni di De Morgan

Siano e due sottoinsiemi di . Si verifica facilmente che
e Tali relazioni si estendono anche al caso di unioni ed intersezioni di famiglie di insiemi. Risulta, infatti, che se è una collezione di sottoinsiemi di , e

---

Esempi Sia , e . Si ha che:

.

.

Partizione di un insieme

Si definisce partizione di un insieme un qualsiasi sottoinsieme dell'insieme delle part di , , composto da sottoinsiemi di a due a due disgiunti e la cui unione è .
Ovviamente un insieme può ammettere partizioni diverse.


Esempio Sia , allora e costituiscono una partizione di , mentre e , pur essendo sottoinsiemi di tali che , non costituiscono una partizione di , poichè non sono disgiunti, cioè

Prodotto cartesiano di insiemi

Siano e due insiemi di , si definisce prodotto cartesiano di e e si denota con l'insieme

Esempio Siano Si ha:




Se ha elementi, ha elementi, ha elementi.
Osserviamo che cioè, a differenza del caso degli insiemi, l'ordine degli elementi è essenziale. Nella coppia l'elemento si dice prima coordinata mentre l'elemento si dice seconda coordinata. Se è un insieme, il prodotto si indica con

Esempio Sia si ha:




Siano insiemi, si definisce prodotto cartesiano di per per l'insieme delle n-ple (ordinate):
ovvero l'insieme i cui elementi sono le -uple ordinate con , . Gli insiemi , si chiamano rispettivamente primo fattore, secondo fattore, , -esimo fattore del prodotto cartesiano e gli elementi prima coordinata, seconda coordinata, , -esima coordinata dell'elemento . Se gli insiemi sono tutti uguali fra loro e coincidenti con un dato insieme , il loro prodotto cartesiano si denota con .




Esempio Sia e , il prodotto cartesiano è dato da:

È evidente che . È ovvio che, essendo costituito da elementi e costituito da elementi, allora sarà composto da elementi.