Reláció

A reláció a matematikában általános és gyakran használt fogalom (kisebb, nagyobb egyenlő, párhuzamos, merőleges, stb), de nem számít alapfogalomnak. Ez azt jelenti, hogy definiálható, bár középiskolában nem tanuljuk, mert a definícó elsőre inkább ijesztő, mint a fogalom megértését segítő. Így inkább csak a szemléletre támaszkodva dolgok valamilyen viszonyát értjük reláció alatt.

Definíció: Az halmazokon értelmezett n-változós reláció az descartes szorzat (direkt szorzat) egy részhalmaza.

Definíció: Az descartes szorzat részhalmazait A feletti, vagy A-n értelmezett n-változós homogén relációnak nevezzük.

Definíció: Az halmaz részhalmazait az A és B halmazon értelmezett bináris relációknak nevezzük.

Definíció: Homogén bináris a reláció, ha a kéttényezős direkt szorzat tényezői megegyeznek. Tehát:

A középiskolai matematika tanulmányok során legtöbbször ilyen relációkkal találkozunk.

Jelölés: Bináris relációk esetén az jelölés helyett általában a könnyebben olvasható (x relációban áll y-nal) jelölést használjuk.

Példák:

• A={hajó,autó,repülő}, B={föld, levegő, víz}, R={(a,b):ha a tud közlekedni b-n} = R={(hajó,víz),(autó,föld),(repülő,föld),(repülő, levegő)}
• részhalmaz reláció
• modulo n reláció: A=B={egész számok} (homogén), R={(a,b): ha a = b mod n}

A relációk kardinalitása a relátumok számosságára vonatkozó mennyiségi megszorítás típusát fejezi ki. Ez a típus csak kétféle lehet: adott relátumban vagy csak egyetlen elem fordulhat elő, vagy több (amit az 1 vagy az N szimbólumok megadásával jelölhetünk).

Ha az A és B – nem üres – halmazokon értelmezett ⊆A×B Descartes-szorzat részhalmaza, akkor jobbról egyértelmű, másként funkcionális reláció, amennyiben A-nak minden x elemére és B-nek minden y és z elemére igaz, hogy ha x és y, illetve x és z relációban állnak, akkor y megegyezik z-vel, vagyis ∀x∈A, ∀y∈B, ∀z∈B, melyekre igaz, hogy ha (x,y)∈ és (x,z)∈, akkor y=z.

A balról egyértelműség a relátumok szerepeinek felcserélésével a fentihez hasonló módon határozható meg.

∀x∈A, ∀y∈A, ∀z∈B, melyekre igaz, hogy ha (x,z)∈ és (y,z)∈, akkor y=x.

Bináris reláció esetén így négyféle kardinalitásérték létezik: 1:1-es (kölcsönösen egyértelmű, például: férj-feleség), 1:N-es (csak balról egyértelmű, például: anya-gyermek), N:M-es (például: fiú testvér-lány testvér) és N:1-es (csak jobbról egyértelmű, például: szülő-elsőszülött).

Ha egy homogén bináris relációban az alaphalmaz minden elemére igaz, hogy relációban áll önmagával, akkor a relációt reflexív relációnak nevezzük. Formálisan:

Ha egy homogén bináris relációban az alaphalmaz egyik eleme sem áll relációban önmagával, akkor a relációt irreflexív relációnak nevezzük. Formálisan:

Ha egy homogén bináris relációban az alaphalmaz bármely két a és b elemére igaz, hogy a pontosan akkor áll relációban b-vel, ha b is relációban áll a-val, akkor a relációt szimmetrikus relációnak nevezzük. Formálisan:

Ha egy homogén bináris relációban az alaphalmaz bármely két a és b elemére melyre fennáll, hogy egyszerre a relációban áll b-vel és b is relációban áll a-val, akkor az a és b azonos, akkor a relációt antiszimmetrikus relációnak nevezzük. Formálisan:

Egyes szakirodalmakban találkozhatunk a szigorú értelemben véve antiszimmetrikus kifejezéssel, melynek jelentése: , azaz a reláció irreflexív és antiszimmetrikus.

Egyszerű példa az antiszimmetrikus relációra a valós számok halmazán értelmezett „kisebb egyenlő” reláció, hiszen ha két a és b valós számokra és , akkor a=b áll fenn.

Hasonló a pozitív egész számok halmazán értelmezett „osztója” reláció. Itt ugyanis ha a osztója b-nek és fordítva b is osztója a-nak, akkor a=b. (Vigyázat! Az egész számok halmazán már nem teljesül a feltétel, mert a és b egymás ellentettjei is lehetnek!)

További példaként említhető egy halmaz hatványhalmazán vett részhalmaz reláció.

Fontos megjegyezni, hogy az antiszimmetrikus reláció nem ellentéte a szimmetrikus relációnak. Van olyan reláció (például az egyenlőség), amely egyben szimmetrikus és antiszimmetrikus, és van olyan reláció, amely nem szimmetrikus és nem antiszimmetrikus (például az egész számok halmazán értelmezett oszthatóság).

Ha egy homogén bináris relációban az alaphalmaz bármely a, b, c elemére igaz, hogy ha a relációban áll b-vel és b relációban áll c-vel, akkor a is relációban áll c-vel, akkor a relációt tranzitív relációnak nevezzük. Formálisan:

Itt jegyezznénk meg, hogy az összefüggőség, a di- és trichotómia nem egyértelműen jelenik meg a szakirodalmakban, itt inkább csak a teljesség kedvéért hivatkozunk rájuk.

Ha egy homogén bináris relációban esetén és közül legalább az egyik teljesül, akkor a relációt összefüggő relációnak nevezzük.

Ha egy homogén bináris relációban esetén és közül legalább az egyik teljesül, akkor a relációt erősen összefüggő (vagy gyengén trichotóm, esetleg teljes) relációnak nevezzük. Több helyen ezt nevezik dichotóm tulajdonságnak.

Ha egy homogén bináris relációban esetén és közül pontosan az egyik teljesül, akkor a relációt dichotóm relációnak nevezzük.

Ha egy homogén bináris relációban esetén , és közül pontosan az egyik teljesül, akkor -t trichotom relációnak nevezzük.

Az A felett értelmezett homogén bináris reláció ekvivalencia-reláció, ha reflexív, szimmetrikus és tranzitív.

Ekvivalencia-reláció esetén a képhalmaz (másnéven érkezési halmaz, A) valamely elemével relációban álló elemek halmaza ekvivalencia-osztályt alkot.

Az állítást tételként is megfogalmazhatjuk:

Tétel: Ha A-n értelmezett ekvivalencia reláció, akkor van olyan halmazrendszer, melyre

• 
• (diszjunkt halamzok)
• 

Ekkor az halmazokat a reláció által definiált ekvivalencia-osztályoknak nevezzük.

Bizonyítás: Nem középiskolás anyag - de ha valaki nagyon ráér…. :)

• maradékosztályok
• vektor, mint az irányított szakaszok ekvivalenciaosztályai
• komponens, mint a „van út P és Q között” reláció ekvivalencia-osztályai a gráfoknál
• …

Az A halmazon értelmezett bináris, homogén relációt rendezési relációnak nevezzük, ha tranzitív és antiszimmetriukus.

A szigorú rendezési reláció, ha irreflexív, illetve gyenge rendezési reláció, ha reflexív rendezési reláció.

Matematikailag a fenti megkülönböztetésnek nincs túl nagy szerepe, mert bármelyik gyenge rendezéshez egyértelműen tartozik egy szigorú rendezés, melyekre két különböző elem akkor és csak akkor áll az egyik szerint relációban, ha a másik szerint is.

Fontos kérdés viszont, hogy a halmaz bármely két eleme összehasonlítható-e egymással, tehát az, hogy a reláció erősen összefüggő-e. Az erősen összefüggő (szigorú rendezés esetén dichotóm) rendezéseket teljes vagy lineáris rendezéseknek nevezzük, egyébként részben rendezési vagy parciális rendezési relációról beszélünk.

Az rendezett párt (részben) rendezett halmaznak nevezzük.

Példa:

• A valós számok halmaza a < relációval rendezett halmaz.
• A pozitív egészek | (osztója) relációja részben rendezés
• a valós számok körében értelmezett kisebbegyenlő (), illetve nagyobbegyenlő () reláció gyenge rendezés
• a halmazok körében értelmezett „részhalmaza” () reláció (beleértve a nem valódi részhalmazokat is!) részben rendezés

Ha az A és B – nem üres – halmazokon értelmezett ⊆A×B Descartes-szorzat részhalmaza, akkor totális reláció, amennyiben A-nak minden x elemére létezik B-nek olyan y eleme, hogy x és y relációban állnak, vagyis ∀x∈A esetén létezik y∈B, hogy (x,y)∈.

A fueggvenyek felfoghatók speciális relációként is:

Definíció: Az bináris reláció függvény, ha -hoz pontosan egy olyan található, amelyre . Ekkor A-t indulási, B-t érkezési halmaznak (képhalmaz) nevezzük.
Megjegyzés: a függvény értékkészleténél B lehet bővebb halmaz, nem azonos tehát a két fogalom!

Rövidebben: a funkcionális és totális bináris relációt függvénynek nevezzük.