Bijection - Bijection

Bijektivní funkce, f : XY , kde množina X je {1, 2, 3, 4} a množina Y je {A, B, C, D}. Například f (1) = D.

V matematice je bijekce , bijektivní funkce , individuální korespondence nebo invertibilní funkce , funkce mezi prvky dvou sad , kde každý prvek jedné sady je spárován s přesně jedním prvkem druhé sady a každý prvek druhé sady je spárováno přesně s jedním prvkem první sady. Nejsou žádné nepárové prvky. Matematicky vyjádřeno, bijective funkce f : XY je jedna ku jedné (injective) a (surjektivní) na mapování ze souboru X k sadě Y . Pojem korespondence jeden na jednoho nesmí být zaměňován s funkcí one-to-one ( injektivní funkce ; viz obrázky).

Bijection z množiny X do množiny Yinverzní funkce z Y pro X . Pokud X a Y jsou konečné množiny , pak existence bijekce znamená, že mají stejný počet prvků. U nekonečných množin je obrázek složitější, což vede ke konceptu světového čísla - způsobu, jak rozlišit různé velikosti nekonečných množin.

Bijektivní funkce ze sady k sobě se také nazývá permutace a množina všech permutací množiny tvoří symetrickou skupinu .

Bijektivní funkce jsou nezbytné pro mnoho oblastí matematiky, včetně definic izomorfismu , homeomorfismu , difeomorfismu , permutační skupiny a projektivní mapy .

Definice

Aby párování mezi X a Y (kde Y nemusí být odlišné od X ) bylo bijekce, musí platit čtyři vlastnosti:

  1. každý prvek X musí být spárován s alespoň jedním prvkem Y ,
  2. žádný prvek X nesmí být spárován s více než jedním prvkem Y ,
  3. každý prvek Y musí být spárován s alespoň jedním prvkem X , a
  4. žádný prvek Y může být spárována s více než jedním prvkem X .

Uspokojující vlastnosti (1) a (2) znamená, že párování se o funkci s domény X . To je více obyčejné vidět vlastnosti (1) a (2) písemné formě jediného příkazu: Každý prvek X je spárován s přesně jeden prvek Y . O funkcích, které uspokojují vlastnost (3), se říká, že jsou " na Y " a říká se jim přeludy (nebo surjektivní funkce ). O funkcích, které splňují vlastnosti (4), se říká, že jsou " individuální funkce " a nazývají se injekce (nebo injektivní funkce ). S touto terminologií je bijekce funkcí, která je jak přeludem, tak injekcí, nebo jinými slovy, bijekcí je funkcí, která je jak „jeden na jednoho“, tak „na“.

Bijekce jsou někdy označovány dvouhlavého Šipka vpravo s ocasem ( U + 2916 směrem doprava oboustrannou šipku s ocasem ), stejně jako v f  : XY . Tento znak je kombinací dvouhlavého Šipka vpravo ( U + 21A0 směrem doprava dvě šipky v čele ), které se někdy používá k označení surjections a šipka vpravo s ostnatým ocasem ( U + 21A3 Šipka vpravo s ocasem ), někdy se používá k označení injekce.

Příklady

Pálkařská sestava baseballového nebo kriketového týmu

Zvážit odpalování line-up o baseballu nebo kriketovém týmu (nebo jakýkoli seznam všech hráčů jakékoliv sportovní tým, kde každý hráč drží zvláštní místo v sestavě). Sada X budou hráči v týmu (velikost devět v případě baseballu) a sada Y budou pozice v pořadí pálkování (1., 2., 3. atd.) „Párování“ je dáno tím, hráč je v jaké pozici v tomto pořadí. Vlastnost (1) je uspokojena, protože každý hráč je někde v seznamu. Vlastnost (2) je uspokojena, protože žádný hráč netopí na dvou (nebo více) pozicích v pořadí. Vlastnost (3) říká, že pro každou pozici v pořadí existuje nějaké hráčské odpalování na této pozici a vlastnost (4) uvádí, že dva nebo více hráčů nikdy nepálí na stejné pozici v seznamu.

Sedadla a studenti ve třídě

Ve třídě je určitý počet míst k sezení. Do místnosti vejde parta studentů a instruktor je požádá, aby se posadili. Po rychlém rozhlédnutí po místnosti instruktor prohlásí, že mezi sadou studentů a sadou sedadel existuje bijekce, kde je každý student spárován se sedadlem, na kterém sedí. Co instruktor pozoroval, aby dospěl k tomuto závěru bylo to:

  1. Každý student seděl (nikdo nestál),
  2. Žádný student nebyl na více než jednom sedadle,
  3. Na každém sedadle někdo seděl (nebyla tam žádná volná místa) a
  4. Žádné sedadlo nemělo více než jednoho studenta.

Instruktor mohl usoudit, že tam bylo tolik míst, kolik studentů, aniž by museli počítat obě sady.

Další matematické příklady a některé příklady

  • Pro libovolnou množinu X je funkce identity 1 X : XX , 1 X ( x ) = x bijektivní.
  • Funkce f : RR , f ( x ) = 2 x + 1 je bijektivní, protože pro každé y existuje jedinečné x = ( y - 1)/2 takové, že f ( x ) = y . Obecněji platí, že jakákoli lineární funkce přes reals, f : RR , f ( x ) = ax + b (kde a je nenulová) je bijekce. Každé reálné číslo y je získáno z (nebo spárováno) s reálným číslem x = ( y - b ) / a .
  • Funkce f : R → (−π/2, π/2) daná f ( x ) = arctan ( x ) je bijektivní, protože každé reálné číslo x je spárováno s přesně jedním úhlem y v intervalu (−π/ 2, π/2) tak, že tan ( y ) = x (tj. Y = arktan ( x )). Pokud by byla doména (−π/2, π/2) větší, aby zahrnovala celočíselný násobek π/2, pak by tato funkce již nebyla na (surjektivní), protože neexistuje skutečné číslo, které by bylo možné spárovat s násobek π/2 touto arktanovou funkcí.
  • Exponenciální funkce , g : RR , g ( x ) = e x , není bijective: například, neexistuje x v R takový, že g ( x ) = 1, což ukazuje, že g není na (surjektivní) . Pokud je však doména omezena na kladná reálná čísla , pak by g bylo bijektivní; jeho inverzní (viz níže) je přirozená logaritmická funkce ln.
  • Funkce h : RR + , h ( x ) = x 2 není bijektivní: například h (−1) = h (1) = 1, což ukazuje, že h není one-to-one (injektivní). Pokud je však doména omezena na , pak by h bylo bijektivní; jeho inverzní funkce je kladná odmocnina.
  • Tím, Cantor-Bernstein-Schroder teorém , vzhledem k tomu, žádné dvě skupiny X a Y , a dvě injektivních funkce f : X? Y a g : Y → X existuje bijective funkce h : X? Y .

Inverzní

Bijekce f s doménou X (označená f : X → Y ve funkční notaci ) také definuje konverzní vztah začínající v Y a přecházející do X (otáčením šipek). Proces „otáčení šipky kolem“ pro libovolnou funkci nemá, obecně , výtěžek funkci, ale vlastnosti (3) a (4) z bijection říci, že tento inverzní vztah je funkce s doménou Y . Navíc vlastnosti (1) a (2) pak říkají, že tato inverzní funkce je přesahem a injekcí, to znamená, že inverzní funkce existuje a je také bijekcí. Funkce, které mají inverzní funkce, jsou prý invertovatelné . Funkce je invertibilní, pouze pokud je to bijekce.

Ve stručném matematickém zápisu je funkce f : X → Y bijektivní tehdy a jen tehdy, splňuje -li podmínku

pro každé y v Y existuje jedinečné x v X s y = f ( x ).

Pokračování příkladu sestavy baseballového odpalování, definovaná funkce bere jako vstup jméno jednoho z hráčů a vydává pozici tohoto hráče v pořadí odpalování. Protože tato funkce je bijekce, má inverzní funkci, která bere jako vstup pozici v pořadí pálkování a vydává hráče, který bude pálkovat v této pozici.

Složení

Složení dvou bijekce f : X → Y a g : Y → Z je bijection, jehož inverzní je dán , je .

Bijekce složená z injekce (vlevo) a projekce (vpravo).

A naopak, je-li složení dvou funkcí je bijective, z toho vyplývá, že pouze f znamená injective a g znamená surjective .

Mohutnost

Pokud X a Y jsou konečné množiny , pak existuje bijekce mezi dvěma množinami X a Y právě tehdy, když X a Y mají stejný počet prvků. V axiomatické teorii množin je to skutečně bráno jako definice „stejného počtu prvků“ ( ekvinumerita ) a zobecnění této definice na nekonečné množiny vede ke konceptu světového čísla , způsobu, jak rozlišit různé velikosti nekonečných množin.

Vlastnosti

  • Funkce f : RR je bijektivní právě tehdy, když její graf splňuje každou vodorovnou a svislou čáru přesně jednou.
  • Pokud X je soubor, pak bijective funkce z X k sobě, spolu s provozem funkčního prostředku (∘), tvoří skupinu , je symetrický skupinu z X , který je označený různě S ( X ), S X , nebo X ! ( X faktoriál ).
  • Bijekce zachovávají kardinality množin: pro podmnožinu A domény s mohutností | A | a podmnožina B codomény s mohutností | B |, jeden má následující rovnosti:
    | f ( A ) | = | A | a | f −1 ( B ) | = | B |.
  • Pokud X a Y jsou konečné množiny se stejnou mohutností a f : X → Y , pak jsou následující ekvivalentní:
    1. f je bijekce.
    2. f je surjekce .
    3. f je injekce .
  • Pro konečné množiny S , je bijection mezi množiny možných celkových orderings prvků a množiny bijekce z S na S . To znamená, že počet permutací prvků S je stejný jako počet celkových uspořádání této sady - jmenovitě n !.

Teorie kategorie

Bijekce jsou přesně isomorphisms v kategorii Sada ze sad a nastavených funkcích. Bijekce však nejsou vždy izomorfismy pro složitější kategorie. Například, v kategorii GRP ze skupin se morfizmy musí být homomorfismů protože musí zachovat strukturu skupiny, takže jsou isomorphisms skupina isomorphisms které jsou bijective homomorfizmy.

Zobecnění na dílčí funkce

Pojem korespondence jeden na jednoho zobecňuje na dílčí funkce , kde se nazývají částečné bijekce , ačkoli částečné bijekce musí být pouze injektivní. Důvodem této relaxace je, že (správná) částečná funkce již není pro část její domény definována; neexistuje tedy žádný pádný důvod omezovat jeho inverzi na celkovou funkci , tj. definovanou všude v jeho doméně. Množina všech dílčích bijekcí na dané základní sadě se nazývá symetrická inverzní poloskupina .

Dalším způsobem, jak definovat stejný pojem, je říci, že částečná bijekce od A do B je jakýkoli vztah R (který se ukazuje jako částečná funkce) s vlastností, že R je graf bijekce f : A 'B' , kde a ' je podmnožinou z a a B' je podmnožinou B .

Když je částečná bijekce na stejné sadě, někdy se tomu říká částečná transformace jeden na jednoho . Příkladem je Möbiova transformace jednoduše definovaná na komplexní rovině, nikoli její dokončení na rozšířenou komplexní rovinu.

Viz také

Poznámky

Reference

Toto téma je základním pojmem v teorii množin a lze jej nalézt v jakémkoli textu, který obsahuje úvod do teorie množin. Téměř všechny texty, které se zabývají úvodem do psaní důkazů, budou obsahovat část o teorii množin, takže téma lze nalézt v kterémkoli z těchto:

  • Vlk (1998). Proof, Logic and Conjecture: A Mathematician's Toolbox . Freeman.
  • Sundstrom (2003). Matematické uvažování: Psaní a dokazování . Prentice-Hall.
  • Kovář; Eggen; St.Andre (2006). Přechod k pokročilé matematice (6. vydání) . Thomson (Brooks/Cole).
  • Schumacher (1996). Kapitola nula: Základní pojmy abstraktní matematiky . Addison-Wesley.
  • O'Leary (2003). Struktura důkazu: s logikou a teorií množin . Prentice-Hall.
  • Morash. Most k abstraktní matematice . Náhodný dům.
  • Maddox (2002). Matematické myšlení a psaní . Harcourt/ Academic Press.
  • Ležel (2001). Analýza s úvodem k důkazu . Prentický sál.
  • Gilbert; Vanstone (2005). Úvod do matematického myšlení . Pearson Prentice-Hall.
  • Fletcher; Patty. Základy vyšší matematiky . PWS-Kent.
  • Iglewicz; Stoyle. Úvod do matematického uvažování . MacMillana.
  • Devlin, Keith (2004). Sady, funkce a logika: Úvod do abstraktní matematiky . Chapman & Hall/ CRC Press.
  • D'Angelo; Západ (2000). Matematické myšlení: Řešení problémů a důkazy . Prentický sál.
  • Cupillari . Ořechy a šrouby důkazů . Wadsworth.
  • Pouto. Úvod do abstraktní matematiky . Brooks/Cole.
  • Barnier; Feldman (2000). Úvod do pokročilé matematiky . Prentický sál.
  • Popel. Primer abstraktní matematiky . MAA.

externí odkazy