If you want to make money online : Register now

[Solved]: Why absence of surjection with the power set is not enough to prove the existence of an undecidable language?

, , No Comments
Problem Detail: 

From this statement

As there is no surjection from $\mathbb{N}$ onto $\mathcal{P}(\mathbb{N})$, thus there must exist an undecidable language.

I would like to understand why similar reasoning does not work with a finite set $B$ which also has no surjection onto $\mathcal{P}(B)$! (with $|B|=K$ and $K \in \mathbb{N}$)

Why is there a minimum need for the infinite set?

EDIT Note:

Although I chose an answer, many answers and all comments are important.

Asked By : Hernan_eche

Answered By : Kaveh

If you take any finite set $A$ of TMs, there is a language not decided by any TM in $A$ and the finite powerset would suffice for that. But this is not what we want. We want to show that there is an undecidable language, i.e. a language that no TM can decide it. The cardinality difference between a finite set and its power set would not show that. You need the cardinality difference with the set of all TMs which is countable to say there is a language which is not decided by any machine in the set.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/1993

 Ask a Question

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback