Monday, January 29, 2007

How Many Functions are There of Type Bool -> Bool?

This post is incorrect. See the corrections.

Or, rather, how many continuous functions are there of type Bool_|_ -> Bool_|_? I count 11, which seems like a strange number. The trick is to remember that if f is continuous, then f _|_ =/= _|_ implies that for all x, f x = f _|_. This gives us only two functions which take _|_ to non-_|_:

one = const True
two = const False

The rest of the continuous functions fill the space Bool -> Bool_|_. Since Bool_|_ is of size 3, there are 32 remaining functions, which gives us 9+2 = 11 functions.

We can generalize to say that A_|_ -> B_|_ has |B| + (|B|+1)|A| inhabitants.

No comments: