computation-theory - 有限のアルファベット上のすべての言語の集合が数えられないことを証明する

Question

いくつかの改訂を試みていますが、これについてはわかりません：

有限のアルファベット上のすべての言語の集合が数えられないことを証明してください。

カントール対角化法を使用する必要があると感じていますが、この問題にどのように使用するかはわかりません。

Answer 1

計算理論のクラスでこの証明を見つけました。お役に立てば幸いです。

|N| < |言語(N)|

|N| とします。>= |言語(N)|。したがって、language(N) の各要素は、N の要素の 1 つに関連付けることができます。したがって、それらを順番に並べることができます。

言語(N) = {S_1、S_2、S_3、...}

集合 D を次のように定義します。

D = {N 内の n / S_n 内の n}

D は有効であり、D は N のサブセットであるため、D は言語 (N) に属します。したがって、 D = S_k となるkが存在する必要があります。

1) k が D に属する場合、D の定義により、k は S_k に属しません。また、k は D に属していません D = S_k であるため (矛盾が見つかりました)

2) k が D に属さない場合: k は S_k (D の定義による) に属し、k は D = S_k であるため D に属します (再び矛盾)。

想定されているようなシーケンスは存在しません。したがって、言語 (N) の各要素に N の要素を割り当てる単射関数は使用できません。|languages(N)| と結論付けます。!<= |N| なので |言語(N)| > |N|