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?

, ,
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:

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.