coldboot · appunto
Teoria degli Insiemi, Principio d'Induzione e Campi Numerici
ALGEBRA LINEARE E MATEMATICA DISCRETA
Dati due insiemi A e B contenuti in un universo S:
1. Fondamenti di Teoria degli Insiemi (o Classi)
- Classe: Raggruppamento qualsiasi di oggetti.
- Insieme: Una classe che è anche membro di un'altra classe.
Appartenenza e Notazione
- \(a \in A\) \(\longrightarrow\) "\(a\) è contenuto (o appartiene) ad \(A\)"
- \(a \notin A\) \(\longrightarrow\) "\(a\) non appartiene ad \(A\)"
Rappresentazione degli Insiemi
- Per elencazione: \(A = \{a, b, c\}\)
- Per proprietà caratteristica: \(A = \{x \mid x \text{ è una delle prime 3 lettere dell'alfabeto}\}\)
Inclusione e Simboli Logici
- Inclusione debole (Sottoinsieme):
\[B \subseteq A \iff [\forall x \in B \implies x \in A]\]
- Inclusione stretta (Sottoinsieme proprio):
\[B \subset A \iff [(\forall x \in B \implies x \in A) \land (\exists y \in A \text{ t.c. } y \notin B)]\]
| Simbolo | Significato |
|---|---|
| \(\forall\) | Per ogni |
| \(\exists\) | Esiste |
| \(\nexists\) | Non esiste |
| \(P_1 \implies P_2\) | Implicazione logica |
| \(P_1 \iff P_2\) | Doppia implicazione / Equivalenza |
| \(\land\) | Congiunzione ("e") |
| \(\lor\) | Disgiunzione ("o") |
Insieme Vuoto e Universo
- Insieme Vuoto (\(\emptyset\) oppure \(\{\}\)): Definibile come \(\emptyset = \{x \mid x \neq x\}\).
- Attenzione alla notazione: \(\{\emptyset\}\) è un insieme che contiene l'insieme vuoto (\(\vert\{\emptyset\}\vert = 1\), per cui \(\{\emptyset\} \neq \emptyset\)).
- Insieme Universo (\(U\)): L'insieme contenitore globale del contesto considerato.
2. Operazioni Insiemistiche e Insieme delle Parti
Dati due insiemi \(A\) e \(B\) contenuti in un universo \(S\):
- Intersezione: \(A \cap B = \{x \mid x \in A \land x \in B\}\)
- Unione: \(A \cup B = \{x \mid x \in A \lor x \in B\}\)
- Differenza: \(A \setminus B = \{x \mid x \in A \land x \notin B\}\)
- Complementare: \(A^c = \complement_S(A) = \{x \mid x \in S \land x \notin A\}\)
Insieme delle Parti \(\mathcal{P}(A)\)
L'insieme delle parti \(\mathcal{P}(A)\) contiene tutti i sottoinsiemi di \(A\).
Esempio: Se \(A = \{a, b, c\}\):
\[\mathcal{P}(A) = \{\emptyset, \{a\}, \{b\}, \{c\}, \{a,b\}, \{a,c\}, \{b,c\}, \{a,b,c\}\}\]
3. Cardinalità e Prodotto Cartesiano
Cardinalità \(|A|\)
Indica il numero di elementi di un insieme.
- \(|\emptyset| = 0\)
- Se \(|A| = 3\), allora \(|\mathcal{P}(A)| = 8 = 2^3\).
- In generale, se \(|A| = n \implies |\mathcal{P}(A)| = 2^n\).
Dimostrazione per Induzione: \(|\mathcal{P}(A)| = 2^n\) dove \(n = |A|\)
1. Passo Base (\(n=1\)): Per \(A = \{a\}\), si ha \(\mathcal{P}(A) = \{\emptyset, \{a\}\}\), quindi \(|\mathcal{P}(A)| = 2 = 2^1\) (Verificato).
2. Ipotesi Induttiva: Valga \(|\mathcal{P}(A)| = 2^n\) per \(|A| = n\).
3. Passo Induttivo: Consideriamo \(B\) tale che \(|B| = n+1\). Sia \(B = A \cup \{x_0\}\) con \(x_0 \notin A\) (quindi \(A = B \setminus \{x_0\}\)).
* I sottoinsiemi di \(B\) si dividono in due gruppi disgiunti: quelli che non contengono \(x_0\) (cioè \(\mathcal{P}(A)\)) e quelli che contengono \(x_0\) (ossia l'insieme \(X = \{S \cup \{x_0\} \mid S \in \mathcal{P}(A)\}\)).
* Di conseguenza, \(\mathcal{P}(B) = \mathcal{P}(A) \cup X\), con \(|X| = |\mathcal{P}(A)| = 2^n\).
* Pertanto:
\(|\mathcal{P}(B)| = |\mathcal{P}(A)| + |X| = 2^n + 2^n = 2 \cdot 2^n = 2^{n+1} \quad \blacksquare\)
Prodotto Cartesiano
\[A \times B = \{(a, b) \mid a \in A, \, b \in B\}\]
- Esempio: Se \(A = \{a, b, c\}\) e \(B = \{1, 2\}\):
\[A \times B = \{(a,1), (a,2), (b,1), (b,2), (c,1), (c,2)\}\]
- Prodotto cartesiano di \(n\) insiemi:
\[A_1 \times A_2 \times \dots \times A_n = \{(a_1, a_2, \dots, a_n) \mid a_1 \in A_1, \, a_2 \in A_2, \, \dots, \, a_n \in A_n\}\]
4. Assiomi di Peano e Principio d'Induzione
Assiomi di Peano per \(\mathbb{N}\)
- \(1 \in \mathbb{N}\)
- Esiste un unico successore \(s(n) \in \mathbb{N}\) per ogni \(n \in \mathbb{N}\) (es. \(s(5) = 6\)).
- \(1\) non è il successore di alcun numero naturale.
- Se \(m, n \in \mathbb{N}\) con \(m \neq n \implies s(m) \neq s(n)\).
- Se \(A \subseteq \mathbb{N}\) tale che \(1 \in A\) e \((\forall m \in A \implies s(m) \in A)\), allora \(A = \mathbb{N}\).
Principio d'Induzione Matematica
Sia \(P(n)\) una proprietà definita su \(\mathbb{N}\):
- Passo Base: Verifico \(P(1)\) (oppure \(P(n_0)\)).
- Ipotesi Induttiva: Ipotizzo vera \(P(n)\).
- Passo Induttivo: Verifico \(P(s(n))\), ossia \(P(n+1)\).
Se \(1\) è vera e \(P(n) \implies P(n+1)\) è dimostrata, allora \(P(n)\) è vera \(\forall n \in \mathbb{N}\).
Esempio 1: Somma dei primi \(n\) numeri naturali
Dimostrare che \(P(n): \sum_{i=1}^{n} i = \frac{n(n+1)}{2}\)
- Passo Base \(P(1)\):
\[1 = \frac{1(2)}{2} = 1 \quad \text{(Vero)}\]
- Ipotesi Induttiva \(P(n)\):
\[1 + 2 + 3 + \dots + n = \frac{n(n+1)}{2}\]
- Passo Induttivo \(P(n+1)\):
\[\sum_{i=1}^{n+1} i = \underbrace{1 + 2 + 3 + \dots + n}_{\frac{n(n+1)}{2}} + (n+1) = \frac{n(n+1)}{2} + (n+1)\]
\[= \frac{n(n+1) + 2(n+1)}{2} = \frac{(n+1)(n+2)}{2} \quad \blacksquare\]
Esempio 2: Divisibilità
Dimostrare che \(10^m - 1\) è divisibile per \(9\), \(\forall m \ge 1\).
- Passo Base \(P(1)\):
\[10^1 - 1 = 9 \quad \text{(Divisibile per 9, OK)}\]
- Ipotesi Induttiva \(P(m)\):
\[10^m - 1 \text{ è divisibile per } 9\]
- Passo Induttivo \(P(m+1)\): Verifico per \(10^{m+1} - 1\):
\[10^{m+1} - 1 = 10^m \cdot 10 - 1 = 10 \cdot 10^m - 1 + 10 - 10\]
\[= 10(10^m - 1) + 9\]
Poiché \(10^m - 1\) è divisibile per \(9\) per ipotesi induttiva, e \(9\) è divisibile per \(9\), la loro somma è anch'essa divisibile per \(9\). \(\quad \blacksquare\)
5. Insiemi e Campi Numerici
- Numeri Interi Relativi: \(\mathbb{Z} = \{0, \pm 1, \pm 2, \dots\}\)
- Numeri Razionali: \(\mathbb{Q} = \left\{x \;\middle|\; x = \frac{a}{b}, \, a,b \in \mathbb{Z}, \, b > 0\right\}\)
- Numeri Reali: \(\mathbb{R}\)
- Numeri Complessi: \(\mathbb{C} = \{a + ib \mid a, b \in \mathbb{R}, \, i = \sqrt{-1}\}\)
Campi Numerici
Gli insiemi \(\mathbb{Q}\), \(\mathbb{R}\) e \(\mathbb{C}\) costituiscono dei campi numerici.