====== 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]].