Insiemi, relazioni e funzioni

Lezione precedente Materia Lezione successiva
Insiemi, proposizioni e predicati Analisi matematica Numeri naturali


Un insieme si indica con

lezione
lezione
Insiemi, relazioni e funzioni
Tipo di risorsa Tipo: lezione
Materia di appartenenza Materie:


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.


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 si indica con

ed è diversa dalla sequenza

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


Definizione: Prodotto cartesiano
Si dice prodotto cartesiano il prodotto tra due insiemi tale che



Definizione: Corrispondenza
Una corrispondenza tra due insiemi e è un qualunque sottoinsieme del loro prodotto cartesiano .



Esempio:
Siano e due insiemi, con
Una corrispondenza è , che è un sottoinsieme del prodotto cartesiano .



Definizione: Corrispondenza ovunque definita
Data una corrispondenza , è ovunque definita su ogni elemento del dominio se



Definizione: Corrispondenza funzionale
Una corrispondenza è funzionale quando



Definizione: Corrispondenza suriettiva
Una corrispondenza è suriettiva quando



Definizione: Corrispondenza iniettiva
Una corrispondenza è iniettiva quando



Definizione: Funzione
Una corrispondenza è una funzione quando è ovunque definita e funzionale, cioè


Nel caso in cui sia una funzione, la notazione diventa

dove .


Definizione: Immagine
Data una funzione , si dice immagine di f l'insieme


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

Si otterrà che


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 i numeri pari sono una parte propria; siccome vale la funzione biunivoca allora è infinito.


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



Definizione: Relazione
Dato un insieme si dice relazione su un sottoinsieme del prodotto cartesiano .
  1. una relazione su è riflessiva se .
  2. una relazione su è simmetrica se .
  3. una relazione su è transitiva se .



Esempio: La relazione "divide"
La relazione "divide" sull'insieme
  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 è 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, ;
  2. se una retta è parallela ad un'altra, vale il viceversa ;
  3. se .
Si deduce che è una relazione di equivalenza.



Definizione: Partizione
Dato un insieme , si dice partizione di un insieme di sottoinsiemi di 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 .


Nell'esempio delle rette, sia l'insieme di tutte le rette parallele a . L'insieme

è una partizione di .


Osservazione:
Se c'è una relazione tra e di uno stesso blocco di partizione, allora questa è una relazione di equivalenza.


Classi di resti

modifica


Definizione: Congruenza modulo m
Lavoriamo nell'insieme degli interi . Sia ; dico che quando
Questa è una relazione chiamata congruenza modulo m,



Teorema:
La relazione è una relazione di equivalenza.


Dimostrazione:
  1. la relazione è riflessiva, infatti per si ha , quindi ;
  2. la relazione è simmetrica, infatti se , allora ;
  3. la relazione è transitiva, infatti se tali che
allora si ha


Abbiamo trovato una partizione di .

Casi particolari:

  1. per 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 stesso.
  2. per si ha un unico blocco;
  3. la congruenza coincide con la congruenza


Teorema:
Sia . Allora sse e , divisi aritmeticamente per , danno lo stesso resto.


Dimostrazione:
Si ha

da cui

Sia, per comodità, . Si ha

da cui deve essere un multiplo di . Si ottiene che , perché è il solo multiplo di che sia anche minore di .


Quindi, se abbiamo due valori e che, divisi per , danno lo stesso resto, allora questi sono congrui , .


Esempio: La partizione con
Con si ha la partizione di chiamata , composta dai blocchi


Relazioni modulo

modifica


Proprietà: Compatibilità rispetto alla somma
Siano

Allora


Il risultato della somma non dipende dal rappresentante che scelgo nella classe.


Proprietà: Compatibilità rispetto al prodotto
Siano

Allora



Teorema:
Se e . Allora


Dimostrazione:
Questo perché



Teorema:
Siano e , con , cioè e sono primi tra loro. Allora,


Dimostrazione: Caso
Nel caso , si ha

Allora si ha

Questo perché ed sono coprimi, quindi non può dividere . Abbiamo ottenuto

cioè .



Dimostrazione: Caso
Nel caso , si ha:


Definisco le classi di equivalenza con

Questi sono gli elementi che si generano quando definisco la congruenza .