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

Question

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

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

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

Answer 1

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

| N |<| languages ​​(N) | </p>

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

languages ​​(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 |