Okay, so here's the problem:
A function is a decision function if it maps finite length binary strings {0,1}* into codomain {0,1}. Let D be the set of all possible decision functions. Show that D is uncountable.
My attempts so far have been:
Let f be a decision function s.t. $f: \{0,1\}^* \rightarrow \{0,1\}$
Therefore, $f$ is in D, $f(x)$ is in $\{0,1\}$. I also want to say that the input of $f$ must be in the form:
$B_n = \{$ $b_i$ | $b_i \in \{0,1\}\}$
My biggest concern is that this function seems surjective to me, which would indicate that it is countable. But maybe I'm thinking of the wrong part of the problem. I need to show that D is uncountable, so I need to show that the cardinality of D is greater than some other uncountable set. How could I start showing this? What should I be thinking of/about? Any help will be appreciated.