LogicaUniPR - Guida Interattiva

2.1 Cos'è un Insieme? Un'Idea Intuitiva

Immagina un sacchetto. Puoi metterci dentro quello che vuoi: biglie, matite, numeri, persino altri sacchetti! In matematica, un insieme è molto simile: è una collezione, un raggruppamento di oggetti, che chiamiamo elementi dell'insieme.

Ci sono tre regole d'oro per gli insiemi (nella teoria "ingenua" che stiamo vedendo):

• Gli elementi sono ben distinti: Ogni oggetto o c'è o non c'è. Non ci sono ambiguità.
• L'ordine non conta: L'insieme contenente una mela e una banana è lo stesso che contiene una banana e una mela. Scrivere $\{mela, banana\}$ è identico a scrivere $\{banana, mela\}$.
• Non ci sono ripetizioni (significative): Se scriviamo $\{mela, banana, mela\}$, è esattamente lo stesso insieme di $\{mela, banana\}$. Le ripetizioni non aggiungono nuovi elementi.

Gli elementi di un insieme non devono per forza essere dello stesso "tipo". Possiamo avere un insieme come $S = \{1, \text{gatto}, \pi, \{2,4\}\}$. Nota come un elemento di $S$ sia a sua volta un altro insieme $(\{2,4\})$!

2.2 Appartenenza: Chi c'è nel Sacchetto? ($\in$)

Per dire che un oggetto $x$ è un elemento di un insieme $A$, usiamo il simbolo $\in$, che si legge "appartiene a". Quindi, $x \in A$ significa che $x$ si trova dentro l'insieme $A$.

Se un oggetto $y$ non è un elemento di $A$, scriviamo $y \notin A$, che si legge "$y$ non appartiene ad $A$".

Esempio: Se $F = \{\text{leone, tigre, ghepardo}\}$.
Allora, $\text{tigre} \in F$ (la tigre appartiene all'insieme F).
Ma $\text{cane} \notin F$ (il cane non appartiene all'insieme F).

2.3 Come Definiamo un Insieme?

Abbiamo principalmente due modi per specificare quali elementi compongono un insieme:

1. Per Elencazione (o Rappresentazione Estensiva): Elenchiamo semplicemente tutti gli elementi dell'insieme, separati da virgole e racchiusi tra parentesi graffe $\{\ \}$. Questo metodo è comodo per insiemi con pochi elementi.
   Esempio: L'insieme delle prime tre lettere dell'alfabeto italiano: $L = \{a, b, c\}$.
   Esempio: L'insieme dei numeri pari minori di 10: $P = \{0, 2, 4, 6, 8\}$.
2. Per Proprietà (o Rappresentazione Intensiva/Caratteristica): Indichiamo una proprietà che tutti gli elementi dell'insieme devono soddisfare, e solo loro. Si usa la notazione $\{x \mid \text{Proprietà di } x\}$ oppure $\{x : \text{Proprietà di } x\}$, che si legge "l'insieme degli $x$ tali che $x$ soddisfa quella proprietà".
   Formalmente, se $S = \{x \mid P(x)\}$, allora per ogni oggetto $y$, $y \in S \iff P(y)$ è vera.
   Esempio: L'insieme dei numeri naturali maggiori di 10: $M = \{n \mid n \in \mathbb{N} \wedge n > 10\}$.
   Esempio: L'insieme dei film diretti da Fellini: $F_{Fellini} = \{x \mid x \text{ è un film diretto da Federico Fellini}\}$.

2.4 Insiemi Speciali da Conoscere

2.4.1 L'Insieme Vuoto: Il Sacchetto Senza Nulla ($\emptyset$)

Esiste un insieme molto speciale che non contiene alcun elemento: è l'insieme vuoto. Si indica con il simbolo $\emptyset$ oppure con due parentesi graffe vuote $\{\ \}$.

• Per qualsiasi oggetto $x$, l'affermazione $x \in \emptyset$ è sempre FALSA.
• Di conseguenza, $x \notin \emptyset$ è sempre VERA.
• C'è un solo insieme vuoto. Non importa se pensiamo al "sacchetto vuoto di mele" o al "sacchetto vuoto di numeri": se è vuoto, è sempre lo stesso insieme $\emptyset$.

2.4.2 Il Singoletto: Un Solo Abitante

Un insieme che contiene esattamente un elemento è chiamato singoletto (o singleton).

Esempio: $\{gatto\}$, $\{7\}$, $\{\emptyset\}$ sono tutti singoletti.
Attenzione alla differenza: $gatto$ è un animale, mentre $\{gatto\}$ è un insieme che contiene quell'animale. Similmente, $\emptyset$ è l'insieme vuoto, mentre $\{\emptyset\}$ è un insieme che contiene come suo unico elemento l'insieme vuoto (quindi $\{\emptyset\}$ non è vuoto!).

2.5 Sottoinsiemi: Insiemi dentro Altri Insiemi ($\subseteq, \subset$)

Quando tutti gli elementi di un insieme $A$ sono anche elementi di un altro insieme $B$, diciamo che $A$ è un **sottoinsieme** di $B$. Usiamo il simbolo $\subseteq$ per indicare questa relazione: $A \subseteq B$ (si legge "$A$ è incluso in $B$" o "$A$ è contenuto o uguale a $B$").

Formalmente, $A \subseteq B \iff \forall x (x \in A \Rightarrow x \in B)$. Questo significa che se prendi un qualsiasi elemento $x$ da $A$, puoi essere sicuro che lo troverai anche in $B$.

Esempio: Sia $V = \{a, e, i, o, u\}$ (vocali) e $Alfabeto = \{a, b, c, \dots, z\}$. Allora $V \subseteq Alfabeto$.

Se $A$ è un sottoinsieme di $B$, ma $A$ non è uguale a $B$ (cioè $B$ ha almeno un elemento che $A$ non ha), allora $A$ è un **sottoinsieme proprio** di $B$. Si usa il simbolo $\subset$: $A \subset B$.

Proprietà importanti dell'inclusione:

• L'insieme vuoto è sottoinsieme di tutti: Per qualsiasi insieme $A$, $\emptyset \subseteq A$. Perché? L'implicazione "$x \in \emptyset \Rightarrow x \in A$" è sempre vera, perché la premessa "$x \in \emptyset$" è sempre falsa!
• Ogni insieme è sottoinsieme di se stesso: Per qualsiasi insieme $A$, $A \subseteq A$ (proprietà riflessiva).
• Transitività: Se $A \subseteq B$ e $B \subseteq C$, allora $A \subseteq C$. Se le matrioske piccole stanno nelle medie, e le medie nelle grandi, allora le piccole stanno nelle grandi.

2.6 Uguaglianza tra Insiemi: Quando Due Sacchetti Sono Identici?

Due insiemi $A$ e $B$ sono considerati uguali, e scriviamo $A = B$, se e solo se contengono esattamente gli stessi elementi. Non importa l'ordine o le ripetizioni, conta solo quali elementi ci sono.

Un modo molto potente e comune per dimostrare che due insiemi $A$ e $B$ sono uguali è usare la doppia inclusione: bisogna dimostrare sia che $A \subseteq B$ (tutti gli elementi di A sono in B) sia che $B \subseteq A$ (tutti gli elementi di B sono in A). Se entrambe le inclusioni sono vere, allora $A$ e $B$ devono essere lo stesso insieme.

$A = B \iff (A \subseteq B \wedge B \subseteq A)$

2.7 L'Insieme delle Parti $\mathcal{P}(A)$: L'Insieme di Tutti i Sottoinsiemi

Dato un insieme $A$, possiamo formare un nuovo insieme, chiamato insieme delle parti di $A$ (o insieme potenza), indicato con $\mathcal{P}(A)$. Gli elementi di $\mathcal{P}(A)$ sono tutti i possibili sottoinsiemi di $A$.

Formalmente: $\mathcal{P}(A) = \{X \mid X \subseteq A\}$.

Esempio 1: Se $A = \{1, 2\}$.
I sottoinsiemi di $A$ sono: $\emptyset, \{1\}, \{2\}, \{1, 2\}$.
Quindi, $\mathcal{P}(A) = \{\emptyset, \{1\}, \{2\}, \{1, 2\}\}$.

Esempio 2: Se $A = \{a,b,c\}$.
$\mathcal{P}(A) = \{\emptyset, \{a\}, \{b\}, \{c\}, \{a, b\}, \{a, c\}, \{b, c\}, \{a, b, c\}\}$.

Nota bene:

• L'insieme vuoto $\emptyset$ è sempre un elemento di $\mathcal{P}(A)$.
• L'insieme $A$ stesso è sempre un elemento di $\mathcal{P}(A)$.

Quanti elementi ha $\mathcal{P}(A)$? Se un insieme finito $A$ ha $n$ elementi (cioè, la sua cardinalità è $|A|=n$), allora il suo insieme delle parti $\mathcal{P}(A)$ ha $2^n$ elementi. Cioè, $|\mathcal{P}(A)|=2^n$.

2.8 Operazioni Fondamentali tra Insiemi

Proprio come possiamo fare addizioni e sottrazioni con i numeri, possiamo eseguire operazioni sugli insiemi per crearne di nuovi. Per queste operazioni, spesso immaginiamo che i nostri insiemi $A$ e $B$ siano contenuti in un "contesto" più grande, un **insieme universo** $\mathcal{T}$ (o $\mathcal{U}$), che contiene tutti gli elementi di cui stiamo parlando.

2.8.1 Unione ($A \cup B$) - "Mettere tutto insieme"

L'unione di due insiemi $A$ e $B$, scritta $A \cup B$, è l'insieme che contiene tutti gli elementi che si trovano in $A$, oppure in $B$, oppure in entrambi. È come svuotare il contenuto di due sacchetti in uno solo (senza duplicati).

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

Esempio: Se $A=\{1,2,3\}$ e $B=\{3,4,5\}$, allora $A \cup B = \{1,2,3,4,5\}$.

2.8.2 Intersezione ($A \cap B$) - "Solo ciò che è in comune"

L'intersezione di due insiemi $A$ e $B$, scritta $A \cap B$, è l'insieme che contiene solo gli elementi che appartengono sia ad $A$ sia a $B$ contemporaneamente. È quello che i due "sacchetti" hanno in comune.

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

Esempio: Se $A=\{1,2,3\}$ e $B=\{3,4,5\}$, allora $A \cap B = \{3\}$.

Se due insiemi non hanno elementi in comune, la loro intersezione è l'insieme vuoto ($A \cap B = \emptyset$). In tal caso, $A$ e $B$ si dicono disgiunti.

2.8.3 Complementare ($\overline{A}$ o $A^c$) - "Tutto ciò che NON è in A"

Il complementare di un insieme $A$, scritto $\overline{A}$ (o $A^c$, o a volte $A'$), è l'insieme di tutti gli elementi dell'insieme universo $\mathcal{T}$ che *non* sono in $A$.

Formalmente: $\overline{A} = \{x \in \mathcal{T} \mid x \notin A\}$.

Esempio: Se $\mathcal{T}=\{1,2,3,4,5\}$ e $A=\{1,3\}$, allora $\overline{A} = \{2,4,5\}$.

2.8.4 Differenza ($A \setminus B$) - "A senza B"

La differenza tra l'insieme $A$ e l'insieme $B$, scritta $A \setminus B$ (o $A-B$), è l'insieme degli elementi che sono in $A$ ma *non* sono in $B$. È come prendere il sacchetto $A$ e togliere tutti gli elementi che si trovano anche nel sacchetto $B$.

Formalmente: $A \setminus B = \{x \mid x \in A \wedge x \notin B\}$.

Un modo utile per pensarla è: $A \setminus B = A \cap \overline{B}$.

Esempio: Se $A=\{1,2,3,4\}$ e $B=\{3,4,5,6\}$, allora $A \setminus B = \{1,2\}$.
Mentre $B \setminus A = \{5,6\}$.

2.8.5 Differenza Simmetrica ($A \triangle B$) - "Elementi in uno solo dei due"

La differenza simmetrica tra $A$ e $B$, scritta $A \triangle B$, è l'insieme degli elementi che appartengono ad $A$ o a $B$, ma *non* a entrambi. Sono gli elementi che si trovano in un solo dei due insiemi, non nella loro parte comune.

Si può definire in due modi equivalenti:

• $A \triangle B = (A \setminus B) \cup (B \setminus A)$ (gli elementi che sono solo in A uniti a quelli che sono solo in B)
• $A \triangle B = (A \cup B) \setminus (A \cap B)$ (tutti gli elementi dei due insiemi, meno quelli che hanno in comune)

Esempio: Se $A=\{1,2,3,4\}$ e $B=\{3,4,5,6\}$, allora $A \triangle B = \{1,2,5,6\}$.

2.9 Proprietà delle Operazioni (L'Algebra degli Insiemi)

Le operazioni insiemistiche seguono delle regole precise, molto simili a quelle dell'algebra e della logica proposizionale.

• 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: $\overline{(A \cup B)} = \overline{A} \cap \overline{B}$; $\overline{(A \cap B)} = \overline{A} \cup \overline{B}$.
• Leggi del Complemento: $A \cup \overline{A} = \mathcal{T}$; $A \cap \overline{A} = \emptyset$.
• Doppio Complemento: $\overline{(\overline{A})} = A$.

2.10 Prodotto Cartesiano $A \times B$: Creare Coppie Ordinate

Il prodotto cartesiano $A \times B$ è l'insieme di tutte le possibili coppie ordinate $(a,b)$ dove il primo elemento $a$ proviene da $A$ e il secondo elemento $b$ proviene da $B$.

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

Punti chiave: L'ordine conta: $(a,b) \neq (b,a)$ (a meno che $a=b$). Due coppie $(a,b)$ e $(c,d)$ sono uguali se e solo se $a=c$ e $b=d$. Non confondere con l'insieme $\{a,b\}$.

Esempio: Siano $A = \{\text{T, C}\}$ e $B = \{1, 2\}$.
$A \times B = \{ (\text{T}, 1), (\text{T}, 2), (\text{C}, 1), (\text{C}, 2) \}$.

Se $|A|=m$ e $|B|=n$, allora $|A \times B| = m \cdot n$. Si estende a **k-uple ordinate** per $k$ insiemi.

2.11 Esercizi del Capitolo 2