surjective function

surjective function (tsz. surjective functions)

1. (informatika) szürjektív függvény

A szürjektív függvény (angolul surjective function), más néven leképezés, teljes leképezés, vagy onto függvény, a matematikában az egyik legfontosabb típusú függvény. Ez a fogalom központi szerepet játszik az analízisben, halmazelméletben, algebrai struktúrákban, valamint a számítástechnikában is.

Ebben az összefoglalóban részletesen bemutatjuk, hogy mit jelent a szürjektivitás, hogyan ismerhető fel, milyen tulajdonságai és alkalmazásai vannak, és példákkal is szemléltetjük.

Formálisan egy ${\textstyle f:A\to B}$ függvény szürjektív, ha a céltartomány (B) minden elemére létezik olyan értelmezési tartománybeli (A-beli) elem, amelyet rá leképez a függvény:

$${\displaystyle \forall y\in B,\ \exists x\in A\ {\text{melyre}}\ f(x)=y}$$

Tehát nincs olyan “kint maradó” elem a céltartományban, amit a függvény ne tudna elérni. Ilyenkor azt mondjuk, hogy a függvény lefedi a teljes céltartományt.

Képzeljünk el két halmazt:

• ${\textstyle A=\{a_{1},a_{2},a_{3}\}}$
• ${\textstyle B=\{b_{1},b_{2}\}}$

Ha a függvény úgy képez le, hogy minden ${\textstyle b\in B}$-hez van legalább egy ${\textstyle a\in A}$, amely ${\textstyle f(a)=b}$, akkor szürjektív.

A:  a1   a2   a3
     |    |    |
     v    v    v
B:  b1   b2

Minden „B” halmazbeli pontba legalább egy nyíl mutat az „A”-ból.

Egy függvény nem szürjektív, ha van olyan céltartománybeli érték, amit nem ér el. Például:

• ${\textstyle f(x)=x^{2}}$ az egész számok halmazán ${\textstyle \mathbb {Z} \to \mathbb {Z} }$ nem szürjektív, mert nincs olyan egész ${\textstyle x}$, amelyre ${\textstyle f(x)=-1}$ lenne (nincs olyan egész szám, aminek a négyzete negatív).

Legyen ${\textstyle f:\mathbb {Z} \to \mathbb {Z} }$, ${\textstyle f(x)=x+1}$

Ez a függvény szürjektív, mert bármely ${\textstyle y\in \mathbb {Z} }$ esetén tudunk találni olyan ${\textstyle x\in \mathbb {Z} }$-t, hogy ${\textstyle f(x)=y}$. Egyszerűen:

$${\displaystyle f(x)=y\Rightarrow x=y-1}$$

Legyen ${\textstyle f:\mathbb {R} \to \mathbb {R} }$, ${\textstyle f(x)=x^{3}}$

Ez is szürjektív, mivel minden valós számnak van köbgyöke.

$${\displaystyle f^{-1}(y)={\sqrt{y}}}$$

Legyen ${\textstyle f:\mathbb {Z} \to \mathbb {Z} }$, ${\textstyle f(x)=2x}$

Ez nem szürjektív, mert az olyan ${\textstyle y}$-okra, amik páratlanok, nem található ${\textstyle x\in \mathbb {Z} }$, hogy ${\textstyle f(x)=y}$.

• Nem egyértelmű: Egy szürjektív függvény nem feltétlen injektív is (lehet, hogy két különböző érték ugyanarra a célértékre képeződik).
• Létezik bal-inverz: Ha ${\textstyle f:A\to B}$ szürjektív, akkor létezik olyan függvény ${\textstyle g:B\to A}$, amelyre ${\textstyle f(g(y))=y}$.
• Kompozíció:
  • Ha ${\textstyle f:A\to B}$ és ${\textstyle g:B\to C}$ szürjektívek, akkor ${\textstyle g\circ f}$ is szürjektív.
• Halmazelméletben: Ha létezik szürjektív függvény ${\textstyle A\to B}$, akkor ${\textstyle |B|\leq |A|}$.

Csak a bijektív függvényeknek van egyértelműen értelmezett inverz függvénye.

• Algebra: Csoporthomomorfizmusok esetén a szürjektivitás biztosítja, hogy a struktúra “lefedi” a célcsoportot.
• Analízis: Függvények értékkészleteinek vizsgálata során fontos tudni, hogy a függvény eléri-e a céltartomány minden pontját.
• Számítástechnikában:
  • Adattömörítésnél hasznos, hogy ne maradjon ki semmilyen dekódolható forma.
  • Adatbázis-leképezéseknél szükséges, hogy minden céltáblához legyen adatforrás.

1. Adott értékképet meg kell oldani: Képezd fel az egyenletet ${\textstyle f(x)=y}$ alakban.
2. Meg kell nézni, hogy létezik-e megoldás minden ${\textstyle y\in Y}$-ra.
3. Megoldás függvénye: Ha bármely ${\textstyle y}$-ra létezik ${\textstyle x}$, akkor szürjektív.

• Egy függvény szürjektív, ha a céltartomány minden eleme elérhető.
• Nem szükséges, hogy egyedileg érkezzenek az értékek (nem kell injektívnek lennie).
• A szürjektív függvények fontos szerepet játszanak a matematika és az informatika több területén is.
• A szürjektivitás eldöntése általában egy egyenlet megoldhatóságának vizsgálatával történik.

• surjective function - Szótár.net (en-hu)
• surjective function - Sztaki (en-hu)
• surjective function - Merriam–Webster
• surjective function - Cambridge
• surjective function - WordNet
• surjective function - Яндекс (en-ru)
• surjective function - Google (en-hu)
• surjective function - Wikidata
• surjective function - Wikipédia (angol)