Insiemi, relazioni e funzioni

Il linguaggio del corso

La lezione successiva definisce i numeri naturali mediante una funzione, il successore, che è iniettiva e non raggiunge l’$1$. L’unità successiva costruisce gli interi e i razionali come classi di una relazione di equivalenza; la lezione di calcolo combinatorio definisce il numero di elementi mediante biiezioni; l’ordine dei naturali è una relazione d’ordine; e la terza unità compone e inverte funzioni reali. Tutte queste parole appartengono a uno stesso linguaggio, che conviene fissare prima di usarlo, insieme con i primi teoremi che il corso invocherà in seguito.

Conviene avvertire che cosa si anticipa. Gli esempi usano piccoli numeri naturali con il loro ordine, la loro somma, il loro prodotto, la divisibilità e il resto di una divisione, così come si imparano a scuola. La lezione successiva definisce i naturali mediante gli assiomi di Peano, e le lezioni dell’unità definiscono quelle operazioni e ne dimostrano le proprietà senza usare alcun esempio di questa, cosicché non c’è circolo. Nessun teorema di questa lezione dipende dagli esempi: i numeri servono solo a vedere i teoremi all’opera.

Ciò che si ammette

Un insieme è una collezione di oggetti, i suoi elementi; si scrive $a \in A$ per dire che $a$ appartiene ad $A$, e $a \notin A$ per negarlo. Insieme e appartenenza non si definiscono: sono nozioni primitive, come l’$1$ e il successore nell’aritmetica. Ora, non ogni proprietà definisce un insieme. Se esistesse l’insieme $R$ di tutti gli insiemi che non appartengono a se stessi, la domanda se $R$ appartenga a $R$ non avrebbe risposta, perché per la definizione di $R$ si avrebbe $R \in R \leftrightarrow R \notin R$. Questa contraddizione, scoperta da Russell nel 1901, obbliga a restringere la formazione degli insiemi: una proprietà seleziona soltanto elementi di un insieme già dato.

Fatto ammesso (regole della teoria ingenua degli insiemi). Si ammettono senza dimostrazione le regole della teoria ingenua degli insiemi che questa lezione usa: due insiemi con gli stessi elementi sono uguali; da un insieme dato $A$ e da una proprietà $P$ si forma l’insieme $\{ x \in A : P(x) \}$ degli elementi di $A$ che la soddisfano; ed esistono l’insieme vuoto, l’insieme $\{a, b\}$ i cui unici elementi sono $a$ e $b$, l’unione degli elementi di un insieme di insiemi e l’insieme dei sottoinsiemi di un insieme. L’esistenza di un insieme con le proprietà dell’insieme dei naturali si ammette nella lezione successiva.

Queste regole fanno parte degli assiomi di Zermelo e Fraenkel, il cui studio appartiene alla teoria degli insiemi ed eccede questo corso; per questo si ammettono, e si dichiarano perché si sappia esattamente che cosa si usa.

Logica dei quantificatori

Le dimostrazioni combinano enunciati con i connettivi $\neg$, $\wedge$, $\vee$, $\rightarrow$ e $\leftrightarrow$, le cui leggi si studiano nel corso complementare Logica Matematica I: Logica Proposizionale, a partire dal suo linguaggio; qui basta ricordare che l’implicazione $p \rightarrow q$ è falsa solo quando $p$ è vera e $q$ falsa, che equivale alla sua contronominale $\neg q \rightarrow \neg p$, e che le leggi di De Morgan negano una congiunzione o una disgiunzione:

Per parlare di insiemi servono, inoltre, enunciati su tutti gli elementi o su qualcuno. Se $P(x)$ è una proprietà degli elementi di $A$, l’enunciato $(\forall x \in A)\,P(x)$, che si legge «per ogni $x$ di $A$, $P(x)$», afferma che tutti gli elementi di $A$ la soddisfano; l’enunciato $(\exists x \in A)\,P(x)$, «esiste un $x$ di $A$ tale che $P(x)$», afferma che almeno uno la soddisfa; e $(\exists! x \in A)\,P(x)$ afferma che esattamente uno la soddisfa. I simboli $\forall$ e $\exists$ si chiamano quantificatori, universale ed esistenziale.

Fatto ammesso (negazione dei quantificatori). Negare che tutti gli elementi soddisfino una proprietà significa affermare che qualcuno non la soddisfa, e negare che qualcuno la soddisfi significa affermare che nessuno la soddisfa:

Queste regole, proprie della logica del primo ordine, si ammettono; estendono le leggi di De Morgan, perché se $A = \{a, b\}$ l’universale è $P(a) \wedge P(b)$ e l’esistenziale è $P(a) \vee P(b)$. L’ordine dei quantificatori conta: l’enunciato $(\forall n \in \mathbb{N})(\exists m \in \mathbb{N})(n < m)$ dice che ogni naturale ne ha un altro maggiore, ed è vero; l’enunciato $(\exists m \in \mathbb{N})(\forall n \in \mathbb{N})(n < m)$ dice che c’è un naturale maggiore di tutti, anche di se stesso, ed è falso.

La forma logica di un enunciato detta il modo di dimostrarlo. Le strategie che questa lezione usa sono le seguenti; la loro giustificazione logica si studia nella lezione sulle tecniche di deduzione.

• Per dimostrare $(\forall x \in A)\,P(x)$, si prende un elemento $x$ di $A$ qualsiasi, senza supporre su di esso nient’altro che la sua appartenenza ad $A$, e si dimostra $P(x)$.
• Per dimostrare $(\exists x \in A)\,P(x)$, si esibisce un elemento concreto di $A$ che soddisfa $P$; per confutare $(\forall x \in A)\,P(x)$, basta un controesempio, un elemento che non la soddisfa.
• Per dimostrare $p \rightarrow q$, si suppone $p$ e si deduce $q$; oppure si dimostra la contronominale $\neg q \rightarrow \neg p$; oppure si suppone $p \wedge \neg q$ e si giunge a una contraddizione.
• Per dimostrare $p \leftrightarrow q$, si dimostrano le due implicazioni $p \rightarrow q$ e $q \rightarrow p$.

Insiemi

Appartenenza, uguaglianza e inclusione

Un insieme si descrive per elencazione, enumerando i suoi elementi tra parentesi graffe, come $\{1, 2, 3\}$, oppure per comprensione, mediante una proprietà, come $\{ n \in \mathbb{N} : n \leq 3 \}$, che è lo stesso insieme. La regola di estensionalità dice che un insieme è determinato dai suoi elementi:

Ne segue che in una descrizione per elencazione non contano né l’ordine né le ripetizioni: $\{1, 2, 2\}$ e $\{2, 1\}$ sono lo stesso insieme, perché hanno gli stessi elementi. Ne segue anche che c’è un solo insieme senza elementi, l’insieme vuoto $\emptyset$: due insiemi senza elementi hanno gli stessi elementi, cioè nessuno.

Definizione (inclusione). Un insieme $A$ è contenuto in un insieme $B$, o è un sottoinsieme di $B$, quando ogni elemento di $A$ è elemento di $B$:

Se inoltre $A \neq B$, si dice che $A$ è un sottoinsieme proprio di $B$.

L’insieme vuoto è contenuto in ogni insieme $A$, perché l’implicazione $x \in \emptyset \rightarrow x \in A$ ha sempre l’antecedente falso ed è, pertanto, vera. Conviene distinguere l’appartenenza dall’inclusione: $1 \in \{1, 2\}$ e $\{1\} \subseteq \{1, 2\}$ sono veri, mentre $\{1\} \in \{1, 2\}$ è falso, perché gli unici elementi di $\{1, 2\}$ sono $1$ e $2$, e l’insieme $\{1\}$ non è uguale a nessuno dei due: $\{1\} \neq 1$, perché l’insieme che ha come unico elemento l’$1$ non si confonde con l’$1$, e $\{1\} \neq 2$.

Unione, intersezione e differenza

Definizione (operazioni tra insiemi). L’unione di $A$ e $B$ è l’insieme degli elementi che appartengono ad almeno uno di essi; l’intersezione, quello degli elementi che appartengono a entrambi; e la differenza $A \setminus B$, quello degli elementi che appartengono ad $A$ e non a $B$:

Se $B \subseteq A$, la differenza $A \setminus B$ si chiama complementare di $B$ relativo ad $A$. Due insiemi sono disgiunti quando la loro intersezione è vuota.

Ogni operazione traduce un connettivo: l’unione, la disgiunzione; l’intersezione, la congiunzione; la differenza, la congiunzione con una negazione. Se è così, ogni legge logica produce una legge degli insiemi: l’unione e l’intersezione sono commutative, associative e distributive l’una rispetto all’altra perché lo sono i connettivi, e tutte queste leggi si dimostrano come il teorema seguente. Il complementare si prende sempre rispetto a un insieme di riferimento, perché un insieme di tutto ciò che non sta in $B$ ricostruirebbe il paradosso di Russell.

L’insieme delle parti

I sottoinsiemi di un insieme formano a loro volta un insieme, la cui esistenza si è ammessa all’inizio. L’insieme delle parti di $A$, che si denota $\mathcal{P}(A)$, è l’insieme i cui elementi sono i sottoinsiemi di $A$:

Per esempio, l’insieme delle parti di $\{1, 2, 3\}$ ha otto elementi: il vuoto, tre insiemi di un elemento, tre di due elementi e lo stesso $\{1, 2, 3\}$.

Per ogni insieme $A$, il vuoto e lo stesso $A$ sono elementi di $\mathcal{P}(A)$, e per ogni $a$ di $A$ si ha $\{a\} \in \mathcal{P}(A)$, mentre $a$ non è, in generale, elemento di $\mathcal{P}(A)$. Nella lezione sul calcolo combinatorio si dimostrerà che un insieme di $n$ elementi ha $2^n$ sottoinsiemi.

Coppie ordinate e prodotto cartesiano

Un punto del piano, una frazione o una sottrazione in sospeso si descrivono con due oggetti in un ordine determinato: la coppia $(3, 5)$ non è la coppia $(5, 3)$. L’insieme $\{3, 5\}$ non serve a rappresentarla, perché è uguale a $\{5, 3\}$. L’unica cosa che si esige da una coppia ordinata è la sua proprietà caratteristica: due coppie sono uguali se e solo se hanno la stessa prima componente e la stessa seconda componente. Kuratowski osservò nel 1921 che basta la nozione di insieme per costruire un oggetto con questa proprietà.

Definizione (coppia ordinata). La coppia ordinata di prima componente $a$ e seconda componente $b$ è l’insieme

Dimostrata la proprietà caratteristica, la costruzione di Kuratowski può essere dimenticata: tutto ciò che il corso dice delle coppie si deduce da essa.

Definizione (prodotto cartesiano). Il prodotto cartesiano di $A$ e $B$ è l’insieme delle coppie la cui prima componente appartiene ad $A$ e la cui seconda componente appartiene a $B$:

La scrittura $\{ (a, b) : a \in A \wedge b \in B \}$ non è di per sé una delle regole ammesse, che permettono solo di separare elementi di un insieme già formato. Ora, quell’insieme esiste: se $a \in A$ e $b \in B$, gli insiemi $\{a\}$ e $\{a, b\}$ sono contenuti in $A \cup B$, e pertanto sono elementi di $\mathcal{P}(A \cup B)$; ne segue che la coppia $(a, b) = \{ \{a\}, \{a, b\} \}$ è contenuta in $\mathcal{P}(A \cup B)$, cioè è un elemento di $\mathcal{P}(\mathcal{P}(A \cup B))$. Pertanto, il prodotto cartesiano si forma per separazione dentro quell’insieme, che esiste per le regole ammesse: $A \cup B$ è l’unione degli elementi di $\{A, B\}$, e si prende due volte l’insieme delle parti.

Il nome ricorda Cartesio: il piano della geometria analitica è $\mathbb{R} \times \mathbb{R}$. Il prodotto non è commutativo: $\{1\} \times \{2\}$ contiene solo $(1, 2)$, e $\{2\} \times \{1\}$ solo $(2, 1)$, che è distinta per la proprietà caratteristica.

Relazioni

Dire che $2$ divide $6$, che $3$ è minore di $5$ o che due giorni cadono nello stesso giorno della settimana significa affermare che certe coppie di oggetti sono in relazione. Se è così, una relazione è determinata dalle coppie che mette in relazione, e può essere definita come un insieme di coppie.

Definizione (relazione). Una relazione da $A$ in $B$ è un sottoinsieme $R$ del prodotto $A \times B$; una relazione in $A$ è una relazione da $A$ in $A$. Se $(a, b) \in R$, si dice che $a$ è in relazione con $b$ tramite $R$.

Per esempio, la relazione «minore o uguale a» in $\{1, 2, 3\}$ è l’insieme di coppie $\{(1, 1), (1, 2), (1, 3), (2, 2), (2, 3), (3, 3)\}$. Per le relazioni di uso frequente si scrive un simbolo tra i termini, come $a \leq b$ o $a \mid b$, invece di $(a, b) \in R$. Quattro proprietà di una relazione in un insieme ricorrono in tutto il corso.

Definizione (proprietà delle relazioni). Una relazione $R$ in $A$ è riflessiva, simmetrica, antisimmetrica o transitiva quando soddisfa, rispettivamente, le condizioni seguenti.

• È riflessiva se ogni elemento è in relazione con se stesso: $(\forall a \in A)\,((a, a) \in R)$;
• È simmetrica se la relazione di $a$ con $b$ implica quella di $b$ con $a$: $(\forall a, b \in A)\,((a, b) \in R \rightarrow (b, a) \in R)$;
• È antisimmetrica se due elementi in relazione in entrambi i versi sono uguali: $(\forall a, b \in A)\,((a, b) \in R \wedge (b, a) \in R \rightarrow a = b)$;
• È transitiva se la relazione di $a$ con $b$ e quella di $b$ con $c$ implicano quella di $a$ con $c$: $(\forall a, b, c \in A)\,((a, b) \in R \wedge (b, c) \in R \rightarrow (a, c) \in R)$.

Nella griglia di $A \times A$, una relazione è un insieme di punti. È riflessiva quando contiene tutta la diagonale, quella delle coppie $(a, a)$; è simmetrica quando il suo disegno è simmetrico rispetto alla diagonale; ed è antisimmetrica quando nessun punto fuori dalla diagonale ha il suo simmetrico nella relazione. Antisimmetrica non significa «non simmetrica»: l’uguaglianza è entrambe le cose, e il problema proposto 1 chiede una relazione che non sia né l’una né l’altra.

Relazioni di equivalenza

La relazione «avere la stessa parità» si comporta come un’uguaglianza parziale: identifica i numeri che coincidono in un aspetto, la loro parità, e dimentica gli altri. Le tre proprietà che la fanno comportare così ricevono un nome.

Definizione (relazione di equivalenza). Una relazione in $A$ è una relazione di equivalenza quando è riflessiva, simmetrica e transitiva. Si scrive allora $a \sim b$, e si dice che $a$ è equivalente a $b$. La classe di $a$ è l’insieme degli elementi equivalenti ad $a$, e ciascuno di essi è un rappresentante della classe:

L’insieme di tutte le classi si chiama insieme quoziente e si denota $A/{\sim}$.

Sono relazioni di equivalenza l’uguaglianza, le cui classi hanno un solo elemento; la stessa parità, con due classi; avere lo stesso resto nella divisione per $3$, con tre; e cadere nello stesso giorno della settimana, con sette, che è il problema risolto 3. In generale, se $g$ è una funzione definita in $A$, la relazione $g(x) = g(y)$ eredita dall’uguaglianza le tre proprietà, e il problema risolto 5 mostra che ogni equivalenza è di questa forma.

Le classi dividono, pertanto, l’insieme in blocchi che non si sovrappongono. Questo modo di dividere un insieme merita una definizione propria.

Definizione (partizione). Una partizione di un insieme $A$ è un insieme di sottoinsiemi di $A$, detti blocchi, che non sono vuoti, che sono disgiunti a due a due e la cui unione è $A$; equivalentemente, ogni elemento di $A$ appartiene a esattamente un blocco.

Dare un’equivalenza in $A$ e dare una partizione di $A$ sono, pertanto, due modi di dire la stessa cosa; il problema risolto 4 ne approfitta per contare equivalenze. L’insieme quoziente è la partizione vista come un insieme nuovo: passando da $A$ ad $A/{\sim}$, gli elementi equivalenti si fondono in uno solo.

Allo stesso modo, nella lezione sui numeri razionali due frazioni $(p, q)$ e $(r, s)$ sono equivalenti quando $ps = qr$, e un razionale è una classe; e nella lezione sulle congruenze, i resti modulo $n$ sono le classi di un’equivalenza tra interi.

Relazioni d’ordine

La divisibilità dell’esempio precedente non è simmetrica ma antisimmetrica: invece di identificare elementi, li ordina. Le relazioni di questo tipo ricevono un nome proprio.

Definizione (ordine). Una relazione in $A$ è una relazione d’ordine, od ordine parziale, quando è riflessiva, antisimmetrica e transitiva; si scrive allora $a \preceq b$, e si dice che $a$ precede $b$. L’ordine è totale quando due elementi qualsiasi sono confrontabili, cioè quando per tutti gli $a$ e $b$ si ha $a \preceq b$ oppure $b \preceq a$.

Sono ordini la relazione $\leq$ tra naturali, che è totale per la tricotomia dimostrata nella lezione sulle operazioni sui numeri naturali; l’inclusione, per il teorema sulle sue proprietà, che non è totale, perché $\{1\}$ e $\{2\}$ non sono confrontabili; e la divisibilità tra naturali, la cui antisimmetria si dimostra nella lezione sulla divisibilità, che non è totale, perché né $2 \mid 3$ né $3 \mid 2$. Un ordine finito si disegna con un diagramma di Hasse: un punto per elemento, con $b$ più in alto di $a$ quando $a$ precede $b$, e un segmento quando tra i due non c’è nessun altro elemento; la transitività permette di omettere gli altri segmenti.

Definizione (minoranti, maggioranti ed elementi estremi). Siano $\preceq$ un ordine in $A$ e $X$ un sottoinsieme di $A$. I minoranti, i maggioranti e gli elementi estremi di $X$ si definiscono come segue.

• Un elemento $c$ di $A$ è un minorante di $X$ se precede tutti gli elementi di $X$, e un maggiorante se tutti gli elementi di $X$ lo precedono.
• Un minimo di $X$ è un minorante di $X$ che appartiene a $X$, e un massimo è un maggiorante che appartiene a $X$.
• Un elemento $m$ di $X$ è minimale se nessun elemento di $X$ distinto da esso lo precede, e massimale se esso non precede nessun elemento di $X$ distinto da sé.
• L’estremo inferiore di $X$ è il massimo dell’insieme dei suoi minoranti, e l’estremo superiore è il minimo dell’insieme dei suoi maggioranti, quando esistono.