0
$\begingroup$

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.

1 Answers 1

3

HINT: The set of finite binary strings is countably infinite, so there are exactly as many decision functions as there are functions from $\Bbb N$ to $\{0,1\}$.

  • 1
    @alexthebake: That’s one way to go, yes. Alternatively, if you’ve already proved that the set of functions from $\Bbb N$ to $\{0,1\}$ is uncountable, you can just set up a bijection between these functions and your decision functions.2012-10-23