I wrote:
The classical definition of "general recursive function" refers to functions in Integer -> Integer to begin with, so there can only be countably many values by construction.
Luke Palmer wrote:
Except that there are uncountably many (2^Aleph_0) functions in Integer -> Integer.
No, only countably many. By the type expression Integer -> Integer we mean all Haskell functions mapping Integers to Integers. There are only countably many of those. Of course, you can sometimes use Haskell-like notation for discussing other mathematical concepts. In that context, you might mean to include uncomputable functions in your types. (Hey, there's a fun idea - how would you write the infinite injury algorithm in Haskell?) But that was not the context in this thread. The category Hask that we often mention in discussions about Haskell the programming language is most certainly a small category. -Yitz