TOC Not RE language Set

Question

Why set of Not RE languages is uncountable infinite ?Not RE is discrete in nature?

Answer 1

Sigma* is countably infinite and every language is a subset of sigma*. So there will be total possible 2^(Sigma*) possible subsets which is countably infinite. A language is recursively enumerable if and only if there is an enumeration procedure for it.
It proves that NOT RE is uncountable infinite, if it is not then 2^(Sigma*) will become countably infinite which actually is not.

Comments

I didnt get you last line,can you elaborate a bit?

---

@rahul, i think you can prove it like this....

set of all languages are uncountable, call that set as S,

S={L1, L2, L3, L4, L5, L6.............}, where L1, L2, L3.... are all possible languages..

now S can be thought as union of two disjoint set i.e L_REL and L_{not_REL}, where L_REL is set of all REL languages and  L_{not_REL} is set of all not_REL languages..

S=L_REL$\cup$L_{not_REL}= uncountable

now, there will be turing machine for every language in L_REL...and set of turing machines is countable, so L_REL is countable..

if L_REL is countable then L_{not_REL} should definately be uncountable to make S=L_REL$\cup$L_{not_REL} uncountable

---

Countable union countable is countable?

---

yes..

---

ok. Are NOT RE languages also discrete?

---

i dont know this....what discrete means here??

---

I mean the Not RE language is a countable language,right?

---

whatever the language, it will be subset of (sigma)*, since (sigma)* is countable...every type of language over (sigma)* is also countable whether it is REL or not REL...

---

Powerset of "countably infinite" is uncountably infinite. Sigma* is counably infinite, all languages are subsets of Sigma*, it means total possible languages are 2^Sigma*. for each RE language we have a TM which proves that upto RE languages are countably infnite, so now only NOT RE left

---

@joshi_nitish

U mean that the Any language is discrete or Countable  but the set of NOT RE languages is UNcountable ??