On Mon, Feb 2, 2009 at 9:47 AM, Martijn van Steenbergen <span dir="ltr">&lt;<a href="mailto:martijn@van.steenbergen.nl">martijn@van.steenbergen.nl</a>&gt;</span> wrote:<br><div class="gmail_quote"><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
<div class="Ih2E3d">Lennart Augustsson wrote:<br>
<blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
The Haskell function space, A-&gt;B, is not uncountable.<br>
There is only a countable number of Haskell functions you can write,<br>
so how could there be more elements in the Haskell function space? :)<br>
The explanation is that the Haskell function space is not the same as<br>
the functions space in set theory. &nbsp;Most importantly Haskell functions<br>
have to be monotonic (in the domain theoretic sense), so that limits<br>
the number of possible functions.<br>
</blockquote>
<br></div>
I was thinking about a fixed function type A -&gt; B having uncountably many *values* (i.e. implementations). Not about the number of function types of the form A -&gt; B. Is that what you meant?<br>
<br>
For example, fix the type to Integer -&gt; Bool. I can&#39;t enumeratate all possible implementations of this function. Right?</blockquote><div><br>That question has kind of a crazy answer.<br><br>In mathematics, Nat -&gt; Bool is uncountable, i.e. there is no function Nat -&gt; (Nat -&gt; Bool) which has every function in its range.&nbsp; <br>
<br>But we know we are dealing with computable functions, so we can just enumerate all implementations.&nbsp; So the computable functions Nat -&gt; Bool are countable.<br><br>However!&nbsp; If we have a function f : Nat -&gt; Nat -&gt; Bool, we can construct the diagonalization g : Nat -&gt; Bool as:&nbsp; g n = not (f n n), with g not in the range of f.&nbsp; That makes Nat -&gt; Bool &quot;computably uncountable&quot;.<br>
<br>In summary, the set of total computable functions Nat -&gt; Bool is a countable set, but this fact is not observable by any algorithm.&nbsp; (so is it <i>really</i> countable after all? :-)<br><br>Luke<br></div></div>