Injektiivne funktsioon

Joonis illustreerib injektsiooni: hulga Y igal element on ülimalt üks originaal: elementidel A, B ja D on igaühel üks originaal, elemendil C ei ole ühtegi originaali.

Injektiivne funktsioon ehk injektiivne kujutus ehk injektsioon ehk üksühene kujutus on funktsioon $f:X\to Y$, mille korral sihthulga $Y$ iga elemendi $y$ puhul on olemas ülimalt üks (võib-olla mitte ühtegi) lähtehulga $X$ element $x$, millele funktsioon teda vastavusse seab ($f(x)=y$), ehk teiste sõnadega, mille korral lähtehulga kahele eri elemendile ei seata kunagi vastavusse sihthulga üht ja sedasama elementi. Injektiivne funktsioon on injektiivse seose erijuht.

Injektiivse funktsiooni sihthulgal ei saa olla väiksem võimsus kui lähtehulgal, sest muidu ei jätkuks sihthulgas kõigi lähtehulga elementide jaoks elemente.

Injektiivse funktsiooni kujutis $\{f(x)|x\in X\}$ võib olla sihthulga $Y$ pärisalamhulk. Teiste sõnadega, võib olla elemente $y\in Y$, mis ei ole kujutised $f(x)$, (nii on ka joonisel). Selle poolest erineb injektiivne funktsioon bijektiivsest funktsioonist, mille puhul peale injektiivsuse nõutakse veel, et sihthulga iga element on kujutis $f(x)$.

Funktsiooni $f:X\to Y$ injektiivsust tähistatakse mõnikord märgiga $f:X\hookrightarrow Y$, mis on koostatud märkidest $\subset$ ja $\to$. See meenutab hulga $X$ sisestamist ülemhulka $Y$ funktsiooni $f:X\to Y$ abil, mis kujutab hulga $X$ iga elemendi temaks endaks: $f(x)=x$ .

Formaalsed definitsioonid

Olgu $X$ ja $Y$ hulgad ning $f:X\to Y$ funktsioon hulgast $X$ hulka $Y$.
Järgmised definitsioonid on samaväärsed:

• Funktsiooni $f$ nimetatakse injektiivseks, kui iga $y$-i korral hulgast $Y$ eksisteerib ülimalt üks $x$ hulgast $X$, nii et $f(x)=y$. ("Ülimalt üks" tähendab 'mitte ühtegi või täpselt üks, kuid mitte rohkem.)
  Formaalselt: $\mathrm{\forall }y\in Y(\mathrm{\exists }!x\in X:f(x)=y\vee \mathrm{\neg }(\mathrm{\exists }x\in X:f(x)=y)).$

• Funktsiooni $f$ nimetatakse injektiivseks, kui funktsiooni väärtuste (muutuja $y$ väärtuste) võrdusest järeldub funktsiooni argumendi $x$ väärtuste võrdus.
  Formaalselt: $\mathrm{\forall }{x}_1,x_2\in X:(f(x_1)=f(x_2)\Rightarrow x_1=x_2)$

• Funktsiooni $f$ nimetatakse injektiivseks, kui argumendi $x$ erinevad väärtused kujutatakse alati erinevateks funktsiooni väärtusteks.
  Formaalselt: $\mathrm{\forall }{x}_1,x_2\in X:(x_1\ne x_2\Rightarrow f(x_1)\ne f(x_2))$
  

Kui injektiivsuse tõestamiseks kasutatakse kolmandat tõestust, viib see sageli vastuväitelise tõestuseni. Otsene tõestus teise definitsiooni abil võib olla elegantsem ja lühem.

Näiteid ja mittenäiteid

Mitteinjektiivne funktsioon

• Iga funktsioon $\{\bullet ,\bullet \}\to \{\bullet \}$ kaheelemendilisest hulgast üheelemendilisse hulka on mitteinjektiivne.
• Mittematemaatiline näide. Funktsioon, mis seab igale Eesti isikukoodiga inimesele vastavusse tema isikukoodi, on injektiivne, kusjuures sihthulgaks võetakse kõigi isikukoodiks kõlblike arvude hulk. (Eeldame, et ühtki isikukoodi ei rakendata mitu korda.)
• Olgu $\mathbb{N}$ naturaalarvude hulk ja $\mathbb{Z}$ täisarvude hulk.

Funktsioon $f_1:\mathbb{N}\to \mathbb{N},x\mapsto 2x$ on injektiivne.

Funktsioon $f_2:\mathbb{Z}\to \mathbb{Z},x\mapsto 2x$ on injektiivne.

Funktsioon $f_3:\mathbb{N}\to \mathbb{N},x\mapsto x^2$ on injektiivne.

Funktsioon $f_4:\mathbb{Z}\to \mathbb{Z},x\mapsto x^2$ ei ole injektiivne, sest näiteks $f(1)=f(-1)$.

Omadused

Injektiivsus sõltub ainult graafikust

Funktsiooni $f:A\to B$ injektiivsus sõltub ainult graafikust $\{(x,f(x))\mid x\in A\}$ (erinevalt sürjektiivsusest, mis sõltub ka sihthulgast $B$, mille üle graafiku järgi ei saa otsustada).

Injektiivsuse tunnused

Funktsioon $f:A\to B$ on injektiivne parajasti siis, kui kõikide alamhulkade $X,Y\subseteq A$ korral $f(X\cap Y)=f(X)\cap f(Y)$.

Funktsioon $f:A\to B$ on injektiivne parajasti siis, kui kõikide $T\subset A$ korral $f^{-1}(f(T))=T$.

Kategooriateooriaga seotud omadused

Kui funktsioonid $f:A\to B$ ja $g:B\to C$ on injektiivsed, siis ka nende funktsioonide kompositsioon $g\circ f:A\to C$ on injektiivne.

Kui $g\circ f$ on injektiivne, siis $f$ on injektiivne.

Funktsioon $f:A\to B$, mille lähtehulk $A$ on mittetühi, on injektiivne parajasti siis, kui funktsioonil $f$ on vasakpoolne pöördelement, st funktsioon $g:B\to A$ mille korral $g\circ f={\mathrm{id}}_A$, kus ${\mathrm{id}}_A$ on samasuskujutus hulgal $A$. Hulkade kategoorias Set tähendab see tingimus, et injektsioonid on selle kategooria vasakult pööratavad morfismid ehk koretraktsioonid.