Mely halmaz hatványhalmaza alef-null számosságú?

Most azt hiszem, hogy a természetes számok kiszámíthatatlan/felsorolhatatlan részhalmazairól ZF-ben nem lehet bizonyítani hogy van beléjük injekció a természetes számokból, szóval akár hozzáveheted axiómának ZF-hez, hogy a kedvenc nem kiszámítható halmazod számossága kevesebb, mint a természetes számoké, azaz: van belőle injekció a természetes számokba, de nincsen bele injekció a természetes számokból. (De nem vagyok járatos a témában, és van egy olyan érzésem, hogy ha ez az állítás igaz lenne, akkor már szembe jött volna velem, olyan egyszerűnek és aranyosnak tűnik.)

Szerintem egy ilyen nem kiszámítható halmaz hatványhalmazára sem lehet rábizonyítani hogy megszámlálható, azt nem tudom, hogy be lehet-e látni hogy sosem az, vagy van amire független ez is.

Egy n elemű halmaz hatványhalmazának a számossága 2ⁿ.

Ha n véges, akkor nyilván 2ⁿ is véges lesz.

Egy végtelen számosságú halmaz hatványhalmazának a számossága mindig nagyobb mint az eredeti halmaz számossága:

|𝒫(H)| > |H|

Lásd: Cantor-télel

Tehát tulajdonképpen mi egy olyan H halmazt keresünk, ami végtelen számú elemből áll, de a számossága kisebb a természetes számok számosságánál. Nos ilyen nincs. Mert mit jelentene ez? Azt, hogy H minden eleméhez hozzá lehetne úgy rendelni pontosan egy természetes számot, hogy nem minden természetes számhoz lehetne hozzárendelni H egy elemét.

Tegyük fel, hogy van ilyen halmaz. Mivel H minden eleméhez hozzá lehet rendelni egy természetes számot, így sorrendiség van a halmaz elemei között, H jólrendezett halmaz lesz, így minden elemnek van pontosan egy rákövetkező eleme. Így mégiscsak megfeleltethető lenne a természetes számok minden elemének pontosan egy eleme a halmaznak.

Nézzük meg közelebbről. Ha H halmaz minden elemének megfeleltethető pontosan egy természetes szám, akkor vehetjük a legkisebb olyan természetes számot, ami hozzá van rendelve a H halmaz egyik eleméhez, és vegyük azt a H halmazbeli elemet, ami hozzá van rendelve. Ehhez rendeljük hozzá az 0-át. Aztán vegyük a maradékból a legkisebbet olyan természetes számot, ami H valamelyik eleméhez van rendelve, és ahhoz, amihez rendelve van, rendeljük hozzá az 1-et. Ezt a végtelenségig lehet folytatni, H halmaz minden eleméhez hozzá lehet rendelni egy természetes számot, és minden természetes számhoz a H halmaz egy elemét. Így a két halmaz számossága azonos.

Tehát nincs olyan halmaz, aminek a számossága végtelen, de kisebb, mint a természetes számok halmazának számossága. Márpedig egy ilyen halmaznak kellene lennie annak, aminek a hatványhalmazának a számossága אₒ.

Értem, azzal nem vagy tisztában, hogy alef-null-nál nincs kisebb végtelen számosság.

Alef-null a természetes számok halmaza. Minden, ami kisebb nála, másszóval eleme, az definíció szerint természetes szám. Másszóval minden, aminek a számossága alef-nullnál kisebb, véges.

Ezzel #6-ra is válaszoltam: a természetes számok bármely S részhalmazán a benne lévő számok sorrendje automatikusan biztosít egy jólrendezést (AC hiánya sem akadályozza ezt meg), ezért S-nek van számossága, ami vagy kisebb alef-null-nál, vagy egyenlő vele. Előbbi esetben |S| természetes szám, vagyis S véges; nem számít, hogy rekurzív-e.

Igen, #6 az hülyeség, ha van egy orákulum adta nem kiszámítható számhalmazom, akkor őt magát fel lehet használni arra, hogy a tulajdonságait vizsgáljuk... Kb azzal analóg, amit írtam, hogy ha van egy nem kiszámítható számhalmazom, akkor nem uniózhatom össze {1}-gyel, mert az eredmény nem kiszámítható, de mégis van egy kiszámítása... Lapozzunk...

Szerintem ami #8-ban van az jó, mármint ez egy ismert tétel, és ez a bizonyítása.

Kicsit nagyobb vonalakban:

-. a véges rendszámok halmaza rendszám

-. ha H a Cantor féle számosság definíció szerint kisebb-egyenlő számosságú egy O rendszámnál, azaz van H --> O injekció, akkor H jól rendezhető

-. rendszámokra a < jel az ugyanaz mint az "eleme",

-. erre a definícióra a rendszámösszehasonlítás trichotóm, azaz H<O, H=O vagy H>0 fennáll

-. konkrét esetben H>O nem lehet, ha H<O, akkor H véges, ha H=O, akkor H=O.

(Vagy hát részleteztem azokat a lépéseket, amik számomra nem világosak-magától érthetődők.) Legalábbis Komjáth Péter: Halmazelmélet (2007) jegyzete szerint ezek mind igazak ZF-ben is.

(Ez abban különbözik attól, amit 2*Sü ír, hogy nem használja az "ezt végtelenségig lehet folytatni" részt, amiről fogalmam sincs, hogy mikor jogos. A jegyzet maga persze végig használ ilyeneket, de a jegyzet állításaira és tételeire való hivatkozós bizonyítás már nem.)