### 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 3^{2} 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