Talk:Computable ordinal

Latest comment: 10 years ago by LokiClock in topic Recursive set

Recursive set

edit

What does it mean for the well-ordering to be recursive? Is it just the same as the underlying set being recursive while also having a well-order? ᛭ LokiClock (talk) 21:45, 16 March 2014 (UTC)Reply

It seems to me it's meant for the order relation to be a recursive subset of  , where   is the subset of the naturals. ᛭ LokiClock (talk) 21:49, 16 March 2014 (UTC)Reply

Yes. A well-ordering is recursive if and only if the underlying set S is a recursive subset of the natural numbers and the ordering relation on S is a recursive subset of S×S. For purposes of deciding the latter issue, one can either ask if the binary indicator function is recursive or the subset of the natural numbers obtained from the ordering by applying the Cantor pairing function has a (unary) indicator function which is recursive. The result is the same either way. JRSpriggs (talk) 05:23, 17 March 2014 (UTC)Reply
Makes sense. Appreciate it! ᛭ LokiClock (talk) 09:25, 17 March 2014 (UTC)Reply