有限のアルファベットを介したすべての言語のセットが数えられないことを証明する

Question

何らかの改訂をしようとしていますが、これについてはわかりません：

有限のアルファベットを介したすべての言語のセットが数えられないことを証明します。

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

Answer 1

私は私のComputation Theory Class Notesこの証拠で見つけました、私はそれがあなたに役立つことを願っています

| n | <|言語（n）|

それを| n | > = |言語（n）|。したがって、言語の各要素（n）は、Nの要素の1つに関連する可能性があります。

言語（n）= {s_1、s_2、s_3、...}

次のようなセットdを定義します。

d = {n in n / n in in s_n}

Dは有効で、Dはnのサブセットです。したがって、dは言語（n）に属します。したがって、存在する必要があります k d = s_k

1）kがDに属している場合、Dの定義により、KはS_Kに属しません。 d = s_k（矛盾が見つかるため）はdに属していません。

2）kがDに属していない場合：kはs_k（dの定義により）に属し、kはd = s_k（再び矛盾）のためdに属します。

想定されているようなシーケンスは存在できません。したがって、言語の各要素（n）に対してnのelemntを割り当てる言葉遣い関数は不可能です。その結論|言語（n）| ！<= | n |、so |言語（n）| > | n |