Bijekce

V matematice , je bijection je použití bijective . Aplikace je bijektivní, pokud každý prvek její sady příchodů má jednoho a pouze jednoho předchůdce , to znamená obraz přesně jednoho prvku (její definiční oblasti ), nebo pokud je injektivní a surjektivní . Bijekce se také někdy nazývají zápasy jeden na jednoho .

Je možné si všimnout, že v této definici nelze uvalit žádnou podmínku na prvky výchozí sady , kromě té, která definuje aplikaci: každý prvek má obrázek a pouze jednu.

Pokud existuje bijekce f z nastavené E do množiny F potom existuje jeden z F až E : ZAŘÍZENÍ reciproční bijection z F , pro každý prvek F sdružuje jeho předchůdce o f . Můžeme pak říci, že tyto množiny jsou v bijekce nebo ekvipotentní .

Cantor nejprve prokázal, že pokud existuje injekce z E do F a injekce z F do E (ne nutně surjektivní), pak E a F jsou ekvipotentní (jedná se o Cantor-Bernsteinovu větu ).

Jsou-li dvě konečné množiny ekvipotentní, pak mají stejný počet prvků. Rozšíření této ekvivalence na množiny nekonečné vedlo ke konceptu kardinála množiny a rozlišovalo různé velikosti nekonečných množin, což jsou třídy ekvipotence. Můžeme tedy například ukázat, že množina přirozených čísel má stejnou velikost jako množina racionálních čísel , ale má velikost striktně menší než množina reálných čísel . Ve skutečnosti, z in , jsou injekce, ale ne overjection. $\ mathbb {N}$ $\ mathbb {R}$

Formální definice

Funkční definice

Mapa je bijective jestliže každý prvek setu příjezdu má zrovna předchůdce (v ) pomocí , která je formálně písemně: $f: E \ až F$ $F$ $E$ $F$

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

nebo, což je ekvivalentní, pokud existuje aplikace, která ve složení vlevo nebo vpravo od dává aplikaci identitu : ${\ displaystyle g: F \ až E}$ $F$

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

a ,

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

to znamená:

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

Taková aplikace je pak jednoznačně určena . Nazýváme ji reciproční bijection of a píšeme ho . Je to také bijekce a její opak je . $G$ $F$ $F$ $f ^ {- 1}$ $F$

Relační definice

Bijection z INTO je binární relace z do které je aplikace, a jejichž vzájemný vztah je také aplikace. Podrobněji musí mít následující čtyři vlastnosti: $E$ $F$ $R$ $E$ $F$ $R ^ {- 1}$ $R$

Funkčnost : každý prvek má nejvýše jeden obrázek na , tj. $E$ $R$

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

;

Použitelnost : každý prvek má alespoň jeden obrázek , tj $E$ $R$

{\ displaystyle \ forall x \ v E, \ \ existuje y \ v F, \ quad xRy}

;

Injektivita : jakýkoli prvek má nanejvýš předchůdce , to znamená $F$ $R$

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

Surjectivity : každý prvek má alespoň jeden předchůdce tím , to znamená $F$ $R$

{\ displaystyle \ for all y \ in F, \ \ existuje x \ v E, \ quad xRy}

Injektivita je ekvivalentní s funkčností a surjektivita je ekvivalentní s použitelností . $R$ $R ^ {- 1}$ $R$ $R ^ {- 1}$

Je obvyklé, že představuje funkční binární relaci tím, že a funkce položením $R$ $F$

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

Pokud zadáme, že se jedná o aplikaci , předpokládáme, že je funkční a aplikovatelná ( rozdíly mezi aplikací a funkcí , které se mohou lišit podle autorů, najdete v části Application_ (mathematics) #Function_and_application ). $F$ $R$

Symetrie mezi funkčností a injektivitou na jedné straně a mezi použitelností a surjektivitou na druhé straně ukazuje, že pokud jde o bijektivní vztah, pak také existuje. $R$ $R ^ {- 1}$

Konkrétní příklad

Vezměte například rekreační středisko, kde má být skupina turistů ubytována v hotelu. Každý způsob distribuce těchto turistů v pokojích hotelu může být reprezentován aplikací množiny X turistů na množinu Y pokojů (každý turista je spojen s místností).

Hoteliér chce, aby aplikace byla surjektivní , to znamená, že každý pokoj je obsazený . To je možné pouze v případě, že je alespoň tolik turistů, kolik je pokojů.
Turisté chtějí, aby aplikace byla injektivní , to znamená, aby každý z nich měl samostatný pokoj . To je možné pouze v případě, že počet turistů nepřekročí počet pokojů.
Tato přání jsou nekompatibilní, pokud se počet turistů liší od počtu pokojů. V opačném případě bude možné rozdělit turisty tak, aby na každou místnost připadal pouze jeden a aby byly všechny pokoje obsazené: pak řekneme, že žádost je injektivní i surjektivní; je to bijektivní .

Příklady a protiklady

Afinní funkce definovaný $f$ $($ $x$ $) = 2$ $x$ $+ 1$ je bijective, protože pro skutečný $y$ , existuje přesně skutečné řešení rovnice $y$ $= 2$ $x$ $+ 1$ neznámého $x$ , a to: $x$ $= ($ $y$ $- 1 ) / 2$ . $f: \ mathbb {R} \ to \ mathbb {R}$
Kvadratickou funkcí, definované $g$ $($ $x$ $) =$ $x$ $2$ je ne bijective, ze dvou důvodů. První je, že máme (například) $g$ $(1) = 1 =$ $g$ $(-1)$ , a proto $g$ není injektivní; druhý je, že neexistuje (například) žádné skutečné $x$ takové, že $x$ $2$ $= -1$ , a proto ani $g$ není surjektivní. Jedno z těchto pozorování postačuje k vyjádření, že $g$ není bijektivní. Na druhou stranu je aplikace individuální . Vysvětlení spočívá v tom, že pro každé kladné reálné $y$ existuje přesně jedno kladné reálné řešení rovnice $y = x$ $2$ , což je $x$ $=$ $\sqrt$ $y$ . Funkce druhé odmocniny je tedy reciproční bijekce funkce druhé mocniny na těchto množinách. ${\ displaystyle g: \ mathbb {R} \ do \ mathbb {R}}$
${\ displaystyle \ mathbb {R} _ {+} \ až \ mathbb {R} _ {+}, \, x \ mapsto x ^ {2}}$
Podobně funkce sine , považovaná za aplikaci in , není ani injektivní, ani surjektivní, a proto není bijektivní; R{\ displaystyle \ mathbb {R}} $\ mathbb {R}$ R{\ displaystyle \ mathbb {R}} $\ mathbb {R}$
- jeho corestriction surjective ale ne injective (například, a mají stejný obraz), proto není bijective; ${\ displaystyle \ sin: \ mathbb {R} \ až [-1,1]}$ ${\ displaystyle 0}$ $\ pi$
- jeho omezení je injektivní, ale nikoli surjektivní (například nemá žádnou hodnotu), proto není bijektivní; ${\ displaystyle \ sin: [- {\ pi / 2}, {\ pi / 2}] \ do \ mathbb {R}}$ $2$
- jeho omezení-korekce je bijektivní (stejně jako nekonečno ostatních jeho omezení-korekce); ${\ displaystyle \ sin: [- {\ pi / 2}, {\ pi / 2}] \ až [-1,1]}$
- jeho inverzní bijection je pak $arcsin$ : ; ${\ displaystyle [-1,1] \ až [- {\ pi / 2}, {\ pi / 2}]}$
- funkce arc sine, která přijímá stejné hodnoty, ale je považována za aplikaci in , je injektivní, ale nikoli surjektivní (například není obrazem jakékoli hodnoty), proto není bijektivní. $[-1,1]$ $\ mathbb {R}$ $\ pi$
Sigmoid funkce definovaná je bijective a je často používán ve vědě o počítačích, a to zejména v neuronových sítí . ${\ displaystyle f: \ mathbb {R} \ až] 0,1 [}$ $f (x) = \ frac {1} {1 + e ^ {- x}}$

Vlastnosti

Bijekce jsou izomorfismy v kategorii sad .
Nechte a . F:E→F{\ displaystyle f: E \ až F} $f: E \ až F$ h:F→G{\ displaystyle h: F \ až G} ${\ displaystyle h: F \ až G}$
- Pokud a jsou bijective, pak je bijective a . $F$ $h$ ${\ displaystyle h \ circ f}$ ${\ displaystyle (h \ circ f) ^ {- 1} = f ^ {- 1} \ circ h ^ {- 1}}$
- Pokud je bijective, pak je injective a je surjective. ${\ displaystyle h \ circ f}$ $F$ $h$
Pro nějaký soubor E , bijekce z E na sebe nazývají permutací z E . Tvoří, s provozem ∘ o složení mapy, je skupina se nazývá symetrický skupinu s E a označený S ( E ) nebo . ${\ displaystyle {\ mathfrak {S}} (E)}$
Počet bijekcí mezi dvěma konečnými množinami se stejnou mohutností n je n ! .
Mapa od ℝ do ℝ je bijektivní právě tehdy, když její graf protíná jakoukoli vodorovnou čáru přesně v jednom bodě.
Aby aplikace konečné množiny sama o sobě byla bijektivní, stačí, aby byla injektivní nebo surjektivní (pak je to obojí). Lze to chápat jako aplikaci principu zásuvek . Pozn .: Může existovat bijekce mezi dvěma nekonečnými sadami, z nichž jedna je striktně zahrnuta do druhé. V spočítatelném případě existuje mnoho příkladů .

Poznámky a odkazy

In N. Bourbaki , Elementy matematiky : Teorie množin [ detail vydání ](Vydání z roku 1970 nebo 2006 ), c. II, § 3, n o 7, po def. 10, s. II. 17 čteme: „Místo toho, abychom říkali, že f je injektivní, také říkáme, že f je jedna ku jedné . […] Pokud je f [mapování z A do B ] jedna ku jedné, řekneme také, že f dá A a B do korespondence jedna k jedné . „ Ale ve„ výsledcích specifikace “na konci stejného svazku, str. ER9 „one-to-one“ se používá pouze ve druhém smyslu.

Související článek

Věta o bijekce