Halmazok számossága

A számosság fogalma

Véges halmazok számossága

• Definíció: Ha A véges halmaz, akkor a számossága az elemszáma
• Az elemszám egy természetes szám (0 is lehet, az üres halmaznál)
• Jelölés: |A| vagy #A

Azonos számosság fogalma

Két halmaz akkor azonos számosságú, ha létezik közöttük bijektív leképezés.

• Bijektív (kölcsönösen egyértelmű) függvény: olyan f: A → B leképezés, ahol
• Minden A-beli elemnek pontosan egy képe van B-ben
• Minden B-beli elemnek pontosan egy ősképe van A-ban
• “Senki nem marad ki, senkiből nem megy ki két nyíl”
• Fontos: Ez a definíció véges és végtelen halmazokra egyaránt érvényes

Végtelen halmazok meglepő tulajdonságai

Valódi részhalmaz azonos számossággal

Végtelen halmazoknál egy valódi részhalmaz lehet azonos számosságú az eredeti halmazzal!

Példa: ℕ (természetes számok) és a páros számok

• A páros számok valódi részhalmaza ℕ-nek
• Mégis azonos a számosságuk!
• Bijekció: f(n) = 2n
• 0 → 0
• 1 → 2
• 2 → 4
• 3 → 6
• stb.

Megjegyzés: Véges halmazoknál ez soha nem fordulhat elő – egy valódi részhalmaz mindig kisebb elemszámú.

Megszámlálhatóan végtelen halmazok

Definíció

• Megszámlálhatóan végtelen: olyan halmaz, amelynek számossága megegyezik ℕ számosságával
• Ekvivalens definíció: egy halmaz akkor megszámlálhatóan végtelen, ha felsorolhatók az elemei
• A felsorolás maga adja a bijekciót ℕ-nel (a sorozat indexe a hozzárendelés)

Megszámlálhatóan végtelen halmazok

Állítás: Az alábbi halmazok mind megszámlálhatóan végtelenek (azonos számosságúak):

• ℕ (természetes számok)
• Páros számok
• Páratlan számok
• ℤ (egész számok)
• ℚ (racionális számok)

Az egész számok felsorolása

Probléma: ℤ mindkét irányban végtelen

Megoldás:
0, 1, -1, 2, -2, 3, -3, 4, -4, …

Így minden egész szám előbb-utóbb szerepelni fog a felsorolásban.

A racionális számok felsorolása

Átlós felsorolás módszere (csak ℚ⁺ bemutatva, ℚ hasonlóan):

1. Készítünk egy táblázatot:

• Sorok: nevezők (1, 2, 3, 4, …)
• Oszlopok: számlálók (1, 2, 3, 4, …)
• Cellák: a törtek (pl. 1/1, 1/2, 2/1, 1/3, 2/2, 3/1, …)

1. Átlósan járjuk végig a táblázatot:

• 1/1 → 1/2 → 2/1 → 3/1 → 2/2 (kihagyjuk, mert = 1/1) → 1/3 → 1/4 → 2/3 → 3/2 → 4/1 → …

1. Az egyszerűsíthető törteket kihagyjuk (ismétlődések elkerülése)

Eredmény: Minden pozitív racionális szám előbb-utóbb szerepel a felsorolásban.

Házi feladat: Miért azonos számosságú ℚ⁺ és ℚ?

Nem megszámlálható halmazok

A valós számok számossága

Állítás: ℝ (valós számok) számossága nagyobb, mint ℕ számossága.

• Jelölés: c (kontinuum)
• Jelentés: ℝ nem megszámlálhatóan végtelen

Cantor átlós bizonyítása

Tétel: A (0,1) nyílt intervallum sem felsorolható → ℝ sem felsorolható

Bizonyítás (indirekt):

1. Feltevés: Tegyük fel, hogy (0,1) felsorolható
2. Ábrázolás: Minden szám 0,a₁a₂a₃a₄… alakú tizedes tört

• Véges tizedes törtet végtelen sok 0-val egészítünk ki

1. Feltételezett felsorolás:

• 1. szám: 0,a₁a₂a₃a₄…
• 2. szám: 0,b₁b₂b₃b₄…
• 3. szám: 0,c₁c₂c₃c₄…
• 4. szám: 0,d₁d₂d₃d₄…
• stb.

1. Új szám konstruálása: 0,y₁y₂y₃y₄…

• y₁ távolsága a₁-től ≥ 2 (ciklikusan)
• y₂ távolsága b₂-től ≥ 2 (ciklikusan)
• y₃ távolsága c₃-től ≥ 2 (ciklikusan)
• stb.

1. Miért ≥ 2 távolság?

• Elkerüljük a 0,999… = 1 típusú egyenlőségeket
• Biztosítjuk, hogy valóban különböző számot kapjunk

1. Ellentmondás:

• Az új szám az 1. felsorolás beli számtól különbözik (1. jegyben)
• A 2. felsorolás beli számtól is különbözik (2. jegyben)
• A 3. felsorolás beli számtól is különbözik (3. jegyben)
• stb.
• Tehát az új szám nincs benne a felsorolásban!

1. Következtetés: A (0,1) intervallum nem sorolható fel → ℝ sem

Összefoglalás

Számosságok hierarchiája

• Megszámlálhatóan végtelen: ℕ, ℤ, ℚ (mind azonos számosságú!)
• Kontinuum (nagyobb): ℝ, (0,1), stb.

Kulcsfogalmak

• Bijekció: kölcsönösen egyértelmű hozzárendelés
• Felsorolhatóság: ekvivalens a megszámlálható végtelennel
• Cantor átlós módszere: nem megszámlálhatóság bizonyítására

Fontos felismerések

• Végtelen halmazoknál egy valódi részhalmaz lehet azonos számosságú
• A racionális számok sűrűek a számegyenesen, mégis megszámlálhatóak
• Léteznek különböző méretű végtelenségek

Megjegyzés: A Cantor-féle bizonyítás és a kontinuum fogalma nem kötelező része az érettséginek, de érdemes ismerni és megérteni!