Surjektion

I matematik er en overvejelse eller en overvejende anvendelse en applikation, for hvilken hvert element i ankomstsættet har mindst et fortilfælde , det vil sige er billedet af mindst et element i det oprindelige sæt . Det svarer til at sige, at billedsættet er lig med ankomstsættet.

Det er muligt at anvende adjektivet "surjective" til en funktion (eller endda til en korrespondance ) hvis definitionsdomæne ikke er hele startsættet, men generelt er udtrykket "Surjection" forbeholdt applikationer (som er defineret over hele deres start sæt), som vi vil begrænse os til i denne artikel (for flere detaljer, se afsnittet "Funktion og anvendelse" i "Applikation" artiklen ).

For at betegne start- og slutningssæt for en overvejelse er det almindeligt at sige “fra A til B ” i stedet for “fra A til B ” som for en applikation generelt.

I tilfælde af en reel funktion af en reel variabel svarer dens surjektivitet til det faktum, at dens graf skærer en hvilken som helst linje parallelt med x-aksen.

En applikation, der er både overvejende og injektiv, er en sammenhæng .

Formel definition

Et kort $f$ fra $X$ til $Y$ siges at være Surjective hvis for ethvert element $y$ af $Y$ , der findes i det mindste et element $x$ af $X$ , således at $f ( x ) = y$ , som formelt skrevet:

{\ displaystyle \ forall y \ i Y \ quad \ findes x \ i X \ quad f (x) = y}

Eksempler

Konkret eksempel

Vi overvejer tilfældet med et feriested, hvor en gruppe turister skal indkvarteres på et hotel. Hver måde at distribuere disse turister i hotellets værelser kan repræsenteres ved en anvendelse af sæt X af turisterne til sæt Y af værelserne (hver turist er forbundet med et værelse).

Hotelmanden ønsker, at ansøgningen skal være overvejende , det vil sige, at hvert værelse er optaget . Dette er kun muligt, hvis der er mindst lige så mange turister, som der er værelser.
Turister ønsker, at applikationen skal være injektionsdygtig , dvs. at hver af dem skal have et individuelt rum . Dette er kun muligt, hvis antallet af turister ikke overstiger antallet af værelser.
Disse ønsker er kun kompatible, hvis antallet af turister er lig med antallet af værelser. I dette tilfælde vil det være muligt at distribuere turisterne, så der kun er en per værelse, og at alle værelser er optaget: applikationen vil så være både injektionsdygtig og surjectiv; vi vil sige, at det er bijektivt .

Eksempler og modeksempler i virkelige funktioner

Funktionen defineret af

{\ begin {matrix} f: & \ mathbb {R} & \ rightarrow & \ mathbb {R} \\ & x & \ mapsto & x ^ {2} \\\ slut {matrix}}

er ikke forventet, fordi nogle reelle tal ikke har noget fortilfælde. For eksempel er der ingen reel x sådan, at f ( x ) = −4. Men hvis vi ændrer definitionen af f ved at give som et slutsæt ℝ + ,

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

så bliver det sådan, fordi hver positiv real har mindst en fortilfælde: 0 har nøjagtigt en fortilfælde, 0, og alle strengt positive realer y har to, kvadratroden af y og dens modsatte .

Funktionen defineret af

{\ begin {matrix} f: & \ mathbb {R} & \ rightarrow & \ mathbb {R} \\ & x & \ mapsto & 2x + 1 \\\ slut {matrix}}

er overvejende, da der for enhver vilkårlig reel y er løsninger til ligningen y = 2 x + 1 af ukendt x ; en opløsning er x = ( y - 1) / 2.

Funktionen defineret af

{\ begin {matrix} g: & \ mathbb {R} & \ højrepil & \ mathbb {R} \\ & x & \ mapsto & \ cos (x) \\\ slut {matrix}}

er ikke overvejende, fordi realerne, der er strengt større end 1 eller strengt mindre end -1, ikke har noget fortilfælde. Men funktionen defineret af

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

som har det samme udtryk som g , men med et ankomstsæt, der er begrænset til sættet af realer mellem –1 og 1, er overvejende. Faktisk for ethvert vilkårligt reelt y i intervallet [–1, 1] findes der løsninger til ligningen y = cos ( x ) af ukendt x : disse er reelle x = ± arccos ( y ) + 2 k $π$ for enhver relativt heltal k .

På disse få eksempler ser vi, at det altid er muligt at omdanne et ikke-spekulativt kort til en overvejelse på betingelse af at begrænse dets endesæt .

Ejendomme

Reduktion af ankomstsættet

Hvis f er et kort fra X til Y og Im ( f ) = f ( X ) er dets billedsæt (dvs. sæt af billeder ved f af elementerne i X ), så er kortet

{\ begin {matrix} s: & X & \ højrepil & f (X) \\ & x & \ mapsto & f (x) \\\ slut {matrix}}

er en overjektion.

Med andre ord, hvis f er begrænset til Im ( f ), det vil sige hvis vi erstatter dets ankomstsæt med dets billedsæt, bliver det overvejende .

Kanonisk nedbrydning

Ethvert kort f kan nedbrydes som f = i ∘ s hvor s er en overvejelse og i en injektion. Denne nedbrydning er unik bortset fra en isomorfisme . En opdeling findes i det detaljerede afsnit. En anden (ækvivalent) er at vælge s den ovenfor definerede udsendelse og for i den kanoniske indsprøjtning af billedet af f i dets ankomstsæt.

Direkte og gensidige billeder

For ethvert kort f : X → Y er følgende fire egenskaber ækvivalente:

f er overvejende;
ethvert delsæt B af Y er det direkte billede af dets gensidige billede , dvs. f ( f −1 ( B )) = B ;
f ( f -1 ( Y )) = Y ;
for enhver del A af X er komplementet af det direkte billede af A inkluderet i det direkte billede af komplementet af A , dvs. Y \ f ( A ) ⊂ f ( X \ A ).

Surjektivitet og forbindelse

Lad f et program X i Y .

For ethvert kort g fra Y til Z :
- hvis g ∘ f er surjective, så er g surjective;
- hvis f og g er surjective, så er g ∘ f surjective;
- hvis g er injektionsdygtig, og hvis g ∘ f er surjektiv, så er f surjektiv.
f er overvejende, hvis og kun hvis, for alle Z og for alle kort g og h fra Y til Z , g ∘ f = h ∘ f medfører g = h . Med andre ord er formodningerne netop epimorfierne i kategorien sæt .

Sektion og aksiom efter eget valg

Lad f et program X i Y . Hvis f er " højre- inverterbar " , dvs. hvis der findes et kort g fra Y til X, således at den sammensatte funktion f ∘ g er lig med identitetskortet på Y , så er f surjective (fra en egenskab set ovenfor ).

Et sådant kort g kaldes et snit eller omvendt til højre for f . Det er nødvendigvis injektionsdygtigt .

Omvendt, hvis f er overvejende, så indrømmer det et afsnit. Denne egenskab er baseret på det faktum, at man altid kan "pil op" af Y til X . Det er altid sandt, hvis Y er færdig. Påstanden om, at det er sandt for ethvert sæt Y , svarer til det valgte aksiom .

Kardinaler

Hvis der er en overvejelse fra X til Y , er der (fra ovenstående, forudsat derfor det valgte aksiom) en injektion fra Y i X , med andre ord har sættet X mindst lige så mange elementer end sættet Y , i følelsen af kardinalerne .
Cantors sætning (uden valgaksiom): for ethvert sæt X er der ingen overvejelse af X i sættet af dets dele .

Noter og referencer

Se for eksempel de korrigerede øvelser i kapitlet "Injektion, omvisning, vedektion" på Wikiversity .
Lucien Chambadal og Jean-Louis Ovaert, Matematik-kursus , vol. 1: Grundlæggende forestillinger om algebra og analyse , Gauthier-Villars ,1966, s. 27.
N. Bourbaki , Elementer af matematik : Indstil teori [ detalje af udgaver ], s. II-19 på Google Bøger .
Bourbaki , s. II-18, demonstrer det ved hjælp af en stærkere form end det valgte aksiom .

Se også

Skuffeprincip
Pascals inversionsformel , der giver antallet af udsagn fra et endeligt sæt til et andet.
Princippet om inklusion-udelukkelse , der giver endnu en demonstration af antallet af udsagn fra et sæt til et andet.