KURZUS: Matematika (Függvénytan)
MODUL: Halmazok
3. lecke: Halmazok számossága
Tanulási cél: Megismerkedni a függvény fogalmával, azzal, hogy két halmazt mikor hívunk azonos számosságúnak. | |||||||||||
Tananyag: | |||||||||||
Elméleti összefoglaló: | |||||||||||
. | |||||||||||
Ekkor teljesül, hogy akkor és csak akkor, ha és . | |||||||||||
Függvénynek rendezett pároknak egy olyan halmazát hívjuk, amelyre minden esetén az igaz, hogy legfeljebb egy olyan van, amelyre . | |||||||||||
A rendezett párok "első elemeiből" álló halmaz a függvény értelmezési tartománya, a "második elemekből" álló halmaz az értékkészlet. Jelölésük , illetve ; valamint , illetve . | |||||||||||
Ha az függvény értelmezési tartománya az halmaz, értékkészlete a halmaz, akkor ezt így is szoktuk jelölni: | |||||||||||
, | |||||||||||
és szokás az függvényre úgy tekinteni, mint amelyik az halmaz minden eleméhez hozzárendeli a halmaz egy elemét, (az -hoz azt az -t, amelyre , ezt az -t gyakran -el is jelöljük). Mi is legtöbbször ilyen hozzárendelésként fogunk a függvényekre gondolni. | |||||||||||
A halmazelmélet során számunkra a kölcsönösen egyértelmű, vagy más néven bijektív, (egy-egy értelmű) függvények lesznek a legfontosabbak. Kölcsönösen egyértelmű függvénynek létezik inverz függvénye. | |||||||||||
Tetszőleges esetén legyen . | |||||||||||
Az és a halmazok azonos számosságúak, ha megadható kölcsönösen egyértelmű függvény. Azt, hogy két halmaz azonos számosságú jelöli. | |||||||||||
Az halmaz véges, és elemszáma, ha . A véges halmaz elemszámát jelöli. | |||||||||||
Ha és véges halmazok, akkor . | |||||||||||
Ez a képlet akárhány véges halmazra általánosítható. Az halmazok esetén az igaz, hogy az uniójuk elemszámát úgy kapjuk, hogy minden lehetséges módon képezzük a különböző halmazokból álló összes egytagú, kéttagú, háromtagú, ..., -tagú metszeteket, ezek közül a páratlan sok halmaz metszetét tartalmazók elemszámát pozitív, a páros sok tagot tartalmazók elemszámát negatív előjellel látjuk el, és összeadjuk az így kapott számokat. Például négy halmaz esetén az alábbi formula igaz. | |||||||||||
Két halmaz esetén, ha , (ilyenkor az -t és -t diszjunktnak hívjuk), akkor | |||||||||||
, | |||||||||||
tehát diszjunkt halmazok uniójának elemszáma a halmazok elemszámának összege. Ez is igaz halmaz esetére is, ha a halmazok páronként diszjunktak, azaz bármely kettő különböző halmaz metszete üres. | |||||||||||
Az és a halmazok direkt szorzata vagy Descartes-szorzata | |||||||||||
, | |||||||||||
ez tehát az összes olyan rendezett pár halmaza, ahol a rendezett pár első eleme az halmazból, második eleme a halmazból van. | |||||||||||
Felhívjuk a figyelmet arra, hogy ez a művelet se nem kommutatív, se nem asszociatív - noha a megfelelő formulák két oldalán álló halmazok elemei között egy természetes megfeleltetés adható. | |||||||||||
Kidolgozott feladatok: | |||||||||||
1. feladat Tekintsük rendezett pároknak a következő halmazát: | |||||||||||
. | |||||||||||
Lássuk be, hogy függvény és adjuk meg az értelmezési tartományát, valamint az értékkészletét. Van-e inverze -nek? | |||||||||||
Megoldás: Az valóban függvény, hiszen az elemei között nincs két olyan rendezett pár, amelynek első tagjai megegyeznének. | |||||||||||
Az értelmezési tartomány a rendezett párok első tagjaiból álló halmaz, azaz | |||||||||||
, | |||||||||||
és | |||||||||||
. | |||||||||||
Az persze mindegy, hogy a és az elemeit milyen sorrendben soroljuk fel, de persze minden elemet csak egyszer szerepeltessünk. | |||||||||||
-nek nincs inverze, mert nem kölcsönösen egyértelmű, hiszen . | |||||||||||
Ezután a függvények értelmezési tartománya legtöbbször valamilyen számhalmaz lesz, de néha azért lesz szó olyan függvényekről is, amelyeknél az értelmezési tartomány elemei halmazok vagy rendezett párok. | |||||||||||
2. feladat Az függvény értelmezési tartomány legyen . | |||||||||||
az reciprokjának tizedes tört alakjában a tizedes pont utáni első tizedes jegy. | |||||||||||
Írjuk fel -et rendezett párok halmazaként. | |||||||||||
Megoldás: Mivel , , , és , így | |||||||||||
, , , és . | |||||||||||
Ezekből pedig | |||||||||||
. | |||||||||||
A továbbiakban a hozzárendelési utasítást legtöbbször képlettel fogjuk megadni. | |||||||||||
3. feladat Az függvényt definiáljuk a következőképpen: , és . Adjuk meg inverzét. | |||||||||||
Megoldás: Írjuk fel -et rendezett párok halmazaként: | |||||||||||
. | |||||||||||
Innen láthatjuk, hogy , és hogy kölcsönösen egyértelmű, tehát van inverze. Formálisan az inverz függvényt úgy kapjuk, hogy minden rendezett párban megcseréljük a tagok sorrendjét. Tehát | |||||||||||
. | |||||||||||
Persze az is nyilvánvaló, hogy . | |||||||||||
Amikor majd az egyváltozós való függvényekről tanulunk további, ennél bonyolultabb függvények inverzét is meg fogjuk határozni. | |||||||||||
4. feladat Igazoljuk, hogy tetszőleges véges és halmazok esetén | |||||||||||
. | |||||||||||
Megoldás: Tudjuk, hogy páronként diszjunkt halmazok uniójának elemszáma a halmazok elemszámának összege. Tekintsük meg az alábbi ábrát. | |||||||||||
| |||||||||||
Erről leolvasható az előállítás, aminek levezetéssel való igazolása sem bonyolult. Valóban, eltüntetve a kivonást és használva az unió metszetre vonatkozó disztributivitását, kapjuk, hogy | |||||||||||
. | |||||||||||
Ráadásul most az -t a diszjunkt és uniójaként állítottuk elő, hiszen . A megoldás elején felidézett tétel alapján tehát | |||||||||||
. | |||||||||||
Ugyanígy egy alkalmas Venn-diagramról megsejthető az | |||||||||||
képlet, aminek a bizonyítása az előzőhöz hasonlóan elvégezhető. Ezt gyakorlásképpen az olvasóra bízzuk. | |||||||||||
5. feladat Az és a halmazokról a következőt tudjuk. , és . Mekkora a halmaz elemszáma? | |||||||||||
Megoldás: Tekintsük a következő ábrát: | |||||||||||
| |||||||||||
Ezen az és a halmazok Venn-diagramját látjuk, amelyen római számokkal megjelöltük azt a négy halmazt, amelyet általános esetben az és a halmaz létrehoz. Érdemes megjegyezni, hogy ezek mindegyike kifejezhető olyan kéttagú metszetként, amelynek első tagja , vagy , a második tagja pedig , vagy . Írjuk is fel ezeket a formulákat: | |||||||||||
, a halmazok elemszámaira pedig vezessük be a következő jelölést: . | |||||||||||
Ekkor a feladat feltételeiből azt tudjuk, hogy | |||||||||||
. | |||||||||||
Ez egy lineáris egyenletrendszer az , , ismeretlenekre, amelyből azok könnyen kiszámolhatók. Valóban, azt kapjuk, hogy , és . Tehát figyelembe véve a jelölésünket . | |||||||||||
6. feladat Az , a és a véges halmazokról a következő információkkal rendelkezünk. | |||||||||||
| |||||||||||
Hány olyan elem van, amely csak a halmazhoz tartozik. | |||||||||||
Megoldás: Rajzoljunk most is egy Venn-diagramot és számozzuk meg a keletkezett részhalmazokat: | |||||||||||
| |||||||||||
Hasonlóan a előző feladathoz, az itteni nyolc halmaz is kifejezhető háromtagú metszetekként, például a halmaz elemeit az jellemzi, hogy azok benne vannak -ben és -ben, de nincsenek -ban, ezek tehát az halmaz elemei. Felírjuk mind a nyolc halmaz előállítását, és az elemszámukra is bevezetünk egy jelölést: | |||||||||||
| |||||||||||
Érdemes megjegyezni, hogy az , , halmazok minden olyan halmazalgebrai kifejezése, amelyben csak az műveletek szerepelnek felírható ezen nyolc halmaz közül néhánynak az uniójaként, (azaz a nyolc halmaz mindegyike teljes egészben az eredeti halmaz része, vagy diszjunkt tőle). Például az ábráról leolvasható, hogy | |||||||||||
| |||||||||||
A bevezetett jelölésekkel az a)-e) feltételek egyenletek formájában írhatók fel a következőképpen: | |||||||||||
A kérdés pedig az, hogy mivel egyenlő ? | |||||||||||
Az első két egyenletből . A negyedik egyenletet is figyelembe véve azt kapjuk, hogy . Ezt beírva az ötödik egyenletbe következik, hogy . Végül ebből, a harmadik egyenletet is figyelembe véve, adódik, tehát olyan elem van, amelyik egyedül csak a halmazhoz tartozik. | |||||||||||
7. feladat Igazoljuk, hogy tetszőleges , és halmazok esetén | |||||||||||
. | |||||||||||
Megoldás: Kétoldali tartalmazással bizonyítunk. | |||||||||||
Legyen . Ekkor és . Tehát két eset lehetséges. Az első, hogy és , ekkor és akkor persze is igaz. A másik lehetőség, hogy és , de ekkor , amiből megint csak következik, hogy . Ezért tehát . | |||||||||||
Fordítva, legyen . Ekkor is két eset lehet. Ha , akkor és , amiből következik, hogy -nek is, tehát . Teljesen hasonlóan, ha , akkor és , tehát most is . Ebből következik, hogy . | |||||||||||
Ez a két tartalmazás együtt valóban azt jelenti, hogy . | |||||||||||
8. feladat Bizonyítsuk be, hogy | |||||||||||
, | |||||||||||
azaz direkt szorzatok metszetét úgy lehet képezni, hogy vesszük az első tényezők és a második tényezők metszeteit, és ezeknek képezzük a direkt szorzatát. | |||||||||||
Megoldás: Ismét a kétoldali tartalmazás módszere a leghatékonyabb bizonyítási mód. | |||||||||||
Legyen . Ekkor és , tehát , illetve és, vagyis . Így , tehát . | |||||||||||
Fordítva, ha , akkor és , és és . Ez, máshogy csoportosítva az információkat azt jelenti, hogy és , azaz , és és , vagyis is igaz, így végül , ami azt jelenti, hogy . | |||||||||||
Az eredeti formulánkban tehát mindkét oldal része a másiknak, ezért valóban igaz a feladat állítása. | |||||||||||
9. feladat Legyen az elemű véges halmaz, azaz legyen . Lássuk be, hogy ekkor . | |||||||||||
Megoldás: Az általánosság megszorítása nélkül feltehetjük, hogy , hiszen az, hogy konkrétan mik az elemek, nem számít, csak az a lényeg, hogy -nak különböző eleme van. | |||||||||||
Ezután csoportosíthatjuk az elemeit a következő módon. | |||||||||||
Az első csoportba kerülnek az típusú elemek, ahol értékeket vehet fel, a direkt szorzatnak ilyen típusú eleme nyilván darab van. | |||||||||||
A második csoportba kerülnek a típusú elemek, ahol értékeket vehet fel, a direkt szorzatban ilyen típusú elemből is nyilván darab van. | |||||||||||
És így tovább, az utolsó csoportba kerülnek az típusú elemek, ahol értékeket vehet fel, ilyen típusú elemből is darab van. | |||||||||||
Világos, hogy a direkt szorzat minden eleme beletartozik valamelyik csoportba, és az is, hogy csak egyetlen csoportba tartozik. Ezért az előbbi csoportokban a direkt szorzat minden eleme szerepel, és minden elem csak egyszer. Mivel csoportunk van, és minden csoportban elem van, tehát összesen valóban rendezett pár van. | |||||||||||
10. feladat Igazoljuk, hogy tetszőleges véges és halmazok esetén | |||||||||||
. | |||||||||||
Megoldás: Láttuk korábban, hogy direkt szorzatok metszetét hogyan lehet képezni. Ezt fogjuk most alkalmazni. Ez alapján | |||||||||||
. | |||||||||||
De az előző feladat alapján egy elemű véges halmaz önmagával vett direkt szorzatának eleme van. Így tehát valóban | |||||||||||
. | |||||||||||
11. feladat Kétszáz embert megkérdeztek, hogy melyik teniszversenyt kisérték figyelemmel az alábbiak közül: US Open, Wimbledon, Australian Open. Az alábbi válaszok születtek: | |||||||||||
30 ember egyik versenyt sem kísérte figyelemmel, | |||||||||||
Hányan kísérték figyelemmel külön-külön az egyes versenyeket? | |||||||||||
Megoldás: Az ilyen típusú feladatok megoldásához a Venn-diagramok nyújthatnak segítséget. Jelöljük -val azoknak az embereknek a halmazát, akik figyelemmel kísérték a US Opent, -vel azok halmazát, akik figyelemmel kísérték Wimbledont és -vel azok halmazát, akik figyelemmel kísérték az Australian Opent. Ezek mellett a jelölések mellett tehát az , és halmazok elemszáma a kérdés. | |||||||||||
Ha megrajzoljuk a halmazaink Venn-diagramját és az egyes részekbe beírjuk azok, egyelőre ismeretlen, elemszámát, az alábbi ábrát kapjuk: | |||||||||||
| |||||||||||
A feladat szövegében felsorolt információk közül az első alapján . | |||||||||||
Érdemes talán az eddig kiderített adatokat egy újabb Venn-diagramon feltüntetni: | |||||||||||
| |||||||||||
Az utolsó előtti feltétel szerint , azaz . | |||||||||||
Végül vegyük figyelembe még azt is, hogy összesen embert kérdeztek meg, tehát , vagyis . | |||||||||||
Ezekből az egyenletekből az , és ismeretlenek könnyedén kiszámolhatók és azt kapjuk, hogy , és . Mivel a Venn-diagram minden részhalmazának az elemszámát meghatároztuk, minden, az elemszámokkal kapcsolatos, kérdésre válaszolni tudunk. | |||||||||||
Így tehát azt kapjuk, hogy | |||||||||||
, | |||||||||||
Ellenőrző kérdések: |
1. kérdés: Az függvényt definiáljuk a következő módon. Legyen és . Ekkor
![]() | ||||||||||
2. kérdés: Húsz ember közül tíz tud angolul, hat tud németül és hat ember nem tud egyik nyelven sem. Hány ember beszéli mindkét nyelvet?
![]() | ||||||||||
3. kérdés: A alaphalmaz , , részhalmazairól az alábbiakat tudjuk. , , , , , és végül . Ekkor
![]() | ||||||||||
4. kérdés: Tetszőleges , és halmazok esetén
![]() | ||||||||||
5. kérdés: Tetszőleges , , és halmazok esetén
![]() | ||||||||||
6. kérdés: Tegyük fel, hogy és véges halmazok és . Ekkor
![]() | ||||||||||
7. kérdés: Tegyük fel, hogy és véges halmazok. Ekkor
![]() |