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:
Tankönyv: Ács László, Gáspár Csaba: Analízis I
Fejezet: 1.1, 1.2

Elméleti összefoglaló:
Az a és a b elemekből alkotott rendezett pár definíciója

a,b ={ { a },{ a,b } } .

Ekkor teljesül, hogy a,b = c,d akkor és csak akkor, ha a=c és b=d .

Függvénynek rendezett pároknak egy olyan f halmazát hívjuk, amelyre minden x esetén az igaz, hogy legfeljebb egy olyan y van, amelyre x,y f .

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 dom f , illetve D f ; valamint im f , illetve R f .

Ha az f függvény értelmezési tartománya az A halmaz, értékkészlete a B halmaz, akkor ezt így is szoktuk jelölni:

f:AB ,

és szokás az f függvényre úgy tekinteni, mint amelyik az A halmaz minden eleméhez hozzárendeli a B halmaz egy elemét, (az xA -hoz azt az yB -t, amelyre x,y f , ezt az y-t gyakran f( x ) -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 n esetén legyen I n ={ 1,2,3,...,n } .

Az A és a B halmazok azonos számosságúak, ha megadható f:AB kölcsönösen egyértelmű függvény. Azt, hogy két halmaz azonos számosságú A~B jelöli.

Az A halmaz véges, és elemszáma n, ha A~ I n . A véges A halmaz elemszámát | A | jelöli.

Ha A és B véges halmazok, akkor | AB |=| A |+| B || AB | .

Ez a képlet akárhány véges halmazra általánosítható. Az A 1 , A 2 ,..., A n 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ú, ..., n-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.

| ABCD |=| A |+| B |+| C |+| D || AB || AC || AD || BC || BD || CD |+ +| ABC |+| ABD |+| ACD |+| BCD || ABCD |

Két halmaz esetén, ha AB= , (ilyenkor az A-t és B-t diszjunktnak hívjuk), akkor

| AB |=| A |+| B | ,

tehát diszjunkt halmazok uniójának elemszáma a halmazok elemszámának összege. Ez is igaz n halmaz esetére is, ha a halmazok páronként diszjunktak, azaz bármely kettő különböző halmaz metszete üres.

Az A és a B halmazok direkt szorzata vagy Descartes-szorzata

A×B={ a,b :aA,bB } ,

ez tehát az összes olyan rendezett pár halmaza, ahol a rendezett pár első eleme az A halmazból, második eleme a B 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:

f={ 1,4 , 4,1 , a,b , b,1 , 0,0 , , } .

Lássuk be, hogy f függvény és adjuk meg az értelmezési tartományát, valamint az értékkészletét. Van-e inverze f-nek?

Megoldás: Az f 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

dom f= D f ={ 1,4,a,b,0, } ,

és

im f= R f ={ 4,1,b,0, } .

Az persze mindegy, hogy a D f és az R f elemeit milyen sorrendben soroljuk fel, de persze minden elemet csak egyszer szerepeltessünk.

f-nek nincs inverze, mert nem kölcsönösen egyértelmű, hiszen f( 4 )=f( b )=1 .

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 függvény értelmezési tartomány legyen D f ={ 2,4,8,16,32 } .
A hozzárendelési utasítás pedig a következő:

f( x )= az x reciprokjának tizedes tört alakjában a tizedes pont utáni első tizedes jegy.

Írjuk fel f-et rendezett párok halmazaként.

Megoldás: Mivel 1 2 =0.5 , 1 4 =0.25 , 1 8 =0.125 , 1 16 =0.0625 és 1 32 =0.03125 , így

f( 2 )=5 , f( 4 )=2 , f( 8 )=1 , f( 16 )=0 és f( 32 )=0 .

Ezekből pedig

f={ 2,5 , 4,2 , 8,1 , 16,0 , 32,0 } .

A továbbiakban a hozzárendelési utasítást legtöbbször képlettel fogjuk megadni.

3. feladat Az f függvényt definiáljuk a következőképpen: D f ={ 1,2,3,4,5,6,7,8 } , és f( x )= x 2 . Adjuk meg f inverzét.

Megoldás: Írjuk fel f-et rendezett párok halmazaként:

f={ 1,1 , 2,4 , 3,9 , 4,16 , 5,25 , 6,36 , 7,49 , 8,64 } .

Innen láthatjuk, hogy R f ={ 1,4,9,16,25,36,49,64 } , és hogy f 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

f 1 ={ 1,1 , 4,2 , 9,3 , 16,4 , 25,5 , 36,6 , 49,7 , 64,8 } .

Persze az is nyilvánvaló, hogy f 1 ( x )= x .

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 A és B halmazok esetén

| AB |=| A |+| B\A | .

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.

3-1. ábra

Erről leolvasható az AB=A( B\A ) 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

A( B\A )=A( B A ¯ )=( AB )( A A ¯ )=( AB )H=AB .

Ráadásul most az AB -t a diszjunkt A és B\A uniójaként állítottuk elő, hiszen A( B\A )=A( B A ¯ )=A A ¯ B=B= . A megoldás elején felidézett tétel alapján tehát

| AB |=| A( B\A ) |=| A |+| B\A | .

Ugyanígy egy alkalmas Venn-diagramról megsejthető az

| AB |=| A\B |+| AB |+| B\A |

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 A és a B halmazokról a következőt tudjuk. | A |=17 , | B |=20 és | A\B |=10 . Mekkora a B A ¯ halmaz elemszáma?

Megoldás: Tekintsük a következő ábrát:

3-2. ábra

Ezen az A és a B halmazok Venn-diagramját látjuk, amelyen római számokkal megjelöltük azt a négy halmazt, amelyet általános esetben az A és a B halmaz létrehoz. Érdemes megjegyezni, hogy ezek mindegyike kifejezhető olyan kéttagú metszetként, amelynek első tagja A, vagy A ¯ , a második tagja pedig B, vagy B ¯ . Írjuk is fel ezeket a formulákat:

I.=A B ¯ II.=AB III.= A ¯ B IV.= A ¯ B ¯ , a halmazok elemszámaira pedig vezessük be a következő jelölést: | A B ¯ |=α | AB |=β | A ¯ B |=γ | A ¯ B ¯ |=δ .

Ekkor a feladat feltételeiből azt tudjuk, hogy

α+β=17 β+γ=20 α=10 .

Ez egy lineáris egyenletrendszer az α, β, γ ismeretlenekre, amelyből azok könnyen kiszámolhatók. Valóban, azt kapjuk, hogy α=10 , β=7 és γ=13 . Tehát figyelembe véve a jelölésünket | B A ¯ |=| A ¯ B |=γ=13 .

6. feladat Az A, a B és a C véges halmazokról a következő információkkal rendelkezünk.

a) 5 olyan elem van, amely csak az A halmazban van,
b) A-nak összesen 12 eleme van,
c) 2 olyan elem van, amely nincs benne A-ban, de B-ben és C-ben benne van,
d) 1 olyan elem van, amely A-ban és B-ben benne van, de nincs benne C-ben,
e) C-nek 15 eleme van.

Hány olyan elem van, amely csak a C halmazhoz tartozik.

Megoldás: Rajzoljunk most is egy Venn-diagramot és számozzuk meg a keletkezett részhalmazokat:

3-3. ábra

Hasonlóan a előző feladathoz, az itteni nyolc halmaz is kifejezhető háromtagú metszetekként, például a VI. halmaz elemeit az jellemzi, hogy azok benne vannak B-ben és C-ben, de nincsenek A-ban, ezek tehát az A ¯ BC halmaz elemei. Felírjuk mind a nyolc halmaz előállítását, és az elemszámukra is bevezetünk egy jelölést:

I.=A B ¯ C ¯ , II.=AB C ¯ , III.= A ¯ B C ¯ , IV.=ABC, V.=A B ¯ C, VI.= A ¯ BC, VII.= A ¯ B ¯ C, VIII.= A ¯ B ¯ C ¯ , a=|A B ¯ C ¯ |, b=|AB C ¯ |, c=| A ¯ B C ¯ |, d=|ABC|, e=|A B ¯ C|, f=| A ¯ BC|, g=| A ¯ B ¯ C|, h=| A ¯ B ¯ C| ¯ ,

Érdemes megjegyezni, hogy az A, B, C 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( B\C )=I.II.III.IV.V.=
=(A B ¯ C ¯ )(AB C ¯ )( A ¯ B C ¯ )(ABC)(A B ¯ C) .

A bevezetett jelölésekkel az a)-e) feltételek egyenletek formájában írhatók fel a következőképpen:

a = 5, a+b+d+e = 12, f = 2, b = 1, d+e+f+g = 15.

A kérdés pedig az, hogy mivel egyenlő g?

Az első két egyenletből b+d+e=7 . A negyedik egyenletet is figyelembe véve azt kapjuk, hogy d+e=6 . Ezt beírva az ötödik egyenletbe következik, hogy f+g=9 . Végül ebből, a harmadik egyenletet is figyelembe véve, g=7 adódik, tehát 7 olyan elem van, amelyik egyedül csak a C halmazhoz tartozik.

7. feladat Igazoljuk, hogy tetszőleges A, B és C halmazok esetén

A×( BC )=( A×B )( A×C ) .

Megoldás: Kétoldali tartalmazással bizonyítunk.

Legyen x,y A×( BC ) . Ekkor xA és yBC . Tehát két eset lehetséges. Az első, hogy xA és yB , ekkor x,y A×B és akkor persze x,y ( A×B )( A×C ) is igaz. A másik lehetőség, hogy xA és yC , de ekkor x,y A×C , amiből megint csak következik, hogy x,y ( A×B )( A×C ) . Ezért tehát A×( BC )( A×B )( A×C ) .

Fordítva, legyen x,y ( A×B )( A×C ) . Ekkor is két eset lehet. Ha x,y A×B , akkor xA és yB , amiből következik, hogy yBC -nek is, tehát x,y A×( BC ) . Teljesen hasonlóan, ha x,y A×C , akkor xA és yCBC , tehát most is x,y A×( BC ) . Ebből következik, hogy ( A×B )( A×C )A×( BC ) .

Ez a két tartalmazás együtt valóban azt jelenti, hogy A×( BC )=( A×B )( A×C ) .

8. feladat Bizonyítsuk be, hogy

( A×C )( B×D )=( AB )×( CD ) ,

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 x,y ( A×C )( B×D ) . Ekkor xA és xB , tehát xAB , illetve yC és yD , vagyis yCD . Így x,y ( AB )×( CD ) , tehát ( A×C )( B×D )( AB )×( CD ) .

Fordítva, ha x,y ( AB )×( CD ) , akkor xA és xB , és yC és yD . Ez, máshogy csoportosítva az információkat azt jelenti, hogy xA és yC , azaz x,y A×C , és xB és yD , vagyis x,y B×D is igaz, így végül x,y ( A×C )( B×D ) , ami azt jelenti, hogy ( AB )×( CD )( A×C )( B×D ) .

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 A n elemű véges halmaz, azaz legyen | A |=n . Lássuk be, hogy ekkor | A×A |= n 2 .

Megoldás: Az általánosság megszorítása nélkül feltehetjük, hogy A= I n ={ 1,2,3,...,n } , hiszen az, hogy konkrétan mik az elemek, nem számít, csak az a lényeg, hogy A-nak n különböző eleme van.

Ezután csoportosíthatjuk az A×A elemeit a következő módon.

Az első csoportba kerülnek az 1,i típusú elemek, ahol i=1,2,3,...,n értékeket vehet fel, a direkt szorzatnak ilyen típusú eleme nyilván n darab van.

A második csoportba kerülnek a 2,i típusú elemek, ahol i=1,2,3,...,n értékeket vehet fel, a direkt szorzatban ilyen típusú elemből is nyilván n darab van.

És így tovább, az utolsó n. csoportba kerülnek az n,i típusú elemek, ahol i=1,2,3,...,n értékeket vehet fel, ilyen típusú elemből is n 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 n csoportunk van, és minden csoportban n elem van, tehát összesen valóban n 2 rendezett pár van.

10. feladat Igazoljuk, hogy tetszőleges véges A és B halmazok esetén

| ( A×B )( B×A ) |= | AB | 2 .

Megoldás: Láttuk korábban, hogy direkt szorzatok metszetét hogyan lehet képezni. Ezt fogjuk most alkalmazni. Ez alapján

( A×B )( B×A )=( AB )×( BA )=( AB )×( AB ) .

De az előző feladat alapján egy n elemű véges halmaz önmagával vett direkt szorzatának n 2 eleme van. Így tehát valóban

| ( A×B )( B×A ) |=| ( AB )×( AB ) |= | AB | 2 .

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,
10 ember mindhármat figyelemmel kísérte,
25 ember kísérte figyelemmel Wimbledont és az Australian Opent,
20 ember figyelemmel kísérte a US Opent és az Australian Opent, de a Wimbledont nem,
65 olyan ember volt, aki pontosan két versenyt kísért figyelemmel,
165 ember figyelte a US Opent vagy Wimbledont,
120 ember figyelte Wimbledont vagy az Australian Opent.

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 A-val azoknak az embereknek a halmazát, akik figyelemmel kísérték a US Opent, B-vel azok halmazát, akik figyelemmel kísérték Wimbledont és C-vel azok halmazát, akik figyelemmel kísérték az Australian Opent. Ezek mellett a jelölések mellett tehát az A, B és C 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:

3-4. ábra

A feladat szövegében felsorolt információk közül az első alapján h=30 .
A második alapján d=10 .
A harmadik feltétel szerint d+f=25 , tehát f=15 .
A negyedik feltétel szerint pedig e=20 , hiszen e az AC B ¯ halmaz elemszáma.
A következő feltétel azt mondja, hogy b+e+f=65 , amiből az következik, hogy b=30 .

Érdemes talán az eddig kiderített adatokat egy újabb Venn-diagramon feltüntetni:

3-5. ábra

Az utolsó előtti feltétel szerint a+c+75=165 , azaz a+c=90 .
Az utolsó feltétel alapján pedig c+g+75=120 , azaz c+g=45 .

Végül vegyük figyelembe még azt is, hogy összesen 200 embert kérdeztek meg, tehát a+c+g+105=200 , vagyis a+c+g=95 .

Ezekből az egyenletekből az a, c és g ismeretlenek könnyedén kiszámolhatók és azt kapjuk, hogy a=50 , c=40 és g=5 . 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

| A |=a+b+d+e=110 ,
| B |=b+c+d+f=95 ,
| C |=d+e+f+g=50 .

Ellenőrző kérdések:

1. kérdés: Az f függvényt definiáljuk a következő módon. Legyen D f ={ x: x 3 4x=0 } és f( x )= 1 x+1 . Ekkor R f =
{ 1,0,1 } .
{ 0,1,2 } .
{ 1,1, 1 3 } .
{ 1 3 ,1, 1 3 } .
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?
Kettő.
Egy.
Egy sem.
Három.
3. kérdés: A H alaphalmaz A, B, C részhalmazairól az alábbiakat tudjuk. | A |=8 , | B |=13 , | C |=11 , | AB |=| AC |=5 , | BC |=7 , | ABC |=4 és végül | H |=29 . Ekkor | A ¯ B ¯ C ¯ |=
10.
11.
12.
13.
4. kérdés: Tetszőleges A, B és C halmazok esetén ( AB )×C=
( A×C )\( B×C ) .
( AB )×C .
( A×C )( B×C ) .
( A×C )( B×C ) .
5. kérdés: Tetszőleges A, B, C és D halmazok esetén
( A×B )( C×D )=( AC )×( BD ) .
( A×B )( C×D )( AC )×( BD ) .
( A×B )( C×D )( AC )×( BD ) .
( A×B )( C×D )( AC )×( BD ) .
6. kérdés: Tegyük fel, hogy A és B véges halmazok és | AB |=2 . Ekkor | ( A×B )( B×A ) |=
2.
3.
4.
8.
7. kérdés: Tegyük fel, hogy A és B véges halmazok. Ekkor
| A×B |=| A || B | .
| A×B |<| A || B | .
| A×B |>| A || B | .
| A×B || A || B | .