1.3Relációk

Legyenek és tetszőleges halmazok, ekkor az

az és halmazok direktszorzata.

Az halmazt bináris relációnak nevezzük. A továbbiakban, ha nem okoz félreértést a bináris jelzőt elhagyjuk.

A reláció értelmezési tartománya:

a reláció értékkészlete:

a reláció értéke egy helyen, vagy szerinti képe:

egy halmaz szerinti képe a halmazt alkotó elemek képeinek uniója, azaz

Az relációt felfoghatjuk egy leképezésnek, megfeleltetésnek is az és a halmaz elemei között. Az értelmezési tartomány jelenti azokat az -beli elemeket, amikhez hozzárendelünk legalább egy -beli elemet. Hasonlóan, az értékkészlet a legalább egy elelemhez hozzárendelt elemek halmaza. Egy elemnek a képe, azoknak a -beli elemeknek a halmaza, amiket a reláció hozzárendel az -hoz. A halmaképét az elemek képeinek uniójával definiáltuk, ez másképpen úgy fogalmazható, hogy a képe azokból az elemekből áll, amik legalább egy -beli elemhez hozzá vannak rendelve, azaz

Azt mondjuk, hogy egy reláció determinisztikus,vagy parciális függvény, ha

Függvénynek nevezünk egy relációt akkor, ha

Az -ból -be képező függvényt általában -vel, a parciális függvényt -vel jelöljük. E jelölés használata esetén nem egy egyelmű halmazt, hanem annak elemét jelenti.

Legyen . Ekkor az reláció az inverze, ha

Legyen tetszőleges halmaz. Ekkor az inverz reláció szerinti képét, -t, a halmaz reláció szerinti inverz képének nevezzük. A definíciókból látszik, hogy

Fontos megkülönböztetni az inverz képet a halmaz reláció szerinti ősképétől, aminek a definíciója a következő:

Az őskép általában nem egyezik meg az inverz képpel, de minmindigsze annak. A két kép kapcsolatát mutatja az ábra. Megjegyezzük azonban, hogy függvény, illetve parciális függvény esetén a két kép megegyezik.

Legyen és . Ha -t leszűkítésének nevezzük.

Ha és

egy leszűkítése, amit úgy is nevezünk, hogy megszorítása -ra.

1.3.1Műveletek

A relációk között értelmezünk műveleteket is. Legyen és . Ekkor az relációt a és relációk kompozíciójának nevezzük, ha

Az relációt a és relációk szigorú kompozíciójának nevezzük, ha

Mint az az ábrán is látható, a kompozíció és a szigorú kompozíció általában nem egyezik meg, , de nem eleme -nek. Könnyű belátni, a szigorú kompozíció minmindigsze a kompozíciónak. Azt sem nehéz belátni, hogy ha a két reláció közül legalább az egyik függvény, vagy ha az első parciális függvény, a kétféle kompozíció megegyezik.

Ha azt mondjuk, hogy homogén reláció. A homogén reláció önmagával komponálható. Ennek alapján definiáljuk hatványait:

és ha

Az relációt identitás relációnak is nevezzük és -val jelöljük.

Az reláció lezártja az az reláció, amelyre:

  • és

  • .

A lezárt tehát olyan pontokban van értelmezve, amelyekből kiindulva a relációt nem lehet végtelen sokszor egymás után alkalmazni, és ezekhez a pontokhoz olyan pontokat rendel, amelyeket úgy kapunk, hogy a reláció véges sokszori alkalmazásával kikerülünk az eredeti reláció értelmezési tartományából. Tehát mindig teljesül és -ra és . Felhívjuk a figyelmet arra, hogy ez a definíció nem egyezik meg azzal, amit tranzitív lezártnak szoktak nevezni.

Az reláció korlátos lezártja az az reláció, amelyre:

  • és

  • .

Vegyük észre, hogy egy reláció lezártja, és korlátos lezártja különbözhet. A definíciókból látható, hogy ez a különbözőség csak az értelmezési tartományok között jelentkezhet. Ennek azonban szükséges feltétele, hogy egy alkalmas pontból kiindulva a relációt ne lehessen végtelen sokszor alkalmazni, de a véges sokszori alkalmazások hosszára ne tudjunk korlátot mondani. Természetesen ez csak akkor lehetséges, ha végtelen sok véges alkalmazás-sorozatot tudunk a pontból indítani. Nézzünk erre egy egyszerű példát: legyen , és

Ekkor .

1.3.2Logikai relációk

Az típusú relációkat – ahol tetszőleges halmaz –, logikai relációknak nevezzük. A logikai relációkra bevezetünk néhány jelölést:

Legyen . Ekkor az igazsághalmaza:

gyenge igazsághalmaza:

Ha függvény, akkor az igazsághalmaz és gyenge igazsághalmaz megegyezik.

Legyen , azt függvényt aminek az igazsághalmaza a halmaz karakterisztikus függvényének nevezzük és -val jeljelöljük A fenti definíciókból következik, hogy tulajdonképpen mindegy, hogy egy halmaz részhalmazairól, vagy a halmazon értelmezett logikai függvényekről (állításokról) beszélünk, hiszen ezen fogalmak kölcsönösen egyértelműen megfelelnek egymásnak.

Gyakran fogjuk használni az azonosan igaz és az azonosan hamis függvényeket: és , és . Ha nem okoz félreértést az indexet nem írjuk ki.

Legyen és . Az

relációt feltételes relációnak nevezzük, ami a reláció leszűkítése és kiterjesztése a feltétel igazsághalmazára, azaz .

A továbbiakban egy feltételes reláció lezártját, illetve korlátos lezártját a reláció feltételre vonatkozó lezártjának, illetve feltételre vonatkozó korlátos lezártjának fogjuk nevezni.