Счетный вопрос (теория)

Question

Завтра я беру GRE, и у меня был вопрос. Основываясь на ключе ответа, этот практический тест утверждает, что набор всех функций от N до {0, 1} не является счетным.

Разве вы не можете сопоставить натуральные числа с этими функциями, как показано ниже?

 i   1 2 3 4 5 6 7 8 ...
f0 = 0 0 0 0 0 0 0 0 ...
f1 = 1 0 0 0 0 0 0 0 ...
f2 = 0 1 0 0 0 0 0 0 ...
f3 = 1 1 0 0 0 0 0 0 ...
f4 = 0 0 1 0 0 0 0 0 ...

То есть f4 (1) = 0, f4 (2) = 0, f4 (3) = 1 и f4 (все остальное) = 0. Не будет ли это в конечном итоге охватить все возможные виды этих функций? И мы определенно можем сопоставить натуральные числа с этим набором.

Answer 1

Все записи в вашем списке будут содержать конечное число единиц. Где в вашем списке появится функция, которая возвращает 0 для всех четностей, но 1 для всех вероятностей или функция, которая всегда возвращает 1? Аргумент диагонализации может показать, что никакая другая схема нумерации не может работать. Для этого рассмотрим функцию, которая возвращает 1- (fi (i)) в позиции i. Тогда эта функция отличается от каждой записи в списке хотя бы в одном месте, поэтому ее нет в списке.

Answer 2

Любая функция f_k, построенная по этому алгоритму, имеет конечное число значений n, таких что f_k (n) = 1, но у вас есть функция f (нечетная) = 1, f (четная) = 0, которая допустимая функция и отсутствует в списке функций, которые могут быть сгенерированы этим алгоритмом.

Как правило, вы можете применять диагональный аргумент Кантора, как это было сказано Дэном. Если такой набор был нумерованным, то у вас есть нумерованное семейство функций g_1, g_2, ..., которые охватывают весь набор. Но тогда вы можете построить новую функцию h, такую, что h (n)! = G_n (n), по конструкции h не может быть равным ни одному из g_k, абсурд!

Answer 3

Если бы это было исчисляемо, то иррациональные числа тоже должны были бы быть исчисляемыми. Просто подумайте о каждой из этих функций, которые вы перечислили как двоичные десятичные дроби, и вы можете поместить их 1: 1 с действительными [0, 1)

Answer 4

Это часть теоремы Кантора. См. этот документ (ближе к концу.)