2004-gre-cs-practice-book.pdf/Q70 — различия между версиями

Текущая версия на 10:19, 16 декабря 2024

Вопрос: Q70-4c9f66

Пусть N — множество всех натуральных чисел.

Какие из следующих множеств счетные?

1. Совокупность всех функций из N в {0, 1}
2. Набор всех функций из {0, 1} в N
3. Наибольшее подмножество в N

Ответы

• Нет правильных ответов
• 1 и 2
• 1 и 3
• Правильный ответ: 2 и 3
• 1, 2, 3

Объяснение

Исходники — вопрос 70 на 45 странице книги «2004-gre-cs-practice-book.pdf»

1. «Совокупность всех функций от N до {0, 1}» — мощность континуум, не посчитать.
2. «Набор всех функций из {0, 1} в N» — каждая такая функция → пара значений для нуля и единицы, посчитаем, катит.
3. Ну тут само N и будет, а оно счетно, катит.