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 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ényekkel foglalkozunk.

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 halmazok és f: A → B leképezés. Az f injekció, ha esetén .

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).

• Injekciók kompozíciója is injekció. Legyen ugyanis f: A → B és g: C → D injekció (B részhalmaza C-nek). Ha a g injektivitása miatt, ekkor viszont f injektivitása miatt , ami épp azt jelenti, hogy az fog függvénykompozíció injekció.
• Ha f: A → B injekció, akkor az f': A → R_f: x → f(x) függvény bijekció.

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 halmazok és f: A → B leképezés. Az f szürjekció, ha -hez

Szemléletesen: ráképezés. Minden B-beli elemnek van őse (lehet hogy több is).

• Ha az f, g leképezések szürjektívek, akkor a kompozíciójuk is szürjektív leképezés.
• Ha az függvénykompozíció szürjektív leképezés, akkor a g leképezés szürjekció.

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 halmazok és f: A → B leképezés. Az f bijekció, ha esetén , valamint
-hez

• 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 gof 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:
  1. f bijekció.
  2. f szürjekció.
  3. f injekció.

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 és végül

Definiáljuk a h hozzárendelést a következő módon:

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 x₁ és x₁. Ha mindkettő egyúttal a C eleme is, akkor h(x₁)=f(x₁) és h(x₂)=f(x₂), melyek nem lehetnek egyenlők f injektivitása miatt. Ha egyik elem sem eleme C-nek, akkor h(x₁)=g^-1(x₁) és h(x₂)=g^-1(x₂), melyek nem lehetnek egyenlők g^-1 injektivitása (azaz g függvény volta) miatt. Végül, ha x₁ eleme C-nek, x₂ pedig nem, akkor a függvényértékek esetleges egyenlőségéből ellentmondásra jutunk:

A h függvény szürjektív. Legyen ugyanis . Ekkor ha , akkor . Ha pedig , akkor , ezért

(Ha , akkor , tehát . Ekkor viszont C_n definíciója miatt )

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.

C₀ a pozitív páratlan számok halmaza lesz.
C₁ a 4-gyel osztható, de 8-cal már nem osztható pozitív számok halmaza lesz.
C₂ a 16-tal osztható, de 32-vel már nem osztható pozitív számok halmaza lesz.
Általában C_n a 2²ⁿ-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:

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 (A₁,A₂,illetve B₁,B₂) bontani úgy, hogy f függvény leszűkítése A₁ → B₁ bijekció, illetve g leszűkítése B₂→ A₂ legyen.

Valójában A₁ megválasztása már meghatározza a többi halmazt:

• B₁ = f[A₁]
• B₂ = B \ B₁ = B \ f[A₁]
• A₂ = g[B2] = g[B \ f[A₁]

A kiválasztott halmaz akkor felel meg az elvárásainknak, ha A₁=A\A₂, azaz A₁=A \ g[B \ f[A₁]].

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 .

az f injektivitása miatt. Ekkor viszont . Ez után g injektivitása miatt , végül a különbség képzéskor megint fordul a relációs jel: , amivel a monotonításra vonatkozó állítást igazoltuk.

Legyen most 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 . A monotonitás miatt . Mivel ez minden a metszetben szereplő Y-ra igaz, ezért

Alkalmazzuk most G-t mindkét halmazra: . Ez azt jelenti, hogy az Y=G(X) halmaz is a metszet egyik tagja, ezért

Így X=G(X) teljesül, tehát találtunk A₁-nak megfelelő halmazt, ami azt jelenti, hogy van bijekció A és B között.

A tétel következménye, hogy a halmazok számosságai között értelmezett (ami nem reláció, csak olyasmi, mert a számosságok nem alkotnak halmazt) antiszimmetrikus.