====== 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 A_1, A_2, ..., A_n halmazokon értelmezett **//n//-változós reláció** az A_1*A_2*cdots*A_n [[matematika:halmazok:halmazok#descartes szorzat]] (direkt szorzat) egy varrho részhalmaza. ===== Homogén reláció ===== **Definíció:** Az A*A*cdots*A=A^n descartes szorzat részhalmazait **//A// feletti**, vagy **//A//-n értelmezett** //n//-változós **homogén** relációnak nevezzük. ===== Bináris reláció ===== **Definíció:** Az A*B 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: varrho subset A*A 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 (x;y) in varrho jelölés helyett általában a könnyebben olvasható x varrho y (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ő)} * [[matematika:halmazok:halmazok#részhalmaz]] reláció * modulo n reláció: A=B={egész számok} (homogén), R={(a,b): ha a = b mod n} ===== Reláció kardinalitása ===== 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). ==== Jobbról egyértelmű reláció ==== Ha varrho az A és B – nem üres – halmazokon értelmezett varrho⊆A×B Descartes-szorzat részhalmaza, akkor varrho **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)∈varrho és (x,z)∈varrho, akkor y=z. ==== Balról egyértelmű ==== 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)∈varrho és (y,z)∈varrho, 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). ===== Relációk tulajdonságai ===== ==== Reflexiv ==== Ha egy varrho 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: forall a in A: ~ a varrho a ==== Irreflexiv ==== Ha egy varrho 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: forall a in A: ~ (a,a) notin varrho ==== Szimmetrikus ==== Ha egy varrho 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: forall (a;b) in A*A: ~ (a varrho b) doubleleftright (b varrho a) ==== Antiszimmetrikus ==== Ha egy varrho 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: a,b in A: ~ (a varrho b) wedge (b varrho a) doubleright a = b Egyes szakirodalmakban találkozhatunk a **szigorú értelemben véve antiszimmetrikus** kifejezéssel, melynek jelentése: a,b in A: ~ (a,b) in varrho doubleright (b,a) notin varrho, 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 a<=b és b<=a, 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 [[matematika:halmazok:halmazok#hatványhalmaz]]án vett [[matematika:halmazok:halmazok#részhalmaz]] reláció. Fontos megjegyezni, hogy az antiszimmetrikus reláció nem ellentéte a [[oktatas:matematika:halmazok:relacio#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). ==== Aszimmetrikus ==== a,b in A: ~ (a varrho b) doubleright (b,a) notin varrho ==== Tranzitív ==== Ha egy varrho 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: a, b, c in A: ~ (a varrho b) wedge (b varrho c) doubleright (a varrho c) ==== Intranzitív ==== a, b, c in A: ~ (a varrho b) wedge (b varrho c) doubleright (a,c) notin varrho ==== Összefüggő, erősen összefüggő, dichotóm, trichotóm ==== //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.// === Összefüggő === Ha egy varrho homogén bináris relációban forall a,b in A, a <> b esetén a varrho b és b varrho a közül legalább az egyik teljesül, akkor a relációt **összefüggő** relációnak nevezzük. === Erősen összefüggő === Ha egy varrho homogén bináris relációban forall a,b in A esetén a varrho b és b varrho a 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.// === Dichotóm === Ha egy varrho homogén bináris relációban forall a,b in A, a <> b esetén a varrho b és b varrho a közül pontosan az egyik teljesül, akkor a relációt **dichotóm** relációnak nevezzük. === Trichotóm === Ha egy varrho homogén bináris relációban forall a,b in A esetén a varrho b, b varrho a és a=b közül pontosan az egyik teljesül, akkor varrho-t **trichotom** relációnak nevezzük. ===== Ekvivalencia-reláció ===== Az //A// felett értelmezett varrho homogén bináris reláció **ekvivalencia-reláció**, ha [[#reflexív]], [[#szimmetrikus]] és [[#tranzitív]]. ==== Ekvivalencia-osztály ==== 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ály**t alkot. Az állítást tételként is megfogalmazhatjuk: **Tétel:** Ha varrho //A//-n értelmezett ekvivalencia reláció, akkor van olyan M_1, M_2,cdots, M_n <> varnothing halmazrendszer, melyre * A = M_1 union M_2 union cdots union M_n * M_i inter M_j = varnothing (forall i,j in [1;n] inter bbN) (diszjunkt halamzok) * x in M_i, (x;y) in varrho doubleright y in M_i (forall i,j in [1;n] inter bbN) Ekkor az M_1, M_2,cdots,M_n halmazokat a varrho 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.... :) === Példák === * [[matematika:algebra:szamelmelet#maradékosztály]]ok * [[oktatas:matematika:geometria:vektor]], mint az irányított szakaszok ekvivalenciaosztályai * [[oktatas:matematika:kombinatorika:grafelmelet#komponens]], mint a "van út //P// és //Q// között" reláció ekvivalencia-osztályai a gráfoknál * ... ===== Rendezési reláció ===== Az //A// halmazon értelmezett varrho bináris, homogén relációt **rendezési reláció**nak nevezzük, ha varrho [[#tranzitív]] és [[#antiszimmetriukus]]. A varrho **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 (A,varrho) rendezett párt (részben) **rendezett halmaz**nak 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" (subset) reláció (beleértve a nem valódi részhalmazokat is!) részben rendezés ===== Függvények ===== ==== Totális reláció ==== Ha varrho az A és B – nem üres – halmazokon értelmezett varrho⊆A×B Descartes-szorzat részhalmaza, akkor varrho **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)∈varrho. A [[matematika:analizis:fueggvenyek]] felfoghatók speciális relációként is: **Definíció:** Az (A,B, varrho) [[oktatas:matematika:halmazok:relacio#bináris reláció]] függvény, ha forall a in A-hoz pontosan egy olyan b in B található, amelyre a varrho b. Ekkor //A//-t indulási, //B//-t érkezési halmaznak ([[matematika:analizis:fueggvenyek#képhalmaz]]) nevezzük.\\ **Megjegyzés:** a függvény [[matematika:analizis:fueggvenyek#értékkészlet]]énél //B// lehet bővebb halmaz, nem azonos tehát a két fogalom! Rövidebben: a [[#Jobbról egyértelmű reláció|funkcionális]] és [[#totális reláció|totális]] bináris relációt függvénynek nevezzük.