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
si indica con
![{\displaystyle A=\{a,b\}=\{b,a\}=\{a,b,a,a,b,a\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/154a88d28809d50554e9115d65936d5e5662d053)
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
![{\displaystyle A=(a,b,c)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3ae8fc88ac1f25dff16d5fefbfa61695228558f5)
ed è diversa dalla sequenza
![{\displaystyle B=(a,c,b)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5b942e2c44118904b52bda01f242dee8ec17363b)
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
![{\displaystyle (a_{1},a_{2},\cdots ,a_{n})\in \mathbb {R\times R\times \cdots \times R} =\mathbb {R} ^{n}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c0d299301178f5049039ed5bfc0586c542fe5c64)
Definizione: Prodotto cartesiano
Si dice prodotto cartesiano il prodotto tra due insiemi tale che
![{\displaystyle A\times B=\{(a,b)|a\in A,\ b\in B\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e738a770990190a5de1e40641d57947cd4804a22)
Definizione: Corrispondenza
Una corrispondenza tra due insiemi
![{\displaystyle A}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7daff47fa58cdfd29dc333def748ff5fa4c923e3)
e
![{\displaystyle B}](https://wikimedia.org/api/rest_v1/media/math/render/svg/47136aad860d145f75f3eed3022df827cee94d7a)
è un qualunque sottoinsieme del loro prodotto cartesiano
![{\displaystyle A\times B}](https://wikimedia.org/api/rest_v1/media/math/render/svg/65f31ae45b0098f06b5d22c38d317eb097a88fa9)
.
Esempio:
Siano
![{\displaystyle A}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7daff47fa58cdfd29dc333def748ff5fa4c923e3)
e
![{\displaystyle B}](https://wikimedia.org/api/rest_v1/media/math/render/svg/47136aad860d145f75f3eed3022df827cee94d7a)
due insiemi, con
![{\displaystyle A=\{a,b,c\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/06b9d8908ec344da80af17b035774ba65e9cc818)
![{\displaystyle B=\{0,1\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f582e459b750046ded8517cf592c0b5adb5247ca)
Una corrispondenza è
![{\displaystyle C=\{(a,0)\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9aa9374d9b5848fb965fc75d450306742305716b)
, che è un sottoinsieme del prodotto cartesiano
![{\displaystyle A\times B}](https://wikimedia.org/api/rest_v1/media/math/render/svg/65f31ae45b0098f06b5d22c38d317eb097a88fa9)
.
Definizione: Corrispondenza ovunque definita
Data una corrispondenza
![{\displaystyle C:A\rightarrow B}](https://wikimedia.org/api/rest_v1/media/math/render/svg/10c134bf65121b7e8646cdcc104595217afbd41a)
,
![{\displaystyle C}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4fc55753007cd3c18576f7933f6f089196732029)
è ovunque definita su ogni elemento del dominio se
![{\displaystyle \forall x\in A\exists y\in B|(x,y)\in C}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ed6dfef1a32b25e75c4e37d3aa7241659997c946)
Definizione: Corrispondenza funzionale
Una corrispondenza
![{\displaystyle C:A\rightarrow B}](https://wikimedia.org/api/rest_v1/media/math/render/svg/10c134bf65121b7e8646cdcc104595217afbd41a)
è funzionale quando
![{\displaystyle \forall x\in A\exists {\text{ al piu un }}y\in B|(x,y)\in C}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2d31de267453f13b992464709884eda1116b013e)
Definizione: Corrispondenza suriettiva
Una corrispondenza
![{\displaystyle C:A\rightarrow B}](https://wikimedia.org/api/rest_v1/media/math/render/svg/10c134bf65121b7e8646cdcc104595217afbd41a)
è suriettiva quando
![{\displaystyle \forall y\in B\exists x\in A|(x,y)\in C}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e05db1694214f8b69dffdf224ed3fd1bf322680b)
Definizione: Corrispondenza iniettiva
Una corrispondenza
![{\displaystyle C:A\rightarrow B}](https://wikimedia.org/api/rest_v1/media/math/render/svg/10c134bf65121b7e8646cdcc104595217afbd41a)
è iniettiva quando
![{\displaystyle \forall y\in B\exists {\text{ al piu un }}x\in A|(x,y)\in C}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f5e2033438722753a5949b0c37cabde369c7975a)
Definizione: Funzione
Una corrispondenza
![{\displaystyle C:A\rightarrow B}](https://wikimedia.org/api/rest_v1/media/math/render/svg/10c134bf65121b7e8646cdcc104595217afbd41a)
è una funzione quando è ovunque definita e funzionale, cioè
![{\displaystyle \forall x\in A\exists !y\in B|(x,y)\in C}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8c60236790ff075aa8e6c120b3c8e153e691d0dc)
Nel caso in cui
sia una funzione, la notazione diventa
![{\displaystyle {\begin{matrix}f:&A&\rightarrow &B\\&x&\rightarrow &y\end{matrix}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/cfd4cf8331c92369a1f1fce831b3331f4d8c6e2f)
dove
.
Definizione: Immagine
Data una funzione
![{\displaystyle f:A\rightarrow B}](https://wikimedia.org/api/rest_v1/media/math/render/svg/aa2fb4d5e9d282ee5442719053c46ad1ad96f2ca)
, si dice immagine di f l'insieme
![{\displaystyle Im(f)=\{y\in B|\exists x\in A|f(x)=y\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2a0bb611c5751cf6e49542604b2126ca7ce6000d)
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
![{\displaystyle x_{1}\neq x_{2}|f(x_{1})=f(x_{2})=y}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9267cbdc0e5ae66a0b21f00aa52e1add99a5a69f)
Si otterrà che
![{\displaystyle f(x_{1})=f_{(}x_{2})\Leftrightarrow x_{1}=x_{2}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0bec304bb0a4e4148a416d1ff47cf3575d153148)
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
Esempio: La relazione "divide"
La relazione "divide" sull'insieme
![{\displaystyle A=\{3,4,6,8,9\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/24579fbe85b3baa702eadd6587ad53337efaabfe)
- 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
![{\displaystyle {\mathcal {R}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/74532dc308c806964b832df0d0d73352195c2f2f)
su
![{\displaystyle A}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7daff47fa58cdfd29dc333def748ff5fa4c923e3)
è di equivalenza quando è riflessiva, simmetrica e transitiva.
Esempio: La relazione di parallelismo
Sia
![{\displaystyle {\mathcal {P}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/10d6ec962de5797ba4f161c40e66dca74ae95cc6)
la relazione di parallelismo tra rette. Allora si ha
- ogni retta è parallela a se stessa,
;
- se una retta è parallela ad un'altra, vale il viceversa
;
- se
.
Si deduce che
![{\displaystyle {\mathcal {P}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/10d6ec962de5797ba4f161c40e66dca74ae95cc6)
è una relazione di equivalenza.
Definizione: Partizione
Dato un insieme
![{\displaystyle A}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7daff47fa58cdfd29dc333def748ff5fa4c923e3)
, si dice partizione di
![{\displaystyle A}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7daff47fa58cdfd29dc333def748ff5fa4c923e3)
un insieme di sottoinsiemi di
![{\displaystyle A}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7daff47fa58cdfd29dc333def748ff5fa4c923e3)
tali che:
- nessuno sia vuoto;
- sono disgiunti tra loro, la loro intersezione a due a due è nulla;
- la loro unione copre tutto
.
Nell'esempio delle rette, sia
l'insieme di tutte le rette parallele a
. L'insieme
![{\displaystyle R=\{[r_{1}],[r_{2}],\cdots \}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a17ee2f4507bbd6c45c5e78445c347bf099ba946)
è una partizione di
.
Osservazione:
Se c'è una relazione tra
![{\displaystyle x}](https://wikimedia.org/api/rest_v1/media/math/render/svg/87f9e315fd7e2ba406057a97300593c4802b53e4)
e
![{\displaystyle y}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b8a6208ec717213d4317e666f1ae872e00620a0d)
di uno stesso blocco di partizione, allora questa è una relazione di equivalenza.
Definizione: Congruenza modulo m
Lavoriamo nell'insieme degli interi
![{\displaystyle \mathbb {Z} }](https://wikimedia.org/api/rest_v1/media/math/render/svg/449494a083e0a1fda2b61c62b2f09b6bee4633dc)
. Sia
![{\displaystyle m\in \mathbb {Z} }](https://wikimedia.org/api/rest_v1/media/math/render/svg/12e01e20e2bc24ab21cca6a82edddec5c1a20ec5)
; dico che
![{\displaystyle x{\mathcal {R}}y}](https://wikimedia.org/api/rest_v1/media/math/render/svg/370b2c18e8e1c2db937f9f4d034c97bbf2ab0a53)
quando
![{\displaystyle \exists q\in \mathbb {Z} |(x-y)=qm}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e45c78650304b5290b401d905336bc58ea3e661f)
Questa è una relazione chiamata congruenza modulo m,
![{\displaystyle {\bmod {(}}m)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/86ccb9a4576f8fffe17ed5a49ef1ea1a9a20db69)
Teorema:
La relazione
![{\displaystyle (x-y)=qm}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7cedf343dac594c611804f42b6756d3e9e82497c)
è una relazione di equivalenza.
Abbiamo trovato una partizione di
.
Casi particolari:
- 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.
- per
si ha un unico blocco;
- la congruenza
coincide con la congruenza ![{\displaystyle {\bmod {(}}-m)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a7cc3c4c06cbc47c48368a373e7ab5474539dbce)
![{\displaystyle x\equiv _{m}y\Rightarrow \left\{{\begin{matrix}\exists q|(x-y)=qm\\\exists -q|(y-x)=-qm\end{matrix}}\right.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8b2f203aa6043e4ac911364f6babc8aa7052e98b)
Teorema:
Sia
![{\displaystyle m>1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7f27527902d05e4c32bcbe28d425d7790f8ae191)
. Allora
![{\displaystyle x\equiv _{m}y}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ecec446a442f2c0873197c41f88c27c872bedcd0)
sse
![{\displaystyle x}](https://wikimedia.org/api/rest_v1/media/math/render/svg/87f9e315fd7e2ba406057a97300593c4802b53e4)
e
![{\displaystyle y}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b8a6208ec717213d4317e666f1ae872e00620a0d)
, divisi aritmeticamente per
![{\displaystyle m}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0a07d98bb302f3856cbabc47b2b9016692e3f7bc)
, danno lo stesso resto.
Dimostrazione:
Si ha
![{\displaystyle x-y=qm\Rightarrow {\frac {x-y}{m}}=q\Rightarrow {\frac {x}{m}}-{\frac {y}{m}}=q\in \mathbb {Z} }](https://wikimedia.org/api/rest_v1/media/math/render/svg/ea65d780dc01e45f7ffecee64356e2038bd021e0)
da cui
![{\displaystyle {\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/59300657a69e2f931f645c64f0e8152f72314116)
Sia, per comodità,
. Si ha
![{\displaystyle (x-y)=(q_{1}-q_{2})m+r_{1}-r_{2}=qm}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2ce5be061cc49cfa710393df9af32b8fef5e69c4)
da cui
![{\displaystyle r_{1}-r_{2}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e8a339cf7e9ec26cfd9e9781efd47d02235cfb70)
deve essere un multiplo di
![{\displaystyle m}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0a07d98bb302f3856cbabc47b2b9016692e3f7bc)
. Si ottiene che
![{\displaystyle r_{1}=r_{2}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/3db82f906d16ec501981ca7c15ae6fd91e3dbe77)
, perché
![{\displaystyle 0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2aae8864a3c1fec9585261791a809ddec1489950)
è il solo multiplo di
![{\displaystyle m}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0a07d98bb302f3856cbabc47b2b9016692e3f7bc)
che sia anche minore di
![{\displaystyle m}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0a07d98bb302f3856cbabc47b2b9016692e3f7bc)
.
Quindi, se abbiamo due valori
e
che, divisi per
, danno lo stesso resto, allora questi sono congrui
,
.
Esempio:
La partizione con ![{\displaystyle m=5}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ed436becdbbbc62c94b057f6922d53e6df39d67b)
Con
![{\displaystyle m=5}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ed436becdbbbc62c94b057f6922d53e6df39d67b)
si ha la partizione di
![{\displaystyle \mathbb {Z} }](https://wikimedia.org/api/rest_v1/media/math/render/svg/449494a083e0a1fda2b61c62b2f09b6bee4633dc)
chiamata
![{\displaystyle \mathbb {Z} _{5}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/20e64a4b3b4926087c2691c2db517c2d9ba465ea)
, composta dai blocchi
Relazioni modulo ![{\displaystyle m}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0a07d98bb302f3856cbabc47b2b9016692e3f7bc)
[modifica]
Proprietà: Compatibilità rispetto alla somma
Siano
![{\displaystyle a\equiv _{m}b\rightarrow [a]=[b]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0deab87736132f6d6e5c08aae049cac2e9a2cb98)
![{\displaystyle c\equiv _{m}d\rightarrow [c]=[d]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5b14fd77d944c963932503a720b33f1f2ece2c38)
Allora
![{\displaystyle a+c\equiv _{m}b+d}](https://wikimedia.org/api/rest_v1/media/math/render/svg/618e1b3f8cd3c4ea15b28829f85dd724daded609)
Il risultato della somma
non dipende dal rappresentante che scelgo nella classe.
Proprietà: Compatibilità rispetto al prodotto
Siano
![{\displaystyle a\equiv _{m}b\rightarrow [a]=[b]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0deab87736132f6d6e5c08aae049cac2e9a2cb98)
![{\displaystyle c\equiv _{m}d\rightarrow [c]=[d]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5b14fd77d944c963932503a720b33f1f2ece2c38)
Allora
Teorema:
Se
![{\displaystyle [a]=[b]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/410d2187c04d4e54d4ccec24556a76fd427a93aa)
e
![{\displaystyle [c]=[d]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2edfa99d27353e231deedbe9ff4aab563d9c8fa9)
. Allora
![{\displaystyle \forall x,y\in \mathbb {Z} {\text{ si ha }}ax+cy\equiv _{m}bx+dy}](https://wikimedia.org/api/rest_v1/media/math/render/svg/22e555627807498c15d73b43ad28bf646dda8991)
Dimostrazione:
Questo perché
![{\displaystyle [a]=[b]\Rightarrow \forall x\in \mathbb {Z} ,\ x\equiv _{m}x{\text{ e }}ax\equiv _{m}bx}](https://wikimedia.org/api/rest_v1/media/math/render/svg/40fdde4df5a5ef05a38603a583bebad0c4ac50f2)
![{\displaystyle [c]=[d]\Rightarrow \forall y\in \mathbb {Z} ,\ y\equiv _{m}y{\text{ e }}cy\equiv _{m}dy}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b6414a14bdaa5ece5d9739e8559da1ab45448967)
Teorema:
Siano
![{\displaystyle a\equiv _{m}b}](https://wikimedia.org/api/rest_v1/media/math/render/svg/71643235c85f27cc0c2ff43275c778b124374bfb)
e
![{\displaystyle a\equiv _{n}b}](https://wikimedia.org/api/rest_v1/media/math/render/svg/96052e7fa0036e4ac0351df262e269811bab121c)
, con
![{\displaystyle (m,n)=1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/151889e4945063abb213dbff4e677f4a6bf3fead)
, cioè
![{\displaystyle m}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0a07d98bb302f3856cbabc47b2b9016692e3f7bc)
e
![{\displaystyle n}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a601995d55609f2d9f5e233e36fbe9ea26011b3b)
sono
primi tra loro. Allora,
![{\displaystyle a\equiv _{m\cdot n}b}](https://wikimedia.org/api/rest_v1/media/math/render/svg/42d61db79f4d3330be580f7e0667e772320cc93f)
Dimostrazione:
Caso ![{\displaystyle b=0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/19206e7d4dab695ccb34c502eff0741e98dbdfc2)
Dimostrazione:
Caso ![{\displaystyle b\neq 0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ad073253b4c817f2ec7e3dd7517b7f89a8e581dc)
Nel caso
![{\displaystyle b\neq 0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ad073253b4c817f2ec7e3dd7517b7f89a8e581dc)
, si ha:
Definisco le classi di equivalenza
con
![{\displaystyle \mathbb {Z} _{m}={\frac {\mathbb {Z} }{\equiv _{m}}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2813d8284461b748a06968b452334a8b16dea28b)
Questi sono gli elementi che si generano quando definisco la congruenza
.