Good morning guys,
I'm a new user of StackExchange, and I have already found here:
Set of decision functions are uncountable
However, I do not really understand the answer. I'm a student of Computer Science, so my math is not really good :)
I'm studing the subject computability, in particular, I understand that there are more decision functions than the Turing Machines (TM), thus there are decision functions that cannot be solved by a TM.
However, my notes say:
$\text{LEMMA:}$
The set of decision functions $ f:\mathbb{N} \rightarrow\{0,1\}$ is uncountable.
Can I ask why? as far as I understand countable means that in some way I can associate al the functions an integer. For example, $\mathbb{N}$ is countable, because I can associate each element to $\mathbb{N}$, something like:
1 associated to 1
2 associated to 2
3 associated to 3
etc etc etc ....
Thanks in advance :)
Let's assume that you could associate (list) all the decision functions to the natural numbers. Let's call the decision function that you associate with $n$ simply $f_n$.
Let's construct a special decision function $f_C$. We set
$$f_C(n)=\left\{\begin{matrix} 0, & \text{if} f_n(n)=1 \\ 1, & \text{if} f_n(n)=0\end{matrix}\right.$$
This is a decision function, and it has the property that it cannot be found in your list, because for any $n$ it differs from $f_n$ at least for the argumnent $n$. So your assumption that you could list all decison functions is impossible.
That proof idea is the famous Cantor diagonal argument, and you can see it referenced on the wikipedia page about the power set, which explains this and more: https://en.wikipedia.org/wiki/Power_set