Metodi Matematici per L'informatica (Logica Matematica) prof. Pietro Cenciarelli

Insiemi e operazioni

Due insiemi si dicono disgiunti se non hanno alcun elemento in comune. Due insiemi si dicono equivalenti se hanno gli stessi elementi. Gli insiemi hanno le seguenti operazioni:

Operazioni sugli insiemi

• Unione: Gli elementi che appartengono o al primo insieme o al secondo (or logico).
• Intersezione: Gli elementi che appartengono sia al primo che al secondo insieme (and logico).
• Differenza (A/B): Gli elementi che appartengono ad A ma che non appartengono a B.
• Complemento: Tutti gli elementi che non appartengono all’insieme di partenza.
• Prodotto cartesiano: L’insieme di tutte le possibili combinazioni di coppie ordinate (a,b) tra i due insiemi.

Si chiama insieme delle parti l’insieme di tutti i sottoinsiemi (compreso l’insieme vuoto e lo stesso insieme di partenza) di un insieme di partenza. Viene indicato con P(A) dove A è l’insieme di partenza.

Chiusura degli insiemi

Un insieme B è detto chiusura di un insieme A rispetto ad una proprietà P quando sono soddisfatte le seguenti condizioni:

• B gode della proprietà P, ovvero P(B).
• A è un sottoinsieme di B.
• Per ogni insieme C, se P(C) ed A è un sottoinsieme di C, allora B è un sottoinsieme di C.

La chiusura di un insieme rispetto ad una proprietà, se esiste, è unica.

Relazioni e proprietà

Si dice relazione tra due insiemi A e B un sottoinsieme del prodotto cartesiano AxB. Una relazione inversa si ottiene invertendo l’ordine delle coppie della relazione di partenza. (b,a).

Proprietà delle relazioni

• Riflessiva: quando un insieme è in relazione con sé stesso (ad esempio la relazione di uguaglianza, in quanto ogni cosa è uguale a sé stessa).
• Antiriflessiva: quando nessun elemento dell’insieme è in relazione con sé stesso (ad esempio la relazione di maggiore/minore, in quanto nessun numero è maggiore o minore di sé stesso).
• Simmetrica: quando, per ogni coppia di elementi a e b di un insieme, a in relazione con b implica b in relazione con a.
• Antisimmetrica: quando il contemporaneo essere a in relazione con b e b in relazione con a, implica che a = b.
• Transitiva: quando, per ogni terna di elementi a, b e c, se a è in relazione con b e b è in relazione con c, allora a è in relazione con c.

Una relazione si dice relazione di equivalenza se gode delle proprietà riflessiva, simmetrica e transitiva. Si dice classe di equivalenza di x rispetto alla relazione R un sottoinsieme di A che contiene tutti e soli gli elementi equivalenti ad un qualche elemento x appartenente ad A. In una classe di equivalenza [x] quindi tutti gli elementi sono equivalenti tra loro.

Si dice insieme quoziente è l’insieme degli elementi contenuti in ogni singola classe di equivalenza.

Una relazione si dice relazione d’ordine se gode delle proprietà riflessiva, antisimmetrica e transitiva. Una relazione si dice relazione d’ordine stretto se gode delle proprietà antiriflessiva e transitiva. Una relazione si dice relazione di preordine se gode delle proprietà riflessiva e transitiva.

Numeri rappresentati tramite insiemi

Il matematico John von Neumann introdusse un metodo di rappresentazione per i numeri naturali tramite gli insiemi.

Ponendo { } = zero, l’uno può essere costruito formando l’insieme dell’unica cosa che ho:

• 1: { { } } ovvero {zero}
• 2: { { } { { } } } ovvero {zero uno}

E così via… Questo è un modo per formare nuovi numeri partendo da numeri che già abbiamo.

Numeri transfiniti

Il numero che contiene tutti i numeri naturali viene chiamato ω. Esso si differenzia dagli altri insiemi dal fatto che presenta infiniti sottoinsiemi. {uno, due, tre, quattro…, mille…}

Da omega possiamo poi creare il numero ω+1 e così via. {uno, due, tre, quattro…, mille…, ω}. Questi numeri (ω e successivi) vengono chiamati numeri transfiniti, in quanto superano l’insieme dei numeri finiti. Possiamo continuare ad iterare il ragionamento fino ad arrivare a ω+ω, per poi continuare ad iterare il ragionamento fino a ω+ω+ω e così via.

Mentre per i numeri finiti sappiamo quale numero è più grande (4 è più grande di 4+4), per i numeri transfiniti la faccenda diventa più complicata. Non potendo effettivamente contare ω, per rispondere alla domanda se sia più grande ω o ω+ω devo prima prendere in considerazione il concetto di cardinalità.

Cardinalità

Due insiemi A e B si dicono equipotenti se sono in corrispondenza biunivoca tra loro. La relazione di equipotenza è una relazione di equivalenza. La cardinalità di un insieme A è la classe di equipotenza di A, quindi essa non è un numero ma un insieme.

La cardinalità di A è minore della cardinalità di B se esiste una funzione iniettiva da A in B. Se la |A| <= |B| e |B| <= |A|, allora esiste una biiezione tra A e B e quindi. |A| = |B|. Questo vuol dire che due insiemi finiti sono equipotenti se hanno lo stesso numero di elementi all’interno.

Il problema si pone nel momento in cui si trattano insiemi non finiti. Provando a mettere in corrispondenza due insiemi infiniti, ovvero ω ed ω+1, si trova una corrispondenza biunivoca. Questo vuol dire che ω è equipotente a ω+1.

Grazie alla definizione formale di Dedekind, possiamo affermare che un insieme si definisce infinito se è equipotente ad un suo sottoinsieme proprio, se ciò non accade l’insieme è finito.

Se un insieme è equipotente all’insieme N dei numeri naturali si dice che ha la potenza del numerabile. Si può verificare come l’insieme N sia infinto in quanto un suo sottoinsieme, ad esempio l’insieme dei numeri pari, è equipotente ad N. Questo ragionamento va contro il ragionamento intuitivo.

Essendoci infiniti numeri razionali tra due numeri naturali, anche l’insieme Q dei numeri razionali ha la potenza del numerabile.

Se un insieme è equipotente all’insieme R dei numeri reali si dice che ha la potenza del continuo. L’insieme R è quindi di un infinito maggiore rispetto all’insieme N. L’insieme delle parti di N è però equipotente ad R.