Nei paragrafi precedenti abbiamo visto che i predicati possono essere combinati tra loro e quantificati. Ma quali sono i predicati elementari che possiamo considerare per fondare tutta la matematica? La teoria degli insiemi ci fornisce la formalizzazione del concetto di appartenenza: il predicato di base (l’unico che ci servirà) è un predicato della forma che significa “l’oggetto è un elemento dell’insieme ”. La teoria degli insiemi non spiega (né tantomento definisce) cosa siano gli oggetti e cosa siano gli insiemi perché questi sono concetti primitivi (come lo sono i punti e le rette per la geometria euclidea). La teoria degli insiemi ci fornisce, semplicemente, le regole formali che possono essere utilizzate per trattare i predicati della forma . Ad esempio un assioma della teoria degli insiemi è il seguente.
L’assioma significa: “esiste un insieme che non contiene alcun elemento ” ovvero stiamo dicendo che esiste l’insieme vuotoinsieme vuoto che normalmente viene denotato con il simbolo . Scriveremo quindi . Possiamo quindi introdurre un contesto dimostrativo in cui è una costante e l’assioma diventa più semplicemente .
Altri opportuni assiomi della teoria degli insiemi garantiscono l’esistenza dell’unione , intersezione e differenza di due insiemi qualunque e . Tali operazioni tra insiemi possono essere ricondotte alla relazione di appartenenza e possono quindi essere definite come segue.
Assioma 1.7 (operazioni tra insiemi). Se e sono insiemi allora esistono gli insiemi (unione), (intersezione) e (differenza). unione intersezione differenzaFormalmente:
La negazione dell’appartenenza viene usualmente abbreviata con .
Sempre utilizzando la semplice relazione di appartenenza possiamo definire le relazioni di inclusione e uguaglianza tra insiemi: si legge “ è un sottoinsieme di ”, si legge “ è un sovrainsieme di ” e si legge “ è uguale a ”. Queste relazioni sono definite dalle seguenti proprietà:
A parole diremo che è un sottoinsieme di , , se ogni elemento di è anche elemento di . Diremo che e sono uguali, , se e hanno gli stessi elementi. Ovviamente la relazione non è altro che la relazione inversa di cioè risulta se e solo se . Scriveremo anche per indicare la relazione opposta dell’uguaglianza ovvero: . Si noti che è equivalente a .
E’ banale osservare che in quanto . Dunque l’assioma di uguaglianza, , può essere in realtà dimostrato.
La relazione significa che ogni elemento di è anche elemento di e quindi non ci sono elementi di che non stiano in cioè non è più grande di . Come stratagemma mnemonico si osservi che il simbolo è orientato in modo che l’insieme più piccolo stia dal lato più stretto della relazione così come nella disuguaglianza il numero più piccolo sta dal lato più stretto del simbolo . Per dimostrare che la relazione è vera bisognerà prendere un qualunque elemento di e dimostrare che tale elemento è anche elemento di . Per dimostrare che vale l’uguaglianza tipicamente si procede dimostrando separatamente le due inclusioni e .
Risulta molto utile la possibilità di costruire insiemi di insiemi. Per questo motivo la teoria degli insiemi usualmente non fa distinzione tra oggetti e insiemi di oggetti. Nella relazione primitiva anche può essere un insieme. Possiamo allora immaginare che ogni oggetto del nostro universo sia un insieme. In questo modo la relazione di uguaglianza che abbiamo definito sopra risulta ben definita per ogni coppia di oggetti (o insiemi, che è lo stesso) e .
Visto che gli elementi di un insieme sono a loro volta insiemi, è possibile considerare l’unione e, seL’intersezione di una famiglia vuota di insiemi darebbe l’insieme universo, che vedremo non può essere definito. , l’intersezione di tutti gli elementi di . Questo estende il concetto di unione e intersezione anche a famiglie eventualmente infinite.
Assioma 1.8 (unione e intersezione arbitraria). Se è un insieme qualunque esiste l’insieme e se esiste l’insieme con le seguenti proprietà:
Una notazione alternativa è la seguente: Questa notazione mette in evidenza il fatto che l’insieme è l’unione di tutti gli elementi dell’insieme mentre è l’intersezione di tutti gli elementi di . L’insieme viene spesso chiamata una famiglia di insiemi perché i suoi elementi vengono trattati come insiemi più che come oggetti.
Un altro assioma della teoria degli insiemi garantisce che per ogni esiste un insieme il cui unico elemento è .
Facendo l’unione di singoletti possiamo definire (per elencazione) insiemi che contengono un numero finito di oggetti:
Si faccia però attenzione: l’insieme contiene due elementi solamente se , infatti se si potrà facilmente verificare che
Esercizio 1.10. Verificare (1.12) utilizzando le definizioni formali date in precedenza.
Svolgimento. Utilizzando le definizioni di unione, di singoletto e di disgiunzione logica si ha l’equivalenza dei seguenti predicati: e dunque per la definizione di uguaglianza tra insiemi. □
Se è un predicato in una sola variabile vorremmo poter definire l’insieme di tutti gli oggetti che rendono vero il predicato . Sorprendentemente se aggiungessimo questo assioma (chiamato assioma di specificazione ingenua) nella teoria degli insiemi avremmo un paradossoGeorg Cantor (1845–1918), Bertrand Russell (1872–1970) vedi note storiche a pag. 186.
Teorema 1.11 (paradosso di Russell). Non esiste un insieme tale che per ogni si abbia (un tale insieme si potrebbe definire così tramite un assioma di specificazione ingenua: ).
Dimostrazione. Se esistesse avremmo: e questo è in contrasto con il principio di non contraddizione (un predicato e la sua negazione non possono essere entrambi veri). □
Per evitare l’incoerenza è necessario limitare l’assioma di specificazione alla costruzione di sottoinsiemi di insiemi già costruiti.
Assioma 1.12 (specificazione). Se è un qualunque predicato con una variabile libera e se è un insieme, allora esiste l’insieme formato da tutti gli elementi di che soddisfano il predicato :
Se ora proviamo a ripetere il ragionamento di Russell dato un insieme possiamo costruire l’insieme e scopriremmo che non può essere (altrimenti dovrebbe essere assurdo). Ma potrebbe benissimo essere se inoltre . Dunque si deduce che dato qualunque insieme c’è un insieme che non è elemento di : dobbiamo quindi rassegnarci al fatto che non esiste un insieme universo contenente qualunque altro insieme, ma almeno non otteniamo una contraddizioneD’altra parte non possiamo comunque escludere che una contraddizione esista. Infatti Goedel ha dimostrato che non è possibile dimostrare che non ci siano contraddizioni nel sistema assiomatico da noi considerato. .
Per completare la teoria degli insiemi introduciamo anche il concetto di insieme delle partiinsieme delle parti cioè l’insieme di tutti i sottoinsiemi di un insieme dato.
Assioma 1.13 (insieme delle parti). Se è un insieme esiste l’insieme delle parti di che è l’insieme di tutti i sottoinsiemi di :
Con i soli assiomi che abbiamo introdotto fin’ora possiamo costruire un numero arbitrariamente grande di insiemi finiti tramite una costruzione dovuta a Von Neumann. Possiamo definire Esplicitando queste definizioni si osserva che: è un insieme con zero elementi, è un insieme con un elemento (lo zero), è un insieme con due elementi (i due precedenti), è un insieme con tre elementi (i tre precedenti), etc. Procedendo a piacere è possibile definire un numero arbitrariamente grande di insiemi finiti, uno diverso dall’altro.
Questi particolari insiemi esistono certamente e potremo quindi utilizzarli nel seguito per fare esempi di insiemi finiti. E’ anche possibile (ma non necessario) utilizzare questi insiemi per definire i numeri naturali (si veda l’Assioma di infinito 1.47).
Grazie agli assiomi precedenti è possibile definire il prodotto cartesiano di due
insiemi: sarà questo un concetto molto importante nel seguito. Innanzitutto
dobbiamo definire il concetto di coppiacoppia: dati definiamo la coppia con primo
elemento e secondo elemento come un oggetto che ha questa proprietà:Un
modo formale per definire la coppia tramite l’utilizzo di insiemi è dovuto
a Kuratowski: Non è difficile verificare che questa definizione soddisfa la
proprietà (1.15). Così possiamo definire l’insieme prodotto
Stiamo cioè richiedendo
che una coppia venga identificata dai due elementi che la compongono in
cui, però, è importante anche l’ordine in cui vengono elencati (a differenza
dell’insieme , in cui l’ordine degli elementi è irrilevante). Nel seguito useremo anche
la notazione per indicare la coppia e la chiameremo frecciafreccia da in
.
Il prodotto cartesiano di due insiemi e è l’insieme di tutte le coppie il cui primo elemento sta in e il secondo elemento sta in :
Se rappresentiamo gli elementi di come dei punti su una retta orizzontale (asse delle ) e gli elementi di come dei punti su una retta verticale (asse delle ) gli elementi di possono essere rappresentati come i punti del piano che proiettati sull’asse delle vanno in e proiettati sull’asse delle vanno in (si veda la figura 1.1).
Una relazionerelazione tra gli elementi di un insieme e gli elementi di un insieme non è altro che un sottoinsieme di ovvero . Per una relazione si userà la notazione infissa per indicare . Oppure con la notazione delle freccie potremo scrivere per indicare che la freccia è un elemento di . Ad esempio se prendo e considero la relazione il predicato rappresenta l’usuale relazione d’ordine sui tre numeri considerati.
Definizione 1.15 (relazione di equivalenza). Sia una relazione sull’insieme . Diremo che è una relazione di equivalenzarelazione di equivalenza se valgono le seguenti proprietà (tipiche dell’uguaglianza) per ogni :
Se è una relazione di equivalenza diremo che è equivalente a (tramite ) quando . Dato l’insieme di tutti gli elementi che sono equivalenti a si chiama classe di equivalenzaclasse di equivalenza di . Si definisce in questo modo: Se è una relazione di equivalenza su definiamo l’insieme quoziente insieme quoziente come l’insieme di tutte le classi di equivalenza:
Se è una relazione di equivalenza su l’insieme quoziente rappresenta l’insieme degli oggetti di in cui vengono identificati tra loro gli oggetti tra loro equivalenti. Spesso diremo che rappresenta a meno della equivalenza .
Ad esempio se e prendiamo (i numeri dispari) e (i numeri pari) possiamo definire una relazione su mediante la proprietà: La relazione rappresenta la proprietà degli elementi di di avere la stessa “parità”. Si avrà e . Dunque e, in effetti, questo insieme ha due elementi e che è quello che si ottiene identificando i numeri di in base alla proprietà di essere pari o dispari.
L’insieme quoziente è una partizionepartizione di in quanto è formato da insiemi disgiunti la cui unione è tutto . In effetti dare una partizione di è equivalente a dare una relazione di equivalenza.
Definizione 1.16 (relazione d’ordine). Una relazione su un insieme viene detta relazione d’ordinerelazione d’ordine se soddisfa le seguenti proprietà (per ogni ):
Si dice inoltre che la relazione d’ordine è una relazione d’ordine totale ordine totale(o lineare) e si dice che è totalmente ordinato se vale
Definizione 1.17. Sia una relazione d’ordine su un insieme sia e sia .
Diremo che è un maggiorante di se per ogni si ha . maggiorante, minoranteDiremo che è un minorante di se per ogni si ha .
Diremo che è il massimo di e scriveremo , se è un maggiorante di e . massimo, minimo Diremo che è il minimo di e scriveremo , se è un minorante di e .
Diremo che è l’estremo superiore di e scriveremo , se è un maggiorante di e non esistono maggioranti di più piccoli di ( è il minimo dei maggioranti). estremo superiore e inferioreDiremo che è l’estremo inferiore di e scriveremo , se è un minorante di e non esistono minoranti di più grandi di ( è il massimo dei minoranti).
Se l’insieme ha almeno un maggiorante , diremo che limitatoè superiormente limitato. Se ha almeno un minorante diremo che è inferiormente limitato. Se è sia superiormente che inferiormente limitato diremo che è limitato.
Si osservi che il massimo e il minimo di un insieme , se esistono, sono unici. Infatti se e sono entrambi massimi di si deve avere in quanto è massimo, ma anche visto che anche è massimo. Dunque per la proprietà antisimmetrica. Lo stesso vale per il minimo. Visto che l’estremo superiore è il minimo dei maggioranti, e l’estremo inferiore è il massimo dei minoranti, anche estremo superiore ed estremo inferiore, se esistono, sono unici. Se il massimo (o il minimo) esiste, allora coincide con l’estremo superiore (o inferiore). Viceversa vedremo degli esempi in cui l’estremo superiore esiste ma non è elemento dell’insieme (dunque non è un massimo, e il massimo non esiste).
In generale, se è una relazione d’ordine su si definisce la relazione inversa ponendo quando . La proprietà riflessiva identifica gli ordinamenti larghi. Si definisce il corrispondente ordinamento stretto ponendo quando e la relazione inversa ponendo quando .
Esempio 1.18. Sia . Si può verificare che c’è una unica relazione d’ordine totale su per cui si ha , e (scriveremo più brevemente ). Questa relazione è definita dall’insieme di coppie: nel senso che se . La relazione inversa corrisponde a: e le relazioni strette e corrispondono a:
Preso si ha e . I maggioranti di sono e . C’è un unico minorante che è .
Esempio 1.19. Se prendiamo l’insieme e consideriamo la relazione su definita da se otteniamo una relazione d’ordine che non è totale. Infatti se e non è vero né che né che . Si ha e .
Esempio 1.20. L’insieme dei numeri naturali (verrà introdotto nel capitolo 1.5) non ha maggioranti quindi non ha né massimo né estremo superiore. Infatti scelto qualunque numero naturale ce n’è sempre un’altro più grande.
Se all’insieme dei numeri naturali aggiungiamo un elemento , che definiamo essere più grande di ogni numero naturale, otteniamo un insieme totalmente ordinato tale che e in . Ma non è un elemento di quindi non è un massimo di in .
Definizione 1.21 (ordinamento denso). Un ordinamento si dice essere densoordinamento denso o divisibile se tra due punti distinti esiste sempre un punto intermedio: Più in generale se è un insieme totalmente ordinato e si dice che è denso in se dati comunque con esiste tale che .
Esempio 1.22. Un esempio di ordinamento denso è quello dato sull’insieme dei punti di una retta geometrica orientata. Dati due punti distinti e sulla retta, esiste sempre un punto intermedio tra e (ad esempio il punto medio).
Intuitivamente osserviamo che se ho un ordinamento denso su un insieme e l’insieme contiene almeno due punti, allora l’insieme contiene infiniti punti visto che c’è un punto intermedio, e poi un altro punto intermedio tra il punto intermedio e uno dei due punti, e così via...
Definizione 1.23 (ordinamento continuo). Un ordinamento denso su un insieme si dice essere continuoordinamento continuo (o Dedekind-completo) se dati comunque sottoinsiemi non vuoti di tali che per ogni e per ogni risulta (concisamente scriveremo e diremo che e sono separati) allora esiste tale che per ogni e ogni si ha (concisamente scriveremo e diremo che è un elemento di separazione tra e ).
A parole la precedente definizione si esprime dicendo che un insieme ordinato denso è continuo se ogni coppia di sottoinsiemi separati ammette un elemento di separazione. In molti testi questa condizione viene chiamata completezza o, più precisamente, completezza di Dedekind.
Esempio 1.24. Un insieme può essere denso ma non continuo. Se ad esempio prendiamo due punti distinti , su una retta orientata, in modo che sia , poi prendiamo il punto medio tra e , poi il punto medio tra tutti i punti precedenti e così via, intuitivamente otteniamo un insieme di punti che risulta essere denso. Ma se prendiamo l’insieme dei punti di che distano da meno del doppio di quanto distano da , e l’insieme è chiaro che i due insiemi sono non vuoti e separati, ma non esiste un punto di separazione tra e in quanto tale punto dovrebbe avere distanza da mentre tutti i punti di hanno una distanza da che si esprime con una frazione di che ha come denominatore una potenza di .
Eviteremo di usare la definizione di continuità sugli ordinamenti che non sono densi, altrimenti tutti gli insiemi finiti avrebbero un ordinamento continuo e anche insiemi come e risulterebbero continui, cosa che va contro l’intuizione di continuità che abbiamo in mente.
Teorema 1.25 (esistenza del ). Sia un insieme con un ordinamento continuo. Se è un insieme non vuoto e superiormente limitato, allora esiste (l’estremo superiore). Se è un insieme non vuoto e inferiormente limitato allora esiste (l’estremo inferiore).
Se ha minimo allora e se ha massimo allora .
Dimostrazione. Consideriamo l’insieme dei maggioranti di : Preso e essendo che è un maggiorante di , si deve avere . Dunque e sono separati. Inoltre è non vuoto per ipotesi e è non vuoto perché è superiormente limitato e dunque esiste almeno un maggiorante di . Dunque, essendo per ipotesi l’ordinamento continuo, deve esistere che è un maggiorante di e un minorante di . Visto che è un maggiorante di si ha . Ma è anche un minorante di dunque . Essendo il minimo dei maggioranti di si ha, per definizione, .
Dimostrazione analoga vale per l’estremo inferiore.
Per quanto riguarda l’insieme vuoto notiamo che ogni è sia un maggiorante che un minorante dell’insieme vuoto. Dunque l’insieme dei maggioranti e l’insieme dei minoranti coincidono con . Il minimo dei maggioranti è dunque e il massimo dei minoranti è . □
Osserviamo che l’esistenza del degli insiemi non vuoti e superiormente limitati è in effetti una condizione equivalente all’assioma di continuità. Infatti se certamente , se esiste, è elemento di separazione tra e .
La retta geometrica è un esempio di insieme che vorremmo avesse la proprietà di continuità. Questo perché quando si traccia una retta che attraversa una figura geometrica vorremmo avere la certezza che, se la retta ha un punto interno alla figura ed un punto esterno, allora abbia anche un punto di intersezione (per noi questo sarà il teorema degli zeri 2.80). Questi punti di intersezione possono essere visti come punti di separazione tra i punti interni e i punti esterni alla figura: per questo motivo siamo interessati alle proprietà di continuità.
La questione è delicata e non banale. Invece che puntare a formalizzare gli assiomi della geometria di Euclide noi avremo un approccio più algebrico nel senso che andremo a definire la retta geometrica utilizzando l’insieme dei numeri reali. Gran parte di questo capitolo sarà sostanzialmente dedicato a questo scopo. Ma si veda la discussione su Euclide e Hilbert nelle note storiche a fine capitolo.