Számosság
A halmazelméletben a számosság fogalma a „halmazok elemszámának” az általánosítása a véges (azaz véges számosságú) halmazokról a végtelen (azaz végtelen számosságú) halmazokra. Véges halmazok esetében a számosság megegyezik tehát a halmaz elemeinek a számával, amely természetes szám, beleértve a nullát is, s ez az üres halmaz elemszámának felel meg. A halmazok számosságának a jelölésére is ugyanazt a jelölést használjuk, mint a véges halmazok esetén a halmazok elemszámának a jelölésére, azaz tetszőleges halmaz számosságának vagy kardinális számának a jele: .
Számosságok relációi
[szerkesztés]Egyenlőség
[szerkesztés]Legyen két tetszőleges halmaz. Akkor mondjuk, hogy az és halmazok ekvivalensek (vagy más szóval egyenlő számosságúak), ha létezik bijektív leképezés.
Megjegyzés: A halmazok ekvivalenciája halmazok tetszés szerinti halmazában ekvivalenciareláció.
Kisebb-nagyobb reláció
[szerkesztés]Legyen két tetszőleges halmaz. Akkor mondjuk, hogy , ha létezik injektív leképezés, ami minden eleméhez más-más elemét rendeli, azaz ekvivalens egy részhalmazával. Ha létezik ilyen injektív leképezés, de -vel magával már nem ekvivalens, azaz nincs megfelelő bijektív leképezés, akkor számossága nagyobb, mint számossága. Jele: .
Cantor-Bernstein-tétel
[szerkesztés]Belátható a következő (végtelen halmazok esetében nem triviális) tétel:
Ha és , akkor .
Alternatív megfogalmazás: Ha az és halmazok között léteznek és injektív leképezések, akkor létezik egy injektív ráképezés (bijekció) is.
Azaz, ha létezik olyan függvény, ami az halmaz elemeihez a halmaz különböző elemeit rendeli, és egy függvény, ami elemeihez különböző elemeit rendeli, akkor létezik olyan függvény is, mely és elemei között kölcsönösen egyértelmű megfeleltetést létesít.
A tétel szemléletesen értelmezve azt jelenti, hogy a halmazok számosságai a rendezési (kisebb-nagyobb) relációjukra nézve láncot alkotnak (a számosságok rendezése trichotom jellegű), azaz ha a és b halmazok (nem feltétlenül finit) elemszámai, akkor az a<b, a=b és a>b lehetőségek közül pontosan egy teljesül.
Megszámlálható halmaz
[szerkesztés]A véges halmazokat és a megszámlálhatóan végtelen halmazokat megszámlálható halmazoknak nevezzük.
Véges halmaz
[szerkesztés]Azt mondjuk, hogy egy halmaz véges, ha nem létezik olyan valódi részhalmaza, amellyel ekvivalens.
Megjegyzés. A véges halmazok fenti definíciója ekvivalens a következő, a természetes szám fogalmát is használó definícióval: Tetszőleges halmazt véges halmaznak nevezünk, ha valamely természetes számra létezik bijekció, beleértve az üres halmazt is esetén.
(Vagy másképpen: véges halmaz, ha létezik természetes szám és bijekció, ahol Neumann-féle halmazelméleti definíciója )
Példák
[szerkesztés]- Legyen . Ekkor .
- A véges halmaz hatványhalmazának a számossága .
Megszámlálhatóan végtelen halmaz
[szerkesztés]Azt mondjuk, hogy a halmaz megszámlálhatóan végtelen, ha létezik bijekció, ahol a természetes számok halmaza.
Jelölés
[szerkesztés]A természetes számok halmaza, illetve a megszámlálhatóan végtelen halmazok számosságát Georg Cantor után szokásosan (ejtsd: alef null, ahol az alef karakter a héber ábécé első betűje) jelöli. Ez a legkisebb végtelen számosság (ezért is a nulla alsó index).
Következmények
[szerkesztés]- A természetes számokkal való bijekció pont azt jelenti, hogy ezek a halmazok sorba rendezhetőek. (Hiszen minden halmazbeli elemhez egy-egy értelmű megfeleltetéssel egy sorszámot rendelünk.)
- A halmazelmélet szokásos felépítésében, a ZFC-axiómarendszer esetén igaz az az állítás, hogy tetszőleges végtelen halmaznak van számosságú részhalmaza. Más axiómarendszerekben ez nem feltétlenül teljesül (például az ún. ZFU-ban).[1]
Példák
[szerkesztés]- A természetes számok halmaza () megszámlálhatóan végtelen sok elemű, hiszen a természetes számok egy-egy értelműen megfeleltethetők a természetes számoknak: minden egyes természetes számhoz hozzárendeljük önmagát mint sorszámot.
- Az egész számok halmaza () megszámlálható, mivel számossága egyenlő a természetes számok számosságával. Ezt könnyű belátni, hiszen legyen a leképező függvényünk a következő:
- Azaz minden nemnegatív számhoz rendeljük a páros számokat és minden negatívhoz a páratlanokat. Ez egy jó példa arra, hogy végtelen halmazok esetében lehetséges, hogy egy halmaz és annak egy valódi részhalmaza egyenlő számosságú.
- A racionális számok halmaza () megszámlálhatóan végtelen. Ugyanis minden pozitív racionális szám egyértelműen felírható alakban, ahol p és q pozitív egész számok relatív prímek. A (p, q) számpárt értelmezhetjük úgy, mint egy P pont koordinátáját a síkon. Minden ilyen P egy egész koordinátájú rácspontra esik. Az egész koordinátájú rácspontokat viszont az alábbi ábrán látható lila út mentén a balfelső sarokból kezdve sorra fel lehet keresni visszatérés nélkül, így a P pontok is sorba rendezhetők a bejárási út mentén, sorrendjük szerint pedig egyértelműen megfeleltethetők a természetes számoknak.
- Hasonlóan belátható, hogy a negatív racionális számok is megszámlálhatóan végtelen sokan vannak. A pozitív és a negatív racionális számok együtt is megszámlálhatóan végtelen sokan vannak, mivel össze tudjuk őket fésülni az egész számok példájában látott leképezéssel. Már csak a 0 maradt ki: tegyük a nullát a számlálásunk legelejére, az 1. pozícióba, a többi racionális szám megszámlálását pedig ismételjük meg a fenti módon, csak éppen a 2. sorszámtól!
Néhány idekapcsolódó egyszerű tétel bizonyítás nélkül
[szerkesztés]- Ha A megszámlálható és a tőle diszjunkt B halmaz véges, akkor is megszámlálható.
- A diszjunkt A és B halmazok egyesítésének s számossága csak A és B számosságától függ, vagyis ha A és B helyére a velük egyenlő számosságú A’, illetve B’ halmazokat tesszük úgy, hogy A’ és B’ diszjunktak, akkor utóbbiak egyesítésének a számossága is s lesz.
- Ha véges sok (mondjuk k darab) diszjunkt Ai halmazunk van és mindegyik megszámlálható, akkor is megszámlálható.
- Megszámlálható sok diszjunkt Ai halmazunk van és mindegyik megszámlálható, akkor az egyesítésük, vagyis halmaz is megszámlálható.
- összes véges részhalmazainak a halmaza is megszámlálható.
Kontinuum halmaz
[szerkesztés]Azt mondjuk, hogy a halmaz kontinuum számosságú, ha létezik bijekció, ahol a valós számok halmaza.
Jelölés
[szerkesztés]A kontinuum számosságot Cantor -vel (gót c) jelölte.
Példa
[szerkesztés]A „legegyszerűbb” ilyen halmaz a [0,1] zárt intervallumba tartozó valós számok halmaza. Ennek számossága kontinuum. Lássuk ezt be!
Ez a számosság legalább megszámlálhatóan végtelen (hisz tartalmazza például a nyilvánvalóan megszámlálhatóan végtelen részhalmazt). Indirekt tegyük fel, hogy megszámlálhatóan végtelen, vagyis elemeit valamilyen (v1, v2, …) sorrendbe rendezhetjük.
Minden ilyen vi egy 0 és 1 közötti valós szám, felírható tehát végtelen tizedes törtként 0,vi1vi2vi3… alakban. (Ez a felírás nem egyértelmű, pl.: 0,5000 = 0,49999…. Ezért most az egyértelműség kedvéért zárjuk ki azt a felírási módot, ahol egy idő után csupa kilences következik.) Az indirekt feltevés szerint tehát a
0,v11v12v13…
0,v21v22v23…
0,v31v32v33…
…
sorozat minden elemét tartalmazná. A táblázat „átlója” mentén végighaladva készítsünk egy olyan w valós számot, melynek w=0,w1w2w3… tizedestört alakjához úgy jutunk, hogy ha vii = 1 volt, akkor legyen wi = 2, ha pedig vii ≠ 1 volt, akkor legyen wi = 1. Ez a w szám biztos nem szerepelhetett a fenti táblázatban, hisz bármely j-re elmondható, hogy vj szám j-edik tizedesjegye különbözik a w szám j-edik tizedesjegyétől. Mivel így nem minden 0 és 1 közötti valós szám szerepel a felsorolásban, ellentmondásra jutunk, tehát nem lehet megszámlálható.
Néhány idekapcsolódó egyszerű tétel bizonyítás nélkül
[szerkesztés]- Legyen A egy véges vagy megszámlálhatóan végtelen halmaz, B pedig egy tőle diszjunkt, kontinuum számosságú halmaz. Ekkor .
- Megszámlálhatóan végtelen halmaz hatványhalmaza épp kontinuum számosságú.
Megjegyzés
[szerkesztés]Kapcsolódó szócikkek
[szerkesztés]További információk
[szerkesztés]- A végtelenen túl (YouProof, Moldvai Dávid)
- A Végtelen Szálló paradoxona (YouTube, TED-Ed, Jeff Dekofsky; magyar felirat lent bekapcsolható hozzá)
Jegyzetek
[szerkesztés]- ↑ Lásd: mathforum.org
- ↑ Csirmaz, László & Hajnal, András: Matematikai logika egyetemi jegyzet, ELTE Bp, 1994 (Postscript változat)
Külső hivatkozások
[szerkesztés]- Rédei László: Algebra (Akadémiai, 1954) I. kötet
- Szendrei Ágnes: Diszkrét matematika (Polygon – JATE Bolyai Intézet, Szeged, 1994)
- Hajnal András – Hamburger Péter: Halmazelmélet (Nemzeti Tankönyvkiadó, 1994) 3. kiadás. ISBN 963-18-5998-3