Matek (Végtelenek közti különbség)?

Megszámolhatóan végtelen: természetes számok

Megszámlálhatatlan végtelen: irracionális számok

Megszámlálhatóan végtelen: fel tudod őket sorolni, egy végtelen hosszú listában. Például a páros számokat: 2, 4, 6, 8.

Pl. egész számok, racionális számok, algebrai számok.

Nem megszámlálhatóan végtelen: nem tudsz egy ilyen végtelen sorozatot mondani az elemeiből.

Pl. irracionális számok, transzcendens számok, valós számok, pontok száma egy szakaszon/egyenesen/síkban.

A különbség a #2 válaszban van, csak eltévesztette a megfogalmazást.

Mint a neve is mutatja, a megszámlálhatóan végtelen össze elemét sorba tudod rakni. A módszer az eldöntésre a következő: elkezded sorba venni a halmaz elemeit, és mindegyikhez hozzárendeled a következő egész számot (indexálás). Ha az összeset be tudtad sorszámozni, akkor egy megszámlálhatóan végtelen halmazzal állsz szemben. Ha nem, akkor megszámlálhatatlanul végtelen. Ennek a bizonyítása általában úgy történik, hogy megmutatunk egy kimaradt elemet.

#2, #4: elfelejtettem hozzátenni, hogy a "létezik sorszámozása" és a "be is tudod sorszámozni" két lényegesen különböző dolog.

Tehát az lehetséges, hogy egy halmazról tudjuk, hogy megszámlálhatóan végtelen (tehát tudjuk, hogy létezik sorszámozás), de a konkrét sorszámozást mégsem tudjuk megmondani.

A megszámlálható itt egészen pontosan azt jelenit, hogy lehet kreálni olyan algoritmust, amivel végig lehet menni az adott halmaz összes elemén (természetesen egy kiinduló elemtől elindulva). Minden elemre lehet definiálni egy előző és egy következő elemet. A halmaz bármelyik elemére meg tudjuk mondani, hogy hányadik lépésben lehet eljutni hozzá a bejárás során. Mondjuk a páros számok halmazára lehet egy olyan algoritmust kreálni, hogy nullával kezd, majd: -2, 2, -4, 4, -6, 6, -8, 8, stb…

Így pl. a -8572-ről tudjuk, hogy előtte a +8570 van, utána meg a +8572 következik. Nullától elindulva a 8571. lépésben érünk ehhez a számhoz. De akármelyik elemről el tudjuk mondani ezeket.

A megszámlálhatatlanul végtelen esetén nem lehet ilyen algoritmust kreálni.

2xSü!

Nem algoritmusnak kell léteznie, hanem egyértelmű hozzárendelésnek a megszámlálhatóan végtelen halmaz és a természetes számok halmaza között.

Nem biztos, hogy létezik is algoritmus, amit pl. implementálhatsz egy számítógépen, és akkor megadsz neki egy n számot, és ő véges időn belül válaszol, hogy melyik az n-edik eleme a megszámlálhatóan végtelen halmaznak.

"Nem algoritmusnak kell léteznie, hanem egyértelmű hozzárendelésnek a megszámlálhatóan végtelen halmaz és a természetes számok halmaza között."

Mi a különbség ha azt mondom hogy van rá algoritmus vagy az hogy van rá egyértelmű hozzárendelés?

Az algoritmust kicsit tágabb értelemben használtam. Átfogalmazva: Van olyan eljárás amivel bejárható egy kezdeti kiindulóelemből az egész halmaz.

A következő mondatok ekvivalensek egymással:

- Létezik egyértelmű hozzárendelés az adott végtelen halmaz és a természetes számok halmazának elemei között.

- Minden elemnek van egy előző, és egy rákövetkező eleme.

- Létezik olyan eljárás, amivel az egész halmaz bejárható.

- Bármely két elemhez definiálható egy távolság, ami a két elem közötti elemek számánál eggyel nagyobb számot jelent.

Ha az egyik igaz, akkor mind igaz. Ha az egyik nem igaz, akkor egyik sem igaz.