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

Question

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

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

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

Answer 1

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

| N | <| языки (N) |

Предположим, что |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(опять противоречие)

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