Appunti del Corso: Capitolo 2 - Teoria degli Insiemi
Definizione di Insieme ed Elementi
Si dice INSIEME un qualsiasi "gruppo" o collezione di ELEMENTI ben distinti. Gli elementi non sono necessariamente omogenei (possono essere di tipi diversi) né necessariamente ordinati.
Esempio: $\{15, 6, \text{mela}, \emptyset, a\} = \{a, 6, 15, \emptyset, \text{mela}\} = \{a, a, a, 6, 15, \text{mela}, \emptyset\}$.
Relazione di Appartenenza ($\in$)
La relazione di appartenenza è un predicato binario $R(x, A)$ che si scrive come $x \in A$ e si legge "$x$ appartiene ad $A$". Indica che $x$ è un ELEMENTO dell'INSIEME $A$. La sua negazione è $x \notin A$.
Modi per Definire un Insieme
Un insieme può essere definito per:
- Elencazione: Elencando i suoi elementi. Esempi: $A = \{1, 2, 3, \dots\}$, $B = \{-1, 4, 9, -7\}$.
- Proprietà Caratteristica: Specificando una proprietà $P(x)$ che i suoi elementi devono soddisfare. Si scrive $C = \{x \mid P(x)\}$. Formalmente, $C = \{x \mid P(x)\} \equiv \forall x (x \in C \Leftrightarrow P(x))$.
Esempio: $C = \{x \mid x \text{ è un felino}\}$.
Insieme Vuoto e Singoletto
L'**INSIEME VUOTO**, denotato con $\emptyset$ (o $\{\}$), è l'insieme che non contiene alcun elemento.
- $x \in \emptyset$ è sempre FALSO (è una contraddizione).
- $x \notin \emptyset$ è sempre VERO (è una tautologia).
Un **SINGOLETTO** è un insieme che contiene un solo elemento. Esempi: $\{a\}, \{1\}, \{\emptyset\}$.
Attenzione: $a \in \{a\}$ è VERO, ma $\{a\} \in \{a\}$ è generalmente FALSO (a meno che $a$ non sia l'insieme $\{\{a\}\}$ stesso).
Gli elementi di un insieme possono essere a loro volta insiemi. Esempio: $P = \{a, \{1\}, \{3,7\}, b, \{\emptyset, \{-1, c, d\}\}\}$.
Relazione di Inclusione ($\subseteq$)
Dati due insiemi $A$ e $B$, $A$ è sottoinsieme di $B$ (o $A$ è contenuto in $B$, o $A$ è incluso in $B$) se ogni elemento di $A$ è anche elemento di $B$. Si scrive $A \subseteq B$.
Formalmente: $A \subseteq B \iff \forall x (x \in A \Rightarrow x \in B)$.
Se $A = \{a, c, e, f\}$ e $B = \{a, b, c, d, e, f\}$, allora $A \subseteq B$.
Se $A \subseteq B$ e $A \neq B$, si dice che $A$ è un **sottoinsieme proprio** di $B$, e si può scrivere $A \subset B$.
Cenno ai Paradossi
La definizione "ingenua" di insiemi può portare a paradossi. Ad esempio, considerare "l'insieme di tutti gli insiemi che non contengono se stessi come elementi", $R = \{X \mid X \notin X\}$. Se $R \in R$, allora per definizione $R \notin R$ (contraddizione). Se $R \notin R$, allora per definizione $R \in R$ (contraddizione). Questo è il famoso Paradosso di Russell. Per evitare tali paradossi, la teoria degli insiemi viene assiomatizzata, ma questo va oltre gli scopi di questo corso introduttivo.
Insieme delle Parti (o Insieme Potenza, $\mathcal{P}(A)$)
L'**insieme delle parti** di un insieme $A$, indicato con $\mathcal{P}(A)$, è l'insieme che ha come elementi tutti i possibili sottoinsiemi di $A$.
Formalmente: $\mathcal{P}(A) = \{X \mid X \subseteq A\}$.
Se $A = \{1, 2, 3\}$, allora $\mathcal{P}(A) = \{\emptyset, \{1\}, \{2\}, \{3\}, \{1,2\}, \{1,3\}, \{2,3\}, \{1,2,3\}\}$.
- Sempre $\emptyset \in \mathcal{P}(A)$.
- Sempre $A \in \mathcal{P}(A)$.
Se l'insieme $A$ è finito e ha $n$ elementi (cioè $|A|=n$), allora il suo insieme delle parti $\mathcal{P}(A)$ ha $2^n$ elementi (cioè $|\mathcal{P}(A)|=2^n$).
Operazioni tra Insiemi
Consideriamo $A$ e $B$ come sottoinsiemi di un insieme universo $\mathcal{T}$.
- Intersezione ($A \cap B$): L'insieme degli elementi che appartengono sia ad $A$ che a $B$.
$A \cap B = \{x \mid x \in A \wedge x \in B\}$. - Unione ($A \cup B$): L'insieme degli elementi che appartengono ad $A$ o a $B$ (o a entrambi).
$A \cup B = \{x \mid x \in A \vee x \in B\}$. - Complementare ($\overline{A}$ o $A^c$): L'insieme degli elementi dell'universo $\mathcal{T}$ che non appartengono ad $A$.
$\overline{A} = \{x \mid x \notin A\}$. - Differenza ($A \setminus B$): L'insieme degli elementi che appartengono ad $A$ ma non a $B$.
$A \setminus B = \{x \mid x \in A \wedge x \notin B\}$.
Si può anche scrivere $A \setminus B = A \cap \overline{B}$. - Differenza Simmetrica ($A \triangle B$): L'insieme degli elementi che appartengono ad $A$ o a $B$, ma non a entrambi.
$A \triangle B = (A \setminus B) \cup (B \setminus A)$.
$A \triangle B = (A \cup B) \setminus (A \cap B)$.
Proprietà delle Operazioni tra Insiemi
Le operazioni tra insiemi godono di molte proprietà, tra cui:
- Idempotenza: $A \cup A = A$; $A \cap A = A$.
- Commutatività: $A \cup B = B \cup A$; $A \cap B = B \cap A$.
- Associatività: $(A \cup B) \cup C = A \cup (B \cup C)$; $(A \cap B) \cap C = A \cap (B \cap C)$.
- Distributività: $A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$; $A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$.
- Leggi dell'Assorbimento: $A \cup (A \cap B) = A$; $A \cap (A \cup B) = A$.
- Leggi di De Morgan per Insiemi: $\overline{(A \cap B)} = \overline{A} \cup \overline{B}$; $\overline{(A \cup B)} = \overline{A} \cap \overline{B}$.
Dimostrare queste proprietà è un ottimo esercizio che collega la teoria degli insiemi alla logica proposizionale.
Insieme Prodotto (Prodotto Cartesiano, $A \times B$)
Dati due insiemi $A$ e $B$, il loro prodotto cartesiano $A \times B$ è l'insieme di tutte le possibili **coppie ordinate** $(a,b)$ tali che $a \in A$ e $b \in B$.
$A \times B = \{(a,b) \mid a \in A \wedge b \in B\}$.
Punti importanti:
- In una coppia ordinata $(a,b)$, l'ordine conta: $(a,b) \neq (b,a)$ a meno che $a=b$.
- Non confondere con l'insieme $\{a,b\}$ dove l'ordine non conta.
Se $A=\{1,2\}$ e $B=\{x,y\}$, allora $A \times B = \{(1,x), (1,y), (2,x), (2,y)\}$.
In generale $A \times B \neq B \times A$.
Se $|A|=m$ e $|B|=n$, allora $|A \times B| = m \cdot n$.
Questa nozione si estende a più insiemi, formando **n-uple ordinate** (o tuple). Ad esempio, $(x_1, x_2, \dots, x_m) \in A_1 \times A_2 \times \dots \times A_m$.