Innbinding

I matematikk , en Bijeksjon er påføring bijektiv . En applikasjon er bindende hvis hvert element i ankomstsettet har ett og bare ett fortilfelle , det vil si bildet av nøyaktig ett element ( av definisjonens domene ), eller hvis det er injeksivt og surjektiv . Bindinger blir også noen ganger kalt en-til-en-kamper .

Man kan legge merke til at man i denne definisjonen ikke stiller noen betingelse for elementene i startsettet , annet enn det som definerer en applikasjon: hvert element har et bilde og bare ett.

Hvis det eksisterer en sammenheng f fra et mengde E til et sett F , eksisterer det en fra F til E : den gjensidige sammenhengen av f , som til hvert element av F forbinder dets fortilfelle med f . Vi kan da si at disse settene er i sammenheng, eller ekvipotente .

Cantor demonstrerte først at hvis det er en injeksjon fra E til F og en injeksjon fra F til E (ikke nødvendigvis surjektiv), så er E og F ekvipotente (dette er Cantor-Bernstein-setningen ).

Hvis to endelige sett er ekvipotente, har de samme antall elementer. Utvidelsen av denne ekvivalensen til uendelige mengder førte til begrepet kardinal i et sett, og skiller forskjellige størrelser på uendelige sett, som er klasser ekvipotens. Dermed kan vi for eksempel vise at settet med naturlige tall er av samme størrelse som settet med rasjonelle tall , men av størrelse strengt mindre enn settet med reelle tall . Faktisk, fra i , det er injeksjoner, men ingen overjection. $\ mathbb {N}$ $\ mathbb {R}$

Formelle definisjoner

Funksjonell definisjon

Et kart er bindende hvis hvert element i ankomstsettet har nøyaktig et antesedent (in ) av , som formelt er skrevet: $f: E \ til F$ $F$ $E$ $f$

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

eller, som er ekvivalent, hvis det er en applikasjon som, sammensatt til venstre eller til høyre av , gir applikasjonens identitet : ${\ displaystyle g: F \ til E}$ $f$

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

og ,

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

det er å si:

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

En slik søknad bestemmes da unikt av . Vi kaller det gjensidig sammenheng med og vi skriver det ned . Det er også en sammenheng, og det omvendte er . $g$ $f$ $f$ $f ^ {- 1}$ $f$

Relasjonell definisjon

En Bijeksjon av i er en binær forbindelse av til hvilken er en applikasjon og hvis gjensidige forhold er også et program. Mer detaljert, må ha følgende fire egenskaper: $E$ $F$ $R$ $E$ $F$ $R ^ {- 1}$ $R$

Funksjonalitet : ethvert element av har maksimalt ett bilde per , dvs. $E$ $R$

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

;

Applicativity : hvert element av har minst ett bilde av , det vil si $E$ $R$

{\ displaystyle \ forall x \ i E, \ \ eksisterer y \ i F, \ quad xRy}

;

Injektivitet : ethvert element av har høyst en fortilfelle av , det vil si $F$ $R$

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

Surjectivity : hvert element av har minst en fortilfelle av , det vil si $F$ $R$

{\ displaystyle \ forall y \ i F, \ \ eksisterer x \ i E, \ quad xRy}

Injeksjonsevnen av tilsvarer funksjonaliteten til og overspenningsevnen av tilsvarer anvendeligheten av . $R$ $R ^ {- 1}$ $R$ $R ^ {- 1}$

Det er vanlig å representere en funksjonell binær relasjon av en funksjon ved å posere $R$ $f$

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

Hvis vi spesifiserer at det er en applikasjon , antar vi at den er funksjonell og applikativ (se Application_ (matematikk) #Function_and_application for forskjellene mellom applikasjon og funksjon , som kan variere i henhold til forfatterne). $f$ $R$

Symmetrien mellom funksjonalitet og injeksjonsevne på den ene siden, og mellom applikativitet og surjektivitet på den annen side, gir at hvis det er et bijektivt forhold, så er det også. $R$ $R ^ {- 1}$

Konkret eksempel

Ta saken med et feriested der en gruppe turister skal innkvarteres på et hotell. Hver måte å distribuere disse turistene i rommene på hotellet kan representeres av en applikasjon av settet X av turistene til settet Y av rommene (hver turist er tilknyttet et rom).

Hotellmannen vil at søknaden skal være omvendt , det vil si at hvert rom er okkupert . Dette er bare mulig hvis det er minst like mange turister som det er rom.
Turister vil at applikasjonen skal være injiserende , det vil si at hver av dem skal ha et individuelt rom . Dette er bare mulig hvis antall turister ikke overstiger antall rom.
Disse ønskene er inkompatible hvis antall turister er forskjellig fra antall rom. Ellers vil det være mulig å distribuere turistene slik at det bare er en per rom, og alle rommene er okkupert: Vi vil da si at applikasjonen er både injiserende og surjectiv; det er bijektiv .

Eksempler og moteksempler

Den affine funksjon definert ved $f$ $($ $x$ $) = 2$ $x$ $+ 1$ er bijektiv, siden det for en hvilken som helst reell $y$ , eksisterer nøyaktig en ekte løsning av likningen $y$ $= 2$ $x$ $+ 1$ av ukjente $x$ , nemlig: $x$ $= ($ $y$ $- 1 ) / 2$ . $f: \ mathbb {R} \ til \ mathbb {R}$
Den kvadratisk funksjon definert av $g$ $($ $x$ $) =$ $x$ $2$ er ikke bijektiv, av to grunner. Den første er at vi har (for eksempel) $g$ $(1) = 1 =$ $g$ $(-1)$ , og derfor er $g$ ikke injiserende; det andre er at det (for eksempel) ikke er noe reelt $x$ slik at $x$ $2$ $= -1$ , og derfor er heller ikke $g$ . En av disse observasjonene er tilstrekkelig til å si at $g$ ikke er bindende. På den annen side er applikasjonen en-til-en . Forklaringen er at for hver positive reelle $y$ er det nøyaktig en positiv reell løsning på ligningen $y = x$ $2$ , som er $x$ $=$ $\sqrt$ $y$ . Den kvadratrot-funksjonen er derfor den resiproke Bijeksjon av plassen funksjon på disse settene. ${\ displaystyle g: \ mathbb {R} \ to \ mathbb {R}}$
${\ displaystyle \ mathbb {R} _ {+} \ til \ mathbb {R} _ {+}, \, x \ mapsto x ^ {2}}$
På samme måte er sinusfunksjonen , sett på som en anvendelse av in , verken injeksjonsfull eller surjektiv, og derfor ikke bijektiv; R{\ displaystyle \ mathbb {R}} $\ mathbb {R}$ R{\ displaystyle \ mathbb {R}} $\ mathbb {R}$
- korestriksjon er surjektiv, men ikke injeksjonsdyktig (for eksempel og har samme bilde), derfor ikke bijektiv; ${\ displaystyle \ sin: \ mathbb {R} \ til [-1,1]}$ ${\ displaystyle 0}$ $\ pi$
- begrensningen er injiserende, men ikke surjektiv (for eksempel er bildet av ingen verdi), derfor ikke bijektiv; ${\ displaystyle \ sin: [- {\ pi / 2}, {\ pi / 2}] \ til \ mathbb {R}}$ $2$
- dens restriksjon-korestriksjon er bijektiv (som også en uendelig andres restriksjon-corestrictions); ${\ displaystyle \ sin: [- {\ pi / 2}, {\ pi / 2}] \ til [-1,1]}$
- dens inverse Bijeksjon er da $arcsin$ : ; ${\ displaystyle [-1,1] \ til [- {\ pi / 2}, {\ pi / 2}]}$
- bue sinusfunksjonen som tar de samme verdiene, men sett på som en anvendelse av in , er imidlertid injiserende, men ikke surjektiv (er for eksempel ikke bildet av noen verdi) derfor ikke bindende. $[-1.1]$ $\ mathbb {R}$ $\ pi$
Den sigmoid funksjon definert av er bijective og er ofte brukt i informatikk, spesielt i nevrale nettverk . ${\ displaystyle f: \ mathbb {R} \ to] 0.1 [}$ $f (x) = \ frac {1} {1 + e ^ {- x}}$

Eiendommer

Bindinger er isomorfismer i kategorien sett .
La og . f:E→F{\ displaystyle f: E \ til F} $f: E \ til F$ h:F→G{\ displaystyle h: F \ til G} ${\ displaystyle h: F \ til G}$
- Hvis og er bijektiv så er bijektiv og . $f$ $h$ ${\ displaystyle h \ circ f}$ ${\ displaystyle (h \ circ f) ^ {- 1} = f ^ {- 1} \ circ h ^ {- 1}}$
- Hvis er bijektiv, er det injeksivt og er surjektiv. ${\ displaystyle h \ circ f}$ $f$ $h$
For noen sett E , bijections av E er på seg selv kalles permutasjoner av E . De danner, med operasjonen ∘ av kartets sammensetning, en gruppe kalt den symmetriske gruppen av E og betegnet S ( E ) eller . ${\ displaystyle {\ mathfrak {S}} (E)}$
Antall bindinger mellom to endelige sett med samme kardinalitet n er n ! .
Et kart fra ℝ til ℝ er bindende hvis og bare hvis grafen krysser en horisontal linje på nøyaktig ett punkt.
For at en anvendelse av et endelig sett i seg selv skal være bijektiv, er det tilstrekkelig for at det skal være injeksivt eller surjektiv (det er da begge deler). Det kan sees på som en anvendelse av skuffeprinsippet . NB: det kan være en sammenheng mellom to uendelige sett, hvorav det ene er strengt tatt med i det andre. Det er mange eksempler på dette i det tellbare tilfellet .

Merknader og referanser

I N. Bourbaki , Elements of mathematics : Theory of sets [ detalj av utgaver ](Utgave 1970 eller 2006 ), c. II, § 3, nr . 7, etter def. 10, s. II. 17 leser vi: «I stedet for å si at f er injeksjonsdyktig, sier vi også at f er en-mot-en . […] Hvis f [kartlegging fra A til B ] er en-til-en, sier vi også at f setter A og B i en-til-en korrespondanse . " Men i" spesifikasjonsresultatene "på slutten av samme volum, s. ER9, "en-til-en" brukes bare i andre forstand.

Relatert artikkel

Teorem for sammenheng