Funzioni

Una funzione mette in relazione oggetti appartenenti ad un insieme con oggetti appartenenti ad un altro insieme (non necessariamente diverso dal primo)

Siano $A$ e $B$ due insiemi. Una funzione da $A$ in $B$, denotata con $f: A\rightarrow B$, associa ciascun elemento di $A$ con esattamente un elemento di $B$

• una funzione è detta iniettiva se e solo se $f(x) = f(y) \Rightarrow x = y$ per ogni x e y nel dominio di f
• una funzione è detta suriettiva se e solo se $\forall b \in B \space \exist a \in A : f(a) =b$
• una funzione è detta biettiva se è iniettiva e suriettiva

Cardinalità

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$, denotata con $|S|$

Definizione alternativa: due insiemi $A$ e $B$ hanno la stessa cardinalità se esiste una corrispondenza uno a uno tra gli elementi di $A$ e quelli di $B$, cioè se esiste una biezione tra $A$ e $B$

Insiemi numerabili

Un insieme che è finito o ha la stessa cardinalità di $\mathbb Z^+$ è detto numerabile, cioè se i suoi elementi possono essere enumerati

Teorema

L’insieme degli interi $\mathbb Z$ è numerabile

dim: dobbiamo far vedere che c’è una funzione biettiva $f: \mathbb Z^+ \rightarrow \mathbb Z$

definiamo la funzione $f: x \in \mathbb Z^+ \rightarrow \begin{cases} \frac{x}{2} \text{ se x è pari} \\-\frac{(x-1)}{2} \text{ se x è dispari} \end{cases}$

• $f$ è iniettiva perchè:

  $f(x) = f(y) \Rightarrow \frac{x}{2} = \frac{y}{2} \Rightarrow x=y$ (se $x$ e $y$ sono pari)

  $f(x)=f(y) \Rightarrow -\frac{(x-1)}{2} = -\frac{(y-1)}{2} \Rightarrow x=y$ (se $x$ e $y$ sono dispari)

• $f$ è suriettiva perchè:

  $\forall z \in \mathbb Z$ $2z$ è un intero pari positivo (se $z$ è positivo)

  $-2z+1$ è un intero dispari positivo (se $z$ è negativo)

Quindi $|\mathbb Z| = |\mathbb Z^+|$

Teorema

I numeri razionali positivi sono numerabili