Self Doubt

Question

Is the diagonalization language (Ld) countable?

Comments

Every language is Countable.

If $L$ is Non-RE language, then also $L$ is Countable.

$\Sigma^*$ is countable, and Every language is subset of $\Sigma^*,$ hence, Every language is Countable.

$L_D$ is defined as:

$L_D = \{ <M> | \text{M is a TM such that} M \notin L(M) \}$

Thus, $L_D$ is the collection of Turing machines (programs) $M$ such that $M$ does not halt and accept when given itself as input.

$L_D$ is Not-RE and we can prove it using simple “proof by contradiction”, BUT $L_D$ is Countable.

$\color{red}{\text{Watch the following playlist for understanding the concept of Countability:}}$

https://youtube.com/playlist?list=PLIPZ2_p3RNHiMGiPFIOPJG_ApL43JkILI

---

Ok. Thanks.

Answer 1

Let $\sum =\left \{ 0,1 \right \}$ be alphabet.

$\sum^{*}$= Set of all strings from alphabet

L=set of all languages , It is actually power set of $\sum^{*}$ .

now $\sum^{*}$ is countable set as there can be one-to-one corresponding between $\sum^{*}$ and natural number.

Now  L is an uncountable set as from cantor theorem, if S is Countably infinite set then P(S) is uncountable. Here $\sum^{*}$ is countable set so it’s power set is L so ,L is uncountable.

So set of all language is uncountable.

now , we know diagonalization language is not Recursively enumerable language(not RE) but still it is a language which is subset of $\sum^{*}$ .As $\sum^{*}$ is countable and subset of every countable set is also countable so Diagonalization language is also countable .

---

 why set of all non RE language is uncountable(not related to question) ?:-

Now,

set of all language ={set of all RE language} $\cup$ {set of all Non RE language}

Now , We know that set of all RE language is countably infinite as there exist a TM for an RE language and set of turing machine is countable.

Now as the  Set of all RE language is countable , now to make the set of all language uncountable , the set of Non RE language must be uncountable.

So set of all non recursive enumerable language is uncountable .

https://math.stackexchange.com/questions/551630/subset-of-a-countable-set-is-itself-countable

https://en.wikipedia.org/wiki/Cantor%27s_theorem

https://gateoverflow.in/378523/self-doubt?state=edit-378531

Comments

Which one bro ?

---

So set of all non recursive language is uncountable which implies set of all diagonalization language is uncoutable.

How this implication came? Can you give an example of 2 different diagonalization languages?

---

Sir my concept was wrong on diagonalization language. I read those concept again and edited my answer .

diagonalization language is an example for non RE languages.