====== Leképezés ======
A hozzárendelés, vagy leképezés a matematikában alapfogalom, tehát nem definiáljuk.
A leképezések más megközelítésben speciális [[oktatas:matematika:halmazok:relacio]]-ként is felfoghatók, bár a leképezés "dinamikus voltát", "átalakító" jellegét ez a statikus megközelítés nem adja vissza.
A leképezések közül a középiskolai matematikában leggyakrabban a [[függvények]]kel foglalkozunk.
===== Injekció =====
Injekciónak vagy injektív leképezésnek nevezzük azokat a leképezéseket, melyek az értelmezési tartomány különböző elemeihez, az értékkészlet különböző elemeit rendelik.
**Definíció:**
//A// és //B// tetszőleges [[oktatas:matematika:halmazok:halmazok]] és //f: A -> B// leképezés. Az //f// **injekció**, ha
forall a,b in A esetén f(a) = f(b) doubleleftright a = b.
Szemléletesen: //A// halmaz elemeit //beleképezi// a //B// halmaz egy részhalmazába. Tehát //B// egy eleméhez legfeljebb egy ős tartozik (tehát 0 vagy 1).
==== Tulajdonságok ====
* Injekciók kompozíciója is injekció. Legyen ugyanis //f: A -> B// és //g: C -> D// injekció (//B// részhalmaza //C//-nek). Ha x_1<>x_2 doubleright g(x_1)<>g(x_2) a //g// injektivitása miatt, ekkor viszont //f// injektivitása miatt f(g(x_1))<>f(g(x_2)), ami épp azt jelenti, hogy az //fog// függvénykompozíció injekció.
* Ha //f: A -> B// injekció, akkor az //f': A -> Rf: x -> f(x)// függvény [[#bijekció]].
===== Szürjekció =====
Szürjekciónak, vagy szürjektív leképezésnek nevezzük azokat a leképezéseket, melyekben a képhalmaz egésze az értékkészlet.
**Definíció:**
//A// és //B// tetszőleges [[oktatas:matematika:halmazok:halmazok]] és //f: A -> B// leképezés. Az //f// **szürjekció**, ha
forall b in B-hez exists a in A : f(a)=b
Szemléletesen: //ráképezés//. Minden //B//-beli elemnek van őse (lehet hogy több is).
==== Tulajdonságok ====
* Ha az //f//, //g// leképezések szürjektívek, akkor a kompozíciójuk is szürjektív leképezés.
* Ha az g circ f függvénykompozíció szürjektív leképezés, akkor a g leképezés szürjekció.
===== Bijekció =====
Bijekciónak vagy bijektív leképezésnek nevezzük azokat a leképezéseket, amelyek egyidejűleg injektívek és szürjektívek.
Más szavakkal azt is mondhatjuk, hogy a bijektív leképezések kölcsönösen egyértelmű leképezések, ami azt jelenti, hogy a bijekció olyan megfeleltetést létesít két halmaz között, aminél az egyik halmaz minden egyes elemének a másik halmaz pontosan egy eleme felel meg, és fordítva.
**Definíció:**
//A// és //B// tetszőleges [[oktatas:matematika:halmazok:halmazok]] és //f: A -> B// leképezés. Az //f// **bijekció**, ha
forall a,b in A esetén f(a) = f(b) doubleleftright a = b, valamint\\
forall b in B-hez exists a in A : f(a)=b
====== Tulajdonságai ======
* Ha az //f// függvény bijektív, akkor a megfeleltetésként (relációként) vett inverze szintén függvény és egyúttal bijektív leképezés.
* Ha az //f//, //g// leképezések bijektívek, akkor a kompozíciójuk is bijektív leképezés.
* Ha az //g//o//f// függvénykompozíció bijektív leképezés, akkor a //g// leképezés szürjekció és az //f// leképezés injekció.
* Ha //X//,//Y// véges halmazok és //|X|=|Y|// , továbbá //f: X -> Y// leképezés, akkor a következő állítások ekvivalensek:
- //f// bijekció.
- //f// szürjekció.
- //f// injekció.
===== Bernstein–Schröder tétel =====
{{matematika:algebra:pro.jpg|}}
Ha van //f: A -> B// és //g: B -> A// injekció két halmaz között, akkor létezik //h: A <-> B// bijekció is.
**Bizonyítás:**
Legyen C_0=A backslash g delim{[}{B}{]}
és C_{n+1}=g delim{[}{f delim{[}{C_n}{]}}{]}
végül C=bigcup{n=0}{infty}{C_n}
Definiáljuk a //h// hozzárendelést a következő módon:
h(x)=delim{lbrace}{matrix{2}{1}{{f(x) ~ , x in C} {g^{-1}(x) ~ , x notin C}}}{}
A //h// hozzárendelés //A//-n értelmezett függvény, mert //A// minden //x// eleméhez rendel pontosan egy értéket. A hozzárendelés jól definiált, mert //g// injektívitása miatt //g-1// a //g[B]//-n értelmezett függvény, és ha //x// nem eleme //C//-nek, akkor //x// a //g// értékkészletében kell legyen.
A //h// injekció. Legyen ugyanis //A// két eleme //x1// és //x1//. Ha mindkettő egyúttal a //C// eleme is, akkor //h(x1)=f(x1)// és //h(x2)=f(x2)//, melyek nem lehetnek egyenlők //f// injektivitása miatt.
Ha egyik elem sem eleme //C//-nek, akkor //h(x1)=g-1(x1)// és //h(x2)=g-1(x2)//, melyek nem lehetnek egyenlők //g-1// injektivitása (azaz //g// függvény volta) miatt.
Végül, ha //x1// eleme //C//-nek, //x2// pedig nem, akkor a függvényértékek esetleges egyenlőségéből ellentmondásra jutunk:
h(x_1)=f(x_1)=g^{-1}(x_2)=h(x_2) doubleleftright g(f(x_1))=x_2 doubleright x_2 in C
A //h// függvény szürjektív. Legyen ugyanis y in B. Ekkor ha g(y) notin C, akkor h(g(y))=g^{-1}(g(y))=y in R_h. Ha pedig g(y) in C, akkor f^{-1}(y) in C, ezért h(f^{-1}(y))=f(f^{-1}(y))=y in R_h
(Ha y in B, g(y) in C, akkor g(y) notin C_0, tehát g(y) in C_n, n>0. Ekkor viszont //Cn// definíciója miatt exists x in C_{n-1}: g(f(x)) = g(y) doubleleftright f(x) = y)
Ezzel beláttuk, hogy //h// bijekció.
**Példa:**
Legyen az egyik halmaz a pozitív, a másik halmaz pedig a pozitív páros számok halmaza, //f: x -> 4x// és //d: x -> x//.
//C0// a pozitív páratlan számok halmaza lesz.\\
//C1// a 4-gyel osztható, de 8-cal már nem osztható pozitív számok halmaza lesz.\\
//C2// a 16-tal osztható, de 32-vel már nem osztható pozitív számok halmaza lesz.\\
Általában //Cn// a 2//2n//-el osztható, de kettő nagyobb hatványával már nem osztható pozitív számok halmazát jelöli.
A //C// halmaz azon pozitív számokat tartalmazza, melyek prím felbontásában a kettő páros kitevős hatványa szerepel.
A hozzárendelés: h(x)=delim{lbrace}{matrix{2}{1}{{x ~, x in C} {4x ~, x notin C}}}{}
[[http://en.wikipedia.org/wiki/Cantor%E2%80%93Bernstein%E2%80%93Schroeder_theorem]]
----
**Bizonyítás 2:**
Próbáljuk az //A// és //B// halmazt két-két diszjunkt részhalmazra (//A1//,//A2//,illetve //B1//,//B2//) bontani úgy, hogy //f// függvény leszűkítése //A1// -> //B1// bijekció, illetve //g// leszűkítése //B2//-> //A2// legyen.
Valójában //A1// megválasztása már meghatározza a többi halmazt:
* //B1// = //f[A1]//
* //B2// = //B \ B1// = //B \ f[A1]//
* //A2// = //g[B2]// = //g[B \ f[A1]//
A kiválasztott halmaz akkor felel meg az elvárásainknak, ha //A1=A\A2//, azaz //A1=A \ g[B \ f[A1]]//.
Legyen akkor //G: P(A) -> P(A)// függvény a következő hozzárendelési szabállyal: //G(X) = A \ g[B \ f[X]]//. Ez után a feladatunk olyan //X// halmaz keresése, melyre //X = G(X)// (fixpont keresés).
Először megmutatjuk, hogy //G// monoton, azaz X subset Y doubleright G(X) subset G(Y).
X subset Y doubleright f delim{[}{X}{]} subset f delim{[}{Y}{]} az //f// injektivitása miatt. Ekkor viszont B backslash f delim{[}{Y}{]} subset B backslash f delim{[}{X}{]}. Ez után //g// injektivitása miatt g delim{[}{B backslash f delim{[}{Y}{]}}{]} subset g delim{[}{B backslash f delim{[}{X}{]}}{]}, végül a különbség képzéskor megint fordul a relációs jel: A backslash g delim{[}{B backslash f delim{[}{Y}{]}}{]} subset A backslash g delim{[}{B backslash f delim{[}{X}{]}}{]}, amivel a monotonításra vonatkozó állítást igazoltuk.
Legyen most X = bigcap{G(Y) subset Y}{}{Y}
Ez a metszet létezik, hiszen van legalább egy a feltételnek megfelelő //Y// halmaz: maga az //A//.
//X// a metszetben szereplő összes //Y//-nak része, azaz X subset Y. A monotonitás miatt G(X) subset G(Y) subset Y. Mivel ez minden a metszetben szereplő //Y//-ra igaz, ezért G(X) subset X
Alkalmazzuk most //G//-t mindkét halmazra: G(G(X)) subset G(X).
Ez azt jelenti, hogy az //Y=G(X)// halmaz is a metszet egyik tagja, ezért X subset G(X)
Így //X=G(X)// teljesül, tehát találtunk //A1//-nak megfelelő halmazt, ami azt jelenti, hogy van bijekció //A// és //B// között.
=== Következmény ===
A tétel következménye, hogy a halmazok [[oktatas:matematika:halmazok:halmazok#számosság]]ai között értelmezett <= (ami nem reláció, csak olyasmi, mert a számosságok nem alkotnak halmazt) [[oktatas:matematika:halmazok:relacio#antiszimmetrikus]].