Kezdőlap


Cím:	Néhány egészen általános konstrukció
Szerző(k):	Fried Ervin
Füzet:	1997/április, 193 - 206. 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 századunk elejére‐közepére kialakult matematika egyik alapvető jellemzője az ,,absztrakt struktúrák'' vizsgálata.
A matematikai rendszerek axiomatikus tárgyalásának célja eredendően (Euklidésztől kezdve) az volt, hogy a tárgykörben annyi axiómát (sarkigazságot) írjunk fel, amennyiből már minden egyéb levezethető. Ez a ‐ mondhatni statikus ‐ szemlélet a legtöbb esetben csődöt mondott. Nem azért, mert a matematikusok olyan ügyetlenek voltak, hanem azért, mert kiderült, hogy ez éppen a legfontosabb esetekben nem is lehetséges. Ennek következtében szemléletváltás következett be a matematikában, amely bizonyos értelemben újabb absztrakciós fokot jelentett.
Ez a szemléletváltás nagyjából a következőket jelenti: Felírunk például annyi geometriai axiómát, amennyit ‐ és amelyeket ‐ fontosnak tartunk. Ezek után csak azokat a tételeket nézzük meg, amelyek a fenti axiómákból (az elfogadott bizonyítási módszerekkel) következnek. Egyszer előfordulhat, hogy olyan tételre bukkanunk, amelyet sem bizonyítani, sem cáfolni nem tudunk. Pontosabban szólva olyan tételre, amelyik nem következik az adott axiómákból; de a tétel tagadása sem következik. Ekkor szemléletünk alapján döntünk, hogy ,,mit tegyünk'' ezzel a tétellel. (Ilyen helyzet állt elő ‐ bár jóval korábban ‐ a párhuzamossági axiómával is. Mindennapi életünkben ezt az axiómát elfogadhatjuk, de a makrokozmoszban nem tudjuk, hogy mi az igazság.)
Vannak azonban olyan matematikai ágak, ahol természetszerűleg könnyebben gyökeret verhetett ez a szemlélet. Mindnyájan azt érezzük, hogy a valós számok, vagy az ,,igazi'' geometriai tér objektíven adott dolgok. Nem ez a helyzet például a halmazokkal, mert sok különböző halmaz van. Nem ez a helyzet a gráfokkal, mert sok különböző gráf van. (Még azonos csúcsszámúak között is.) Ugyanígy nem ez a helyzet egy csoport vagy egy gyűrű esetében vagy akár a topologikus tereknél, mert ezekből mind mind több van¹. A halmazokat, gráfokat, csoportokat, gyűrűket, topologikus tereket stb. matematikai struktúra-fajtáknak nevezik.
Míg a valós számok halmazának vagy a geometriai térnek a vizsgálátánál az volt a lényeg, hogy melyek azok a tulajdonságok, amelyek $a̲$ valós számhalmazra vagy $a̲$ geometriai térre igazak, a felsorolt struktúrák esetében olyan tulajdonságokat nézünk, amelyek $minden̲$ halmazra stb., de legalábbis $minden̲$ bizonyos tulajdonságú halmazra érvényesek.
Az ,,általános igazságokhoz'' sok-sok konkrét esetet kell látni. Szemléletünk gazdagítása és újabb példák vagy ellenpéldák konstruálása céljából számos úgynevezett konstrukciós eljárás született. Halmazok esetében például ilyenek:
a) Egy halmaz részhalmazának a képzése.
b) Adott halmaz egy részhalmaza komplementerének a képzése.
c) Két részhalmaz közös részének a képzése.
d) Két részhalmaz egyesítésének a képzése.
e) Két részhalmaz szimmetrikus differenciájának a képzése.
f) Egy halmaz összes részhalmazai halmazának a képzése.
g) Két halmaz diszjunkt egyesítésének a képzése.
h) Két halmaz direkt szorzatának a képzése.
Ismét túl sok lehetőséget soroltunk fel. Ezek mindegyikét részletesen vizsgálhatnánk; mi azonban csak a két utolsó pontban felsoroltat vesszük szemügyre.
Kezdjük először a direkt szorzattal:
Legyen $A$ és $B$ két tetszőleges halmaz. Ezek $P = A \times B$ direkt szorzatán azon $(a, b)$ párok halmazát értjük, amelyekre $a \in A$ és $b \in B$ teljesül. (Megjegyezzük, hogy ennek akkor is van értelme, ha a két adott halmaz egyike üres; ekkor a direkt szorzat is az üres halmaz lesz.) Könnyen látható, hogy véges halmazok esetében a direkt szorzat elemszáma megegyezik a két halmaz elemszámának a szorzatával. Arra is érdemes felhívni a figyelmet, hogy $A \times B \neq B \times A$ ; annak ellenére, hogy ,,nagyon hasonlítanak''.
Nézzük most két halmaz diszjunkt egyesítését:
Legyen $A$ és $B$ két tetszőleges halmaz. Ezeknek egyesítése az a $C$ halmaz, amelynek elemei pontosan azok, amelyek az $A$ és $B$ halmazok valamelyikében benne vannak. Lehetséges azonban, hogy a két halmaznak vannak közös elemei, amelyeket természetesen csak egyszer számolunk. A diszjunkt egyesítésnél azonban olyan halmazoknak az egyesítését nézzük, amelyeknek nincsenek közös elemei. Még akkor is, ha vannak közös elemek! Ez persze így lehetetlen; valójában arról van szó, hogy az elemeket meg akarjuk különböztetni aszerint, hogy melyik halmazban vannak. Például $A = {1, 2}$ és $B = {2, 3}$ . Ekkor a diszjunkt egyesítésnek elemei az $1$ , a $3$ , a $2$ az $A$ -ból és az ettől különböző $2$ a $B$ -ből. Ezt általában is megtehetjük: például az $A$ elemeihez egy $A$ indexet, a $B$ elemeihez egy $B$ indexet írunk. Például a fenti esetben $A = {1_{A}, 2_{A}}$ és $B = {2_{B}, 3_{B}}$ . Ekkor a diszjunkt egyesítés $Q = A ⊎ B = {1_{A}, 2_{A}, 2_{B}, 3_{B}}$ .

Feladatunk a következő lesz: Képzeljük el, hogy minden egyes halmaz egy ,,mikrovilág'', amelynek a belsejébe nem láthatunk be. Itt a külvilágban csak annyit látunk, hogy minden egyes halmaz egy objektum, de látjuk azokat a függvényeket ‐ például nyilak formájában ‐, amelyek egyik halmazt a másikba képezik. Ezenkívül még az igazán különböző függvényeket meg is tudjuk különböztetni egymástól. (Később még néhány dolgot fel kell tennünk e nyilak kapcsolatáról.)
A

P = A \times B

direkt szorzat elemei az

(a, b)

alakú párok, ahol

a \in A

és

b \in B

. Ez azonnal indukál természetes módon két függvényt, az

α : P \to A

és

β : P \to B

vetítéseket úgy, hogy

α ((a, b)) = a

és

β ((a, b)) = b

. Ezek a függvények annyira szervesen hozzátartoznak a direkt szorzathoz, hogy célszerűbb rögtön hozzávenni az elnevezéshez. Tekintettel arra, hogy a most megadandó definícióban nem lesz benne, hogy az pontosan a megfelelő párokból áll, ezért az elnevezést is egy kissé megváltoztatjuk; elhagyjuk a ,,direkt'' jelzőt:
Az

A

és

B

halmazok szorzata egy

{P \to_{}^{α} A, P \to_{}^{β} B}

pár

...

Ilyen tulajdonságú pár persze rengeteg van. Tetszőleges

X

halmaz esetén létezik az

{X \to_{}^{φ} A, X \to_{}^{ψ} B}

pár. Éppen ezért meg kell találnunk a direkt szorzat legjellemzőbb, függvényekkel megfogalmazható tulajdonságait. A legszembetűnőbb talán az, hogy

A

-ban is és

B

-ben is minden elem fellép képként. Sajnos ezt a tulajdonságot csak akkor tudjuk direkt módon megfogni, ha ,,bekukucskálunk'' a halmazokba. Valami indirekt lehetőséget az ad, hogy tulajdonképpen tudjuk, hogy ilyen függvények vannak. Ha tehát olyan kitétellel fogalmazunk, hogy ,,minden

...

függvényre'', akkor ezek között azok a függvények is ott lesznek, amelyek

A

-ra, illetve

B

-re képeznek. Tekintsünk tehát most egy tetszőleges

X

halmazt, amelyet valamilyen módon leképezünk

A

-ba is és

B

-be is:

...

úgy, hogy valahányszor adott az

{X \to_{}^{φ} A, X \to_{}^{ψ} B}

pár,

...

Mit tudunk erről az esetről mondani? Például azt, hogy az

X

halmaz tetszőleges

x

elemére

φ (x) \in A

és

ψ (x) \in B

. Eszerint a

P

halmazban ott van a

(φ (x), ψ (x))

pár. Ekkor viszont megadható az

x \mapsto (φ (x), ψ (x))

függvény. Ezt most írjuk le gyorsan:

...

mindig létezik egy

X \to_{}^{Φ} P

függvény úgy, hogy

...

Az, hogy milyen tulajdonságú ez a függvény, már látszik, hiszen

α (Φ (x)) = φ (x)

és

β (Φ (x)) = ψ (x)

. Csak az a kérdés, hogy mit értsünk azon, hogy ,,egy függvényt a másik után alkalmazunk''? Az eredmény ismét egy függvény lesz, amit tehát tekinthetünk egy ,,függvényeken értelmezett műveletnek''. Vigyázni kell azonban arra, hogy ez a művelet nem mindig végezhető el.
Ha

V \to_{}^{ξ} W

és

U \to_{}^{η} V

függvények, akkor jelölje

U \to_{}^{ξ \circ η} W

azt a függvényt, amelyet

ξ \circ η (u) = ξ (η (u))

definiál, tetszőleges

u \in U

esetén. Könnyen látható, hogy ez a szorzás asszociatív.
Ezzel a szorzással megfogalmazva:

...

α \circ Φ = φ

és

β \circ Φ = ψ

...

Ezzel már sikerült kifejezni azt, hogy az elképzelt direkt szorzat elég nagy, pontosabban szólva benne van minden

(a, b)

alakú elem. Példának okáért, ha egy

{P' \to_{}^{α'} A, P' \to_{}^{β'} B}

pár teljesíti a megkívánt feltételt, akkor

X

-nek a direkt szorzatot,

φ

-nek és

ψ

-nek a megfelelő vetítést választva a következőket kapjuk:

φ = α' \circ Φ

és

ψ = β' \circ Φ

következtében

a = α' (Φ ((a, b))

és

b = β' (Φ ((a, b))

. Másszóval, ha

Φ

(a_{1}, b_{1})

és

(a_{2}, b_{2})

párt ugyanabba a

p' \in P'

elembe viszi, akkor

\begin{matrix} a_{1} = φ ((a_{1}, b_{1})) = α' (Φ ((a_{1}, b_{1})) = α' (p') = α' (Φ ((a_{2}, b_{2})) = φ ((a_{2}, b_{2})) = a_{2}, \end{matrix}

és hasonlóan

b_{1} = b_{2}

. Ez pedig azt jelenti, hogy a szóbanforgó

P

halmaz valóban tartalmazza a direkt szorzatot. A kérdés csak az, hogy nem lehet-e nagyobb nála. Bizony, az eddigiek alapján ez lehetséges. Nézzük meg, miképpen tudjuk ezt a lehetőséget elkerülni.
Tegyük fel, hogy

P

(a, b)

alakú elemeken kívül tartalmaz még egy további

p

elemet. Ekkor

α (p) \in A

és

β (p) \in B

; és így persze

p_{1} = (α (p), β (p))

is eleme

P

-nek. Nyilván

p_{1} \neq p

, de ezt a két elemet ,,nem tudjuk megkülönböztetni''. Pontosan ez ad lehetőséget ennek az újabb elemnek a kizárására. Az eredeti

X \to_{}^{Φ} P

függvény mellett ugyanis létezik egy olyan

X \to_{}^{Φ_{1}} P

függvény is, amelyik azokat az elemeket, amelyeket

Φ

p_{1}

-re képezett a

p

-re képezi, de a többi elem képe változatlan marad. Így

Φ_{1} \neq Φ

. Ezzel szemben

α \circ Φ_{1} = α \circ Φ = φ

és

β \circ Φ_{1} = β \circ Φ = ψ

. A ,,felesleges'' elem tehát kizárható azzal, hogy:

...

és ez a

Φ

függvény egyértelműen meghatározott.
Összefoglalva:
Az

A

és

B

halmazok direkt szorzata egy

{P \to_{}^{α} A, P \to_{}^{β} B}

pár úgy, hogy valahányszor adott az

{X \to_{}^{φ} A, X \to_{}^{ψ} B}

pár, mindig létezik egy

X \to_{}^{Φ} P

függvény úgy, hogy

α \circ Φ = φ

és

β \circ Φ = ψ

, és ez a

Φ

függvény egyértelműen meghatározott.

Az eddigiekből az már világos, hogy a direkt szorzat (beleértve az adott halmazokra való függvényeket is!) rendelkezik az itt megfogalmazott tulajdonsággal. Az viszont egyáltalában nem látszik, hogy más halmaz és hozzátartozó függvénypár nem lehet ugyancsak ilyen tulajdonságú. Persze, ha ,,belekukucskálunk'' a halmazokba, akkor láthatjuk, hogy más eset nem létezhet. Pontosabban szólva

lényegesen̲

más eset nem létezhet. Ha ugyanis minden elemet ,,átnevezünk'', például

(a, b)

helyett egy

p_{a, b}

-vel jelölt új elemet írunk, akkor ezeknek az elemeknek a

P^{*}

halmaza is éppen olyan megfelelő lesz; még az adott halmazokra való függvények is megadhatók úgy, hogy

α^{*} (p_{a, b}) = a

és

β^{*} (p_{a, b}) = b

.
Ez az átnevezés egy

(a, b) \leftrightarrow p_{a, b}

kölcsönösen egyértelmű megfeleltetést jelent. Ez a fogalom így persze ugyancsak egy ,,belül'' megfogalmazott tulajdonság. ,,Kívül'' csak annyit látunk, hogy az a

ϑ : P \to P^{*}

és

ε : P^{*} \to P

függvény, amelyet

ϑ ((a, b)) = p_{a, b}

, illetve

ε (p_{a, b}) = (a, b)

definiál, egymásnak inverzei; vagyis mind az

ε \circ ϑ

, mind a

ϑ \circ ε

a megfelelő halmazok identikus leképezései, azaz minden elemet önmagára képeznek. Ezzel a ,,szorzat-tulajdonsággal'' csak a kölcsönösen egyértelmű függvények rendelkezhetnek:
Legyenek

U \to_{}^{ξ} V

és

V \to_{}^{η} U

olyanok, hogy mind a

ξ \circ η

mind az

η \circ ξ

az identitás. Ekkor tetszőleges

U

-beli

u

-ra és

V

-beli

v

-re

u = η (ξ (u))

és

v = ξ (η (v)

. Eszerint minden

v

elem fellép

η

-nál képként, de ha

η (v_{1}) = η (v_{2})

, akkor

v_{1} = ξ (η (v_{1})) = ξ (η (v_{2})) = v_{2}

. Hasonlóképpen látható be, hogy

ξ

is kölcsönösen egyértelmű; és akkor már természetesen egymás inverzei.
Ezzel ismét egy újabb akadályba ütköztünk. A kölcsönösen egyértelmű függvények ,,értelmezésétől'' megszabadultunk, de csak azon az áron, hogy az identikus leképezéseket kellene leírni. Tulajdonképpen ez nem nehéz, hiszen:

U \to_{}^{1_{U}} U

pontosan akkor identitás (= identikus függvény), ha bármely

U \to_{}^{ξ} W

és

W \to_{}^{η} U

esetén

ξ \circ 1_{U} = ξ

és

1_{U} \circ η = η

.
Visszatérve a kölcsönösen egyértelmű függvényre:

U \to_{}^{ξ} V

akkor és csak akkor kölcsönösen egyértelmű, ha van olyan

V \to_{}^{η} U

, amelyre

η \circ ξ = 1_{U}

és

ξ \circ η = 1_{V}

.
Most már csak azt kell kimondani, hogy:
Minden

U

-hoz tartozik egy

1_{U}

identitás.
Azt már bárki könnyen bebizonyíthatja, hogy az identitások egyértelműen meghatározottak.
A továbbiakban a jobb áttekinthetőség kedvéért úgynevezett diagramokat fogunk használni. Ez azt jelenti, hogy a halmazokat, mint ,,pontokat'' fogjuk ábrázolni, a függvényeket pedig mint nyilakat, amelyekre (vagy mellé) odaírjuk a szóbanforgó függvény nevét. Maga a direkt szorzat is felírható diagrammal:

Ha odaírjuk a definíciót ,,hordozó'' többi függvényt is, akkor a következő diagramhoz jutunk:

Ez a diagram még azzal a tulajdonsággal is rendelkezik, hogy

(φ =) 1_{A} \circ φ = α \circ Φ

és

(ψ =) 1_{B} \circ ψ = β \circ Φ

. Ez könnyen leolvasható a diagramról. Általában:
Ha egy diagram bármely pontjából a nyilak mentén egy másik ponthoz érve az érintett ,,függvények'' szorzatának eredménye nem függ az út megválasztásától, csupán annak kezdő- és végpontjától, akkor kommutatív diagramról beszélünk.
A diagramok segítségével sokkal ,,látványosabban'' megfogalmazható az, hogy mit jelent a direkt szorzat egyértelműsége. Legyen

és

két, a direkt szorzatot definiáló diagram. Akkor létezik olyan

P \to_{}^{Φ'} P'

és

P' \to_{}^{Φ} P

függvény, amelyek egymás inverzei és a

, valamint

diagramok kommutatívak. Ez valami olyasmit jelent, hogy

Φ

és

Φ'

nemcsak a halmazokon kölcsönösen egyértelműek, hanem a direkt szorzathoz tartozó két függvénypárt is ,,egymásba viszik''.
Annak a belátására, hogy a fenti

Φ

és

Φ'

valóban egymás inverzei, induljunk ki a most felírt két diagramból, amelyeknek a létezése abból következik, hogy

és

mindketten a direkt szorzatot jelentik. A fenti két diagramból a következő két diagramot kaphatjuk:

, valamint

Mindkét diagram esetében a ,,felső téglalap'' is és az ,,alsó téglalap'' is kommutatív diagram. Ebből egyszerű számolással azonnal következik, hogy az egész diagram is kommutatív, mindkét esetben. Kommutatív diagramokat kapunk tehát akkor is, ha a ,,középső sort'' elhagyjuk, és a függőleges nyilakhoz a megfelelő szorzatokat írjuk. Tekintettel arra, hogy az identitást önmagával szorozva ismét az identitást nyerjük, ezért

és

lesz az adódó két diagram. Teljesen hasonló diagramokat írhatunk fel úgy is, hogy a ,,középső'' függőleges nyíl mellé az identitást írjuk:

és

Ez a két diagram ugyancsak kommutatív. Tekintettel arra, hogy a direkt szorzat diagramban a középső nyilak egyértelműek és

P'

P

is a direkt szorzat, ezért

Φ' \circ Φ = 1_{P'}

és

Φ \circ Φ' = 1_{P}

; ami valóban azt bizonyítja, hogy ez a két függvény egymásnak a fenti értelemben is inverze.

Most pedig a diszjunkt unióra kellene térnünk, de ezt nem tesszük. Legalább is nem úgy, mint a direkt szorzatnál. Azért választottuk éppen a diszjunkt uniót a direkt szorzat párjának, mert ezek ,,duálisan viselkednek''. Ezen azt értjük, hogy a diszjunkt uniót ugyanúgy lehet definiálni, mint a direkt szorzatot, csak a nyilak irányát kell megváltoztatni. Eszerint:
Az

A

és

B

halmazok diszjunkt uniója egy

{Q ↤_{}^{α} A, Q ↤_{}^{β} B}

pár úgy, hogy valahányszor adott az

{Y ↤_{}^{φ} A, Y ↤_{}^{ψ} B}

pár, mindig létezik egy

Y ↤_{}^{Φ} Q

függvény úgy, hogy

Φ \circ α = φ

és

Φ \circ β = ψ

, és ez a

Φ

függvény egyértelműen meghatározott.

A diszjunkt unió valóban rendelkezik ezzel a tulajdonsággal. Legyen

α

és

β

úgy definiálva, hogy

Q

elemei pontosan az

α (a)

és

β (b)

alakú elemek, ahol

a \in A

és

b \in B

.
Tegyük fel most, hogy adottak a

A \to_{}^{φ} Y

és

B \to_{}^{ψ} Y

függvények. Definiáljuk ezekután a

Φ

-t úgy, hogy

Φ (α (a)) = φ (a)

és

Φ (β (b)) = ψ (b)

. Biztos, hogy valóban a diszjunkt unióról van szó, mert ha

Y

-t a diszjunkt uniónak választjuk és

φ

-t,

ψ

-t a megfelelő leképezéseknek, akkor

φ (a) = ψ (b)

soha nem lehet, így

α (a) = β (b)

is lehetetlen.
Most azt kellene belátni, hogy a fenti tulajdonsággal csak a diszjunkt unió rendelkezik. Erre viszont nincs szükség! Az a formális bizonyítás ugyanis, amit a direkt szorzatra adtunk, szóról szóra átvihető erre az esetre is, mert ott nem volt lényeges a függvények ,,iránya''; illetve csak abban történik változás, hogy a szorzást fordított sorrendben kell végezni.
A továbbiakban ezeket a konstrukciókat absztraktul, teljes általánosságban fogjuk vizsgálni; majd megnézzük jelentésüket konkrét esetekben.

,,Az absztrakt nonszensz''

A cikk első részében két halmazelméleti konstrukciót tárgyaltunk, a direkt szorzatot és a diszjunkt uniót. Mindkét esetben olyan leírást adtunk, amelyik ,,nem tekintett a halmazok belsejébe''; vagyis csak a halmazok közötti függvények egymáshoz való kapcsolatát használta. Emellett még az is teljesült, hogy e két fogalom leírása ,,duális'' volt, azaz a függvényeket leíró nyilak irányát kellett csupán megváltoztatni.
Az első részben nem csak számos halmazelméleti konstrukciót soroltunk fel; de felsoroltunk olyan matematikai ágakat is, amelyek bizonyos értelemben hasonló jellegűek, mint a halmazelmélet. Ilyenek például a gráfok, vagy a csoportok, vagy a kommutatív csoportok, vagy a gyűrűk vagy a topologikus terek stb. Ezek esetében is lehetne definiálni a direkt szorzat és a diszjunkt unió fogalmát ‐ pontosabban szólva az ezeknek megfelelő fogalmakat. Ekkor a halmazok szerepét a megfelelő objektumok veszik át; a függvények helyére pedig csak olyan függvényeket vehetünk, amelyek ,,megtartják'' a szóbanforgó struktúrát. Gráfok esetében tehát csak azok a függvények jöhetnek szóba, amelyek ,,élt élbe visznek'', csoportok vagy gyűrűk esetében pedig csak azok, amelyek ,,megtartják'' a megfelelő műveleteket. Ezáltal sok eddigi függvény ,,kiesik''; ha például egy kölcsönösen egyértelmű függvény ,,nem tartja meg a struktúrát'', akkor egyáltalában szóba se jöhet egy diagramnál.
Két fontos dolog azonban mindig megmarad. Az egyik az, hogy két ,,struktúratartó'' függvény szorzata is ilyen; a másik meg az, hogy az identitás minden struktúrát megtart. A kapott

C

rendszer tehát kétféle ,,valamikből'' áll. Az egyik a

C

objektumai, a másik azok a ,,valamik'', amelyek a függvények szerepét játsszák. Mivel ezekről nem is akarjuk feltenni, hogy függvények, ezért morfizmusnak fogjuk nevezni őket. Az ilyen rendszereket (a fent megfogalmazott kívánalmakkal együtt) kategóriáknak nevezik:
Egy

C

kategória két részből áll: az

O b (C)

objektumokból és a

M o r (C)

morfizmusokból.
Minden

A

B \in O b (C)

párhoz hozzá van rendelve morfizmusok egy

m o r (A, B)

halmaza, és

M o r (C)

minden eleme pontosan egy

m o r (A, B)

halmazhoz tartozik.
Azt, hogy

α \in m o r (A, B)

úgy is kifejezzük, hogy

α : A \to B

, vagy

α : B ↤ A

, vagy

A \to_{}^{α} B

, vagy

B ↤_{}^{α} A

. Nem követeljük meg, hogy

m o r (A, B)

-nek legyen eleme. (Például ha az

A

gráfnak két szögpontja van, amelyek egy éllel vannak összekötve és a

B

gráfban nincs él, akkor nem létezik olyan éltartó leképezés, amelyik

A

-t

B

-be vinné.)
Egy

C

kategóriában a következő axiómák teljesülését kívánjuk meg:
1.) Ha

α : A \to B

és

β : B \to C

, akkor létezik

m o r (A, C)

-ben egy általuk egyértelműen meghatározott

β \circ α

elem.
Ezt az elemet a továbbiakban a két adott elem szorzatának nevezzük és a ,,

\circ

'' elhagyásával úgy jelöljük, hogy

β α

.
2.) Ha létezik az

α β

és

β γ

szorzat, akkor léteznek az

(α β) γ

és

α (β γ)

szorzatok is; és megegyeznek.
A fentiek ‐ mint látjuk ‐ a függvénykompozíció alapvető tulajdonságait rögzítik. Most még az identitás létét is ki kell kötni:
3.) Minden

A \in O b (C)

esetén létezik olyan

1_{A} \in m o r (A, A)

, amelyre bármely

α : A \to B

és bármely

β : C \to A

esetén

α 1_{A} = α

és

1_{A} β = β

.
(A kategóriák bevezetésekor semmiféle konkrét alkalmazhatóságuk nem látszott. A fogalmak teljesen absztraktak és az első eredmények, amelyeket kategóriák segítségével értek el alig tűntek másnak, mint ismert eredmények bizonyításának. Ennek következtében nevezték el a kategóriákat absztrakt nonszensznek².)
Na mármost, tetszőleges

C

kategóriában teljesen általánosan definiálhatjuk a szorzatot a már látott módon. Sőt ugyanúgy, mint a halmazok esetében is akármennyi (véges vagy végtelen sok) objektum szorzatáról is beszélhetünk.

Szorzat: Legyen adva indexek egy

I

halmaza, és minden

i \in I

esetén egy

A_{i} \in O b (C)

(tehát egy-egy

C

-beli objektum). Ezen objektumok

C

-beli szorzata:

\begin{matrix} P = \prod_{i \in I}^{} A_{i} \to_{}^{α_{i}} A_{i}, ha bármely X \to_{}^{φ_{i}} A_{i} (i \in I) \end{matrix}

esetén létezik olyan egyértelműen meghatározott

Φ : X \to P

morfizmus, amire az

\begin{matrix} \begin{matrix} X & \to_{}^{φ_{i}} & A_{i} \\ Φ ↓ & 1_{i} ↓ \\ P = \prod_{i \in I}^{} A_{i} & \to_{}^{α_{i}} & A_{i} \end{matrix} \end{matrix}

diagramok mindegyike kommutatív (

1_{i} : A_{i} \to A_{i}

jelöli

A_{i}

identitását).
Mi csak olyan eseteket fogunk nézni, amikor az

I

indexhalmaz véges, vagy a természetes számok halmaza. Az

{1, ..., n}

halmazt

n

-nel, a természetes számok

{1, ..., n, ...}

halmazát

N

-nel fogjuk jelölni (tehát például

2 = {1, 2}

).
Ha

C = S

(a halmazok kategóriája), akkor ‐ mint láttuk ‐

α_{i} : \prod A_{i} \to A_{i}

(

i \in 2

) esetén

\prod A_{i}

elemei

(a_{1}, a_{2})

párok, és

α_{1} (a_{1}, a_{2}) = a_{1} \in A_{1}

, illetve

α_{2} (a_{1}, a_{2}) = a_{2} \in A_{2}

. Hasonlóképpen adódik a

α_{i} : \prod A_{i} \to A_{i}

(

i \in n

) szorzatra, hogy a ,,szorzat-objektum'' elemei olyan

n

-elemű sorozatok, amelyekben az

i

-edik elem az

i

-edik objektumból való és az

i

-edik morfizmus a sorozatot éppen erre az

i

-edik komponensre képezi le, vagyis

\prod A_{i}

a direkt szorzat. Nem okoz gondot az

α_{i} : \prod A_{i} \to A_{j}

(

j \in N

) értelmezése sem; itt végtelen sorozatok lépnek fel.
A következő, amit megnézünk, a gráfok

G

kategóriája lesz. Mindenekelőtt meg kell mondani, mik

G

objektumai és mik a morfizmusok. Nos, az objektumok az irányítatlan gráfok³. A morfizmusok definícója az szokott lenni, hogy olyan

φ : A \to B

,,valami'', ami a tartóhalmazokon egy

φ : A \to B

függvény; s ha

[a_{1}, a_{2}]

A

gráf éle, akkor

[φ (a_{1}), φ (a_{2})]

éle a

B

gráfnak. Szinte triviális, hogy valóban egy kategóriát kaptunk.
Nem nehéz belátni, hogy a gráfok kategóriájában a szorzatot a következőképpen kaphatjuk meg:
Legyenek adva az

A_{i}

gráfok (

i \in N

). Készítsük el a tartóhalmazok

P

direkt szorzatát. Ennek egy

(a_{1}, a_{2}, ..., a_{n}, ...)

és egy

(b_{1}, b_{2} ..., b_{n} ...)

elemét akkor kössük össze éllel, ha az adott gráfok mindegyikében ott van a megfelelő

[a_{1}, b_{1}], [a_{2}, b_{2}], ..., [a_{n}, b_{n}], ...

él. A direkt szorzathoz tartozó

α_{i} : P \to A_{i}

morfizmust pedig

α_{i} ((a_{1}, a_{2}, ..., a_{n}, ...)) = a_{i} (\in A_{i})

adja meg.
Érdemes felfigyelni a következőre: A gráfok kategóriájában az objektumok természetesen a gráfok. Az viszont már egyáltalában nem világos, hogy mik legyenek a morfizmusok. Miért ne lehetne a morfizmusok természetesnek vett ,,éltartás''-a mellett azt is megkívánni, hogy a ,,nem-él'' tulajdonságot is megtartsa. Ez azt jelenti, hogy ha

[a_{1}, a_{2}]

nem az

A

gráf éle, akkor

[φ (a_{1}), φ (a_{2})]

sem éle a

B

gráfnak. A kategória definíciójában szereplő axiómák most is triviálisan teljesülnek. Az történt csupán, hogy az előbbi kategória morfizmusai közül jó néhányat elhagytunk. Ennek az a furcsa következménye, hogy ebben a kategóriában nem mindig létezik szorzat. Tekintsük például a kételemű

H = {a, b}

halmazon értelmezhető összes gráfot. Itt a következő élek lehetnek:

[a, a]

[a, b]

[b, b]

. Ennek megfelelően az alábbi ,,lényegesen különböző'' gráfokat kapjuk:

A = 〈 H; [a, a], [a, b], [b, b] 〉

B = 〈 H; [a, a], [a, b] 〉

C = 〈 H; [a, a], [b, b] 〉

D = 〈 H; [a, a] 〉

E = 〈 H; [a, b] 〉

F = 〈 H; 〉

. Itt a ,,

〈

'' és ,,

〉

'' jelek között először a gráf alaphalmaza szerepel, majd a ,,;'' jel után az élek felsorolása. A következő ábrán bemutatjuk ezeket:

I.) Az

A

és

F

gráfoknak nincs szorzata. Ha ugyanis létezik egy

P \to A

morfizmus, akkor

P

alaphalmazának bármely két eleme össze van kötve. Ha pedig egy

P \to F

morfizmus létezik, akkor egyik sem lehet összekötve.
II.) Tekintsük most az

A

és

B

gráfok szorzatát, a megfelelő

α : P \to A

és

β : P \to B

morfizmusokkal. Mint az előbb láttuk, a

P

gráfban bármely két csúcs össze van kötve. Mivel

β

éltartó, ezért

β

minden csúcsot az

a

csúcsra képez, hiszen a

b

csúcsra csak olyan csúcs lehetne leképezve, amelyik nincs összekötve önmagával. A ,,legkisebb'' ilyen

P

maga az

A

, és

α

az identitás, míg

β

mindegyik csúcsot az

a

csúcsra képezi. Ha most

φ : X \to A

és

ψ : X \to B

morfizmusok, akkor

φ

,,szerint''

X

-ben bármely két csúcs össze van kötve, és így

ψ

minden csúcsot

a

-ra képez. Eszerint

Φ

csak az identitás lehet, és az jó is.
III.) Az

A

és

C

gráfoknak egészen más okból nincs szorzatuk, mint I.) alatt. Itt ugyanis két jelölt is akad, de ezek ,,összeférhetetlenek''. Mint már láttuk, szorzatnál csak olyan

P

gráf jöhet szóba, amelyikben bármely két csúcs össze van kötve. Ugyanúgy, mint a II.) alatti példában, ekkor

γ : P \to C

vagy csak az

a

csúcsra vagy csak a

b

csúcsra képez. Ilyen gráfok vannak is; például

A

is ilyen, mert akár

a

-ra akár

b

-re képezzük a csúcsokat, a kategória egy-egy morfizmusát kapjuk. Ennek megfelelően, ha

α : P \to A

tetszőleges morfizmus és

γ_{a} : P \to C

minden csúcsot

a

-ba visz, akkor tekintsünk egy

X

gráfot, amelyet leképezünk valahogy

A

-ba (

φ : X \to A

). Eszerint

X

-ben is minden csúcs össze van kötve. Ezért az a

γ_{b} : X \to C

leképezés, amely minden csúcsot

b

-be visz ugyancsak hozzátartozik a kategóriához. Ekkor viszont akárhogyan is választjuk a

Φ : X \to P

morfizmust,

γ_{a} \circ Φ

-nél minden csúcs

a

-ra képződik, míg

1_{C} \circ γ_{b}

esetében a csúcsok képe

b

lesz. Hasonlóképpen látható be a másik eset lehetetlensége, hiszen

a

és

b

szerepe szimmetrikus. Ezt az esetet a következő diagram szemlélteti:

IV.) Végül nézzük az

A

gráfnak önmagával vett szorzatát. Ez úgy viselkedik, ahogy ,,elvárható''. Csúcsai az

(a, a)

(a, b)

(b, a)

(b, b)

párok, bármely két csúcs össze van kötve, és a megfelelő morfizmusok az első, illetve második komponensre való ,,vetítések''.

A fenti furcsa helyzet azért adódott, mert a morfizmusokat nem megfelelően választottuk. Tulajdonképpen az objektumok közül is elhagyhatunk, ami ugyancsak ,,patologikus'' helyzetet eredményezne. Vannak ,,elég tisztességes'' kategóriák is, ahol baj van a szorzattal. Nagyon sok esetben azonban a szorzat ,,természetesen'' adódik.
Ha a kategória objektumai valamilyen struktúrák, amelyen relációk és műveletek vannak értelmezve, és a morfizmusok a reláció-, illetve művelet-tartó leképezések, akkor a szorzat-struktúra alaphalmaza mindig az alaphalmazok direkt szorzata. A megfelelő reláció bizonyos elemekre pontosan akkor áll fenn, ha minden komponensen fennáll; míg a megfelelő művelet az eredeti műveletek komponensenként való elvégzésével történik. A szorzathoz tartozó morfizmusok pedig az egyes komponensekre való vetítések.
Mi most két kategóriát nézünk meg röviden, a kommutatív csoportok

A

kategóriáját és az összes csoport⁴

B

kategóriáját. Morfizmusoknak azokat a leképezéseket tekintjük, amelyek művelettartóak, azaz a

φ : A \to B

morfizmusra

φ (a b) = φ (a) φ (b)

teljesül.
Mindkét kategóriában létezik szorzat, a csoport az adott csoportok direkt szorzata és a morfizmus a megfelelő komponensre való vetítés. Erről nincs sok mondanivalónk; de a diszjunkt unió megfelelőjének tárgyalásánál majd furcsa dolgokat fogunk tapasztalni.
A diszjunkt unió a szorzat ,,duálisa'', ennek megfelelően ko-szorzatnak nevezik. Jelölésére a produktum jel ,,fejreállított'' változatát használják. A dualitás abban nyilvánul meg, hogy a nyilak irányítása megfordul.

Ko-szorzat: Legyen adva indexek egy

I

halmaza, és minden

i \in I

esetén egy

A_{i} \in O b (C)

(tehát egy-egy

C

-beli objektum). Ezen objektumok

C

-beli ko-szorzata:

\begin{matrix} P = ∐_{i \in I}^{} A_{i} \leftarrow_{}^{α_{i}} A_{i}, ha bármely Y \leftarrow_{}^{φ_{i}} A_{i} (i \in I) \end{matrix}

esetén létezik olyan egyértelműen meghatározott

Φ : Y ↤ P

morfizmus, amire az

\begin{matrix} \begin{matrix} Y & \leftarrow_{}^{φ_{i}} & A_{i} \\ Φ ↑ & 1_{i} ↑ \\ P = ∐_{i \in I}^{} A_{i} & \leftarrow_{}^{α_{i}} & A_{i} \end{matrix} \end{matrix}

diagramok mindegyike kommutatív (

1_{i} : A_{i} \to A_{i}

jelöli

A_{i}

identitását).
A ko-szorzat fenti definíciója azt a szemléletet takarja, hogy ez az a ,,legkisebb'' objektum, amely az adott objektumokat ,,függetlenül'' tartalmazza.
A cikk első részében láttuk, hogy a halmazok

S

kategóriájában a ko-szorzat a diszjunkt unió. Könnyen belátható, hogy hasonló a helyzet a gráfok

G

kategóriájában is. Mint már említettük, nem így van a csoportok vagy a kommutatív csoportok esetében.
Először nézzük a kommutatív csoportokat, mégpedig additív írásmódban. Legyen

A

és

B

két kommutatív csoport és legyen

P

a direkt szorzat. Ennek elemei tehát

(a, b)

alakú párok, ahol

a \in A

b \in B

, és a művelet a komponensenként való összeadás. Definiáljuk az

α : A \to P

és

β : B \to P

morfizmusokat úgy, hogy tetszőleges

a \in A

b \in B

esetén

α (a) = (a, 0)

és

β (b) = (0, b)

legyen. Mind

α

mind

β

művelettartó; azt állítjuk, hogy ezzel éppen a ko-szorzatot írtuk le. A definíció első része már megvan. Legyen most

φ : A \to Y

és

ψ : B \to Y

tetszőleges. Definiáljuk a

Φ : P \to Y

morfizmust úgy, hogy

Φ ((a, b)) = φ (a) + ψ (b)

. Ez a leképezés művelettartó, mert

\begin{matrix} \begin{matrix} Φ ((a_{1} + a_{2}, b_{1} + b_{2})) = φ (a_{1} + a_{2}) + ψ (b_{1} + b_{2}) = φ (a_{1}) + φ (a_{2}) + ψ (b_{1}) + ψ (b_{2}) = \\ φ (a_{1}) + ψ (b_{1}) + φ (a_{2}) + ψ (b_{2}) = Φ ((a_{1}, b_{1})) + Φ ((a_{2}, b_{2})), \end{matrix} \end{matrix}

ami éppen a művelettartást jelenti. Ekkor

\begin{matrix} Φ (α (a)) = Φ ((a, 0)) = φ (a) + ψ (0) = φ (a) + 0 = φ (a) = φ (1_{A} (a)), \end{matrix}

vagyis

Φ \circ α = φ \circ 1_{A}

. Hasonlóképpen adódik a

Φ \circ β = ψ \circ 1_{B}

összefüggés; ami éppen azt jelenti, hogy a ko-szorzatot kaptuk. Az is könnyen belátható, hogy a

Φ

morfizmus egyértelmű.
Mégse gondoljuk azt, hogy a kommutatív csoportok kategóriájában a szorzat és a ko-szorzat teljesen ugyanaz. A különbséget azonban csak akkor vehetjük észre, ha végtelen sok csoportot tekintünk. Tekintsük az

A_{i}

csoportokat (

i \in N

). Ezek

P

szorzatának az elemei olyan

(a_{1}, a_{2}, ..., a_{n}, ...)

végtelen sorozatok, ahol minden egyes

a_{i}

az ugyanazon indexű

A_{i}

csoportban van. Az összeadást komponensenként végezzük; és az

A_{i}

-hez tartozó morfizmus az

i

-edik komponensre való vetítés. Most is megadhatók az

α_{i} : A_{i} \to P

morfizmusok, amelyek az

A_{i}

-beli

a

elemet abba a sorozatba viszik, amelynek az

i

-edik helyén a megadott

a

elem áll, míg a többi helyen

0

van. Ha most adottak a

φ_{i} : A_{i} \to Y

morfizmusok, akkor a

Φ : P \to Y

morfizmus csak az lehet, amelyik az

(a_{1}, a_{2}, ..., a_{n}, ...)

sorozatot az összes

φ_{i} (a_{i})

összegébe viszi. Ennek viszont nincs értelme, mert végtelen sok elemet nem lehet összeadni⁵. Egyetlen kivétel az, amikor véges sok tag kivételével mindegyik tag

0

. Ebben az esetben teljesen jó felfogás az, hogy csak a

0

-tól különböző tagokat adjuk össze. Erre viszont csak akkor van lehetőségünk, ha a szóbajövő

P

-beli sorozatokban csak véges sok helyen áll

0

-tól különböző elem. És erre van lehetőség! Tekintsük ugyanis

P

-ben azokat a sorozatokat, ahol csak véges sok helyen áll nem-

0

elem. Két ilyen elem összege is ilyen; a csoport

0

-eleme is ilyen, hiszen ebben minden komponens

0

; és ilyen elem inverze is ilyen, hiszen az inverz elemet a komponensenkénti inverz adja. Eszerint ez egy

Q

csoport. Észrevehetjük, hogy az adott

α_{i}

morfizmusok nem csak

P

-be, hanem egyszersmind

Q

-ba is képeznek, és továbbra is művelettartó módon. Ha mármost

Φ

-t csak a

Q

elemeire definiáljuk, akkor

Φ : Q \to Y

értelmes lesz. Eszerint

α_{i} : A_{i} \to Q

éppen a ko-szorzat diagram.
Kommutatív csoportok ko-szorzata már sokkal előbb ismert volt, mint ahogy a ko-szorzat fogalmát bevezették. Akkor ezt a csoport-struktúrát direkt összegnek nevezték. Ez az elnevezés persze ma is életben van.
Végezetül a csoportok kategóriájában nézzük meg a ko-szorzatot. Először azt mutatjuk meg, hogy itt a szorzat nem egyenlő a ko-szorzattal.
Az

A

és

B

csoportok szorzatában ‐ mint láttuk ‐ a csoport elemei

(a, b)

alakú párok, ahol

a \in A

b \in B

. A műveletet komponensenként végezzük és az adott csoportokra való morfizmusok a megfelelő komponensekre való vetítések. Itt is létezik az

α' : A \to P

és

β' : B \to P

morfizmus, amelynél

α' (a) = (a, 1)

és

β' (b) = (1, b)

teljesül⁶. Ha adott egy

φ : A \to Y

és egy

ψ : B \to Y

morfizmus, akkor egyáltalán nem biztos, hogy

φ (a) ψ (b) = ψ (b) φ (a)

; míg egy megfelelő

Φ' : P \to Y

létezéséből

\begin{matrix} φ (a) ψ (b) = Φ' (α (a) β (b)) = Φ' ((a, 1) (1, b)) = Φ' ((1, b) (a, 1)) = Φ' (β (b) α (a)) = ψ (b) φ (a) \end{matrix}

következik. A fenti ,,nem biztos'' helyett azt is mondhatjuk, hogy nem igaz. Erre mutatunk egy igen egyszerű példát:
Jelölje 1, 2, 3 egy szabályos háromszög csúcsait. A példában szereplő összes csoport e háromszög egybevágósági transzformációiból fog állni; e transzformációk kompozíciójával mint művelettel. Legyen

e

az identikus transzformáció,

a

az a transzformáció, amelyik az

1

és a

2

csúcsot cseréli fel,

b

az a transzformáció, amelyik az

1

és

3

csúcsot cseréli fel.

A = {e, a}

és

B = {e, b}

. Ezek mindegyike csoport; éppen úgy, mint az összes transzformáció

Y

csoportja.

φ : A \to Y

és

ψ : B \to Y

legyen az a morfizmus, amely mindegyik transzformációnak önmagát felelteti meg. Ekkor

a b (1) = a (b (1)) = a (3) = 3

, míg

b a (1) = b (a (1)) = b (2) = 2

; ez a két transzformáció tehát különböző.
Az

A \to_{}^{α} Q ↤_{}^{β} B

ko-szorzat diagramban a

Q

megadása sem túlságosan egyszerű.
Tekintsük az

a_{1} b_{1} ... a_{r} b_{r}

alakú ,,szavakat'', ahol

a_{i} \in A

b_{i} \in B

. Ezeket a szavakat bizonyos esetekben ,,rövidíthetjük''. Ha valamilyen

1 < i \leq r

esetén

a_{i} = 1

, vagy valamilyen

1 \leq j < r

esetén

b_{j} = 1

, akkor

b_{i - 1} 1 b_{i}

helyébe a

B

-beli

b_{i - 1}' = b_{i - 1} b_{i}

, illetve

a_{j} 1 a_{j + 1}

helyée az

A

-beli

a_{j}' = a_{j} a_{j + 1}

elemet írjuk. Ha addig végezzük a rövidítéseket, amíg csak lehet, akkor egy ,,rövidíthetetlen'' szóhoz jutunk. Nem túlságosan nehéz, de elég aprólékos munka belátni, hogy a rövidítéseket bármilyen sorrendben végezve mindig ugyanahhoz a szóhoz jutunk.

Q

elemei a rövidíthetetlen szavak lesznek. Az

u

és

v

rövidíthetetlen szavak szorzatát a következőképpen kapjuk: Egymás mellé írjuk őket és a kapott

uv

szónak vesszük a lerövidített alakját. Egységelem az ,,

11

'' szó lesz, ahol az ,,első''

1

A

-ból, a ,,második'' a

B

-ből való. Az inverzet úgy kapjuk, hogy a ,,betűk'' inverzeit fordított sorrendben írjuk fel; majd az elejére is és a végére is egy-egy

1

-t írunk. Így

{(a b)}^{- 1} = 1 b^{- 1} a^{- 1} 1

és

{(1 b a 1)}^{- 1} = 11^{- 1} a^{- 1} b^{- 1} 1^{- 1} 1 = a^{- 1} b^{- 1}

α : A \to Q

a

elemnek az

a 1

és

β : B \to Q

b

elemnek az

1 b

rövidíthetetlen szót felelteti meg. Ha mármost adott az

A \to_{}^{φ} Y ↤_{}^{ψ} B

diagram, akkor a

Φ : Q \to Y

morfizmust a következőképpen definiálhatjuk:

\begin{matrix} Φ (a_{1} b_{1} ... a_{r} b_{r}) = φ (a_{1}) ψ (b_{1}) ... φ (a_{r}) ψ (b_{r}) . \end{matrix}

Azt kellene még belátni, hogy

Φ

a csoportok kategóriájának egy morfizmusa. Ebben az egyetlen kellemetlen dolog annak a megmutatása, hogy a fenti

Φ

hozzárendelés egyértelmű. Ennek a kellemetlenségnek az az oka, hogy egy-egy szót többféle alakban is megadhatunk, és nem eleve biztos, hogy bármilyen alakból indulunk is ki, mindig ugyanaz lesz a kép.
Ez a csoportkonstrukció is ismert volt még a ko-szorzat ismerete előtt. Magát a csoportot az adott csoportok szabad szorzatának nevezték. Ez az elnevezés is használatban van.
A kategóriákat és a diagramokat ma is elsősorban fogalmi segédeszközöknek tekintik. Nagy szerepük van a ,,dolgok'' precíz megfogalmazásában és ,,átértésében''. Ahol ,,elvi'' vizsgálatok folynak, ott szinte kivétel nélkül ezt a nyelvet használják. Igen fontosak a matematikai logikában és az elméleti számítástechnikában is. Vannak olyan nem kategóriaelméleti eredmények is, amelyeket először kategóriaelmélet segítségével sikerült bizonyítani.

Fried Ervin

¹Nem igazán fontos, hogy minden esetben tudjuk, mik azok a dolgok, amiket itt megjegyeztünk; csak az a lényeg lássuk, hogy számos olyan matematikai objektum-fajta van, amelyekből igen sok áll rendelkezésünkre.

²Tartozom az igazságnak azzal, hogy bevalljam, nem vagyok egészen biztos abban, hogy ezt az ,,elnevezést'' a kategóriaelméletre vagy az univerzális algebrára alkalmazták; de bármelyikük ,,kiérdemelte'' ezt az elnevezést.

³Irányítatlan gráf egy $G$ nem üres halmaz, ellátva ,,élekkel''. A halmaz elemeit a gráf csúcsainak nevezzük. Bizonyos csúcspárok ki vannak jelölve; ha egy csúcspár ki van jelölve, akkor azt mondjuk, hogy e csúcsok össze vannak kötve éllel, egyébként nincsenek. A gráfot egyértelműen meghatározza a csúcsok és az élek halmaza. A csúcsok halmazát a gráf tartóhalmazának nevezzük. A $G$ gráffal együtt a tartóhalmazt is $G$ -vel jelöljük.

⁴Csoporton a következőket értjük: Adott egy $G$ halmaz, amelyen értelmezve van egy szorzásnak nevezett művelet; $a$ és $b$ szorzatát $a b$ jelöli. A szorzás asszociatív. Léteznie kell egy $1 \in G$ egységelemnek, amire tetszőleges $a \in G$ esetén 1a=a1=a; továbbá minden $a \in G$ elemhez kell lennie egy inverznek ‐ amit $a^{- 1}$ jelöl ‐, amire $a^{- 1} a = a a^{- 1} = 1$ . Ha a szorzás kommutatív, akkor kommutatív csoportról beszélünk. Ez esetben sokszor ,, $+$ '' jelöli a műveletet, aminek a neve összeadás; az egységelem jele $0$ , és $a$ inverzét $- a$ jelöli. E mellett a jelölés mellett additív írásmódról beszélünk.

⁵Az összeadást eleve csak két elemre értelmeztük. Az asszociativitást felhasználva akármennyi ‐ de véges sok ‐ elemre értelmezhető és egyértelmű az összeadás. A soroknak a határérték felhasználásával definiált összegéről itt nem beszélhetünk, mert itt általában nem létezik határérték.

⁶Most nem használjuk az additív írásmódot, mert a szorzás kommutativitását nem tesszük fel.