II. Halmazok. Relációk II.1. Rövid halmazelmélet A halmaz (sokaság) „jól meghatározott, megkülönböztetett dolgok (tárgyak, fogalmak, stb.) összessége”. A halmaz alapfogalom. Ez azt jelenti, hogy csak példákon keresztül magyarázzuk, szemléltetjük, de értelmezése nincs. A halmazelméletet, melyet önálló diszciplínává Cantor fejlesztett a XIX. század második felében, a matematika minden ága felhasználja. (Georg Cantor német matematikus, 1845 – 1918) A halmazokat az abc nagybetűivel jelöljük. Azt a tényt, hogy x elem az A halmaz eleme (hozzátartozik az A halmazhoz) x ∈ A jelöljük és „x eleme A halmaznak” olvassuk. Az x ∉ A jelölés olvasata: x nem eleme A-nak (x elem nincs benne az A halmazban). A halmaz megadása. -A halmaz megadható az elemei felsorolásával, vagyis szintetikus módon. A felsorolt elemeket { } zárójelbe írjuk. Minden elemet csak egyszer írunk le. A felsorolt elemek sorrendje nem számít. Az ilyen halmazokat rendezetlen halmazoknak nevezzük. -A halmaz másik megadási módja az analitikus megadás, vagyis megadjuk a halmaz elemeinek jellemző tulajdonságát. E jelölési mód formája: {x p( x )}. Olvasata: „azon x elemek halmaza, amelyekre p(x)”, vagyis azon x elemek halmaza, amelyek rendelkeznek a p(x) tulajdonsággal. Pl. A = {x 10 < x ≤ 35, x Μ 5, x ∈ N } = {x ∈ N 10 < x ≤ 35, x Μ 5} = {x ∈ N ; 10 < x ≤ 35, x Μ 5} Kiolvasása: azon x számok, melyek 10 és 35 között vannak, utóbbit beleértve, amelyek oszthatók 5-tel és természetes számok. Szabatosan, tömören fogalmazva: azon, 5-tel osztható természetes számok halmaza, amelyek 10 és 35 között vannak, beleértve az utóbbit. Az A halmaz felsorolással megadva: A = {15,20,25,30,35}. Egy halmazban lehet véges számú elem, végtelen számú (pl. a természetes számok halmazában), vagy egyetlen elemet sem tartalmaz. Ez utóbbi neve üres halmaz, jele:Ø. Ha az A halmaz minden eleme a B halmaznak is eleme, akkor azt mondjuk, hogy A részhalmaza B-nek. Jele: A ⊆ B . Kiolvasása: „A halmaz részhalmaza B halmaznak”, „A benne van a B-ben”, „ B magában foglalja (tartalmazza) A-t”. Ez az értelmezés tömörítve: def
( A ⊆ B ) ⇔ (∀x ∈ A ⇒ x ∈ B ) . 1
Ugyanez Venn-Euler diagrammal: A B Az A halmaz részhalmazai között van az Ø és A maga A halmaz is. Ezeket az A halmaz nem valódi részhalmazainak nevezzük. Az A halmaz többi részhalmazának a neve az A valódi részhalmazai. Ha azt akarjuk jelölni, hogy A halmaz valódi részhalmaza B-nek, akkor a ⊂ részhalmaz jelet használjuk, vagyis: A ⊂ B. Az A halmaz részhalmazainak a halmazát P(A) jelöli: Vagyis P( A) = {X X ⊆ A} . Ha az A halmaznak n eleme van ( n ≥ 0 ), akkor A részhalmazainak száma 2 n . Ez az állítás matematikai indukcióval, Newton binom képletével bizonyítható. A bizonyítást az olvasóra bízom. Pl. Legyen A = {a, b, c}. Írjuk föl a P(A)-t. P( A) = {O/ , {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, A}. Látható, hogy a megadott 3 elemes halmaznak 8 = 2 3 darab részhalmaza van. Két halmaz egyenlő, ha ugyanazokat az elemeket tartalmazza, vagyis egymásnak def
kölcsönösen részhalmazai: ( A = B ) ⇔ ( A ⊆ B ∧ B ⊆ A) .
Halmazműveletek 1.Halmazok egyesített halmaza tartalmazza szóban forgó halmazok összes elemét A ∪ B = {x x ∈ A ∨ x ∈ B}
A
B
2.Két vagy több halmaz metszete csak azon elemeket tartalmazza, amelyek mindenik halmazban előfordulnak. A ∩ B = {x x ∈ A ∧ x ∈ B}. A B Az ábrán a mindkét irányban satírozott rész. Ha két halmaz metszete az üres halmaz, ezeket diszjunkt halmazoknak nevezzük. 3.Két halmaz különbséghalmaza az első halmaz azon elemeit tartalmazza, amelyek nincsenek A meg a második halmazban. A − B = {x x ∈ A ∧ x ∉ B}. (jelöljük A \ B-vel is.) 4.Egy halmaznak adott halmazra vonatkozó kiegészítő (komplementer) halmaza tulajdonképpen a két halmaz különbsége: Ha A ⊂ E , akkor C E A = E − A = {x x ∈ E ∧ x ∉ A} .
2
B
E
5.Két halmaz Descartes-szorzata a két halmaz elemeiből képezett rendezett elempárok halmaza. A × B = {( x, y ) x ∈ A, y ∈ B} Amennyiben ezek a halmazok számhalmazok, a Descartes-szorzat mértani ábrázolása derékszögű koordináta rendszerben lehetséges. Ha A és B halmazok egész számokat tartalmaznak, akkor a sík rácspontjainak részhalmazát kapjuk ábraként. Pl. Ha A = {2, 3, 5}, B = {1, 3}, akkor A × B = {(2,1); (2,3); (3,1); (3,3); (5,1); (5,3)}. Az így kapott szorzat rácspontjai a mellékelt ábrán láthatók
Ha A és B zárt intervallumok, akkor az AxB képe egy téglalap, a belsejével együtt. Pl. Ha A = [2, 5], B = [1, 3], akkor az A × B szorzat mértani képe az ábrán látható téglalap és annak belseje. Nyilvánvaló, hogy amennyiben nyílt, vagy félig nyílt, félig zárt intervallumokat veszünk, e szerint fog változni az, hogy a téglalap belsejéhez éppen melyik határszakasza fog hozzátartozni.
3
A halmazokkal végzett műveletek tulajdonságai: A ∪ A = A, A ∪ O/ = A A∪ B = B ∪ A ( A ∪ B ) ∪ C = A ∪ (B ∪ C ) A ∩ A = A, A ∩ O/ = O/ A∩ B = B ∩ A ( A ∩ B ) ∩ C = A ∩ (B ∩ C )
A ∪ (B ∩ C ) = ( A ∪ B ) ∩ ( A ∪ C ) A ∩ (B ∪ C ) = ( A ∩ B ) ∪ ( A ∩ C ) Ha A, B ⊂ E , akkor CE (A ∪ B) = CE A ∩ CE B CE (A ∩ B) = CE A ∪ CE B (de Morgan képletek)
Nevezetes számhalmazok: A természetes számok halmaza: N = {0,1,2,3,...} Az egész számok halmaza: Z = {...,−3,−2,−1,0,1,2,3,...} a A racionális számok halmaza: Q.= a, b ∈ Z , b ≠ 0 b Valós számok halmaza: R Irracionális számok halmaza: R \ Q Minden olyan számhalmaz esetében, ha a halmaz nem tartalmazza a 0-t, akkor a szokásos jelölés, hogy „megcsillagozzuk” a halmaz nagybetűjét: N* = N \ {0}. A számhalmazok között fennáll a következő bennfoglalás: N ⊂ Z ⊂ Q ⊂ R . A halmazműveletek és feladatmegoldás Pl. Egy osztályban 30 tanuló van. Ezek háromféle sportkörre járnak: futballozni, kosarazni és úszni. 20 tanuló futballozik, 16 tanuló kosarazik, 10 tanuló úszik, 11-en futballoznak
4
és kosaraznak, 7 tanuló futballozik és úszik, 5 tanuló kosarazik és úszik, 4 tanuló mindhárom tevékenységen részt vesz. Hány tanuló nem jár egyetlen sportkörre sem? Megoldás A halmazdiagrammot „belülről kifelé” haladva kell kitölteni a feladat adatainak megfelelően, aztán számolunk: (6 + 4 + 2) + (7 + 1+ 3) + 4 =27, 30 – 27 = 3 Tehát van 3 tanuló, aki nem vett részt semmilyen sporttevékenységen.
Pl.Egy 38-as létszámú nagyobb közösségben mindenki jár valamilyen nyelvórára. Angolra 21-en, németre 19-en, franciára 12-en. 7-en járnak angolra is és németre is, 6-on németre és franciára, 3-an pedig angolra és franciára. Hányan vannak akik mind a három nyelvet tanulják? Megoldás Kitöltjüka halmazábrát. Az ismeretlen középső mezőben levők száma legyen x. Ilyenformán a csak a és n = 7-x, a csak n és f = 6-x, csak a és f = 3-x. A csak angol: 21-7-(3-x) = 11+x. A csak német: 19-7-(6-x) = 6+x A csak francia: 12-6-(3-x) = 3+x Ezeket rendre összeadva meg kell kapnunk az összlétszámot: (11 + x) + (6 + x) + (3 + x) + (7 – x) + (3 – x) + (6 – x) x = 38 Tehát 36 + x = 38, x = 2. Ketten tanulják mindhárom nyelvet.
5
II.2. A relációk Pl.1. Adottak A = {2,5} és B = {10,11,12,15} halmazok. Képezzük az A×B Descartes-szorzatot. A × B = {(2,10); (2,11); (2,12); (2,15); (5,10); (5,11); (5,12); (5,15)} . Válasszuk a fenti halmaz következő részhalmazát: {(2,10); (2,12); (5,10); (5,15)}. Vajon milyen szabály szerint válogattunk? Milyen összefüggés figyelhető meg a Descartes-szorzat választott elempárjai között? Ha az elempárok (a,b), akkor a osztója b-nek. A példa az A és B halmaz elemei között egy kapcsolatot értelmez. A példánkban azt mondjuk: aρb (a elem ρ relációban van b-vel), ha a osztója b-nek. A ρ („ró”)görög betű. Pl.2. Maradjunk az előző példa két halmazánál. Ebben a példában ρ relációt megadó szabály legyen: aρb, ha 7a+2>b Ekkor a ρ = {(2,10); (2,11); (2,12); (2,15); (5,10); (5,11); (5,12); (5,15)} = A × B halmaz pontosan a megadott relációban levő elempárokat adja meg. Értelmezés. Adottak az A és B halmazok. Az A és B halmazon értelmezett bináris (kétváltozós) reláció az A és B halmazok A×B Descartes-szorzatának egy részhalmaza. 6
Megjegyzések -Mivel maga a Descartes-szorzat nem kommutatív, a két halmaz szerepe általában nem felcserélhető. -A fenti példákból adódik, hogy a reláció megadásához, a halmazok megadása mellett, elégséges a Descartes-szorzat részhalmazának megadása. Ilyen esetben lehet az a feladat, hogy fogalmazzuk meg a reláció, a válogatás, a megfeleltetés szabályát. -Fordítva is eljárhatunk: megadjuk a két halmazt és azt a szabályt, amely szerint az első halmaz valamely elemének megfeleltetjük a második halmaz valamely elemét. Ilyenkor viszont az lehet a feladat, hogy adjuk meg az A×B-nek a relációt leíró részhalmazát, vagyis soroljuk fel a relációban levő elempárokat. -A következőkben a relációban mindig elempár fog szerepelni, vagyis bináris (kétváltozós) relációkról lesz szó. Ezeket röviden relációknak fogjuk nevezni. Pl.3. A={Eszter, Anna, Kincső, Rózsa}, B={eper, málna, egres, alma, szamóca, narancs}. Ha képeznénk az A×B szorzatot, annak 24 db eleme lenne. Ebből ad meg a következő reláció ötöt. ρ = {(Eszter , eper ); (Eszter , egres ); ( Anna, alma ); ( Anna, narancs ); (Rózsa, szamóca )} . Vajon mi lehet a reláció szabálya? Ha megfigyeljük a megadott relációt, meg tudjuk fogalmazni a reláció törvényét: aρb, ha a és b magánhangzói azonosak. A fenti példákból látható, hogy bármilyen természetű elemeket tartalmazó halmazokkal fogalmazhatunk relációkat. A példák sora szinte kimeríthetetlen. Pl.4. A = {piros, zöld, fehér, sárga}, B = {Sára, Panka, Zelma, Ernő, Flóra}. (a, b) ∈ A × B, aρb ⇔ ha a szó ugyanazzal a betűvel kezdődik, mint b szó. Tehát ρ = {(piros, Panka), (zöld, Zelma), (fehér, Flóra), (sárga, Sára)}. Pl.5. A = {1, 2, 3, 4}, B = {1, 2, 3, 4}, vagyis A = B. ρ = {(1,1), (1,2), (1,3), (1,4), (2,2), (2,3), (2,4), (3,3), (3,4), (4,4)}. Mi a reláció törvénye? aρ b ⇔ a ≤ b . Pl.6. A = B = a III. éves hallgatók halmaza. (a, b) ∈ A, aρb , ha a hallgató ugyanolyan magas, mint b hallgató. Készítünk egy gyors felmérést. A ρ relációt azok a hallgatópárok alkotják, akik ugyanolyan magasak. Tegyük föl, hogy ezekkel a hallgatókkal dolgoztunk: A = {BM, VE, SA, DM, ME, SzT, SzE, BA} és ezeket az adatokat kaptuk: 1,58 – BM, VE 1,59 – SA, DM,ME 1,56 – SzT 7
1,57 – SzE 1,53 - BA Tehát ρ = {(BM, BM); (BM, VE); (VE, BM); (VE,VE); (SA, SA); (SA, DM); (DM, SA); (DM, DM); (SA, ME); (ME, SA); (ME, ME); (DM, ME); (ME, DM); (SzT, SzT); (SzE, SzE); (BA, BA)} Ha egy relációban A = B, akkor a relációt bináris homogén relációnak nevezzük. Tehát az utolsó két példa bináris, homogén reláció.
A relációk ábrázolása (1)Rács A vízszintes tengelyen sorra „ábrázoljuk” az A halmaz elemeit, a függőleges tengelyen a B halmaz elemeit, ezeken keresztül rendre függőleges, illetve vízszintes szakaszokat húzunk és az egymással relációban levők metszéspontját megjelöljük.
Pl.1. A = {2,5} és B = {10,11,12,15} . ρ = {( a, b) a osztja b − t} reláció gráfja látható a fenti ábrán. A lenti rács a 3. példa gráfját ábrázolja. Pl.3. A={Eszter, Anna, Kincső, Rózsa}, B={eper, málna, egres, alma, szamóca, narancs}. ρ = {(Eszter , eper ); (Eszter , egres ); ( Anna, alma ); ( Anna, narancs ); (Rózsa, szamóca )}
8
.
(2)Nyíldiagram A legegyszerűbb függvények ábrázolásánál is használjuk. A halmazok elemeit felsorakoztatjuk, a párban levő elemek közé kitesszük a nyilakat a megfelelő irányba. Pl.4. A = {piros, zöld, fehér, sárga}, B = {Sára, Panka, Zelma, Ernő, Flóra}. ρ = {(piros, Panka), (zöld, Zelma), (fehér, Flóra), (sárga, Sára)}.
(3)Gráf (pontosabb az irányított gráf megnevezés) Csak a homogén relációkat ábrázoljuk gráffal, vagyis ha ugyanazon a halmazon értelmeztük, A = B. Itt PL.6. ábrája következik gráffal ábrázolva: 9
SzT
BA
SA BM DM
SzE VE ME Az önmagába visszakanyarodó nyílat hurokélnek nevezzük. Ez azt jelenti, hogy bármely hallgató relációban van önmagával, mivel önmagával egyenlő magasságú.
A következők egy A halmazon értelmezett bináris homogén relációkra vonatkoznak A relációk tulajdonságai (1)Relációban van-e egy elem önmagával, vagy nem?
(a)Reflexivítás Értelmezés Egy bináris homogén reláció reflexív, ha az A halmaz minden eleme relációban van önmagával. ρ : A → A reflexív ⇔ ∀a ∈ A esetén aρ a Ha a relációt gráffal ábrázoljuk, minden elem esetén megvannak a hurokélek. Ha ráccsal ábrázoljuk, az átlóról nem hiányzik egyetlen metszéspont sem Példák 1.)A fenti gráfból látszik, hogy a PL.6.-ban egy reflexív reláció van megadva, minden elemnek relációban van önmagával, minden elem esetében visszafordul önmagába is a nyíl (hurokélek). 2.)A Pl.5.-ban szintén reflexív relációt adtunk meg, mert bármely szám esetén igaz, hogy a ≤ a. Az alábbi ábra a Pl.5. ábrája ráccsal:
10
3.)A következőkben megadott példáknál csak a halmaz lesz megadva, amelyen a relációt értelmezzük és a reláció rövid leírása. A reflexivítás fennállásának ellenőrzése az olvasóra marad. a.)A természetes számok halmazán az egyenlőségi reláció. (reflexív, mert bármely természetes szám egyenlő önmagával). b.)Az emberek egy csoportján az ugyanolyan súlyos reláció c.)Az emberek egy csoportján az ugyanolyan magas d.)Az emberek egy csoportján az ugyanolyan idős e.)Az emberek egy csoportján a nem magasabb f.)A természetes számok halmazán a ≤ g.)A Föld országainak halmazán az ugyanazon a földrészen vannak h.)Az emberek egy csoportjának halmazán ugyanabban a városban lakik i.)Az egy óvodába járó gyerekek halmazán az ugyanabba a csoportba jár j.)Az emberek egy csoportjának halmazán nem hosszabb a haja
(b)Irreflexív reláció Értelmezés Egy bináris homogén relációt akkor nevezünk irreflexívnek, ha egyetlen elem sincs az alaphalmazban, amely relációban lenne önmagával. ρ : A → A irreflexív ⇔ ∀a ∈ A esetén aρ/ a A rácson. illetve a gráfon a reflexivítást jelentő részletek egyetlen esetben sem jelenhetnek meg, vagyis nincs egy hurokél sem és nincs egyetlen pont sem az átlón.
11
Példák 1.)Nyilván, hogy a reflexivításnál felhozott példák nem felelhetnek meg. 2.)a.)Egy megye lakóinak halmazán az édesanyja reláció. (Egy lakos akkor van relációban egy másikkal, ha az első édesanyja a másodiknak). Nyilván, mivel senki sem lehet saját magának édesanyja, ezért ez egy irreflexív reláció. b.)Az emberek egy csoportja halmazában az alacsonyabb c.)Valamely számhalmazban a > d.)Az emberek egy csoportján a súlyosabb e.)Az emberek egy csoportján a fiatalabb f.)A síklapok halmazán a kisebb területű (Egy síklap relációban van egy másikkal, ha a területe kisebb, mint a másik területe) (2)A kölcsönösséggel kapcsolatos tulajdonságok
(a)Szimmetria Értelmezés Egy bináris homogén relációt szimmetrikusnak nevezzük, ha abból, hogy egy elem relációban van egy másikkal, következik, hogy a második elem is relációban van az elsővel ρ : A → A szimmetrikus ⇔ ha aρ b, akkor bρ a A gráfon ez úgy látszik, hogy két elem között, vagy nincs nyíl, vagy oda-vissza megy a nyíl. Ha a ráccsal való ábrázolást nézzük, akkor minden pont a főátlóra nézve szimmetrikusan kell elhelyezkedjen, esetleg magán a főátlón lehetnek pontok. Példák 1.)A Pl.5. szimmetrikus reláció, mert ha egyik hallgató magassága egyezik a másikéval, akkor a másodiké is egyezik az elsőével. 2.)A reflexivításnál felsoroltak közül szimmetrikusak: a.), b.), c.), d.), g.), h.), i.) Térjünk ezekre vissza és indokoljuk a szimmetriát. 3.)A háromszögek halmazán a kongruencia 4.)Az egyenesek halmazán a merőlegesség (ha a ⊥ b ⇒ b ⊥ a ).
(b)Aszimmetria Értelmezés Egy bináris homogén reláció aszimmetrikus, ha egyetlen esetben sem teljesül a szimmetria ρ : A → A aszimmetrikus ⇔ ha aρb, akkor ⇒ / egyetlen esetben sem, hogy bρ a A ráccsal való ábrázolásnál két pontot ha él köt össze, az csak egyirányú lehet. Nincsenek hurokélek sem. A ráccsal való ábrázolásnál nincs olyan pont, amely valamelyik másiknak az átlóra nézve szimmetrikusa lenne.
12
Példák 1.)A reflexivításnál megadottak közül egyik sem aszimmetrikus 2.)Az irreflexivításnál megadottak közül a 2.) példában megadott mind a hat reláció aszimmetrikus. (pl. a c.) példánál: ha egy szám nagyobb, mint a másik, akkor nem lehet, hogy a második nagyobb legyen, mint az első). Indokoljuk végig az összes példát.
(c)Antiszimmetria Értelmezés Egy bináris homogén relációt antiszimmetrikusnak nevezünk, ha abból, hogy aρb és bρa következik, hogy a elem egyenlő a b elemmel. ρ : A → A antiszimmetrikus ⇔ ha abból , hogy (aρb és bρa) ⇒ a = b A gráffal való ábrázoláson bármely két pontot nem köt össze él, vagy csak egyik irányú él köt össze. Hurokélek léte nem kizárt. A ráccsal való ábrázolásnál nincs olyan pontpár, amelyek egymás szimmetrikusai az átlóra nézve, illetve ezek csak az átlón lehetnek. Példák 1.)Valamely számhalmaz a ≤ relációval (ha a≤b és b≤a, akkor a = b) 2.)Valamely számhalmaz a ≥ relációval 3.)N, osztója (ha a|b és b|a, akkor a = b) 4.)A szavak halmazában az „ábécésorrendben nem előzi meg” reláció (Ha egy szót abc rendben nem előz meg egy másik szó, de a másikat sem előzi meg az első, akkor a két szó ugyanaz kell legyen.) 5.)Egy A halmaz összes részhalmazainak P(A) halmazán a ⊆ reláció. (Ha M , N ∈ P ( A), M ⊆ N és N ⊆ M ⇒ M = N ) (3)Az átörökíthetőségről szóló tulajdonság Tranzitivítás, vagy láncszabály Értelmezés Egy bináris homogén reláció tranzitív, ha abból, hogy egy elem relációban van egy másodikkal, a második pedig relációban van egy harmadikkal, következik, hogy akkor az első elem is relációban van a harmadikkal. ρ : A → A tranzitív ⇔ ha abból , hogy (aρb és bρc) ⇒ aρc A gráfon az látható, hogy ha egy elemből van egy út egy másik felé, a másiktól egy harmadik felé, akkor az első és a harmadik között is van egy „direkt” út is. A rácsról a tranzitivítást nehezebb leolvasni. Példák 1.)A Pl.5. és Pl.6. relációk tranzitívak. 2.)A reflexivításnál megadott mind a 10 reláció tranzitív 13
3.)Az irreflexivításnál megadottak az a.) kivételével mind tranzitívak 4.)A háromszögek halmazán a kongruencia, a hasonlóság 5.)A természetes számok halmazán az oszthatóság 6.)Az emberek egy csoportjának halmazán az unokatestvére reláció nem tranzitív 7.)Az egyenesek halmazán a merőlegesség nem tranzitív
Nevezetes kétváltozós homogén relációk (I.)Ekvivalencia reláció Értelmezés Egy bináris homogén relációt ekvivalencia relációnak nevezünk, ha reflexív, szimmetrikus és tranzitív. Pl. Adottak a következő halmazok: A = {3 alma}, B = {3 dió}, C = {alma, fésű, öv}, D = {4 egér}, E = {5 kutya}, F = {4 ember}, G = {5 jaguár}, I = {BMW, Opel, Audi, W}. A felsorolt halmazok által alkotott halmazban értelmezzük a következő relációt: Egy halmaz relációban van egy másikkal, ha ugyanannyi elemet tartalmaznak. A relációt gráffal ábrázoljuk. A B
D
E
I
C
G F
A fent megadott példa egy ekvivalencia reláció. Valóban a reláció reflexív, mert egy halmaz ugyanannyi elemet tartalmaz, mint saját maga, vagyis bármely elem relációban van önmagával. A gráf minden elemének megvan a hurokéle. A reláció szimmetrikus: ha az egyik halmazban ugyanannyi elem van, mint a másikban, akkor a másodikban is ugyanannyi elem van mint az elsőben, vagyis ha egyik elem relációban van egy másikkal, akkor ez a második is relációban van az elsővel. Az ábrát nézve ha két elem között van egy él, akkor megvan a visszafelé tartó él is a két elem között. A reláció tranzitív, mert ahol 3 elem kapcsolódik egybe, ott megvan az első és a harmadik közötti direkt él is. (A→B, B→C, akkor A→C is). Tulajdonság 14
Bármely ekvivalencia reláció azon a halmazon, amelyen értelmezett egy osztályfelbontást valósít meg. Vagyis az alaphalmazt ekvivalencia osztályokra bontja. Osztályok: az alaphalmaz olyan részhalmazai, amelyeknek páronként nincs közös elemük (páronként diszjunktak) és az osztályokat képező halmazok egyesítése pontosan az alaphalmazzal egyenlő. A tulajdonság fordítva is igaz Ha van egy alaphalmaz és azon egy osztályfelbontás, akkor ehhez tartozik egy ekvivalencia reláció, amely ezt az osztályfelbontást létrehozza. Röviden mondva az ekvivalencia reláció osztályokat hoz létre. Ha a fenti példát nézzük, akkor 3 osztály kaptunk: {A, B, C}; {E, G}; {D, F, I}. Ezek a ráccsal való ábrázoláson láthatóan elkülönülnek. Ezek valóban osztályok: a 3 elemes halmazokat tartalmazó, az 5 elemes halmazokat tartalmazó, illetve a 4 elemes halmazokat tartalmazó osztályokról van szó.. Megjegyzés Ha az összes halmazok halmazán értelmezzük ezt a relációt, már el is jutottunk a számosság fogalmához, amely az ugyanannyi elemet tartalmazó halmazokat sorolja egy osztályba. Egy ilyen osztály reprezentánsa lesz egy természetes szám. Ezt a relációt nevezzük ekvipotencia relációnak (lásd a Számhalmazok című fejezetet) Pl. Legyen az alaphalmaz az emberek egy csoportja, a reláció: ugyanabban az évben született. A reláció valóban ekvivalencia reláció. Bármely ember ugyanabban az évben született, mint önmaga, tehát reflexív. Ha egy ember ugyanabban az évben született, mint egy másik, akkor a másik is ugyanabban az évben született, mint az első, tehát szimmetrikus. Ha egy ember ugyanabban az évben született, mint egy másik, a másik, mint egy harmadik, akkor az első is ugyanabban az évben született, mint a harmadik, tehát tranzitív. A reláció az emberek adott csoportját ún. kortárs osztályokra bontja föl. Az osztály reprezentánsa bármelyik személy a kortársak közül. Pl. A háromszögek halmaza és a kongruencia Hogy ez egy ekvivalencia reláció, az igazolást az olvasóra bízom. Az ekvivalencia osztályok az egymással egybevágó háromszögek. Pl. A logi készlet lapjai és a szín (ugyanolyan színű/) Ez alapján a 48 lapot 3 osztályba soroljuk. A példák sora végeláthatatlan, hiszen már egész kicsi kortól „osztályozzuk”, osztályokba soroljuk valamilyen szempont szerint (ez a reláció) a minket körülvevő világ dolgait (ez az alaphalmaz).
15
Érdemes végiggondolni az előzőkben felsorolt összes példát és közülük kiválogatni az ekvivalencia relációkat, megadva az alaphalmazon meghatározott osztályfelbontást is.
(II.)Rendezési relációk Értelmezés Egy homogén bináris reláció irreflexív rendezési reláció, ha rendelkezik a következő tulajdonságokkal: irreflexív, aszimmetrikus és tranzitív. Értelmezés Egy homogén bináris reláció reflexív rendezési reláció, ha rendelkezik a következő tulajdonságokkal: reflexív, antiszimmetrikus és tranzitív. Megjegyzés. Ha a fenti rendezési relációk bármelyike olyan, hogy az alaphalmaz bármely két elem között az a = b, aρ b, bρ a közül valamelyik fennáll, akkor a rendezési relációt teljes rendezésnek nevezzük. Ez az alaphalmaz elemei között létrehoz egy sorbarendezést. Ellenkező esetben a sorbarendezés nem teljes, parciális. Példák Irreflexív rendezési relációk: a.)valamely számhalmazon a < b.)valamely számhalmazon a > c.)az emberek halmazán az idősebb, mint d.)az emberek halmazán az könnyebb, mint c.)az emberek halmazán az magasabb, mint e.)a szavak halmazán a kevesebb betűből áll, mint f.)természetes számok halmazán: 3-mal osztva több maradékot ad mint Reflexív rendezési relációk: a.)valamely számhalmazon a ≤ b.)valamely számhalmazon a ≥ c.)N*, oszthatóság d.)Egy halmaz részhalmazainak halmazán a részhalmaz reláció Ezek közül teljes rendezést valósít meg az irreflexívek közül az a.), b.), a reflexívek közül az a.), b.), d.).
16
