Talk:Turing jump

transfinite iteration

I wanted to add a mention that the jump operator can be transfinitely iterated[1] but I undid my edit because I think it was wrong--is it the case that you can iterate all the way to ω₁ but the sets stop being hyperarithmetic after ω₁^CK? This seems necessary but I may be missing something, so I decided to ask for someone more knowledgeable to update the article. Thanks. 66.127.52.47 (talk) 02:16, 9 April 2010 (UTC)

I don't believe you can iterate all the way to ω₁, but there are definitions that let you iterate as far as ω^L₁. The difficulty is that no increasing sequence of degrees has a least upper bound, so the limit stages of the iteration are problematic, and finding a "reasonable" way to handle them takes work. For the hyperarithmetic hierarchy this is not too hard to handle, but after that it becomes very set theoretic and related to the structure of the constructible hierarchy. For a starting point in the literature, you could try Hodes, "Jumping through the transfinite", Journal of Symbolic Logic, 1980 [2]. This is not my area of expertise. — Carl (CBM · talk) 02:37, 9 April 2010 (UTC)

Thanks, I don't know anywhere near enough set theory to understand that article, but I added a reference anyway. Feel free to revert my addition if I messed it up too badly. 66.127.52.47 (talk) 10:21, 9 April 2010 (UTC)

The only difficulty is that the usual jump can be viewed two ways, as an operation on sets of naturals or as an operation on Turing degrees. Thiey correspond perfectly for finite iterations, but this breaks down when you move to infinite levels. When you iterate the Turing jump of a degree α times, where α is a computable ordinal, you get a degree. But when you iterate the Turing jump of a set α times, you have to start by picking a computable presentation of α, and the actual set you get in the end depends on the presentation you obtained. So while the degree 0^(ω) is perfectly well defined, the set $\emptyset$^(ω) is only defined up to a choice of a computable presention of ω. A well-known theorem of Spector closes the gap by showing that if you pick different presentations of the same computable ordinal, the resulting sets have the same degree. For iterations beyond $\omega _{1}^{CK}$, apparently the methods only provide for iterating the jump on degrees, not on sets.— Carl (CBM · talk) 11:41, 9 April 2010 (UTC)

ω jump

Can we use Cantor's pairing function to define ω jump? I mean, we can create list of binary sequences, such that pair (a,b) is 1 if a belongs to X^(b) and else 0, and define X^(ω) as set corresponding to binary sequence constructed using pairing function — Preceding unsigned comment added by 83.21.59.98 (talk) 20:05, 16 April 2012 (UTC)

Yes, that ends giving a set that is Turing equivalent to the set defined in the article, and so they give the same Turing degree. — Carl (CBM · talk) 20:26, 16 April 2012 (UTC)