Surjection

V matematiky , je surjekce nebo surjektivní aplikace je aplikace , pro které každý prvek množiny příjezdu má alespoň jeden předchůdce , to znamená, že je obraz z alespoň jednoho prvku z počáteční sady . Je ekvivalentní říci, že sada obrázků se rovná sadě příjezdu.

Je možné použít adjektivum „surjektiv“ na funkci (nebo dokonce na korespondenci ), jejíž doménou definice není celá výchozí množina, ale obecně je termín „surjekce“ vyhrazen pro aplikace (které jsou definovány v celé své startovací sada), na kterou se v tomto článku omezíme (více viz odstavec „Funkce a aplikace“ v článku „Aplikace“ ).

Pro označení počáteční a koncové množiny surjekce je obvyklé říkat „od A do B “ místo „od A do B “ jako u aplikace obecně.

V případě reálné funkce reálné proměnné je její surjektivita ekvivalentní skutečnosti, že její graf protíná jakoukoli přímku rovnoběžnou s osou x.

Surjektivní a injektivní aplikace je bijekce .

Formální definice

Mapa $f$ z $X$ k $Y$ je prý surjektivní-li z jakéhokoliv prvku $y$ z $Y$ , existuje alespoň jeden prvek $x$ o $X,$ tak, že $f ( x ) = y$ , který je z formálního:

{\ displaystyle \ forall y \ in Y \ quad \ existuje x \ in X \ quad f (x) = y}

Příklady

Konkrétní příklad

Zvažujeme případ rekreačního střediska, kde musí 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 kompatibilní, pouze pokud se počet turistů rovná počtu pokojů. V tomto 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é: aplikace bude poté injektivní i surjektivní; řekneme, že je to bijektivní .

Příklady a protiklady reálných funkcí

Funkce definovaná

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

není surjektivní, protože některá reálná čísla nemají předchůdce. Například neexistuje žádné skutečné x takové, že f ( x ) = −4. Pokud ale změníme definici f tak, že jako koncovou množinu dáme + ,

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

pak se to stane proto, že každý pozitivní reálné má alespoň jeden předchůdce: 0 má právě jeden vyvolávající předchozí, 0, a všechna striktně pozitivní reálných čísel y mají dvě, na druhou odmocninu z y a její opak .

Funkce definovaná

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

je surjective, protože pro libovolné reálné y existují řešení rovnice y = 2 x + 1 neznámého x ; řešení je x = ( y - 1) / 2.

Funkce definovaná

{\ begin {matrix} g: & \ mathbb {R} & \ rightarrow & \ mathbb {R} \\ & x & \ mapsto & \ cos (x) \\\ end {matrix}}

není surjektivní, protože realita přísně větší než 1 nebo přísně menší než –1 nemá předchůdce. Ale funkce definovaná

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

který má stejný výraz jako g , ale s množinou příchodů, která byla omezena na množinu realů mezi –1 a 1, je surjektivní. Ve skutečnosti pro libovolné reálné y intervalu [–1, 1] existuje řešení rovnice y = cos ( x ) neznámého x : jedná se o reálné oblasti x = ± arccos ( y ) + 2 k $π$ pro libovolné relativní celé číslo k .

Na těchto několika příkladech vidíme, že je vždy možné transformovat nesurjektivní mapu na surjekci za podmínky omezení její koncové sady .

Vlastnosti

Snížení příletové sady

Pokud je f mapa od X do Y a Im ( f ) = f ( X ) její obrazová sada (tj. Sada obrazů f prvků X ), pak mapa

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

je nadmíru.

Jinými slovy, je-li f korestrikováno na Im ( f ), tj. Nahradíme-li jeho příchod nastavený jeho sadou obrazů, stane se surjektivním .

Kanonický rozklad

Libovolná mapa f může být rozložena jako f = i ∘ s, kde s je surjection a i injekce. Tento rozklad je jedinečný s výjimkou izomorfismu . Rozpis je uveden v podrobném odstavci. Další (ekvivalent), je zvolit pro S na surjekce definované výše, a i na kanonický injekci obrazu o f v jeho příjezdu sadě.

Přímé a vzájemné obrázky

Pro libovolnou mapu f : X → Y jsou ekvivalentní následující čtyři vlastnosti:

f je surjektivní;
jakýkoli podmnožina B z Y je přímá obraz jejího vzájemného obrazu , tj. f ( f -1 ( B )) = B ;
f ( f -1 ( Y )) = Y ;
pro jakoukoli část A z X je doplňkem přímého obrazu A, je zahrnuta v přímém obrazu komplementu A , tj. Y \ f ( A ) ⊂ f ( X \ A ).

Surjektivita a sloučenina

Nechť f aplikační X v Y .

Pro jakoukoli mapu g od Y do Z :
- je-li g ∘ f surjektivní, pak g je surjektivní;
- jestliže f a g jsou surjektivní, pak g ∘ f je surjektivní;
- jestliže g je injective a pokud g ∘ f je surjective, pak f je surjective.
f je surjektivní tehdy a jen tehdy, když pro všechny Z a pro všechny mapy g a h z Y do Z , g ∘ f = h ∘ f sebou nese g = h . Jinými slovy, surjekce jsou přesně epimorfismem v kategorii množin .

Sekce a axiom výběru

Nechť f aplikační X v Y . Pokud f je „ pravým invertovat “ , tj. V případě, že existuje mapy g z Y pro X tak, že složená funkce f ∘ g se rovná mapy identity na Y , potom f surjective (od vlastnosti pohledu shora ).

Taková mapa g se nazývá řez nebo inverzní napravo od f . Je to nutně injekční .

Naopak, je-li f surjektivní, pak připouští část. Tato vlastnost je založena na skutečnosti, že jeden může vždy „šipka nahoru“ z Y na X . Vždy platí, pokud je Y hotové. Tvrzení, že platí pro jakoukoli množinu Y, je ekvivalentní s axiomem volby .

Kardinálové

Pokud existuje surjekce z X do Y , pak (z výše uvedeného, tedy za předpokladu axiomu volby) existuje injekce z Y do X , jinými slovy množina X má alespoň tolik prvků než množina Y , v smysl kardinálů .
Cantorova věta (bez zvoleného axiomu): pro libovolnou množinu X neexistuje žádné překvapení X v množině jejích částí .

Poznámky a odkazy

Viz například opravená cvičení kapitoly „Injekce, surjekce, bijekce“ na Wikiversity .
Lucien Chambadal a Jean-Louis Ovaert, kurz matematiky , sv. 1: Základní pojmy algebry a analýzy , Gauthier-Villars ,1966, str. 27.
N. Bourbaki , Základy matematiky : Teorie množin [ detail vydání ], str. II-19 v Knihách Google .
Bourbaki , str. II-18, předveďte to pomocí silnější formy než axiom výběru .

Podívejte se také

Princip zásuvky
Pascalův inverzní vzorec , který udává počet surjekcí z jedné konečné sady do druhé.
Princip zahrnutí-vyloučení , který poskytuje další ukázku počtu surjekcí z jedné sady do druhé.