L’insieme è una struttura discreta utilizzata per rappresentare oggetti discreti
Formalmente: collezione non ordinata di oggetti, chiamati elementi dell’insieme
Un insieme può essere rappresentato mediante: lista degli elementi che lo costituiscono; definizione formale delle proprietà che caratterizzano i suoi elementi
Due insiemi si dicono uguali se e solo se sono costituiti dagli stessi elementi
Un modo alternativo per dire che $A=B$ è $\forall x \space (x \in A) \leftrightarrow (x \in B)$
Un insieme $A$ è detto sottoinsieme di un insieme $B$ se e solo se ogni elemento di $A$ è anche elemento di $B$.
Un modo alternativo per dire che $A \subseteq B$ è $\forall x \space (x \in A) \rightarrow (x \in B)$
$\emptyset \subseteq S$ cioè l’insieme vuoto è sottoinsieme di qualunque insieme
dim: dobbiamo far vedere che $\forall x \space (x \in \emptyset) \rightarrow (x \in S)$
Poichè $\emptyset$ non contiene alcun elemento allora $x \in \emptyset$ è sempre falsa, ma una implicazione è sempre vera se l’ipotesi è falsa, quindi $\forall x \space ( x \in \emptyset) \rightarrow (x \in S)$ è vera
Un insieme $A$ è detto sottoinsieme proprio di $B$ se e solo se $A \subseteq B$ e $A \neq B$
Sia $S$ un insieme e sia $n$ un intero non negativo. Se ci sono esattamente $n$ distinti elementi in $S$, diciamo che $n$ è la cardinalità di $S$, e la indichiamo con $|S|$
Un insieme si dice infinito se la sua cardinalità è infinita