Reja: Algoritm tushunchasi

Isbot (diagonal usuldan foydalangan holda): To'plamning son-sanoqsizligini isbotlash uchun, uning ba'zi bir qismining hisobsizligini isbotlash uchun etarli. Fi (x) shaklidagi bitta o'zgaruvchining funktsiyalarini ko'rib chiqamiz. Bitta o'zgaruvchining funktsiyalarining sanab bo'ladigan to'plami bo'lsin, ya'ni. ularni qayta nomlash mumkin. FO (x), E1 (x), F2 (x), ... b (x) = E (x) +1 funktsiyasini tuzamiz. Bu diagonali deb ataladigan funktsiya G (0) = Eo (0) +1, G (1) = X1 (1) +1, b (2) = E2 (2) +1 va boshqalar. 6-sanab o'tilgan barcha funktsiyalardan farq qiladi, chunki u har bir funktsiyadan kamida bitta nuqtada farq qiladi. U E0 (x) funktsiyadan x = 0 nuqtada, F1 (x) funktsiyadan x = 1 nuqtada va hokazo bilan farq qiladi. Biroq, qurilish bo'yicha G (x) bitta o'zgaruvchining arifmetik funktsiyalari to'plamiga tegishli, shuning uchun u ro'yxatda bo'lishi kerak, ya'ni. ushbu funktsiyalardan biriga mos

Bizda qarama-qarshilik bor, shuning uchun boshlang'ich taxmin noto'g'ri va bitta o'zgaruvchining son-sanoqsiz funktsiyalari mavjud. Shunday qilib, n o'zgaruvchilarning barcha funktsiyalari son-sanoqsizdir.