Teoria degli insiemi: una presentazione essenziale

Home » Teoria degli insiemi: una presentazione essenziale

Teoria degli insiemi: una presentazione essenziale

Questa dispensa è una risorsa educativa sulla teoria degli insiemi. Essa guida il lettore che si avvicina a questa affascinante materia tra le seguenti domande:

Cos’è un insieme e come si rappresenta?
Cosa sono i diagrammi di Eulero-Venn?
Cos’è un sottoinsieme?
Quali operazioni si possono effettuare con gli insiemi e quali sono le loro proprietà?
Cosa sono le relazioni? E cos’è una relazione d’ordine?
In cosa consiste il paradosso di Russel e come ha messo in crisi i fondamenti della matematica?

Se desideri un’introduzione concisa e chiara su questa disciplina che apre le porte a tutta la Matematica, inizia pure la lettura!

Scarica la teoria

Ottieni la dispensa teorica sulla teoria degli insiemi.

Autori e revisori

Mostra autori e revisori.

Autori: Daniele Fakhoury.

Revisori: Valerio Brunetti.

Introduzione

Leggi...

La teoria degli insiemi è in sostanza, insieme al concetto di funzione, il fondamento su cui si basa tutta la matematica moderna. La teoria ingenua degli insiemi si distingue dalla teoria assiomatica degli insiemi per il fatto che la prima considera gli insiemi come collezioni di oggetti, chiamati elementi o membri dell’insieme, mentre la seconda considera insiemi quelli che soddisfano determinati assiomi. La teoria ingenua degli insiemi venne creata alla fine del XIX secolo da Georg Cantor per permettere ai matematici di lavorare in modo consistente con gli insiemi infiniti. Famosa è la frase di uno dei più importanti matematici della storia, Hilbert, che afferma:

$\text{``Nessuno ci scaccerà dal paradiso che Cantor ha creato per noi."}$

Studiare la teoria (ingenua) degli insiemi porta in maniera naturale a confrontarsi con problemi di tipo filosofico legato agli aspetti più fondazionali della matematica moderna. Lo scopo di questa dispensa non è certo quella di entrare nel cuore di queste questioni, ma presentare una trattazione semplice di questa teoria mostrando solo vagamente i suoi aspetti più critici che hanno portato ad una più profonda formalizzazione tramite la teoria assiomatica di Zermelo e di Fraenkel. In fondo, la teoria assiomatica degli insiemi ha poca influenza sulla matematica ordinaria ma solo sui suoi aspetti più filosofici. Quindi è utile studiare gli insiemi nell’originale senso ingenuo allo scopo di sviluppare abilità nel lavorare con essi. Inoltre, una buona padronanza della teoria ingenua degli insiemi è necessaria per la comprensione della motivazione per la teoria assiomatica.

Insiemi e notazioni

Leggi...

In teoria ingenua degli insiemi, i concetti di insieme e di elemento sono presentati in maniera informale come oggetti primitivi: un insieme non è altro che una collezione (o famiglia) di oggetti che vengono detti elementi dell’insieme. Di solito gli insiemi vengono indicati con lettere maiuscole: $A, B, C \dots$ mentre gli elementi dell’insieme con lettere minuscole $x, e, a, b, \dots$ . Se $x$ è un elemento dell’insieme $A$ si scriverà $x\in A$ e si legge “ $x$ appartiene (o appartenente) ad $A$ “. Se non ci sono elementi $x\in A$ , diremo che l’insieme $A$ è l’insieme vuoto e scriveremo $A= \emptyset$ . Osserviamo che la nostra definizione presuppone la conoscenza intuitiva del concetto di uguaglianza tra elementi di un insieme $x,y\in A$ , in simboli $x=y$ . Osserviamo inoltre che la collezione di elementi di un insieme non è “ordinata”, ovvero se immaginiamo un insieme come un sacchetto, gli elementi dell’insieme sono come delle biglie gettate alla rinfusa nel sacchetto. Per rappresentare un insieme può essere conveniente elencare esplicitamente i suoi elementi tra parantesi graffe; in questo caso parleremo di rappresentazione per elencazione . Per esempio

$A = \{ 3, \mbox{cavallo}, 7, \mbox{John} \} = \{ 7, \mbox{John}, 3, \mbox{cavallo} \},$

significa che l’insieme $A$ è composto dai seguenti elementi: i numeri $3$ e $7$ , la parola cavallo e il nome John.

Osservazione. La rappresentazione di un insieme per elencazione è da intendersi priva di ripetizioni, nel senso che due elementi uguali che si ripetono nell’elencazione possono essere contati una sola volta. Ad esempio

$\{ 3, \mbox{cavallo}, 7, \mbox{John} \} =\{ 3, \mbox{cavallo}, 3, 7, \mbox{John} , \mbox{cavallo} \}.$

Il concetto di insieme con elementi ripetuti, detto multinsieme, esula dai nostri scopi.

Definizione 1. Un insieme finito è un insieme che ha un numero finito di elementi e tale numero è detto la cardinalità dell’insieme. Un insieme che non ha un numero finito di elementi si dice avere cardinalità infinita.

Per esempio dato $A = \{ 3, \mbox{cavallo}, 7, \mbox{John} \}$ , la cardinalità di $A$ è $4$ . Per indicare la cardinalità di un insieme $A$ si usa il simbolo $|A|$ oppure ${\#}A$ e dunque in questo caso avremo

$|A| = \# A = 4.$

Se invece un elemento $x$ non appartiene ad un dato insieme $A$ si scriverà $x\not\in A$ e si leggerà “ $x$ non appartiene ad $A$ “. Per esempio, se $A$ è l’insieme di prima, $A = \{ 3, \mbox{cavallo}, 7, \mbox{John} \}$ , allora $5 \not\in A$ . Chiaramente non sempre è possibile elencare tutti gli elementi di un insieme o perchè sono troppi e ci vorrebbe molto tempo oppure perchè sono infiniti e non è proprio possibile elencarli tutti! A volte utilizzeremo i puntini per indicare che ci sono altri elementi che non abbiamo scritto ma che risultano chiari dal contesto. Pensiamo ad esempio all’insieme di tutti i numeri naturali $0, 1, 2, 3, \dots$ che viene in genere indicato appunto come

$\mathbb{N} = \{0,1,2, \dots \}.$

Pensiamo ad esempio a l’insieme di tutti i granelli di sabbia della Terra. Di sicuro ci sono un numero finito di granelli di sabbia ma è assurdo pensare di scrivere l’insieme di tutti i granelli di sabbia esplicitamente. Questi insiemi non hanno meno dignità degli altri e in realtà possono essere rappresentati in maniera intuitiva attraverso la seguente dichiarazione

$A = \{x \quad \mbox{tale che} \quad x \mbox{ è un granello di sabbia della Terra} \}.$

In altri termini abbiamo espresso tale insieme tramite un predicato (cioè una proposizione, una frase) che descrive univocamente i suoi elementi; in questo caso parleremo di rappresentazione per caratteristica. Come notazione, invece della scritta “tale che” si usano spesso l’abbreviazione “t.c.” oppure i due punti “:” o anche una barretta verticale “|”. In generale, per mantenere il rigore logico, si fissa un insieme $U$ detto “universo”, una proposizione $P$ su $U$ e si definisce l’insieme $A$ composto da tutti gli elementi di $U$ che soddisfano la proposizione $P$ come segue

$A = \{ x\in U : P(x) \mbox{ è verificata}\}= \{ x\in U : P(x) \}.$

Ad esempio per indicare l’insieme dei numeri naturali dispari scriveremo

$D=\{n \in \mathbb{N} : n \mbox{ è dispari}\}.$

Notiamo come quest’ultimo insieme possa essere descritto anche come

$D=\{ 2n + 1 : n \in \mathbb{N}\}$

cioè gli elementi della forma $2n + 1$ dove $n$ è un numero naturale. Infatti tutti i numeri naturali dispari possono essere descritti come il successivo di un multiplo naturale di $2$ .

Richiami di logica

Per concludere con questo paragrafo, elenchiamo alcuni dei principali simboli utilizzati nelle proposizioni logiche, che hanno lo scopo di semplificare la notazione e snellire il processo deduttivo. Forniamo solo un piccolo richiamo a tale importante argomento e rimandiamo alla dispensa di logica per una trattazione esaustiva. Essi costituiscono nella pratica dei veri e propri strumenti che permettono di costruire un insieme a partire da diversi predicati. Nello specifico abbiamo i quantificatori

il quantificatore esistenziale $\exists$ che è l’abbreviazione della parola “esiste”
la sua controparte con il punto esclamativo $\exists!$ che sta per “esiste ed è unico”
la sua negazione $\nexists$ che sta per “non esiste”
il quantificatore universale $\forall$ che abbrevia la locuzione “per ogni” o “qualunque”

e i connettivi logici

la congiunzione logica “e”: $\wedge$ che sta per “e (contemporaneamente)”
la disgiunzione inclusiva $\vee$ che abbrevia la locuzione “o” nel senso di “oppure”
l’implicazione $\Rightarrow$ che è l’abbreviazione della parola “implica”
la co-implicazione $\Leftrightarrow$ che sta per “se e soltanto se”

Per esempio la proposizione

$\forall\, x \in A \; \exists\,!\,\, y \in B\, :\, y = 2 x,$

è un modo compatto (e astruso) per dire che, per qualunque elemento $x$ dell’insieme $A$ esiste un unico elemento $y$ dell’insieme $B$ che è il doppio di $x$ . (evidentemente $A$ e $B$ sono degli insiemi di numeri). Oppure, per esempio, date le proposizioni

$p(x)$ : “ $x$ supera l’esame di Analisi 1″
$q(x)$ : “ $x$ riceve un regalo”

la proposizione $p(x) \Rightarrow q(x)$ è la proposizione “se $x$ supera l’esame di Analisi 1 allora $x$ riceve un regalo”. Mentre la proposizione $p(x) \Leftrightarrow q(x)$ significa che $x$ riceverà il regalo se e soltanto se passerà l’esame di Analisi 1.

Diagrammi di Eulero-Venn

Leggi...

Per visualizzare gli insiemi spesso si usano quelli che vengono detti diagrammi di Eulero-Venn. Questi diagrammi raffigurano gli elementi come punti nel piano, e gli insiemi come regioni racchiuse da curve chiuse. Un diagramma di Eulero-Venn è composto da molteplici curve chiuse (di solito cerchi, o rettangoli, se le curve sono al massimo tre) che si sovrappongono, come mostrato in figura 1. I punti all’interno di una curva etichettata $A$ rappresentano elementi dell’insieme $A$ , mentre i punti all’esterno rappresentano gli elementi che non fanno parte di $A$ . Così, per esempio, l’insieme di tutti gli elementi che sono membri di entrambi gli insiemi $A$ e $B$ è visivamente rappresentato dall’area dove si sovrappongono le regioni $A$ e $B$ . Questi diagrammi sono usati spesso per insegnare teoria degli insiemi elementare, oltre che per illustrare e visualizzare semplici relazioni tra insiemi in probabilità, logica, statistica, linguistica e informatica. Per esempio dati i tre insiemi

$A=\{1,\,2,\,5\}, \qquad B=\{1,\,6\}, \qquad C=\{4,\,7\},$

otteniamo il seguente diagramma

Rendered by QuickLaTeX.com

Figura 1: diagramma di Eulero-Venn.

Sottoinsiemi

Leggi...

Prima di iniziare con le operazioni tra insiemi introduciamo un concetto che ci sarà utile per il proseguimento: il concetto di sottoinsieme.

Definizione 2. Dati due insiemi $A$ e $B$ diremo che $A$ è un sottoinsieme di $B$ (o è contenuto in $B$ ) se ogni elemento di $A$ è anche un elemento che appartiene a $B$ . Se $A$ è contenuto in $B$ scriveremo

$A \subseteq B.$

Ovvero, diremo in formule

$A \subseteq B \quad \iff \quad x \in B \; \forall x \in A$

o equivalentemente

$A \subseteq B \iff \Big( x \in A \implies x \in B\Big).$

Osservazione. Dati due insiemi $A$ e $B$

$\begin{equation*} A=B\quad \Leftrightarrow \quad A\subseteq B\,\wedge\, B\subseteq A. \end{equation*}$

Se invece $A$ non è un sottoinsieme di $B$ , $A \not\subseteq B$

$\begin{equation*} \exists a\in A \,:\, a\notin B, \end{equation*}$

ovvero esiste un elemento di $A$ che non appartiene a $B$ . Infine se $A$ è un sottoinsieme di $B$ e sappiamo già che non sono uguali, diremo che $A$ è un sottoinsieme proprio e scriveremo

$A \subset B.$

Per esempio se

$B = \{ x: x \in \text{astuccio} \},$

$A = \{ x \in B : x \; \text{è una penna} \}$

allora chiaramente $A$ è un sottoinsieme di $B$ ovvero $A \subseteq B$ . Se inoltre, nel nostro astuccio non ci sono solo penne ma anche gomme e matite, allora $A$ è un sottoinsieme proprio di $B$ ovvero $A \subset B$ . Per finire notiamo che in alcuni libri si usa il simbolo $\subset$ per indicare $\subseteq$ , ma in genere il significato di questi simboli è chiarificato in una sezione preliminare del testo stesso. Se $A$ è un sottoinsieme di $B$ , utilizzando un diagramma di Eulero-Venn possiamo mostrare graficamente questa relazione come in figura 2.

Rendered by QuickLaTeX.com

Figura 2: diagramma di Eulero-Venn per un sottoinsieme.

Se $A$ è un insieme finito è possibile elencare tutti i suoi possibili sottoinsiemi. In particolare risulta vero il seguente teorema la cui dimostrazione, basata sul principio di induzione è riportata come approfondimento alla fine di queste pagine.

Teorema 1. Dato un insieme $A$ con $n$ elementi (ovvero, ricordando la definizione di cardinalità, $|A| = n$ ), la cardinalità dei suoi sottoinsiemi è $2^n$ .

Per la dimostrazione del teorema 1 cliccare qui. Per esempio, dato l’insieme $A = \{ 3, 7 \}$ , listiamo di seguito tutti i suoi sottoinsiemi, partendo dall’insieme vuoto $\emptyset$ e l’insieme stesso che sono sottoinsiemi di qualunque insieme

$A_1 = \emptyset$

$A_2 = \{ 3, 7 \}=A$

$A_3 = \{3\}$

$A_4 = \{ 7\}.$

Dato un’insieme $A$ , l’insieme di tutti i suoi sottoinsiemi si chiama insieme delle parti e si indica come ${P}(A)$ o anche $2^A$ e dal Teorema 1 evinciamo che

$\# P(A) = \# 2^A = 2^{\#A},$

che motiva la notazione $2^A$ per indicare l’insieme delle parti di $A$ . Nell’esempio precedente con $A = \{ 3, 7 \}$ , abbiamo che l’insieme delle parti è

$2^A = \{ A_1, A_2, A_3, A_4 \}.$

Notiamo esplicitamente che gli elementi dell’insieme delle parti $A$ sono a loro volta altri insiemi: tutti i possibili sottoinsiemi di $A$ !

Operazioni elementari tra insiemi

Leggi...

Da ora in avanti consideriamo due insiemi $A$ e $B$ entrambi contenuti in un insieme $U$ detto insieme universo tale che

$A \subseteq U, \quad B \subseteq U.$

Intersezione

Leggi...

Definizione 3. L’intersezione dei due insiemi $A$ e $B$ è un nuovo insieme indicato come $A \cap B$ formato da tutti gli elementi che appartengono contemporaneamente ad $A$ e a $B$ , in formule:

$A \cap B = \{x \in U: x \in A \wedge x \in B \}.$

L’intersezione può essere vista come un’operazione binaria tra insiemi: dati due insiemi $A$ e $B$ , possiamo formare un terzo insieme $C= A\cap B$ .

Osservazione. Se

$\begin{gathered} A=\{x\in U\,:\, p(x) \}\\ B=\{x\in U\,:\,q(x)\} \\ A\cap B= \{x\in U\,:\, p(x)\wedge q(x) \} \end{gathered}$

ovvero $A\cap B$ è l’insieme formato da tutti gli elementi che soddisfano entrambe le proprietà $p$ e $q$ .

Per esempio, se

$A=\{1,\,2,\,5\}, \qquad B=\{1,\,6\}$

allora l’insieme

$A \cap B = \{ 1 \}.$

Utilizzando un diagramma di Eulero-Venn, l’intersezione rappresenta l’area in comune tra il cerchio che rappresenta $A$ e il cerchio che rappresenta $B$ come illustrato dalla figura 3.

insiemi diagrammi Eulero-Venn

Figura 3: diagramma di Eulero-Venn per l’intersezione.

Notiamo infine che se $A$ e $B$ non hanno elementi in comune allora $A\cap B = \emptyset$ e i due insiemi $A$ e $B$ si dicono disgiunti. Inoltre si ha che $A \subseteq B \Leftrightarrow A \cap B = A$ , ovvero $A$ è un sottoinsieme di $B$ se e solo se l’intersezione tra $A$ e $B$ è l’insieme $A$ stesso.

La seguente proposizione esprime le proprietà dell’intersezione.

Proposizione 5. Valgono le seguenti proprietà:

Proprietà Commutativa $A\cap B= B\cap A$ ;
Proprietà Associativa $(A\cap B)\cap C= A\cap (B\cap C)$ .

Dimostrazione. La proprietà commutativa segue dalla definizione. Proviamo la proprietà associativa dimostrando l’uguaglianza tra i due insiemi; sia $x\in (A\cap B)\cap C$ allora per definizione

$\begin{equation*} x\in A\cap B\,\wedge\, x\in C\quad \Leftrightarrow \quad x\in A\,\wedge\, x\in B\,\wedge\, x\in C\quad \Leftrightarrow \quad x\in A\,\wedge\, x\in B\cap C, \end{equation*}$

ovvero $x\in A\cap (B\cap C)$ . Osserviamo che l’implicazione $\Rightarrow$ dimostra l’inclusione $(A\cap B)\cap C\subseteq A\cap (B\cap C)$ , mentre $\Leftarrow$ dimostra $A\cap (B\cap C)\subseteq(A\cap B)\cap C$ ; quindi il se e solo se dimostra la doppia inclusione tra i due insiemi e quindi l’uguaglianza.

Unione

Leggi...

Definizione 4. L’unione dei due insiemi $A$ e $B$ è un nuovo insieme indicato come $A \cup B$ formato da tutti gli elementi che appartengono (almeno) ad $A$ o a $B$ , in formule:

$A \cup B = \{x \in U: x \in A \vee x \in B \}.$

L’unione può essere vista come un’operazione binaria tra insiemi: dati due insiemi $A$ e $B$ , possiamo formare un terzo insieme $C= A\cup B$ .

Osservazione. Se

$\begin{gathered} A=\{x\in U\,:\, p(x) \}\qquad \text{ e } \qquad B=\{x\in U\,:\,q(x)\}, \\\\ A\cup B= \{x\in U\,:\, p(x)\vee q(x) \}, \end{gathered}$

ovvero $A\cup B$ è formato da tutti gli elementi che soddisfano la proprietà $p$ oppure la proprietà $q$ .

Per esempio, se

$A=\{1,\,2,\,5\}, \qquad B=\{1,\,6\},$

allora l’insieme

$A \cup B = \{ 1 ,2,5,6\}.$

Utilizzando un diagramma di Eulero-Venn, l’unione è rappresentata come tutta l’area del cerchio che rappresenta $A$ e il cerchio che rappresenta $B$ come mostrato in figura 4.

insiemi unione

Figura 4: diagramma di Eulero-Venn per l’unione.

La seguente proposizione esprime le proprietà dell’unione.

Proposizione 6. Valgono le seguenti proprietà:

Proprietà Commutativa $A\cup B= B\cup A$ ;
Proprietà Associativa $(A\cup B)\cup C= A\cup (B\cup C)$ ;
Proprietà Distributiva
- a) $A\cap (B\cup C)= (A\cap B)\cup (A\cap C)$ ;
- b) $A\cup (B\cap C)= (A\cup B)\cap (A\cup C)$ .

Dimostrazione. La proprietà commutativa segue dalla definizione, mentre la proprietà associativa si dimostra analogamente a quella dell’unione del paragrafo precedente. Proviamo la proprietà distributiva parte a) dimostrando l’uguaglianza tra i due insiemi; sia $x\in A\cap (B\cup C)$ allora per definizione

$\begin{equation*} x\in A\, \wedge\, x\in (B\cup C)\quad\Leftrightarrow \quad x\in A\,\wedge\, (x\in B\,\vee\,x\in C)\quad \Leftrightarrow \quad (x\in A\, \wedge\, x\in B) \,\vee\, (x\in A\, \wedge\, x\in C), \end{equation*}$

ovvero $x\in (A\cap B)\cup (A\cap C)$ . Osserviamo nuovamente che l’implicazione $\Rightarrow$ dimostra l’inclusione $A\cap (B\cup C)\subseteq (A\cap B)\cup (A\cap C)$ , mentre $\Leftarrow$ dimostra $(A\cap B)\cup A\cap (B\cup C)$ ; quindi il se e solo se dimostra la doppia inclusione tra i due insiemi e quindi l’uguaglianza.

Differenza e complementare

Leggi...

Definizione 5. La differenza di $A$ da $B$ è l’insieme indicato $B \setminus A$ formato da tutti gli elementi di $B$ che non appertengono ad $A$ ovvero

$B \setminus A = \{ x \in U : x\in B \wedge x \not\in A\}$

Per esempio, se

$A=\{1,\,2,\,5\}, \qquad B=\{1,\,6\},$

allora l’insieme

$B \setminus A = \{ 6 \}.$

Questo insieme rappresentato come diagramma di Eulero-Venn in figura 5 è anche chiamato il complementare di $A$ in $B$ :

insiemi complementare

Figura 5: diagramma di Eulero-Venn per il complemento.

Più in generale, quando è chiaro chi è l’insieme universo $U$ si dice complementare di $A$ il complementare di $A$ in $U$ ovvero $U \setminus A$ , si indica $A^C$ . La figura 6 ne mostra una rappresentazione in termini di diagramma di Eulero-Venn

insiemi complementare

Figura 6: diagramma di Eulero-Venn per il complemento.

Valgono le seguenti proprietà dette formule di De Morgan:

Proposizione 7. Valgono le seguenti:

$(A\cap B)^{C}=A^{C}\cup B^{C}$ ;
$(A\cup B)^{C}=A^{C}\cap B^{C}$ .

Dimostrazione. Dimostriamo la prima uguaglianza; sia $x\in (A\cap B)^{C}$ allora

$\begin{equation*} x\notin A\cap B, \end{equation*}$

ovvero $x$ non può essere un elemento comune di A e di B; allora $x$ deve appartenere al complementare di A o al complementare di B.

$\begin{equation*} x\in A^C\vee x\in B^C\quad\Leftrightarrow\quad x\in A^{C}\cup B^{C}. \end{equation*}$

In modo analogo possiamo dimostrare la seconda legge di De Morgan.

Prodotto cartesiano

Leggi...

Introduciamo ora il prodotto cartesiano, un insieme particolarmente interessante che si costruisce a partire da due insiemi $A$ e $B$ . La dimostrazione della sua esistenza viene rimandata ai testi di logica matematica, qui ci limitiamo a darne una definizione operativa.

Il concetto di prodotto cartesiano è basato su quello di coppia ordinata $(a,b)$ di elementi. Rimandando all’appendice per una sua definizione formale, in questa sede è sufficiente ricordare che il simbolo $(a,b)$ denota appunto una coppia costituita da due elementi, in cui l’ordine è importante: in altri termini, la coppia $(a,b)$ è diversa dalla coppia ordinata $(b,a)$ . Ciò differisce dalla notazione per gli insiemi, in cui l’ordine con cui si elencano gli elementi non è rilevante: ad esempio l’insieme $\{a,b\}$ è lo stesso insieme di $\{b,a\}$ .

Analogamente si possono definire le $n$ -uple ordinate, $(a_1,\ldots,a_n)$ , che possiamo vedere come insiemi di $n$ elementi in cui conta l’ordine.

Possiamo ora dare la definizione di prodotto cartesiano.

Definizione 6. Il prodotto cartesiano di due insiemi $A$ e $B$ è l’insieme formato da tutte le possibili coppie ordinate di elementi di $A$ e $B$ e si indica come $A \times B$ . In formule

$A \times B = \{ (a,b): a \in A, b \in B \}.$

Il prodotto cartesiano può essere visto come un’operazione binaria tra insiemi: dati due insiemi $A$ e $B$ , possiamo formare un terzo insieme $C= A\times B$ . Segue subito dalla definizione che questa operazione non è commutativa, ovvero in generale $A \times B \neq B\times A$ se $A \neq B$ , in quanto la definizione distingue l’ordine in cui compaiono $A$ e $B$ .

Per esempio, se

$A=\{1,\,2,\,5\}, \qquad B=\{1,\,6\}$

allora l’insieme

$A \times B = \{ (1,1), (1,6), (2,1), (2,6),(5,1), (5,6) \}.$

È possibile rappresentare il prodotto tra due insiemi in un diagramma cartesiano come mostra la figura 7.

Rendered by QuickLaTeX.com

Figura 7: rappresentazione del prodotto cartesiano mediante il diagramma cartesiano.

Chiaramente, per costruzione avremo che la cardinalità di $A \times B$ è uguale alla cardinalità di $A$ moltiplicata per la cardinalità di $B$ , in formule

$\#(A\times B)= \#A\cdot \#B.$

È naturale estendere l’operazione di prodotto cartesiano a un’operazione $n$ -aria, ovvero dato un numero $n>1$ di insiemi $A_1, \dots A_n$ , possiamo formare il loro prodotto cartesiano $A_1\times \dots \times A_n$ definito come

$A_1 \times \ldots \times A_n = \{ (a_1,\ldots,a_n) \colon a_1 \in A_1, \, \ldots, a_n \in A_n \}.$

Segnaliamo che, dato un insieme $A$ , è possibile considerare il prodotto cartesiano di un insieme $A$ con se stesso $n$ volte ottenendo l’insime

$A^n = \underbrace{ A \times A \times \dots \times A}_{n \text{ volte}},$

composto di $n$ -uple di elementi di $A$ .

Relazioni

Leggi...

Il concetto di relazione è tra i più importanti in matematica e comprende al suo interno il concetto stesso di funzione. Intuitivamente, una relazione tra un insieme $A$ e un insieme $B$ è una regola che lega un qualche elemento $x\in A$ ad un secondo elemento $y\in B$ secondo un certo principio.

La seguente definizione formalizza il concetto di relazione su un insieme.

Definizione 7. Una relazione $\mathcal{R}$ tra $A$ e $B$ è un sottoinsieme del prodotto cartesiano

$\mathcal{R} \subseteq A\times B.$

Per dare un senso pratico alla definizione osserviamo che possiamo interpretare un elemento della relazione $(x,y) \in \mathcal{R}$ come l’affermazione “ $x$ è in relazione con $y$ “, in simboli $x\mathcal{R}y$ .

Se la regola associa ad ogni elemento di $A$ qualche elemento di $B$ e se tale elemento è univocamente determinato, la relazione prende il nome di funzione tra $A$ e $B$ .

Definizione 8. Dati due insiemi $A$ e $B$ , una funzione $f: A \to B$ è una relazione $f \subset A\times B$ tale che $\forall x \in A \; \exists ! y \in B$ tale che $(x,y)\in f$ (in simboli $x f y$ , oppure più comunemente $y=f(x)$ ).

Per approfondimenti sulle funzioni rimandiamo a [ 4, 1, 2 ].

Un caso particolare di relazione è quando $A=B$ .

Definizione 9. Una relazione binaria $\mathcal{R}$ su un insieme $A$ è un sottoinsieme di $A\times A$ :

$\mathcal{R} \subseteq A\times A.$

Esempio 1.

$\mathcal{R}=\emptyset$ . In questo caso non c’è alcuna relazione e gli elementi di $A$ sono “sconnessi”;
$\mathcal{R}=A\times A$ . Anche questo è un caso degenere in cui la relazione non esprime nulla di significativo, in quanto tutto è nella relazione.
$\mathcal{R}=\Delta$ , dove $\Delta=\{ (x,x): x\in A \}$ è la diagonale di $A$ . Questa è la relazione di uguaglianza tra elementi, in simboli $x\mathcal{R}y \Leftrightarrow x=y$ . Osserviamo che quest’ultima relazione è una funzione $id_A:A \to A$ , detta identità di $A$ .

Relazioni d’ordine

Leggi...

Una particolare famiglia di relazioni su un insieme $A$ sono le cosiddette relazioni d’ordine su $A$ .

Definizione 10. Dato un insieme non vuoto $A$ una relazione binaria $\mathcal{R}$ è una relazione d’ordine (o relazione d’ordine parziale) se soddisfa le seguenti proprietà:

Proprietà riflessiva: $a\mathcal{R}a\qquad\forall a\in A;$
Proprietà antisimmetrica: Se $a\mathcal{R}b\quad\text{ e }\quad b\mathcal{R}a\Rightarrow a=b \qquad\forall a, b\in A;$
Proprietà transitiva: Se $a\mathcal{R}b\quad\text{ e }\quad b\mathcal{R}c\Rightarrow a\mathcal{R}c \qquad\forall a, b, c\in A.$

Scriviamo $(A,\mathcal{R})$ per indicare l’insieme $A$ dotato della relazione d’ordine $\mathcal{R}$ .

Definizione 11. Una relazione $\mathcal{R}$ definita su un insieme non vuoto $A$ è una relazione d’ordine totale se è una relazione d’ordine e se $\forall \,(a,b)\in A\times A$ risulta che $a\mathcal{R}b$ oppure $b\mathcal{R}a$ . In questo caso l’insieme $A$ si dice totalmente ordinato da $\mathcal{R}$ .

L’aggettivo parziale nella definizione di relazione d’ordine sta a significare che non necessariamente tutte le coppie $(a,b)$ di elementi dell’insieme $A$ sono tra loro confrontabili, come ci mostra il seguente esempio.

Esempio 2. Sia $X$ un insieme non vuoto. Nell’insieme $\mathcal{P}(X)$ (l’insieme delle parti di $X$ , i cui elementi sono i sottoinsiemi di $X$ ) è possibile definire la relazione d’ordine

$\begin{equation*} A\mathcal{R} B\Leftrightarrow A\subseteq B. \end{equation*}$

Si controlla facilmente che è una relazione d’ordine parziale; consideriamo ad esempio l’insieme $X=\{a, b\}$ allora $\mathcal{P}(X)=\{\emptyset, \{a\},\{b\}, A\}$ . Ovviamente i due singleton non sono confrontabili ovvero

$\{a\}\cancel{\mathcal{R}} \{b\}\text{ e }\{b\}\cancel{\mathcal{R}} \{a\}.$

Solitamente le relazioni d’ordine vengono indicate con i simboli $\leq$ o $\geq$ e così faremo anche noi nel prosieguo.

Definizione 12. Sia $(A,\leq)$ un insieme parzialmente ordinato.

Un elemento $M\in A$ è detto massimo
$\begin{equation*} M=\max A\quad \Leftrightarrow \quad a\leq M\quad\forall a\in A \end{equation*}$
Un elemento $m\in A$ è detto minimo
$\begin{equation*} m=\min A\quad \Leftrightarrow \quad m\leq a\quad\forall a\in A \end{equation*}$

Proposizione 8. Se esistono il massimo e il minimo di un insieme parzialmente ordinato $(A,\leq )$ , allora essi sono unici.

Dimostrazione. Segue dalla proprietà di antisimmetria della relazione d’ordine. Supponiamo che esistano due massimi $M_1$ e $M_2$ . Allora, siccome $M_1$ è un massimo, $M_2 \leq M_1$ , ma poichè anche $M_2$ è un massimo, $M_1\leq M_2$ , dunque $M_1=M_2$ .

Di seguito elenchiamo alcune definizioni elementari nel contesto generale degli insiemi parzialmente ordinati. Esse saranno riprese in seguito nello studio degli insiemi numerici.

Definizione 13. Sia $A\subseteq X$ un sottoinsieme di un insieme parzialmente ordinato $(X,\leq).$

Un elemento $x\in X$ è un maggiorante di $A$ se
$\begin{equation*} a\leq x\qquad\forall a\in A \end{equation*}$
Un elemento $x\in X$ è un minorante di $A$ se
$\begin{equation*} x\leq a\qquad\forall a\in A \end{equation*}$

Indicheremo rispettivamente con $M(A)$ e $m(A)$ l’insieme dei maggioranti e dei minoranti di $A$ :

$M(A)=\{ x\in X: \forall a \in A \;\, a\leq x \} \quad m(A)=\{ x\in X: \forall a \in A \;\, x\leq a\}.$

Definizione 14. Sia $A$ un sottoinsieme di un insieme totalmente ordinato $X$ . Diremo che:

$A$ è limitato superiormente se $M(A)\neq\emptyset$ , ovvero se $\exists \, M \in X$ tale che $a\leq M\quad \forall a\in A$ ;
$A$ è limitato inferiormente se $m(A)\neq\emptyset$ , ovvero se $\exists \, m \in X$ tale che $m\leq a \quad \forall a\in A$ ;

Paradosso di Russel

Leggi...

Terminiamo motivando il titolo di queste note spiegando perchè quella di cui abbiamo parlato viene detta “Teoria ingenua degli insiemi”. Parlando dell’insieme delle parti abbiamo dato un primo esempio di un insieme che ha come elementi altri insiemi. Di certo non è l’unico insieme che ha questa caratteristica. Le cose diventano interessanti quando lavoriamo con insiemi di cardinalità infinita (nel senso che hanno un numero infinito di elementi).

Consideriamo ad esempio l’insieme $A$ che ha come elementi tutti gli insiemi di cardinalità finita. Questo insieme ha cardinalità infinita: esistono infiniti insiemi che hanno cardinalità finita e sono tutti gli elementi di questo insieme. In modo particolare $A$ stesso essendo infinito non è elemento di se stesso. Quindi esistono insiemi che non hanno come elemento se stessi!

Consideriamo invece $B$ l’insieme che ha come elementi tutti gli insiemi di cardinalià infinita. Questo insieme ha cardinalità infinita: esistono infiniti insiemi che hanno cardinalità infinita e sono tutti gli elementi di questo insieme. In modo particolare $B$ stesso essendo infinito è elemento di se stesso! Quindi esistono insiemi che hanno come elemento se stessi!

Quindi abbiamo due classi di insiemi, quelli che appartengono e quelli che non appartengono a se stessi:

Gli insiemi che tra i loro elementi non hanno loro stessi, cioè gli insiemi che non appartengono a sé stessi; ad esempio, come notò Russell stesso, “l’insieme di tutte le tazze da tè” non è una tazza da tè.
Gli insiemi che tra i loro elementi hanno loro stessi, cioè gli insiemi che appartengono a sé stessi; si cita spesso come esempio “l’insieme di tutti i concetti astratti”, che appartiene a sé stesso perché, a sua volta, è un concetto astratto.

Adesso le cose diventano davvero interessanti: consideriamo $R$ , l’insieme di tutti gli insiemi che non contengono se stesso:

$R = \{ x : x \not\in x \}.$

Adesso ci chiediamo: “ $R$ contiene se stesso?”

Se $R$ contensse se stesso non dovrebbe contenere se stesso per definizione di $R$ .
Allo stesso modo se $R$ non contenesse se stesso, dovrebbe contenere se stesso in quanto $R$ è l’insieme di tutti gli insiemi che non contengono se stesso!

In altre parole

$R \in R \Leftrightarrow R \not \in R,$

ovvero $R$ appartiene a se stesso se e soltanto se $R$ non appartiene a se stesso che è palesemente una contraddizione in termini.

Questa follia è nota come il paradosso di Russell, formulato dal filosofo e logico britannico Bertrand Russell tra il 1901 e il 1902, è una delle antinomie più importanti della storia della filosofia e della logica.

Si tratta più propriamente di un’antinomia che di un paradosso: un paradosso è una conclusione logica e non contraddittoria che si scontra con il nostro modo abituale di vedere le cose, mentre un’antinomia è una proposizione che risulta autocontraddittoria sia nel caso che sia vera, sia nel caso che sia falsa.

L’antinomia di Russell può essere espressa in modo “intuitivo” per mezzo di altre formulazioni, come il paradosso del barbiere:

$\begin{aligned} &\text{``In una cittadina c'è un unico barbiere che taglia i capelli a tutti quelli che non si tagliano i capelli da soli;}\\ &\text{chi taglia i capelli al barbiere?"} \end{aligned}$

Crisi dei fondamenti della matematica

Leggi...

¹ Il paradosso di Russell ebbe un ruolo fondamentale nella crisi dei fondamenti della matematica, la quale a sua volta ebbe un peso notevole nella più ampia crisi che interessò le certezze fondamentali della fisica, della filosofia e appunto della matematica all’inizio del XX secolo, crisi che spesso è associata al crollo delle dottrine filosofiche di stampo positivista. In particolare, dimostrò la contraddittorietà della teoria ingenua (o intuitiva) degli insiemi di Georg Cantor, che faceva uso di strumenti matematici analoghi a quelli su cui si era basato Gottlob Frege nel tentativo di produrre una completa fondazione della matematica sulla logica (tale tentativo va sotto il nome di Logicismo). Nel tentativo di risolvere l’antinomia, in modo tale da conservare la validità dell’idea (alla base del Logicismo) per cui la matematica può essere fondata completamente dalla logica, Russell sviluppò in collaborazione con Alfred North Whitehead la teoria dei tipi, esposta nel loro libro Principia Mathematica.

Tra la fine del XIX secolo e l’inizio del XX, diversi matematici e filosofi avevano cominciato a interrogarsi sul problema dei ”fondamenti della matematica”, cioè sulla definizione di basi precise in grado di fondare l’intero edificio concettuale della matematica. L’attenzione, che precedentemente era concentrata quasi esclusivamente sul contenuto dei giudizi matematici, si spostò in questo periodo sulla giustificazione dei giudizi stessi.

Le tre prospettive principali sul problema dei fondamenti furono quella logicista, quella intuizionista e quella formalista.

L’antinomia di Russell, oltre che mandare in crisi il Logicismo, generò problemi contro cui si scontrarono tutti gli studiosi di matematica suoi contemporanei, e che – nonostante diversi tentativi di trovare risposte al paradosso – rimasero insolubili sia per la teoria dei tipi elaborata da Russell insieme a Whitehead, sia per l’Intuizionismo di Luitzen Brouwer sia per il Formalismo di David Hilbert.

Fu il logico austriaco Kurt Gödel che, nel 1931, risolse definitivamente la questione dimostrando l’impossibilità tout court di produrre una fondazione certa anche solo per l’aritmetica. I suoi risultati sono enunciati da due teoremi di incompletezza.

Per quanto riguarda l’insiemistica, le contraddizioni messe in luce dal paradosso di Russell sono insolubili nell’ambito della teoria di Cantor, se non generando altri paradossi; per superare questo scoglio furono elaborate diverse teorie assiomatiche più rigorose: quella che ebbe più seguito fu la teoria degli insiemi di Zermelo-Fraenkel, formulata inizialmente da Ernst Zermelo e perfezionata da Abraham Fraenkel e Thoralf Skolem che, con le successive estensioni (ad esempio, la teoria ZFC), fornisce tuttora la base teorica per la maggior parte delle costruzioni matematiche. La vecchia teoria degli insiemi (peraltro tuttora largamente utilizzata a livello scolastico e divulgativo) viene chiamata teoria intuitiva o ingenua degli insiemi, in contrapposizione alla teoria assiomatica degli insiemi.

1. Fonte Wikipedia: Crisi dei fondamenti della matematica (↩)

Riferimenti bibliografici

Leggi...

[1] Qui Si Risolve Funzioni elementari: algebriche, esponenziali e logartimiche.

[2] Qui Si Risolve Funzioni elementari: trigonometriche e iperboliche.

[3] Qui Si Risolve Logica elementare.

[4] Qui Si Risolve Teoria sulle funzioni.

Approfondimenti

In questa sezione dimostriamo il teorema 1 sulla cardinalità dell’insieme delle parti. Ricordiamo che tale dimostrazione si fonda sul principio di induzione, quindi il lettore è invitato a leggere la costruzione dei numeri naturali per comprenderla.

Leggi la dimostrazione del Teorema 1.

Teorema 1. Dato un insieme $A$ con $n$ elementi (ovvero, ricordando la definizione di cardinalità, $|A| = n$ ), tutti i suoi sottoinsiemi sono $2^n$ .

Dimostrazione. Se $|A|=n$ allora $A=\{x_1,x_2,...,x_n \}$ ; dimostriamo per induzione che $|P(A)|=2^n$ .

Passo base. Per $n=0$ allora $A=\emptyset$ quindi
$P(A)=\{\emptyset\}\Rightarrow |P(A)|=1=2^0.$
Passo induttivo. Supponiamo vera l’ipotesi per $n$ e dimostriamo l’asserto per $n+1$ . Riscriviamo l’insieme $A=\{x_1,x_2,...,x_{n+1}\}$ come unione disgiunta tra un insieme $A'$ di cardinalità $n$ e l’insieme $\{x_{n+1}\}$ formato da un unico elemento. Per ipotesi induttiva
$P(A')=2^n.$

e questo insieme contiene tutti i sottoinsiemi di $A$ che non contengono $x_{n+1}$ . Tutti i sottoinsiemi che contengono $x_{n+1}$ sono della forma $B\cup\{x_{n+1}\}$ con $B\subseteq A'$ e, sempre per ipotesi induttiva, sono $2^n$ . Quindi

$\begin{equation*} |P(A)|=2^n+2^n=2^n\cdot (1+1)=2^n\cdot 2=2^{n+1}, \end{equation*}$

ovvero la tesi.