Timeline for What is the Turing degree associated with an ultrafilter $U$?
Current License: CC BY-SA 4.0
20 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 18 at 3:58 | history | edited | Noah Schweber | CC BY-SA 4.0 |
added 45 characters in body
|
| Aug 17, 2017 at 2:15 | comment | added | Andreas Blass | @NoahSchweber I don't recall seeing a proof or disproof of the broad conjecture, so I think it's still open. | |
| Aug 16, 2017 at 20:28 | comment | added | Noah Schweber | @AndreasBlass Hi Andreas, I've had a chance to look at the article you mentioned, which is quite interesting. I'm curious: do you know whether the broader conjecture you discuss (that normal Kleene reducibility between ultrafilters is always due to Rudin-Keisler reducibility or taking ultralimits) is still open? | |
| Aug 14, 2017 at 18:17 | comment | added | Noah Schweber | (I see the confusion, given that I mentioned spectra of structures, but they're really different things; I brought up spectra of structures just as something you might separately be interested in.) It turns out that as soon as we start talking about things other than individual sets/functions of natural numbers, Turing degrees themselves are usually the wrong tool to use: more natural ones are Turing ideals, upwards-directed sets of Turing degrees, enumeration degrees and their ideals and up-sets, and so forth. Turing degrees are just the simplest complexity measure; they're quite limited. | |
| Aug 14, 2017 at 18:14 | comment | added | Noah Schweber | @PyRulez That was what I answered: the set of functions you defined does not correspond to a Turing degree, but rather a Scott set. It would only correspond to a Turing degree if there were a "maximally complicated" such function, but there isn't. This was the whole point of my answer: that while each individual function we can construct by using an ultrafilter obviously has a Turing degree of its own, the collection $\mathcal{U}({\bf d})$ of all of them does not have in any sense a single Turing degree. (cont'd) | |
| Aug 14, 2017 at 18:13 | comment | added | Noah Schweber | not every structure has a Turing degree in this sense! This was first observed by Linda Richter; she showed e.g. that no linear order (without a computable copy) has a Turing degree in this sense. Later, Slaman and Wehner independently constructed structures whose spectrum was exactly the noncomputable degrees, which is even more wild. | |
| Aug 14, 2017 at 18:13 | vote | accept | Christopher King | ||
| Aug 14, 2017 at 18:13 | comment | added | Christopher King | @NoahSchweber well, I was never really asking about what Turing degree can "compute" an ultrafilter, but rather the Turing degree associated with the set of functions I defined. | |
| Aug 14, 2017 at 18:11 | comment | added | Noah Schweber | @PyRulez Incidentally, re: things that don't really have Turing degrees even though they can be studied computability-theoretically, you should check out [computable structure theory](). Given a (countable, although there are ways around this) structure $\mathfrak{S}$, call the spectrum of $\mathfrak{S}$ the set of Turing degrees which compute copies of $\mathfrak{S}$ (this isn't quite the usual definition but meh, they're equivalent in all nontrivial cases). We can imagine defining the Turing degree of $\mathfrak{S}$ as the least degree in $Spec(\mathfrak{S})$, but it turns out this breaks: | |
| Aug 14, 2017 at 18:09 | comment | added | Christopher King | @NoahSchweber I don't think so right now. | |
| Aug 14, 2017 at 18:08 | comment | added | Noah Schweber | @PyRulez I think this is a really interesting question, so I want to come back and check: do you have any further questions around this? If so, I'd be happy to (try to) answer them. | |
| Jul 29, 2017 at 16:50 | comment | added | Noah Schweber | @AndreasBlass I am indeed interested in that paper! (Currently I'm trying to get deeper into higher type computability - mostly a la Kleene - so I'm always happy to be pointed towards more sources.) | |
| Jul 29, 2017 at 16:29 | comment | added | Andreas Blass | Self-promotion: In connection with Kleene degrees, you might be interested in an ancient paper of mine on these degrees for the case of ultrafiters. The publication information (from MathSciNet) is: MR0820773 (87f:03129) Blass, Andreas(1-MI) Kleene degrees of ultrafilters. Recursion theory week (Oberwolfach, 1984), 29–48, Lecture Notes in Math., 1141, Springer, Berlin, 1985. | |
| Jul 29, 2017 at 1:42 | history | edited | Noah Schweber | CC BY-SA 3.0 |
edited body
|
| Jul 28, 2017 at 20:54 | history | edited | Noah Schweber | CC BY-SA 3.0 |
added 1150 characters in body
|
| Jul 28, 2017 at 20:43 | comment | added | Noah Schweber | @PyRulez Yes, that's right. But note that $\mathcal{U}({\bf 0})$ is not a Turing degree - rather, it's a Scott set. In particular, there is no Turing-maximal element of $\mathcal{U}({\bf 0})$ - in fact, we can uniformly find, for each computable $X$, a computable $Y$ such that $\mathcal{U}(X)<_T\mathcal{U}(Y)$ for every nonprincipal ultrafilter $\mathcal{U}$! | |
| Jul 28, 2017 at 20:42 | history | edited | Noah Schweber | CC BY-SA 3.0 |
added 1150 characters in body
|
| Jul 28, 2017 at 20:41 | comment | added | Christopher King | So would $U(0)$ be the Turing degree associated with $U$, according to the definition in my question? | |
| Jul 28, 2017 at 20:29 | history | edited | Noah Schweber | CC BY-SA 3.0 |
added 1150 characters in body
|
| Jul 28, 2017 at 20:24 | history | answered | Noah Schweber | CC BY-SA 3.0 |