Feladat: N.192 Korcsoport: 18- Nehézségi fok: nehéz
Megoldó(k):  Gyenes Zoltán ,  Juhász András ,  Lukács László ,  Pálvölgyi Dömötör ,  Pozsár Balázs ,  Szabó Péter ,  Terpai Tamás ,  Végh A. László ,  Zábrádi Gergely 
Füzet: 1999/április, 231. oldal  PDF file
Témakör(ök): Részhalmazok, Halmazok számossága, Nehéz feladat
Hivatkozás(ok):Feladatok: 1998/december: N.192

A H halmaz elemei a pozitív egész számok halmazának bizonyos részhalmazai, közülük bármely két különbözőnek a metszete véges halmaz. Következik-e ebből, hogy H megszámlálható?

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.

A válasz nemleges. Konstruálunk egy olyan halmazt, amely eleget tesz a feladat feltételeinek, ugyanakkor nem megszámlálható.
Tetszőleges 0,a1a2a3...¯ tizedestörthöz rendeljük hozzá a következő halmazt:

f(0,a1a2a3...¯)={1a1¯,1a1a2¯,1a1a2a3¯,1a1a2a3a4¯,...}.
Ezzel minden 0 és 1 közötti valós számhoz hozzárendeltünk egy pozitív egész számokból álló halmazt. A halmaz elemei egyértelműen meghatározzák a tizedestörtet, ezért különböző számokhoz különböző halmazt rendeltünk.
Ha a=0,a1a2a3...¯ és b=0,b1b2b3...¯ két különböző szám, amelyek tizedestört alakja először az n-edik tizedesjegyben különbözik, akkor az f(a) és az f(b) halmazoknak az 1a1, 1a1a2, 1a1a2...,an-1 számok közös elemeik, a további elemek viszont különböznek az (n+1)-edik jegyükben. Ezért az f(a) és f(b) halmazoknak csak véges sok, egészen pontosan n-1 közös eleme van.
Álljon most H az összes olyan halmazból, amely előáll f(x) alakban valamely [0,1) intervallumbeli x valós számra. A fentiek szerint H bármely két elemének a metszete véges. Ugyanakkor az f függvény kölcsönösen egyértelmű megfeleltetés a nem megszámlálható [0,1) intervallum és H között, ezért a H maga sem megszámlálható.