Insiemi, relazioni e funzioni

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.

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.

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 $ℝ$, allora si ha

$(a_1,a_2,\cdots ,a_n)\in ℝ\mathbb{\times }ℝ\mathbb{\times }\mathbb{\cdots }\mathbb{\times }ℝ={ℝ}^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\to B$, $C$ è ovunque definita su ogni elemento del dominio se

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

Definizione: Corrispondenza funzionale

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

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

Definizione: Corrispondenza suriettiva

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

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

Definizione: Corrispondenza iniettiva

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

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

Definizione: Funzione

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

$\mathrm{\forall }x\in A\mathrm{\exists }!y\in B|(x,y)\in C$

Nel caso in cui $C$ sia una funzione, la notazione diventa

$\begin{array}{cccc}f:& A& \to & B\\ & x& \to & y\end{array}$

dove $f(x)=y$.

Definizione: Immagine

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

$Im(f)=\{y\in B|\mathrm{\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\ne x_2|f(x_1)=f(x_2)=y$

Si otterrà che

$f(x_1)=f_{(}{x}_2)\iff 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 $ℛ$ su $A$ è riflessiva se $\mathrm{\forall }x\in A,xℛx$.
2. una relazione $ℛ$ su $A$ è simmetrica se $xℛy\Rightarrow yℛx$.
3. una relazione $ℛ$ su $A$ è transitiva se $xℛy\text{ e }yℛz\Rightarrow xℛ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 $ℛ$ su $A$ è di equivalenza quando è riflessiva, simmetrica e transitiva.

Esempio: La relazione di parallelismo

Sia $𝒫$ la relazione di parallelismo tra rette. Allora si ha

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

Si deduce che $𝒫$ è 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ℛy$ quando

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

Questa è una relazione chiamata congruenza modulo m, $mod(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ℛx$;
2. la relazione è simmetrica, infatti se $\mathrm{\exists }q|(x-y)=qm$, allora $\mathrm{\exists }-q|(y-x)=-qm$;
3. la relazione è transitiva, infatti se $\mathrm{\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 $mod(m)$ coincide con la congruenza $mod(-m)$

$x{\equiv }_{m}y\Rightarrow \{\begin{array}{c}\mathrm{\exists }q|(x-y)=qm\\ \mathrm{\exists }-q|(y-x)=-qm\end{array}$

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{array}{cc}x=q_{1}m+r_1& 0\le r_1<m\\ y=q_{1}m+r_2& 0\le r_2<m\end{array}$

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 $mod(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[\begin{array}{c}0\\ 5\\ 10\\ 15\\ .\\ .\\ .\end{array}\right],\left[\begin{array}{c}1\\ 6\\ 11\\ 16\\ .\\ .\\ .\end{array}\right],\left[\begin{array}{c}2\\ 7\\ 12\\ 17\\ .\\ .\\ .\end{array}\right],\left[\begin{array}{c}3\\ 8\\ 13\\ 18\\ .\\ .\\ .\end{array}\right],\left[\begin{array}{c}4\\ 9\\ 14\\ 19\\ .\\ .\\ .\end{array}\right]\}$

Relazioni modulo $m$

Proprietà: Compatibilità rispetto alla somma

Siano

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

$c{\equiv }_{m}d\to [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\to [a]=[b]$

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

Allora

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

Teorema:

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

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

Dimostrazione:

Questo perché

$[a]=[b]\Rightarrow \mathrm{\forall }x\in \mathbb{Z},x{\equiv }_{m}x\text{ e }ax{\equiv }_{m}bx$

$[c]=[d]\Rightarrow \mathrm{\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 \mathrm{\exists }{k}_1|a=k_{1}m$

$a{\equiv }_{n}0\Rightarrow \mathrm{\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 \mathrm{\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\ne 0$

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

$\begin{array}{ccc}a{\equiv }_{n}b& \Rightarrow & a-b{\equiv }_{n}0\\ a{\equiv }_{m}b& \Rightarrow & a-b{\equiv }_{m}0\end{array}\}a-b{\equiv }_{m\cdot n}0\Rightarrow a{\equiv }_{m\cdot n}b$

Definisco le classi di equivalenza $mod(m)$ con

${\mathbb{Z}}_m=\frac{\mathbb{Z}}{{\equiv }_m}$

Questi sono gli elementi che si generano quando definisco la congruenza $mod(m)$.