Insiemi, relazioni e funzioni

Un insieme $A$ si indica con

Definizione: Insieme

L'insieme è un concetto primitivo. Conosco un insieme quando so quali sono gli elementi che vi appartengono oppure quando conosco quali proprietà tali elementi devono soddisfare.

$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.

Definizione: Sequenza

Una sequenza è una n-upla ordinata di elementi.

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}$

Definizione: Prodotto cartesiano

Si dice prodotto cartesiano il prodotto tra due insiemi tale che

$A\times B=\{(a,b)|a\in A,\ b\in B\}$

Definizione: Corrispondenza

Una corrispondenza tra due insiemi $A$ e $B$ è un qualunque sottoinsieme del loro prodotto cartesiano $A\times B$.

Esempio:

Siano $A$ e $B$ due insiemi, con

$A=\{a,b,c\}$

$B=\{0,1\}$

Una corrispondenza è $C=\{(a,0)\}$, che è un sottoinsieme del prodotto cartesiano $A\times B$.

Definizione: Corrispondenza ovunque definita

Data una corrispondenza $C:A\rightarrow B$, $C$ è ovunque definita su ogni elemento del dominio se

$\forall x\in A\exists y\in B|(x,y)\in C$

Definizione: Corrispondenza funzionale

Una corrispondenza $C:A\rightarrow B$ è funzionale quando

$\forall x\in A\exists {\text{ al piu un }}y\in B|(x,y)\in C$

Definizione: Corrispondenza suriettiva

Una corrispondenza $C:A\rightarrow B$ è suriettiva quando

$\forall y\in B\exists x\in A|(x,y)\in C$

Definizione: Corrispondenza iniettiva

Una corrispondenza $C:A\rightarrow B$ è iniettiva quando

$\forall y\in B\exists {\text{ al piu un }}x\in A|(x,y)\in C$

Definizione: Funzione

Una corrispondenza $C:A\rightarrow B$ è una funzione quando è ovunque definita e funzionale, cioè

$\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$.

Definizione: Immagine

Data una funzione $f:A\rightarrow B$ , si dice immagine di f l'insieme

$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}$

Definizione: Funzione biunivoca

Quando tutte e quattro le proprietà sono verificate, allora la funzione è detta biunivoca, cioè c'è una corrispondenza 1 a 1 tra gli elementi di A e gli elementi di B.

Definizione: Insieme infinito

Un insieme è infinito quando può essere messo in corrispondenza biunivoca con una sua parte propria.

Per esempio, in $\mathbb {N}$ i numeri pari sono una parte propria; siccome vale la funzione biunivoca $f(x)=2x$ allora $\mathbb {N}$ è infinito.

Osservazione:

L'inverso di una funzione biunivoca è un'altra funzione biunivoca.

Definizione: Relazione

Dato un insieme $A$ si dice relazione su $A$ un sottoinsieme del prodotto cartesiano $A\times A$.

1. una relazione ${\mathcal {R}}$ su $A$ è riflessiva se $\forall x\in A,\ x{\mathcal {R}}x$.
2. una relazione ${\mathcal {R}}$ su $A$ è simmetrica se $x{\mathcal {R}}y\Rightarrow y{\mathcal {R}}x$.
3. una relazione ${\mathcal {R}}$ su $A$ è transitiva se $x{\mathcal {R}}y{\text{ e }}y{\mathcal {R}}z\Rightarrow x{\mathcal {R}}z$.

Esempio: La relazione "divide"

La relazione "divide" sull'insieme

$A=\{3,4,6,8,9\}$

1. Questa relazione è riflessiva, perché ogni elemento divide se stesso.
2. Questa relazione non è simmetrica, perché se 3 divide 6 non è vero che 6 divide 3.
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.

Definizione: Relazione di equivalenza

Una relazione ${\mathcal {R}}$ su $A$ è di equivalenza quando è riflessiva, simmetrica e transitiva.

Esempio: La relazione di parallelismo

Sia ${\mathcal {P}}$ la relazione di parallelismo tra rette. Allora si ha

1. ogni retta è parallela a se stessa, $x{\mathcal {P}}x$;
2. se una retta è parallela ad un'altra, vale il viceversa $x{\mathcal {P}}y\Rightarrow y{\mathcal {P}}x$;
3. se $r{\mathcal {P}}s{\text{ e }}s{\mathcal {P}}t\Rightarrow r{\mathcal {R}}t$.

Si deduce che ${\mathcal {P}}$ è una relazione di equivalenza.

Definizione: Partizione

Dato un insieme $A$, si dice partizione di $A$ un insieme di sottoinsiemi di $A$ tali che:

1. nessuno sia vuoto;
2. sono disgiunti tra loro, la loro intersezione a due a due è nulla;
3. 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$.

Osservazione:

Se c'è una relazione tra $x$ e $y$ di uno stesso blocco di partizione, allora questa è una relazione di equivalenza.

Classi di resti

Definizione: Congruenza modulo m

Lavoriamo nell'insieme degli interi $\mathbb {Z}$. Sia $m\in \mathbb {Z}$; dico che $x{\mathcal {R}}y$ quando

$\exists q\in \mathbb {Z} |(x-y)=qm$

Questa è una relazione chiamata congruenza modulo m, ${\bmod {(}}m)$

Teorema:

La relazione $(x-y)=qm$ è una relazione di equivalenza.

Dimostrazione:

1. la relazione è riflessiva, infatti per $q=0$ si ha $(x-y)=qm=0$, quindi $x{\mathcal {R}}x$;
2. la relazione è simmetrica, infatti se $\exists q|(x-y)=qm$, allora $\exists -q|(y-x)=-qm$;
3. 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:

1. 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.
2. per $m=1$ si ha un unico blocco;
3. 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.$

Teorema:

Sia $m>1$. Allora $x\equiv _{m}y$ sse $x$ e $y$, divisi aritmeticamente per $m$, danno lo stesso resto.

Dimostrazione:

Si ha

$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$

da cui $r_{1}-r_{2}$ deve essere un multiplo di $m$. Si ottiene che $r_{1}=r_{2}$, perché $0$ è il solo multiplo di $m$ che sia anche minore di $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$.

Esempio: La partizione con $m=5$

Con $m=5$ si ha la partizione di $\mathbb {Z}$ chiamata $\mathbb {Z} _{5}$, composta dai blocchi

$\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$

Proprietà: Compatibilità rispetto alla somma

Siano

$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.

Proprietà: Compatibilità rispetto al prodotto

Siano

$a\equiv _{m}b\rightarrow [a]=[b]$

$c\equiv _{m}d\rightarrow [c]=[d]$

Allora

$a\cdot c\equiv _{m}b\cdot d$

Teorema:

Se $[a]=[b]$ e $[c]=[d]$. Allora

$\forall x,y\in \mathbb {Z} {\text{ si ha }}ax+cy\equiv _{m}bx+dy$

Dimostrazione:

Questo perché

$[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$

Teorema:

Siano $a\equiv _{m}b$ e $a\equiv _{n}b$, con $(m,n)=1$, cioè $m$ e $n$ sono primi tra loro. Allora,

$a\equiv _{m\cdot n}b$

Dimostrazione: Caso $b=0$

Nel caso $b=0$, si ha

$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$

cioè $a\equiv _{m\cdot n}0$.

Dimostrazione: Caso $b\neq 0$

Nel caso $b\neq 0$, si ha:

$\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\}a-b\equiv _{m\cdot n}0\Rightarrow a\equiv _{m\cdot n}b$

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)$.