Докажите, что набор всех языков над конечным алфавитом неисчисляется

Question

Пытаясь сделать редакцию, но не уверен на этом:

Докажите, что набор всех языков над фиксирующим алфавитом неисчисляется.

У меня есть чувство, что он потребует использовать Диагонализация кантора Метод - но я не уверен, как вы будете использовать его для этой проблемы.

Answer 1

Я нашел в моем классе теории вычислений, отмечает это доказательство, я надеюсь, что это полезно для вас

| N |. <| Языки (n) |

Supose, что | n | > = | Языки (n) |. Следовательно, каждый из элементов языков (N) может быть связан с одним из элементов N. Итак, они могут быть введены в порядок:

Языки (n) = {s_1, s_2, s_3, ...}

Мы определяем множество D понравится:

D = {n в n / n не в s_n}

D Действительно, и d представляет собой подмножество n, поэтому d принадлежит языкам (n). Итак, должен существовать k. для которого D = S_K

1) Если K относится к D, то по определению D, K не принадлежит S_K. И k не принадлежит d, потому что d = s_k (мы нашли противоречие)

2) Если K не принадлежит D, то: k принадлежит s_k (по определению d) и k принадлежит d, потому что d = s_k (снова противоречит)

Последовательность, как предполагаемая, не может существовать. Следовательно, инъективная функция, которая присваивает ELEMNT N для каждого элемента языков (N), невозможен. Заключение, что | Языки (N) | ! <= | N |, так | языки (n) | > | N |