Biiezione

In matematica , una biiezione sta applicando un biettivo . Un'applicazione è biiettiva se ogni elemento del suo insieme di arrivo ha uno e un solo antecedente , vale a dire è l' immagine di esattamente un elemento (del suo dominio di definizione ), o se è iniettivo e suriettivo . Le biiezioni sono talvolta chiamate anche partite uno a uno .

Si può notare che in questa definizione non si impone alcuna condizione agli elementi del set di partenza , se non quella che definisce un'applicazione: ogni elemento ha un'immagine e una sola.

Se esiste una biiezione f da un insieme E in un insieme F allora ne esiste una da F ad E : la reciproca biiezione di f , che ad ogni elemento di F associa il suo antecedente con f . Possiamo quindi dire che questi insiemi sono in biiezione o equipotenti .

Cantor ha prima dimostrato che se c'è un'iniezione da E a F e un'iniezione da F a E (non necessariamente suriettiva), allora E ed F sono equipotenti (questo è il teorema di Cantor-Bernstein ).

Se due insiemi finiti sono equipotenti, hanno lo stesso numero di elementi. L'estensione di questa equivalenza agli insiemi infiniti ha portato al concetto di cardinale di un insieme, e distingue diverse dimensioni di insiemi infiniti, che sono classi di equipotenza. Quindi, per esempio, possiamo mostrare che l'insieme dei numeri naturali è della stessa dimensione dell'insieme dei numeri razionali , ma di dimensione strettamente minore dell'insieme dei numeri reali . In effetti, da dentro , ci sono iniezioni ma nessuna sovraiezione. $\ mathbb {N}$ $\ mathbb {R}$

Definizioni formali

Definizione funzionale

Una mappa è biiettiva se ogni elemento dell'insieme di arrivo ha esattamente un antecedente (in ) di , che è formalmente scritto: $f: E \ a F$ $F$ $E$ $f$

{\ displaystyle \ forall y \ in F, \ \ exist! \ x \ in E, \ quad f (x) = y}

oppure, che è equivalente, se esiste un'applicazione che, composta a sinistra oa destra da , fornisce l' identità dell'applicazione : ${\ displaystyle g: F \ to E}$ $f$

{\ Displaystyle g \ circ f = \ operatorname {id} _ {E}}

e ,

{\ Displaystyle f \ circ g = \ operatorname {id} _ {F}}

cioè:

{\ Displaystyle \ forall x \ in E, \ \ forall y \ in F, \ quad f (x) = y \ Longleftrightarrow g (y) = x}

Tale applicazione viene quindi determinata in modo univoco da . Lo chiamiamo biiezione reciproca di e lo scriviamo . È anche una biiezione, e il suo contrario lo è . $g$ $f$ $f$ $f ^ {- 1}$ $f$

Definizione relazionale

Una biiezione di into è una relazione binaria di in cui è un'applicazione e la cui relazione reciproca è anche un'applicazione. Più in dettaglio, deve avere le seguenti quattro proprietà: $E$ $F$ $R$ $E$ $F$ $R ^ {- 1}$ $R$

Funzionalità : qualsiasi elemento di ha al massimo un'immagine per , ad es. $E$ $R$

{\ Displaystyle \ forall x \ in E, \ \ forall y, y '\ in F, \ quad [(xRy {\ text {and}} xRy') \ Rightarrow y = y ']}

;

Applicatività : ogni elemento di ha almeno un'immagine di , vale a dire $E$ $R$

{\ Displaystyle \ forall x \ in E, \ \ esiste y \ in F, \ quad xRy}

;

Iniettività : qualsiasi elemento di ha al massimo un antecedente da , vale a dire $F$ $R$

{\ displaystyle \ forall x, x '\ in E, \ \ forall y \ in F, \ quad [(xRy {\ text {and}} x'Ry) \ Rightarrow x = x']}

Surjectivity : ogni elemento di ha almeno un antecedente by , vale a dire $F$ $R$

{\ displaystyle \ forall y \ in F, \ \ exist x \ in E, \ quad xRy}

L'iniettività di è equivalente alla funzionalità di e la suriettività di è equivalente all'applicabilità di . $R$ $R ^ {- 1}$ $R$ $R ^ {- 1}$

È normale rappresentare una relazione binaria funzionale mediante una funzione ponendo $R$ $f$

{\ displaystyle \ forall x \ in E, \ \ forall y \ in F, \ quad f (x) = y \ Longleftrightarrow xRy}

Se specifichiamo che è un'applicazione , assumiamo che sia funzionale e applicativa (vedi Application_ (matematica) #Function_and_application per le differenze tra applicazione e funzione , che possono variare a seconda degli autori). $f$ $R$

La simmetria tra funzionalità e iniettività da un lato, e tra applicatività e suriettività dall'altro, dà che se è una relazione biiettiva, allora lo è anche. $R$ $R ^ {- 1}$

Esempio concreto

Prendiamo il caso di un luogo di villeggiatura in cui un gruppo di turisti deve essere alloggiato in un hotel. Ogni modo di distribuire questi turisti nelle stanze dell'hotel può essere rappresentato da un'applicazione dell'insieme X dei turisti all'insieme Y delle stanze (ogni turista è associato ad una stanza).

L'albergatore vuole che la domanda sia suriettiva , cioè che ogni camera sia occupata . Questo è possibile solo se ci sono almeno tanti turisti quante sono le stanze.
I turisti vogliono che l'applicazione sia iniettiva , cioè che ciascuno di loro abbia una stanza individuale . Ciò è possibile solo se il numero di turisti non supera il numero di camere.
Questi desideri sono incompatibili se il numero di turisti è diverso dal numero di camere. Altrimenti sarà possibile distribuire i turisti in modo che ve ne sia uno solo per camera, e tutte le stanze siano occupate: diremo quindi che la domanda è sia iniettiva che suriettiva; è biettivo .

Esempi e controesempi

La funzione affine definita da $f$ $($ $x$ $) = 2$ $x$ $+ 1$ è biiettiva, poiché per ogni $y$ reale esiste esattamente una soluzione reale dell'equazione $y$ $= 2$ $x$ $+ 1$ di $x$ sconosciuta , vale a dire: $x$ $= ($ $y$ $- 1 ) / 2$ . $f: \ mathbb {R} \ to \ mathbb {R}$
La funzione quadrata definita da $g$ $($ $x$ $) =$ $x$ $2$ non è biiettiva, per due ragioni. Il primo è che abbiamo (ad esempio) $g$ $(1) = 1 =$ $g$ $(-1)$ , e quindi $g$ non è iniettiva; la seconda è che (per esempio) non esiste $x$ reale tale che $x$ $2$ $= -1$ , e quindi neanche $g$ è suriettiva. Ciascuna di queste osservazioni è sufficiente per affermare che $g$ non è biiettiva. D'altra parte, l'applicazione è uno a uno . La spiegazione è che per ogni $y$ reale positivo , c'è esattamente una soluzione reale positiva dell'equazione $y = x$ $2$ , che è $x$ $=$ $\sqrt$ $y$ . La funzione radice quadrata è quindi la reciproca biiezione della funzione quadrata su questi insiemi. ${\ displaystyle g: \ mathbb {R} \ to \ mathbb {R}}$
${\ displaystyle \ mathbb {R} _ {+} \ to \ mathbb {R} _ {+}, \, x \ mapsto x ^ {2}}$
Allo stesso modo, la funzione seno , vista come un'applicazione di in , non è né iniettiva né suriettiva, e quindi non biiettiva; R{\ displaystyle \ mathbb {R}} $\ mathbb {R}$ R{\ displaystyle \ mathbb {R}} $\ mathbb {R}$
- la sua corestrizione è suriettiva ma non iniettiva (ad esempio, e ha la stessa immagine) quindi non biiettiva; ${\ Displaystyle \ sin: \ mathbb {R} \ to [-1,1]}$ ${\ displaystyle 0}$ $\ pi$
- la sua restrizione è iniettiva ma non suriettiva (ad esempio, è l'immagine senza valore) quindi non biiettiva; ${\ displaystyle \ sin: [- {\ pi / 2}, {\ pi / 2}] \ to \ mathbb {R}}$ $2$
- la sua restrizione-correlazione è biiettiva (come anche un'infinità di altre sue restrizioni-restringimenti); ${\ displaystyle \ sin: [- {\ pi / 2}, {\ pi / 2}] \ a [-1,1]}$
- la sua corrispondenza biunivoca inversa è quindi $arcsin$ : ; ${\ displaystyle [-1,1] \ to [- {\ pi / 2}, {\ pi / 2}]}$
- tuttavia, la funzione arcoseno che assume gli stessi valori, ma vista come un'applicazione di in , è iniettiva ma non suriettiva (ad esempio, non è l'immagine di alcun valore) quindi non biiettiva. $[-1,1]$ $\ mathbb {R}$ $\ pi$
La funzione sigmoidea definita da è biiettiva ed è spesso utilizzata in informatica, soprattutto nelle reti neurali . ${\ displaystyle f: \ mathbb {R} \ to] 0,1 [}$ $f (x) = \ frac {1} {1 + e ^ {- x}}$

Proprietà

Le biiezioni sono isomorfismi nella categoria degli insiemi .
Lascia e . f:E→F{\ displaystyle f: E \ to F} $f: E \ a F$ h:F→G{\ displaystyle h: F \ to G} ${\ displaystyle h: F \ to G}$
- Se e sono biettivi, allora è biettivo e . $f$ $h$ ${\ displaystyle h \ circ f}$ ${\ displaystyle (h \ circ f) ^ {- 1} = f ^ {- 1} \ circ h ^ {- 1}}$
- Se è biettivo, allora è iniettivo ed è suriettivo. ${\ displaystyle h \ circ f}$ $f$ $h$
Per ogni insieme E , biiezioni di E su se stesso sono chiamati permutazioni di E . Formano, con l'operazione ∘ di composizione delle mappe, un gruppo denominato gruppo simmetrico di E e indicato con S ( E ) o . ${\ displaystyle {\ mathfrak {S}} (E)}$
Il numero di biiezioni tra due insiemi finiti con la stessa cardinalità n è n ! .
Una mappa da ℝ a ℝ è biiettiva se e solo se il suo grafico interseca una qualsiasi linea orizzontale esattamente in un punto.
Affinché un'applicazione di un insieme finito in sé sia biiettiva, è sufficiente che sia iniettiva o suriettiva (è quindi entrambe le cose). Può essere visto come un'applicazione del principio dei cassetti . NB: può esserci una biiezione tra due insiemi infiniti di cui uno è strettamente compreso nell'altro. Ci sono molti esempi di questo nel caso numerabile .

Note e riferimenti

In N. Bourbaki , Elementi di matematica : Teoria degli insiemi [ dettaglio delle edizioni ](Edizione 1970 o 2006 ), c. II, § 3, n o 7, dopo la def. 10, p. II. 17, leggiamo: “Invece di dire che f è iniettiva, diciamo anche che f è uno a uno . […] Se f [mappatura da A a B ] è uno a uno, diciamo anche che f mette A e B in corrispondenza uno a uno . " Ma nei" risultati delle specifiche "alla fine dello stesso volume, p. ER9, "uno a uno" è usato solo nel secondo senso.

Articolo correlato

Teorema della biiezione