1. Halmazok Flashcards
Halmaz
alapfogalom, nem definiáljuk.
Halmaz eleme
alapfogalom, nem definiáljuk.
Halmaz elemeinek meghatározása
- körülírjuk
- felsoroljuk az elemeit
- logikai állítással határozzuk meg
Részhalmaz
’A’ halmaz részhalmaza ’B’ halmaznak, ha ’A’ halmaz minden eleme eleme ’B’ halmaznak is. Jelölés: A⊆B
Valódi részhalmaz
’A’ halmaz valódi részhalmaza ’B’ halmaznak, ha ’A’ halmaz minden eleme eleme ’B’ halmaznak is, és van ’B’ halmaznak olyan eleme, amely nem eleme ’A’ halmaznak. Jelölés: A⊂B
Komplementer
Egy ’A’ halmaz komplementere az alaphalmaz minden olyan eleme, amely nem eleme ’A’ halmaznak.
Unió
Az ’A’ és ’B’ halmazok uniója az alaphalmaz azon elemeit tartalmazza, amelyek ’A’ és ’B’ halmaz közül legalább az egyiknek elemei. Jelölés: A∪B
Metszet
Az ’A’ és ’B’ halmazok metszete az alaphalmaz azon elemeit tartalmazza, amelyek az ’A’ és ’B’ halmaznak egyaránt elemei. Jelölés: A∩B
Különbség
Az ’A’ különbség ’B’ az alaphalmaz azon elemeit tartalmazza, amelyek elemei ’A’ halmaznak, de nem elemei ’B’ halmaznak. Jelölés: A\B
Szimmetrikus differencia
Az ’A’ és ’B’ halmaz szimmetrikus differenciája az alaphalmaz azon elemeit tartalmazza, amelyek vagy az ’A’ halmaznak, vagy a ’B’ halmaznak elemei. (de nem mind a kettőnek)
Jelölés: A∆B
Descartes-szorzat
A relációk definiálásához ismernünk kell a Descartes-szorzat fogalmát. Az ’A’ és ’B’ halmaz Descartes-szorzatának nevezzük azt a halmazt, amelynek elemei a két halmaz elemeiből álló rendezett párok. Jele: A X B
σ reláció
Rendezett párok halmazát, amelyet az A X A Descartes-négyzet részhalmazaként kapunk σ relációnak nevezzük.
Reflexív
A σ reláció reflexív, ha minden a ∈ A-ra teljesül, hogy (a,a) ∈ σ, azaz, ha a halmaz minden eleme relációban van önmagával.
Szimmetrikus
A σ reláció szimmetrikus, ha minden a, b ∈ A-ra teljesül, hogy ha (a, b) ∈ σ, akkor (b, a) ∈ σ. Azaz, ha a relációban van b-vel, akkor b is relációban van a-val.
Tranzitív
A σ reláció szimmetrikus, ha minden a, b, c ∈ A-ra teljesül, hogy ha (a, b) ∈ σ és (b, c) ∈ σ akkor (a, c) ∈ σ. Azaz, ha a relációban van b-vel és b relációban van c-vel, akkor a is relációban van c-vel.
Antiszimmetria
A σ reláció antiszimmetrikus, ha minden a, b ∈ A-ra teljesül, hogy ha (a, b) ∈ σ és (b, a) ∈ σ, akkor a=b. Azaz, ha a relációban van b-vel, akkor b csak abban az esetben lehet relációban a-val, ha a = b.
Dichotom
A σ reláció dichotom, ha minden a, b ∈ A-ra teljesül, hogy (a, b) ∈ σ vagy
(b, a) ∈ σ. Azaz bármely két elemet tekintve az egyik relációban van a másikkal.
Függvény
Akkor mondjuk, hogy az A, B halmazpáron értelmezett f reláció függvény, ha (a, b) ∈ f és (a, c) ∈ f, akkor b=c. Azaz a reláció egyértelmű, vagyis bármely elemhez az A halmazból (a) pontosan egy elem tartozik a B halmazból (b). Ebben az esetben az a elem a b f szerinti ősképe, a b pedig az a f szerinti képe.
Injektív
Egy X -> Y függvény injektív, ha bármely két elemének a képe különböző.
Szürjektív
Egy X -> Y függvény szürjektív, ha a B minden elemének van ősképe A-ban.
Bijektív
Egy X -> Y függvény bijektív, he egyszerre injektív és szürjektív is.
Ekvivalenciareláció
A σ reláció ekvivalenciareláció/ekvivalencia, ha egyszerre reflexív, tranzitív és szimmetrikus.
Ekvivalenciareláció tulajdonságai
Minden ~ ekvivalenciareláció egyértelműen meghatároz egy osztályozást azon az A halmazon, amelyen definiálva van. Azaz, az a, b ∈ A elemek pontosan akkor kerülnek egy osztályba, ha a~b reláció fennáll.
Egy A halmaz egy osztályozása az ~A~ halmazrendszer, ha a halmazai páronként diszjunktak és lefedik az A halmazt.
Részbenrendezés
A σ reláció részbenrendezés, ha egyszerre reflexív, tranzitív és antiszimmetrikus.