Surjection

In matematica , un surjection o surjective applicazione è un'applicazione per la quale ogni elemento della serie arrivo ha almeno un antecedente , cioè è l' immagine di almeno un elemento della prima serie . È equivalente a dire che il set di immagini è uguale al set di arrivo.

È possibile applicare l'aggettivo "surjective" a una funzione (o anche a una corrispondenza ) il cui dominio di definizione non è l'intero insieme di partenza, ma in generale il termine "surjection" è riservato alle applicazioni (che sono definite nel loro intero set di partenza), a cui ci limiteremo in questo articolo (per maggiori dettagli si veda il paragrafo “Funzione e applicazione” dell'articolo “Applicazione” ).

Per designare l'insieme iniziale e finale di una suriezione, è consuetudine dire "da A a B  " invece di "da A a B  " come per un'applicazione in generale.

Nel caso di una funzione reale di una variabile reale , la sua suriettività è equivalente al fatto che il suo grafico interseca una qualsiasi linea parallela all'asse x.

Un'applicazione che è sia suriettiva che iniettiva è una biiezione .

Definizione formale

Una mappa f da X a Y si dice che sia suriettiva se per ogni elemento y di Y , esiste almeno un elemento x di X tale che f ( x ) = y , che è formalmente scritto:

∀y∈Y∃X∈Xf(X)=y{\ Displaystyle \ forall y \ in Y \ quad \ esiste x \ in X \ quad f (x) = y}.

Esempi

Esempio concreto

Consideriamo il caso di un luogo di villeggiatura in cui un gruppo di turisti deve essere alloggiato in un albergo. 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 compatibili solo se il numero di turisti è uguale al numero di camere. In questo caso sarà possibile distribuire i turisti in modo che ve ne sia uno solo per camera, e che tutte le stanze siano occupate: la domanda sarà quindi sia iniettiva che suriettiva; diremo che è biettivo .

Esempi e controesempi in funzioni reali

La funzione definita da

f:R→RX↦X2{\ displaystyle {\ begin {matrix} f: & \ mathbb {R} & \ rightarrow & \ mathbb {R} \\ & x & \ mapsto & x ^ {2} \\\ end {matrix}}}

non è suriettivo perché alcuni numeri reali non hanno antecedenti. Ad esempio, non esiste una x reale tale che f ( x ) = −4. Ma se cambiamo la definizione di f dando come insieme finale ℝ + ,

f:R→R+X↦X2{\ displaystyle {\ begin {matrix} f: & \ mathbb {R} & \ rightarrow & \ mathbb {R} _ {+} \\ & x & \ mapsto & x ^ {2} \\\ end {matrix} }}

allora diventa così perché ogni reale positivo ha almeno un antecedente: 0 ha esattamente un antecedente, 0, e tutti i reali strettamente positivi y ne hanno due, la radice quadrata di y e il suo opposto .

La funzione definita da

f:R→RX↦2X+1{\ displaystyle {\ begin {matrix} f: & \ mathbb {R} & \ rightarrow & \ mathbb {R} \\ & x & \ mapsto & 2x + 1 \\\ end {matrix}}}

è suriettivo poiché, per ogni y reale arbitrario , ci sono soluzioni all'equazione y  = 2 x  + 1 di x sconosciuta  ; una soluzione è x  = ( y  - 1) / 2.

La funzione definita da

g:R→RX↦cos⁡(X){\ displaystyle {\ begin {matrix} g: & \ mathbb {R} & \ rightarrow & \ mathbb {R} \\ & x & \ mapsto & \ cos (x) \\\ end {matrix}}}

non è suriettivo perché i reali strettamente maggiori di 1 o strettamente minori di –1 non hanno antecedenti. Ma la funzione definita da

h:R→[-1,1]X↦cos⁡(X){\ displaystyle {\ begin {matrix} h: & \ mathbb {R} & \ rightarrow & [- 1,1] \\ & x & \ mapsto & \ cos (x) \\\ end {matrix}}}

che ha la stessa espressione di g , ma con un insieme di arrivo che è stato limitato all'insieme di reali compreso tra –1 e 1, è surjective. Infatti, per ogni y reale arbitrario dell'intervallo [–1, 1], esistono soluzioni all'equazione y  = cos ( x ) di x sconosciuta  : questi sono i reali x = ± arccos ( y ) + 2 k π per ogni intero relativo k .

In questi pochi esempi, vediamo che è sempre possibile trasformare una mappa non suriettiva in una suriezione a condizione di restringere il suo insieme finale .

Proprietà

Riduzione del set di arrivo

Se f è una mappa da X a Y e Im ( f ) = f ( X ) il suo insieme di immagini (cioè l'insieme di immagini di f degli elementi di X ), allora la mappa

S:X→f(X)X↦f(X){\ displaystyle {\ begin {matrix} s: & X & \ rightarrow & f (X) \\ & x & \ mapsto & f (x) \\\ end {matrix}}}

è una sovraiezione.

In altre parole, se f è limitato a Im ( f ), vale a dire se sostituiamo il suo insieme di arrivo con il suo insieme di immagini, diventa suriettivo .

Decomposizione canonica

Qualsiasi mappa f può essere scomposta come f = i ∘ s dove s è una suriezione e i un'iniezione. Questa decomposizione è unica tranne che per un isomorfismo . La ripartizione è fornita nel paragrafo dettagliato. Un altro (equivalente) è scegliere per s la suriezione definita sopra, e per i l' iniezione canonica dell'immagine di f nel suo insieme di arrivo.

Immagini dirette e reciproche

Per qualsiasi mappa f  :  X → Y , le seguenti quattro proprietà sono equivalenti:

1. f è suriettiva;
2. qualsiasi sottoinsieme B di Y è l' immagine diretta della sua immagine reciproca , ad es. f ( f −1 ( B )) = B  ;
3. f ( f −1 ( Y )) = Y  ;
4. per qualsiasi parte A di X , il complemento dell'immagine diretta di A è incluso nell'immagine diretta del complemento di A , ad es. Y \ f ( A ) ⊂ f ( X \ A ).

Surjectivity e compound

Lasciare f un'applicazione X in Y .

• Per qualsiasi mappa g da Y a Z  :
  • se g ∘ f è suriettiva allora g è suriettiva;
  • se f e g sono surjective quindi g ∘ f IS surjective;
  • se g è iniettiva e se g ∘ f è suriettiva allora f è suriettiva.
• f è suriettiva se e solo se, per ogni Z e per tutte le mappe g e h da Y a Z , g ∘ f  = h ∘ f implica g  = h . In altre parole, le suriezioni sono proprio gli epimorfismi nella categoria degli insiemi .

Sezione e assioma di scelta

Lasciare f un'applicazione X in Y . Se f è "  invertibile a destra" , cioè se esiste una mappa g da Y a X tale che la funzione composta f ∘ g è uguale alla mappa identità su Y , allora f è suriettiva (da una proprietà vista sopra ).

Tale mappa g è chiamata sezione , o inversa a destra di f . È necessariamente iniettivo .

Al contrario, se f è suriettiva, ammette una sezione. Questa struttura si basa sul fatto che si può sempre "freccia" di Y a X . È sempre vero se Y è finito. L'affermazione che è vero per qualsiasi insieme Y è equivalente all'assioma di scelta .

Cardinali

• Se c'è una suriezione da X in Y , allora (da quanto sopra, assumendo quindi l'assioma di scelta) c'è un'iniezione da Y in X , in altre parole l'insieme X ha almeno tanti elementi dell'insieme Y , in il senso dei cardinali .
• Il teorema di Cantor (senza scelta assioma): per ogni insieme X , non v'è alcuna surjection di X nella serie delle sue parti .

Note e riferimenti

1. Si vedano ad esempio gli esercizi corretti del capitolo "Iniezione surjection, bijection" su Wikiversità .
2. Lucien Chambadal e Jean-Louis Ovaert, Corso di matematica , vol.  1: Nozioni fondamentali di algebra e analisi , Gauthier-Villars ,1966, p.  27.
3. N. Bourbaki , Elementi di matematica  : Teoria degli insiemi [ dettaglio delle edizioni ], p.  II-19 su Google Libri .
4. Bourbaki , p.  II-18, dimostralo usando una forma più forte dell'assioma della scelta .

Vedi anche

• Principio dei cassetti
• Formula di inversione di Pascal , che fornisce il numero di suriezioni da un insieme finito a un altro.
• Principio di inclusione-esclusione , che fornisce un'altra dimostrazione del numero di sottrazioni da un insieme all'altro.