Insiemi, relazioni e funzioni

Da Wikiversità, l'università aperta.

L'insieme è un concetto primitivo. Conosco un insieme quando so quali sono gli elementi che vi appartengono.

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)

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: Corrispondeza 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: Insieme

L'insieme è un concetto primitivo. Conosco un insieme quando so quali sono gli elementi che vi appartengono.

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)

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 dominiose

$\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: Corrispondeza 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) = 2 x$ 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$ .

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

Esempio: La relazione divide

La relazione divide sull'insieme

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.

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

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

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

Definizione: Partizione

Dato un insieme

A

, di dice partizione di

A

un insieme di sottoinsiemi di

A

tali che:

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

Osservazione:

Se c'è una relazione tra

x

e

y

di uno stesso blocco di partizione, allora questa è una relazione di equivalenza.

[modifica] 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,

mod (m)

Teorema:

La relazione

(x - y) = q m

è una relazione di equivalenza.

Dimostrazione:

la relazione è riflessiva, infatti per $q = 0$ si ha $(x - x) = q m = 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 $mod (m)$ coincide con la congruenza $mod ( - 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 \le r_1 < m \\ y = q_1 m + r_2 & 0 \le 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 = q m

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

[modifica] 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 + c y = b x + d y$

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 = q n m

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 $mod (m)$ con

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

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

Insiemi, relazioni e funzioni

Da Wikiversità, l'università aperta.

[modifica] Classi di resti

[modifica] Relazioni modulo $m$

Visite

Strumenti personali

Navigazione

Comunità

Ricerca

Strumenti

Insiemi, relazioni e funzioni

Da Wikiversità, l'università aperta.

[modifica] Classi di resti

[modifica] Relazioni modulo m

Visite

Strumenti personali

Navigazione

Comunità

Ricerca

Strumenti

[modifica] Relazioni modulo $m$