Cím: Relációk, függvények, morfizmusok
Szerző(k):  Fried Ervin 
Füzet: 1988/november, 346 - 351. oldal  PDF  |  MathML 
Témakör(ök): Szakmai cikkek

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.

A KöMaL 2697. sz. feladatára nem érkezett be egyetlen helyes megoldás sem. Ennek fő oka az volt, hogy a beküldők azt a feltételt, hogy egy gráfot önmagába képezünk, úgy értelmezték, hogy a leképezés önmagára történik, azaz minden csúcs fellép valamelyik csúcs képeként (noha ezek különbözőségére már az elsős gimnáziumi tankönyv is felhívja a figyelmet). Ilyen félreértések elkerülése végett néhány alapvető fogalmat szeretnénk tisztázni.
Emellett néhány ekvivalens fogalmat és elemi tételecskét is megmutatunk, hogy az olvasó egy-egy fogalom más-más oldalával is találkozhasson.

 

I. Relációk
 
Reláción halmazok elemei közötti kapcsolatot értünk. Egészen általánosan adva van két halmaz A és B; és bizonyos A-beli elemek állnak kapcsolatban valamilyen B-beli elemekkel. Ezt a kapcsolatot rendszerint valamilyen módon leírjuk. Arra nincs lehetőségünk, hogy minden lehetséges kapcsolatot valamilyen utasítással adjunk meg. Azt viszont megtehetjük, hogy felsoroljuk azokat a párokat, amelyekre a kapcsolat fennáll. Akkor is megtehetjük ezt, ha a tényleges felsorolás nem keresztülvihető.
Az összes szóba jövő párok halmazát A×B jelöli; ez a halmaz mindazon (a,b) párokból áll, amelyekre a∈A és b∈B teljesül. Egy relációt tehát úgy tekinthetünk, mint az A×B halmaz valamely R részhalmazát.
Az A-beli a és a B-beli b elemek pontosan akkor vannak R relációban, ha (a,b)∈R.
(Ezt a kapcsolatot sokszor aRB-vel is jelöljük. Például az A=B esetben az ,,egyenlőség'' relációt úgy definiáljuk, hogy két elem pontosan akkor áll egymással e relációban, ha megegyezik. Ha a relációt, mint az A×A részhalmazát az = jel jelöli, akkor a és b egyenlőségét (a,b)∈= helyett a=b jelöli.)
A relációkból kiindulva két úton megyünk tovább. Először olyan relációkat nézünk, ahol a két halmaz megegyezik; majd az általános fogalmat úgy szűkítjük le, hogy a függvény fogalmához jussunk.
 

II. Irányított gráfok
 
Nézzük most azt az esetet, amikor a B halmaz megegyezik az A-val. Ekkor az A×A valamely R részhalmazáról van szó, és azt mondjuk, hogy R egy reláció az A-n (vagy az A egy relációja).
 
Ha R egy reláció az A-n, akkor (A,R)-t egy irányított (egyszerű) gráfnak nevezzük.
Ez már ,,gráfelméleti nézőpont''; ezért elmondjuk az itt használatos elnevezéseket. Az A elemei a gráf csúcsai, vagy csúcspontjai, vagy szögpontjai. Az R elemei (irányított) élek. Ezt úgy képzelhetjük el, hogy ha (a,b)R-beli, akkor egy ,,nyilat'' húzunk az a csúcstól a b csúcsig. A gráf elnevezésében erre utal az ,,irányított'' szó; míg az ,,egyszerű'' azt fejezi ki, hogy az a-ból a b-be egyetlen nyilat rajzolunk. Ha (a,b)R-beli, akkor azt mondjuk, hogy az a csúcsban hurok van.
 

III. Irányítatlan gráfok
 
Az A halmazon adott R relációt szimmetrikusnak nevezzük, ha valahányszor (a,b) eleme R-nek, mindannyiszor (b,a) is R-hez tartozik.
Ha R egy szimmetrikus reláció az A-n, akkor (A,R) neve (irányítatlan) gráf.
A szimmetria miatt, ha (a,b) R-beli, akkor úgy képzelhetjük, hogy a köztük levő nyílnak ,,két feje van'', mind az a, mind a b irányában. Éppen ezért ezeket a fejeket el is hagyhatjuk, hiszen nem kell az irányokat megkülönböztetni. (Megemlítjük, hogy a hurok minden esetben irányítatlan élnek tekinthető.)
 

IV. Rendezés
 
E címszó alatt a ,,kisebb vagy egyenlő'' fogalmát szeretnénk megfogalmazni. Ehhez a relációk három tulajdonságára van szükségünk.
Az A halmazon értelmezett R relációt reflexív-nek nevezzük, ha bármely A-beli a esetén (a,a) R-beli.
Az R reláció tranzitív, ha valahányszor (a,b) és (b,c) R-beliek, mindannyiszor (a,c) is R-ben van.
Az R reláció antiszimmetrikus, ha (a,b) és (b,a) csak akkor lehet R-beli, ha a=b.
(Jegyezzük meg, hogy nem tettük itt fel azt, hogy (a,a) feltétlenül R-beli.)
Egy R reflexív, antiszimmetrikus és tranzitív reláció neve: részben-rendezés.
Részben-rendezést alkotnak például a természetes számok az oszthatóságra mint relációra nézve: Minden szám osztható önmagával (reflexív), ha a osztója b-nek és b osztója c-nek, akkor a is osztója c-nek (tranzitív), végül pedig ha a és b mindegyike osztója a másiknak, akkor biztosan egyenlőek (antiszimmetria).
Ez a reláció nem olyan, mint a számok ,,sorbarakása'', mert itt összehasonlíthatatlan elemek is vannak; pl. 2 és 3 egyike sem osztója a másiknak. Ha az összehasonlíthatóságot is megköveteljük, akkor kapjuk a rendezést (vagy elrendezést).
Az A halmazon értelmezett R részbenrendezést rendezésnek nevezzük, ha bármely A-beli a és b elemek esetén (a,b) és (b,a) valamelyike R-ben van.
Természetesen ilyen rendezés az egész, racionális stb. számoknak a nagyság szerinti összerakása.
(Megjegyezzük, hogy sok esetben a rendezést úgy definiálják, hogy azzal ne a ,,kisebb-egyenlő'', hanem a ,,kisebb'' fogalmát írják le. Ez a reláció ,,irreflexív'', és az antiszimmetriát is másképpen kell megfogalmazni.)
 

V. Ekvivalencia reláció
 
Ez a reláció az ,,ugyanúgy viselkedést'' fogalmazza meg.
Az A halmazon értelmezett reflexív, szimmetrikus és tranzitív R relációt ekvivalencia-relációnak nevezzük.
Ilyen reláció például a sík háromszögein az egybevágóság. Ilyen reláció a sík egyenesei között a párhuzamosság (az egymással párhuzamos egyeneseknek ,,közös tulajdonsága'' az irányuk). Ilyen R relációt kaphatunk például az egész számokon, ha azt mondjuk, hogy (a,b) legyen R-beli, ha a-b osztható 5-tel (5 helyett bármely más egész szám megfelelne).
Az ekvivalencia-relációknak a függvényekkel való kapcsolatára még visszatérünk.
 

VI. Függvények
 
A függvény fogalmának pontos definiálása igen körülményes volna; de ez nem is feltétlenül szükséges. Azt kell viszont megérteni, hogy mi egy függvény. Akkor beszélünk az A halmazt a B halmazba leképező függvényről, ha az A halmaz minden egyes eleméhez hozzárendelünk egy B-beli elemet. Persze a fenti magyarázat olyan szavakat tartalmaz, amelyeket értünk ugyan, de éppen úgy nincsenek definiálva, mint a függvény. Mindenesetre, a fenti eszmefuttatás arra jó, hogy indokolja: a függvény szó helyett ugyanebben az értelemben használhatjuk (és használjuk) a leképezés és a hozzárendelés szavakat.
Most néhány (jól ismert) elnevezést és jelölést közlünk:
Azt a tényt, hogy az f függvény az A halmazt képezi le a B halmazba, úgy jelöljük, hogy
f:A→B

Az A halmaz az f értelmezési tartománya. B-t szokták az f értékkészletének nevezni, ez azonban azt a félreértést sugallja, hogy B pontosan az f értékeiből áll. Ennek elkerülése végett mi B-t az f képtartományának fogjuk hívni.
Ha a∈A, akkor azt a B-beli elemet, amelyre f az a elemet képezi, f(a) jelöli. Ha b=f(a), akkor ezt a tényt úgy is jelöljük, hogy
f:a↦b.

(Vegyük észre, hogy itt a nyílnak egy ,,talpa'' is van. Ez azt mutatja, hogy a függvény a nyíl bal oldalán álló elemet a jobb oldali elemre képezi le.)
Az alábbiakban a függvény fogalmát kissé elbonyolítjuk avégett, hogy lehetőségünk nyíljon a ,,precízkedés''-re.
Az f:A→B függvény azzal van megadva, ha megmondjuk minden egyes A-beli elemnek a képét. Más szóval fel kell sorolni az összes (a,f(a)) párokat. Ilyen párok halmaza viszont nem más, mint egy reláció az A és B halmazok között. Ha ezt a relációt R(f)-fel jelöljük, akkor azt kapjuk, hogy az A×B halmaz R(f) részhalmazának elemei éppen az (a,f(a)) alakú párok.
Hogyan ismerhető fel, hogy ez a reláció egy függvényt ad? Úgy, hogy a párok első eleme egyértelműen meghatározza a második elemét. Ez módot ad arra, hogy a függvényt a relációk segítségével definiálhassuk:
Az A×B egy R részhalmazát akkor nevezzük az A-t B-be képező függvénynek, ha (a,u), (a,v)∈R-ből u=v következik. (Ez csak egy definiálási lehetőség, mi valójában tudjuk, mi a függvény).
Most a függvények néhány speciális fajtájával ismerkedünk meg:
I. Szürjektív függvény. Az f:A→B függvény értékei, tehát az f(a) elemek a B-ben vannak. Az azonban nem feltétlenül igaz, hogy minden B-beli elem ilyen alakú volna. (Legyen például A=B a pozitív egészek halmaza, és f(i)=i+1. Ez esetben az 1 szám B-ben van, de nem írható f(i) alakban.) A B f(a) alakú elemeinek a halmazát az f értékkészletének nevezzük.
Az f függvényt szürjektívnek nevezzük, ha értékkészlete megegyezik képtartományával.
Ez az az eset, amikor a függvény a képtartományba képez le.
2. Injektív függvény. Ez a fogalom a szürjektivitás ,,duálisa''. Egy függvényt akkor nevezünk injektívnek, ha különböző elemek képe is különböző. Az előbbi f:i↦i+1 függvény például injektív. Nem injektív azonban az a pozitív egészeken értelmezett g függvény, amelyre g(i)=i-1, ha i>1, és g(1)=1. (Viszont g nyilván szürjektív.)
A g függvényt injektívnek nevezzük, ha g(a)=g(b) esetén a=b is fennáll.
Természetesen vannak olyan függvények, amelyek nem szürjektívek és nem is injektívek. Képezzük például a pozitív egészek halmazát önmagába úgy, hogy minden egész szám képe legyen a 3. Nem ennyire triviális az a h függvény, amelyre h(2i)=2i-1 és h(2i+1)=2i+1.
Az előzőekben olyan függvényeket láttunk, amelyek a pozitív egészek halmazát önmagába képezték le; egyikük injektív volt, de nem szürjektív; másikuk szürjektív volt, de nem injektív. Ez véges halmazok esetén nem lehetséges.
 
Tétel: Legyen A véges halmaz. Az f:A→A függvény pontosan akkor injektív, ha szürjektív.
 

Bizonyítás. Tegyük fel, hogy A-nak n darab eleme van. Nem megy az általánosság rovására, ha feltesszük, hogy az A elemei éppen az 1,2,...,n természetes számok. Az f függvény értékei az f(1),f(2),...,f(n) számok. Ezeknek a száma legfeljebb n; mert nem feltétlen különbözőek. Az f függvény injektivitása pontosan azt jelenti, hogy a kapott függvényértékek mind különbözőek ‐ tehát számuk n. Ez viszont éppen azt jelenti, hogy az A halmaz n eleméből n darab függvényérték, azaz mindegyik‐ vagyis a függvény szürjektív.
A fenti függvénytípusoknak szoros kapcsolata van az egyenletek megoldhatóságával. Az f szürjektivitása azt mondja, hogy B minden b eleme előfordul képként; vagyis az f(x)=b egyenlet mindig megoldható. A g injektivitása azt jelenti, hogy különböző elemek képe is különböző, azaz amennyiben a g(x)=b egyenletnek van megoldása, akkor ez a megoldás egyértelmű.
 

3. Bijektív függvény. Ez a fenti két függvénytípus egyesítése:
Az f függvényt akkor nevezzük bijektívnek (kölcsönösen egyértelműnek), ha injektív és szűrjektív.
 

4. Függvények kompozíciója.
 

Az f:A→B és g:B→C függvények kompozícióján azt a gf:A→C függvényt értjük, amelyre gf:a↦g(f(a)), minden a∈A esetén.
Vegyük észre, hogy az f és a g sorrendje nagyon fontos (ha C és A különbözőek, akkor nincs is értelme annak, hogy fg). Így a kompozíció mint függvények közötti művelet nem is lehet kommutatív.
*
Feladat: Mutassuk meg, hogy a kompozíció mint függvények közötti művelet asszociatív (ha elvégezhető).
*
Minden egyes halmazon külön-külön értelmezhető egy triviálisnak tűnő, de nagyon fontos függvény:
Az A halmaz identitásfüggvényének nevezzük azt az iA:A→A függvényt, amelyre minden A-beli a esetén iA:a↦a.
 
Tétel: Ha f:A→B és g:C→A tetszőleges függvények, akkor fiA=f és iAg=g.
 
Bizonyítás Tetszőleges A-beli a-ra fiA(a)=f(iA(a))=f(a); és tetszőleges C-beli c-re iAg(c)=iA(g(c))=g(c). (Megjegyezzük, hogy ez a tulajdonsága csak az identitásfüggvényeknek van meg. Ez azt jelenti, hogy az identitásfüggvények jellemezhetők a függvénykompozíció segítségével; anélkül, hogy megmondanánk, mi az identitás-függvény definíciója.)
Az identitásfüggvények segítségével jellemezhetőek az injektív, szürjektív és bijektív függvények is. Ehhez azonban mindenekelőtt szükség van három elnevezésre:
Ha az f függvényhez található olyan g függvény, amelyre gf identitásfüggvény, akkor g-t az f egy bal inverzének nevezzük; ha olyan h függvény található, amelyre fh identitásfüggvény, akkor h az f egy jobb inverze; amennyiben olyan k függvényt találunk, amelyre mind fk mind kf identitás, akkor azt mondjuk, hogy k az f (egy) inverze.
Megjegyezzük, hogy sem a bal inverz, sem a jobb inverz nem egyértelmű, de az inverz igen.
Legyen pl. A a valós számok, B pedig az egész számok halmaza. Jelölje f azt az A→B függvényt, amelyre f(a)=[a] (az a egész része). Ha 0≦r<1, és a gr:B→A függvényre gr(b)=b+r, akkor tetszőleges B-beli b-re fgr(b)=f(gr(b))=f(b+r)=[b+r]=b, tehát fgr=iB; azaz minden ilyen gr jobb inverze az f-nek. Legyen h:B→B az a függvény, melyre h(b)=8⋅b. Tetszőleges, 8-nál kisebb nemnegatív n egész számmal értelmezzük a Kn:B→B függvényeket a következőképpen : Kn(b)=[b+n8]. Ha b∈B, akkor Knh(b)=Kn(8b)=[b+n8]=b, tehát a K0,K1,...,K7 függvények valamennyien bal inverzei h-nak.
*

Feladat: Igazoljuk, hogy K0,K1,...,K7 páronként különböző függvények. Mutassuk meg továbbá, hogy ezeken kívül h-nak még végtelen sok bal inverze van.
*

Tétel: Az f függvénynek pontosan akkor van bal inverze, ha injektív; pontosan akkor van jobb inverze, ha szürjektív; és pontosan akkor van inverze, ha bijektív.
 

Bizonyítás. Tegyük fel először, hogy f:A→B injektív, és definiáljuk a g függvényt a következőképpen: g(f(a))=a, a B minden f(a) alakú elemére; és definiáljuk akárhogyan a B összes többi elemére. Az f injektivitása következtében ezzel egy függvényt definiáltunk, amire gf(a)=g(f(a))=a=iA(a); azaz gf=iA.
Legyen most f:A→B szürjektív. Ez azt jelenti, hogy minden B-beli b előáll f(a) alakban. Válasszunk ki tehát minden egyes b elemhez olyan a-t, amelyre f(a)=b; és legyen h az a függvény, amely az adott b-hez pontosan ezt az a-t rendeli. Az f szürjektivitása miatt egy függvényt értelmeztünk; erre a függvényre fh(b)=fh(f(a))=f(h(f(a)))=f(a)=b=iB(b) teljesül, és így fh=iB.
Ha f bijektív, akkor a fent definiált két függvény megegyezik; és így f-nek létezik inverze.
Az állítás megfordításánál is három eset van, amelyek közül az első kettő együtt bizonyítható. Azt kell megmutatni ugyanis, hogy ha gf identitás, akkor f injektív, és ha fh identitás, akkor f szürjektív. Ezt úgy is fogalmazhatjuk, hogy ha egy kéttényezős kompozíció identitás, akkor az első tényező szürjektív, a második pedig injektív.
Legyen tehát gf=iA. Ha f az A halmazt a B-be képezi le, akkor g természetesen a B-t képezi le A-ba.
Tegyük fel, hogy f(u)=f(v). Ekkor
u=iA(u)=gf(u)=g(f(u))=g((f(v))=gf(v)=iA(v)=v;
tehát f injektív.
Továbbá tetszőleges A-beli a-ra g(f(a))=gf(a)=iA(a)=a, vagyis g, szürjektív.
Azt kell megmutatni, hogy ha f-nek van inverze, akkor f bijektív. Ez viszont világos, hiszen ha van inverze, akkor van bal inverze is és jobb inverze is; így a már bizonyítottak alapján injektív is és szürjektív is.
 
Most megmutatunk egy érdekes tényt:
 

Tétel: Ha az f függvénynek van bal inverze és jobb inverze is, akkor csak egyetlen bal inverze és csak egyetlen jobb inverze van; és ezek is megegyeznek.
 

Bizonyítás: Legyen f:A→B és g tetszőleges bal inverz, h tetszőleges jobb inverz. Ez azt jelenti, hogy gf=iA és fh=iB. Ebből azonnal következik, hogy g is és h is B-t képezi le A-ba. Így iAh=h és giB=g. Ezt felhasználva (az asszociativitás alapján) a következőket kapjuk:
g=giB=g(fh)=(gf)h=iAh=h,
ami bizonyítja állításunkat.
Végezetül megadjuk, hogy milyen kapcsolatban vannak a függvények az ekvivalencia-relációkkal:
 
Tétel: Ha f:A→B tetszőleges függvény, akkor a következő reláció:
,,(u,v)∈R⊆A×A akkor és csak akkor, ha f(u)=f(v)'' ekvivalenciareláció.
 
Bizonyítás: f(u)=f(v) bizonyítja a reflexivitást. A szimmetria a reláció szimmetrikus definíciójából következik. Ha f(u)=f(v) és f(v)=f(w), akkor természetesen f(u)=f(w), ami bizonyítja a reláció tranzitivitását.
(Megjegyezzük, hogy minden ekvivalenciarelációhoz található olyan függvény, amelyből az ekvivalenciarelációt a fenti módon kaphatjuk.)
 
VII. Morfizmusok
 
Az eddigiekben azt tettük fel, hogy A és B tetszőleges halmazok, és f:A→B valamilyen függvény. A matematikában azonban általában valamilyen ,,struktúra'' is adott e halmazokon. Mi most csak arra gondolunk, hogy e halmazokon valamilyen művelet vagy reláció van adva. (Például mindegyikük egy számhalmaz, amelyben elvégezhető az összeadás, vagy mindketten irányított gráfok.)
Ilyen esetekben fontosak azok a függvények, amelyek a struktúrát megtartják. Ezeket a függvényeket homomorfizmusoknak nevezzük. Ha például összeadásról van szó, akkor a feltétel azt mondja, hogy w=u+v esetén f(w)=f(u)+f(v). Gráfok esetén a feltétel úgy szól, hogy ha u-ból megy nyíl v-be, akkor f(u)-ból is megy nyíl f(v)-be.
A homomorfizmusok esetén is használjuk a függvényeknél elmondott neveket; így beszélünk injektív, szürjektív és bijektív homomorfizmusokról. Van azonban két fontos speciális eset is, amelyeknek külön nevük van;
Az f:A→A morfizmust endomorfizmusnak nevezzük; amennyiben pedig ez bijekció, akkor a neve automorfizmus.
Így a 2697. feladatnál azt kellett bizonyítani, hogy a mondott gráfnak egyetlen endomorfizmusa az identitás. (Az identitás nyilván mindig homomorfizmus.)
Végezetül egy érdekes dolgot említünk meg. A bijektív függvényekről beláttuk, hogy azoknak van inverzük. Morfizmusok esetében az a probléma, hogy ez az inverz vajon maga is morfizmus-e. Ha a struktúrában csak műveletek vannak, akkor be lehet bizonyítani, hogy ez így van. Mutatunk viszont egy példát, hogy gráfokra az inverz nem mindig morfizmus.
Legyen A az egészek halmaza; és az R reláció álljon azokból az (i,i+1) párokból, amelyekre i pozitív. Az f:A→A függvényre legyen f(i)=i+1. Világos, hogy f morfizmus. Az is világos, hogy az f-nek a g inverzére g(i)=i-1 (egy ilyen van, mivel tudjuk, hogy az inverz egyértelmű). Ezzel szemben nem tartja meg a relációt, hiszen (1,2) relációban van, míg g-t alkalmazva a kapott (0,1) nincsen.