# Insiemi, relazioni e funzioni

Un insieme $A$ si indica con
    $A=\{a,b\}=\{b,a\}=\{a,b,a,a,b,a\}$
e non importa quale sia l'ordine o il numero di volte in cui si ripete un elemento nell'elenco.
Una sequenza $A$ si indica con
    $A=(a,b,c)$
ed è diversa dalla sequenza
    $B=(a,c,b)$
in quanto due sequenze sono equivalenti se e solo se hanno gli stessi elementi nelle stesse posizioni.
Se la n-upla contiene soltanto elementi in $\mathbb {R}$, allora si ha
    $(a_{1},a_{2},\cdots ,a_{n})\in \mathbb {R\times R\times \cdots \times R} =\mathbb {R} ^{n}$
    $A\times B=\{(a,b)|a\in A,\ b\in B\}$
$A$
$B$
$A\times B$
$A$
$B$
    $A=\{a,b,c\}$
    $B=\{0,1\}$
$C=\{(a,0)\}$
$A\times B$
$C:A\rightarrow B$
$C$
    $\forall x\in A\exists y\in B|(x,y)\in C$
$C:A\rightarrow B$
    $\forall x\in A\exists {\text{ al piu un }}y\in B|(x,y)\in C$
$C:A\rightarrow B$
    $\forall y\in B\exists x\in A|(x,y)\in C$
$C:A\rightarrow B$
    $\forall y\in B\exists {\text{ al piu un }}x\in A|(x,y)\in C$
$C:A\rightarrow B$
    $\forall x\in A\exists !y\in B|(x,y)\in C$
Nel caso in cui $C$ sia una funzione, la notazione diventa
    ${\begin{matrix}f:&A&\rightarrow &B\\&x&\rightarrow &y\end{matrix}}$
dove $f(x)=y$.
$f:A\rightarrow B$
    $Im(f)=\{y\in B|\exists x\in A|f(x)=y\}$
L'immagine di una funzione coincide con il suo codominio sse è suriettiva. Se una funzione è suriettiva, la si può chiamare suriezione; se una funzione è iniettiva, la si può chiamare iniezione.
L'iniettività di una funzione è importante. Se voglio che una funzione sia iniettiva, non deve capitare che due elementi di A finiscano nello stesso elemento di B; per dimostrare che una funzione è iniettiva si procede per assurdo, ipotizzando che non lo sia e che esistano
    $x_{1}\neq x_{2}|f(x_{1})=f(x_{2})=y$
Si otterrà che
    $f(x_{1})=f_{x_{2})\Leftrightarrow x_{1}=x_{2}$
Per esempio, in $\mathbb {N}$ i numeri pari sono una parte propria; siccome vale la funzione biunivoca $f(x)=2x$ allora $\mathbb {N}$ è infinito.
$A$
$A$
$A\times A$
* una relazione ${\mathcal {R}}$ su $A$ è riflessiva se $\forall x\in A,\ x{\mathcal {R}}x$.
* una relazione ${\mathcal {R}}$ su $A$ è simmetrica se $x{\mathcal {R}}y\Rightarrow y{\mathcal {R}}x$.
* una relazione ${\mathcal {R}}$ su $A$ è transitiva se $x{\mathcal {R}}y{\text{ e }}y{\mathcal {R}}z\Rightarrow x{\mathcal {R}}z$.
    $A=\{3,4,6,8,9\}$
* Questa relazione è riflessiva, perché ogni elemento divide se stesso.
* Questa relazione non è simmetrica, perché se 3 divide 6 non è vero che 6 divide 3.
* Questa relazione è transitiva. Questo può sembrare strano, dal momento che la tesi non è verificata; si noti, però, che non sono verificate nemmeno le ipotesi.
${\mathcal {R}}$
$A$
${\mathcal {P}}$
* ogni retta è parallela a se stessa, $x{\mathcal {P}}x$;
* se una retta è parallela ad un'altra, vale il viceversa $x{\mathcal {P}}y\Rightarrow y{\mathcal {P}}x$;
* se $r{\mathcal {P}}s{\text{ e }}s{\mathcal {P}}t\Rightarrow r{\mathcal {R}}t$.
${\mathcal {P}}$
$A$
$A$
$A$
* nessuno sia vuoto;
* sono disgiunti tra loro, la loro intersezione a due a due è nulla;
* la loro unione copre tutto $A$.
Nell'esempio delle rette, sia $[r_{1}]$ l'insieme di tutte le rette parallele a $r_{1}$. L'insieme
    $R=\{[r_{1}],[r_{2}],\cdots \}$
è una partizione di $A$.
$x$
$y$

## Classi di resti

$\mathbb {Z}$
$m\in \mathbb {Z}$
$x{\mathcal {R}}y$
    $\exists q\in \mathbb {Z} |(x-y)=qm$
${\bmod {}m)$
$(x-y)=qm$
* la relazione è riflessiva, infatti per $q=0$ si ha $(x-y)=qm=0$, quindi $x{\mathcal {R}}x$;
* la relazione è simmetrica, infatti se $\exists q|(x-y)=qm$, allora $\exists -q|(y-x)=-qm$;
* la relazione è transitiva, infatti se $\exists q_{1},q_{2}$ tali che
      * $(x-y)=q_{1}m$
      * $(y-z)=q_{2}m$
    allora si ha
       $x-y+y-z=q_{1}m+q_{2}m\Rightarrow x-z=(q_{1}+q_{2})m$
Abbiamo trovato una partizione di $\mathbb {Z}$.
Casi particolari:
* per $m=0$ gli elementi sono in relazione solo quando sono uguali, quindi ogni blocco della partizione è costituito da un solo elemento; si tratta di una partizione banale che coincide con $\mathbb {Z}$ stesso.
* per $m=1$ si ha un unico blocco;
* la congruenza ${\bmod {}m)$ coincide con la congruenza ${\bmod {}-m)$
       $x\equiv _{m}y\Rightarrow \left\{{\begin{matrix}\exists q|(x-y)=qm\\\exists -q|(y-x)=-qm\end{matrix}}\right.$
$m>1$
$x\equiv _{m}y$
$x$
$y$
$m$
    $x-y=qm\Rightarrow {\frac {x-y}{m}}=q\Rightarrow {\frac {x}{m}}-{\frac {y}{m}}=q\in \mathbb {Z}$
da cui
    ${\begin{matrix}x=q_{1}m+r_{1}&0\leq r_{1}<m\\y=q_{1}m+r_{2}&0\leq r_{2}<m\end{matrix}}$
Sia, per comodità, $r_{1}>r_{2}$. Si ha
    $(x-y)=(q_{1}-q_{2})m+r_{1}-r_{2}=qm$
$r_{1}-r_{2}$
$m$
$r_{1}=r_{2}$
$0$
$m$
$m$
Quindi, se abbiamo due valori $x$ e $y$ che, divisi per $m$, danno lo stesso resto, allora questi sono congrui ${\bmod {}m)$, $x\equiv _{m}y$.
$m=5$
$\mathbb {Z}$
$\mathbb {Z} _{5}$
    $\mathbb {Z} _{5}=\left\{\left[{\begin{matrix}0\\5\\10\\15\\.\\.\\.\end{matrix}}\right],\left[{\begin{matrix}1\\6\\11\\16\\.\\.\\.\end{matrix}}\right],\left[{\begin{matrix}2\\7\\12\\17\\.\\.\\.\end{matrix}}\right],\left[{\begin{matrix}3\\8\\13\\18\\.\\.\\.\end{matrix}}\right],\left[{\begin{matrix}4\\9\\14\\19\\.\\.\\.\end{matrix}}\right]\right\}$

### Relazioni modulo $m$

    $a\equiv _{m}b\rightarrow [a]=[b]$
    $c\equiv _{m}d\rightarrow [c]=[d]$
Allora
    $a+c\equiv _{m}b+d$
Il risultato della somma $a+c$ non dipende dal rappresentante che scelgo nella classe.
    $a\equiv _{m}b\rightarrow [a]=[b]$
    $c\equiv _{m}d\rightarrow [c]=[d]$
Allora
    $a\cdot c\equiv _{m}b\cdot d$
$[a]=[b]$
$[c]=[d]$
    $\forall x,y\in \mathbb {Z} {\text{ si ha }}ax+cy\equiv _{m}bx+dy$
    $[a]=[b]\Rightarrow \forall x\in \mathbb {Z} ,\ x\equiv _{m}x{\text{ e }}ax\equiv _{m}bx$
    $[c]=[d]\Rightarrow \forall y\in \mathbb {Z} ,\ y\equiv _{m}y{\text{ e }}cy\equiv _{m}dy$
$a\equiv _{m}b$
$a\equiv _{n}b$
$(m,n)=1$
$m$
$n$
    $a\equiv _{m\cdot n}b$
$b=0$
    $a\equiv _{m}0\Rightarrow \exists k_{1}|a=k_{1}m$
    $a\equiv _{n}0\Rightarrow \exists k_{2}|a=k_{2}n$
Allora si ha
    $a\equiv _{n}0\Rightarrow {\frac {a}{n}}={\frac {km}{n}}={\frac {k}{n}}\cdot m\Rightarrow \exists q|k=qn$
Questo perché $m$ ed $n$ sono coprimi, quindi $n$ non può dividere $m$. Abbiamo ottenuto
    $a=k_{1}m=qnm$
$a\equiv _{m\cdot n}0$
$b\neq 0$
    $\left.{\begin{matrix}a\equiv _{n}b&\Rightarrow &a-b\equiv _{n}0\\a\equiv _{m}b&\Rightarrow &a-b\equiv _{m}0\end{matrix}}\right\$
Definisco le classi di equivalenza ${\bmod {}m)$ con
    $\mathbb {Z} _{m}={\frac {\mathbb {Z} }{\equiv _{m}}}$
Questi sono gli elementi che si generano quando definisco la congruenza ${\bmod {}m)$.