<br><br><div class="gmail_quote">On Fri, Mar 4, 2011 at 8:45 AM, Markus Läll <span dir="ltr"><<a href="mailto:markus.l2ll@gmail.com">markus.l2ll@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">
<font class="Apple-style-span" face="'courier new', monospace"><br>Would this also have an uncomputable order type? At least for comparing tuples you'd just:</font></blockquote><div><br></div><div>You can tell if an enumeration will have an uncomputable order type by whether or not your enumeration has to "count to infinity" before it can continue. For example, let's use top-left to bottom-right diagonals. Then you would have to "count infinitely many steps" (0,0), (1,1), (2,2), (3,3) ... before you could go to the next diagonal. This excludes an enumeration from being computable in the usual sense (or having a computable order type). As Daniel pointed out, every countable set can be put in <i>some</i> computable order, since it can inherit the order of the naturals through the enumeration. </div>
<div><br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;"><br><br><font class="Apple-style-span" face="'courier new', monospace">lt :: (Integer,Integer) -> (Integer,Integer) -> Bool</font><br>
<font class="Apple-style-span" face="'courier new', monospace">
(a,b) `lt` (c,d) = let</font><br><font class="Apple-style-span" face="'courier new', monospace"> sum1 = (a + b)</font><br><font class="Apple-style-span" face="'courier new', monospace"> sum2 = (c + d)</font><br>
<font class="Apple-style-span" face="'courier new', monospace"> in if sum1 == sum2</font><br><font class="Apple-style-span" face="'courier new', monospace"> then a < c</font><br><font class="Apple-style-span" face="'courier new', monospace"> else sum1 < sum2</font></blockquote>
<div><br></div><div>The order you impose is a bit broken, but the principle of using diagonals is sound. (Consider (1,2) and (2,1): under this order, (1,2) `lt` (2,1) and (2,1) `lt` (1,2), so (1,2) == (2,1))</div><div><br>
</div><div>Indeed, the diagonal construction is how an enumeration of the rationals is demonstrated.</div><div><br></div><div><br></div></div><br>