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:
Post a Comment