Számosság

Nem tévesztendő össze a következővel: Megszámlálhatósá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 ${\displaystyle H}$ halmaz számosságának vagy kardinális számának a jele: ${\displaystyle |H|}$.

Számosságok relációi

Egyenlőség

Legyen ${\displaystyle A,B}$ két tetszőleges halmaz. Akkor mondjuk, hogy az ${\displaystyle A}$ és ${\displaystyle B}$ halmazok ekvivalensek (vagy más szóval egyenlő számosságúak), ha létezik ${\displaystyle A\to B}$ bijektív leképezés.

Megjegyzés: A halmazok ekvivalenciája halmazok tetszés szerinti halmazában ekvivalenciareláció.

Kisebb-nagyobb reláció

Legyen ${\displaystyle A,B}$ két tetszőleges halmaz. Akkor mondjuk, hogy ${\displaystyle |A|\leq |B|}$, ha létezik ${\displaystyle f:A\to B}$ injektív leképezés, ami ${\displaystyle A}$ minden eleméhez ${\displaystyle B}$ más-más elemét rendeli, azaz ${\displaystyle A}$ ekvivalens ${\displaystyle B}$ egy részhalmazával. Ha létezik ilyen injektív leképezés, de ${\displaystyle A}$ ${\displaystyle B}$-vel magával már nem ekvivalens, azaz nincs megfelelő bijektív leképezés, akkor ${\displaystyle B}$ számossága nagyobb, mint ${\displaystyle A}$ számossága. Jele: ${\displaystyle |A|<|B|}$.

Cantor-Bernstein-tétel

Belátható a következő (végtelen halmazok esetében nem triviális) tétel:

Ha ${\displaystyle |A|\geq |B|}$ és ${\displaystyle |A|\leq |B|}$, akkor ${\displaystyle |A|=|B|\,}$.

Alternatív megfogalmazás: Ha az ${\displaystyle A\,}$ és ${\displaystyle B\,}$ halmazok között léteznek ${\displaystyle f:A\to B}$ és ${\displaystyle g:B\to A}$ injektív leképezések, akkor létezik egy ${\displaystyle h:A\to B}$ injektív ráképezés (bijekció) is.

Azaz, ha létezik olyan ${\displaystyle f\,}$ függvény, ami az ${\displaystyle A\,}$ halmaz elemeihez a ${\displaystyle B\,}$ halmaz különböző elemeit rendeli, és egy ${\displaystyle g\,}$ függvény, ami ${\displaystyle B\,}$ elemeihez ${\displaystyle A\,}$ különböző elemeit rendeli, akkor létezik olyan ${\displaystyle h\,}$ függvény is, mely ${\displaystyle A\;}$ és ${\displaystyle B\,}$ 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

A véges halmazokat és a megszámlálhatóan végtelen halmazokat megszámlálható halmazoknak nevezzük.

Véges halmaz

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 ${\displaystyle A}$ halmazt véges halmaznak nevezünk, ha valamely ${\displaystyle n\in \mathbb {N} }$ természetes számra létezik ${\displaystyle \{0,...,n-1\}\to A}$ bijekció, beleértve az üres halmazt is ${\displaystyle n=0}$ esetén.

(Vagy másképpen: ${\displaystyle A}$ véges halmaz, ha létezik ${\displaystyle n}$ természetes szám és ${\displaystyle b:n\to A}$ bijekció, ahol ${\displaystyle n}$ Neumann-féle halmazelméleti definíciója ${\displaystyle 0=\emptyset ,1=\{0\},2=\{0,1\},\dots }$ )

Példák

• Legyen ${\displaystyle A=\{1,3,7,21\}}$. Ekkor ${\displaystyle |A|=4}$.
• A ${\displaystyle H}$ véges halmaz hatványhalmazának a számossága ${\displaystyle 2^{|H|}}$.

Megszámlálhatóan végtelen halmaz

Azt mondjuk, hogy a ${\displaystyle H}$ halmaz megszámlálhatóan végtelen, ha létezik ${\displaystyle H\to \mathbb {N} }$ bijekció, ahol ${\displaystyle \mathbb {N} }$ a természetes számok halmaza.

Jelölé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 ${\displaystyle \aleph _{0}}$ (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

• 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 ${\displaystyle \aleph _{0}}$ 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

• A természetes számok halmaza (${\displaystyle \mathbb {N} }$) 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 (${\displaystyle \mathbb {Z} }$) 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ő: ${\displaystyle f(x)=\left\{{\begin{array}{ll}2x&(x\geq 0)\\-2x-1&(x<0)\end{array}}\right.}$

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 (${\displaystyle \mathbb {Q} }$) megszámlálhatóan végtelen. Ugyanis minden pozitív racionális szám egyértelműen felírható ${\displaystyle {\frac {p}{q}}}$ 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.

Az egész rácspontok bejárási útja

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

• Ha A megszámlálható és a tőle diszjunkt B halmaz véges, akkor ${\displaystyle A\cup B}$ 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 A_i halmazunk van és mindegyik megszámlálható, akkor ${\displaystyle A=\bigcup \limits _{i=1}^{k}A_{i}}$ is megszámlálható.
• Megszámlálható sok diszjunkt A_i halmazunk van és mindegyik megszámlálható, akkor az egyesítésük, vagyis ${\displaystyle \bigcup \limits _{i=1}^{\infty }A_{i}}$ halmaz is megszámlálható.
• ${\displaystyle \mathbb {N} }$ összes véges részhalmazainak a halmaza is megszámlálható.

Kontinuum halmaz

Azt mondjuk, hogy a ${\displaystyle H}$ halmaz kontinuum számosságú, ha létezik ${\displaystyle H\to \mathbb {R} }$ bijekció, ahol ${\displaystyle \mathbb {R} }$ a valós számok halmaza.

Jelölés

A kontinuum számosságot Cantor ${\displaystyle {\mathfrak {c}}}$-vel (gót c) jelölte.

Példa

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 ${\displaystyle |H|}$ számosság legalább megszámlálhatóan végtelen (hisz ${\displaystyle H}$ tartalmazza például a nyilvánvalóan megszámlálhatóan végtelen ${\displaystyle {\Big \{}{\frac {1}{2}},{\frac {1}{3}},{\frac {1}{4}},...{\Big \}}}$ részhalmazt). Indirekt tegyük fel, hogy ${\displaystyle H}$ megszámlálhatóan végtelen, vagyis elemeit valamilyen (v₁, v₂, …) sorrendbe rendezhetjük.

Minden ilyen v_i egy 0 és 1 közötti valós szám, felírható tehát végtelen tizedes törtként 0,v_i1v_i2v_i3… 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,v₁₁v₁₂v₁₃…

0,v₂₁v₂₂v₂₃…

0,v₃₁v₃₂v₃₃…

…

sorozat ${\displaystyle H}$ 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,w₁w₂w₃… tizedestört alakjához úgy jutunk, hogy ha v_ii = 1 volt, akkor legyen w_i = 2, ha pedig v_ii ≠ 1 volt, akkor legyen w_i = 1. Ez a w szám biztos nem szerepelhetett a fenti táblázatban, hisz bármely j-re elmondható, hogy v_j 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 ${\displaystyle |H|}$ nem lehet megszámlálható.

Néhány idekapcsolódó egyszerű tétel bizonyítás nélkül

• 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 ${\displaystyle |A\cup B|=|B|}$.
• Megszámlálhatóan végtelen halmaz hatványhalmaza épp kontinuum számosságú.

Megjegyzés

• Struktúra számosságán a struktúra alaphalmazának számosságát értjük.^[2]

Kapcsolódó szócikkek

• Mérhető számosság
• Kontinuumhipotézis
• Cantor-tétel
• Számossági adaptációs hatás

További információk

• 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

1. Lásd: mathforum.org
2. Csirmaz, László & Hajnal, András: Matematikai logika egyetemi jegyzet, ELTE Bp, 1994 (Postscript változat)

Külső hivatkozások

• 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