Számosság

A Wikipédiából, a szabad enciklopédiából

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[szerkesztés | forrásszöveg szerkesztése]

Egyenlőség[szerkesztés | forrásszöveg szerkesztése]

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ó[szerkesztés | forrásszöveg szerkesztése]

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[szerkesztés | forrásszöveg szerkesztése]

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[szerkesztés | forrásszöveg szerkesztése]

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

Véges halmaz[szerkesztés | forrásszöveg szerkesztése]

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[szerkesztés | forrásszöveg szerkesztése]

Megszámlálhatóan végtelen halmaz[szerkesztés | forrásszöveg szerkesztése]

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[szerkesztés | forrásszöveg szerkesztése]

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 [1]

Példák[szerkesztés | forrásszöveg szerkesztése]

  • 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[szerkesztés | forrásszöveg szerkesztése]

  • 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 Ai 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 Ai 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[szerkesztés | forrásszöveg szerkesztése]

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[szerkesztés | forrásszöveg szerkesztése]

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 (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 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,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 |H| nem lehet megszámlálható.

Néhány idekapcsolódó egyszerű tétel bizonyítás nélkül[szerkesztés | forrásszöveg szerkesztése]

  • 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[szerkesztés | forrásszöveg szerkesztése]

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

Lásd még[szerkesztés | forrásszöveg szerkesztése]

Jegyzetek[szerkesztés | forrásszöveg szerkesztése]

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

Hivatkozások[szerkesztés | forrásszöveg szerkesztése]

  • 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