Jump to content

Talk:Computable ordinal

Page contents not supported in other languages.
From Wikipedia, the free encyclopedia

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]