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, ami egy természetes szám, beleértve a nullát is, ami 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 $H$ halmaz számosságának vagy kardinális számának a jele: $|H|$.

Számosságok relációi

Egyenlőség

Legyen $A, B$ két tetszőleges halmaz. Akkor mondjuk, hogy az $A$ és $B$ halmazok ekvivalensek (vagy más szóval egyenlő számosságúak), ha létezik $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 $A, B$ két tetszőleges halmaz. Akkor mondjuk, hogy $|A|\leq|B|$, ha létezik $f: A \to B$ injektív leképezés, ami $A$ minden eleméhez $B$ más-más elemét rendeli. Ha $A$ ekvivalens $B$ egy részhalmazával, de $B$-vel magával nem, azaz az $f$ leképezés nem bijektív, akkor $B$ számossága nagyobb, mint $A$ számossága. Jele: $|A|<|B|$

Cantor-Bernstein tétel

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

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

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

Azaz, ha létezik olyan $f\,$ függvény ami a $A\,$ halmaz elemeihez az $B\,$ halmaz különböző elemeit rendeli, és egy $g\,$ függvény ami $B\,$ elemeihez $A\,$ különböző elemeit rendeli, akkor létezik olyan $h\,$ függvény is, mely $A\;$ és $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 saját 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 $A$ halmazt véges halmaznak nevezünk, ha valamely $n \in \Bbb N$ természetes számra létezik $\{ 0,..., n-1 \} \to A$ bijekció, beleértve az üres halmazt is $n = 0$ esetén.

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

Példák

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

Megszámlálhatóan végtelen halmaz

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

Következmény

A természetes számokkal való bijekció pont azt jelenti, hogy ezek a halmazok sorbarendezhetőek. (Hiszen minden elemhez egy-egy sorszámot rendelünk.) A természetes számok halmazának, illetve a megszámlálhatóan végtelen halmazoknak a számosságát szokásosan $\aleph_0$ (e. "alef null") jelöli. Ez a legkisebb végtelen számosság (ezért is a nulla index). Ezzel összefüggésben, a halmazelmélet legszokványosabb felépítésében (ZFC-axiómarendszer) igaz az az állítás, hogy tetszőleges végtelen halmaznak van $\aleph_0$ számosságú részhalmaza. Mellesleg, ez más axiómarendszerekben (például az ún. ZFU) nem teljesül

Példák

• 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ő: $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 ($\Bbb Q$) megszámlálható

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 $A \cup B$ is megszámlálható.
• A diszjunkt A, 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’, ill. 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 $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 $\bigcup\limits_{i=1}^{\infty} A_i$ halmaz is megszámlálható.
• $\Bbb N$ összes véges részhalmazainak a halmaza is megszámlálható.

Kontinuum halmaz

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

Példák

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

Lásd még

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

Hivatkozások

• Rédei László: Algebra I. kötet, Akadémiai Kiadó, Bp (1954)
• Szendrei Ágnes: Diszkrét matematika, Polygon, JATE Bolyai Intézet, Szeged (1994)
• Hajnal András, Hamburger Péter: Halmazelmélet, Nemzeti Tankönyvkiadó, Budapest, 3. kiadás, (1994) ISBN 963-18-5998-3