Yeah, there's a sort of trick here. The natural question is uniform--we want a single reduction that can work from any consistent guessing oracle, and we think it would be cheating to do different things with different oracles. But this doesn't matter for the solution, since we produce a single consistent guessing oracle that can't be reduced to the halting problem.
This reminds me of the theory of enumeration degrees, a generalization of Turing degrees allowing open-set-flavoured behaviour like we see in partial recursive functions; if the answer to an oracle query is positive, the oracle must eventually tell you, but if the answer is negative it keeps you waiting indefinitely. I find the theory of enumeration degrees to be underemphasized in discussion of computability theory, but e.g. Odifreddi has a chapter on it all the way at the end of Classical Recursion Theory Volume II.
The consistent guessing problem isn't a problem about enumeration degrees. It's using a stronger kind of uniformity--we want to be uniform over oracles that differently guess consistently, not over a set of ways to give the some answers, but to present them differently. But there is again a kind of strangeness in the behaviour of uniformity, since we get equivalent notions if we do or do not ask that a reduction between sets , be a single function that uniformly enumerates from enumerations of , so there might be some common idea here. More generally, enumeration degrees feel like they let us express more naturally things that are a bit awkward to say in terms of Turing degrees--it's natural to think about the set of computations that are enumerable/ in a set--so it might be a useful keyword.
Note that Andy Drucker is not claiming to have discovered this; the paper you link is expository.
Since Drucker doesn't say this in the link, I'll mention that the objects you're discussing are conventionally know as PA degrees. The PA here stands for Peano arithmetic; a Turing degree solves the consistent guessing problem iff it computes some model of PA. This name may be a little misleading, in that PA isn't really special here. A Turing degree computes some model of PA iff it computes some model of ZFC, or more generally any theory capable of expressing arithmetic.
Drucker also doesn't mention the name of the theorem that this result is a special case of: the low basis theorem. "Low" here suggests low computability strength. Explicitly, a Turing degree is low if solving the halting problem for machines with an oracle for is equivalent (in the sense of reductions) to solving the halting problem for Turing machines without any oracle. The low basis theorem says that every computable binary tree has a low path. We are able to apply the theorem to this problem, concluding that there is a consistent guessing oracle which is low. So, we cannot use this oracle to solve the halting problem; if we could, then an oracle machine with access to would be at least as strong as an oracle machine with access to the halting set, but we know that the halting set suffices to compute the halting problem for such a machine, which is a contradiction.
Various other things are known about PA degrees, though I'm not sure what might be of interest to you or others here. This stuff is discussed in books on computability theory, like Robert Soare's Computability Theory and Applications. Though, I thought I learned about PA degrees from his earlier book, but now I don't see them in there, so maybe I just learned about PA degrees around the same time, possibly following my interest in your and others' work on reflective oracles. The basics of computability theory--Turing degrees, the Turing jump, and the arithmetic hierarchy in the computability sense--may be of interest to the extent there is anything there that you're not already familiar with. With regard to PA degrees, in particular people like to talk about diagonally nonrecursive functions. This works as follows. Let denote the th partial computable function according to some Goedel numbering. The PA degrees are exactly the Turing degrees that compute functions such that for all numbers at which the right-hand side is defined. This is suggestive of the ideas around reflective oracles, the Lawvere fixed-point theorem, etc. But I wouldn't say that when I think about these things, I think of them in terms of diagonally nonrecursive functions; plausibly that's not an interesting direction to point people in.
Q5 is true if (as you assumed), the space of lotteries is the space of distributions over a finite set. (For a general convex set, you can get long-line phenomena.)
First, without proof, I'll state the following generalization.
Theorem 1. Let be a relation on a convex space satisfying axioms A1, A2, A3, and the following additional continuity axiom. For all , the set
is open in . Then, there exists a function from to the long line such that iff .
The proof is not too different, but simpler, if we also assume A4. In particular, we no longer need the extra continuity axiom, and we get a stronger conclusion. Nate sketched part of the proof of this already, but I want to be clearer about what is stated and skip fewer steps. In particular, I'm not sure how Nate's hypotheses rule out examples that require long-line-valued functions—maybe he's assuming that the domain of the preference relation is a finite-dimensional simplex like I am, but none of his arguments use this explicitly.
Theorem 2. Let be a relation on a finite-dimensional simplex satisfying axioms A1-A4. Then, there is a quasiconcave function such that iff .
First, I'll set up some definitions and a lemma. For any lotteries , , let denote the line segment
We say that preferences are increasing along a line segment if whenever , we have
We will also use open and half-open interval notation in the corresponding way.
Lemma. Let be a preference relation on a finite-dimensional simplex satisfying axioms A1-A4. Then, there are -minimal and -maximal elements in .
Proof. First, we show that there is a minimal element. Axiom A4 states that for any mixture , either or . By induction, it follows more generally that any convex combination C of finitely many elements satisfies for some . But every element is a convex combination of the vertices of , so some vertex of is -minimal.
The proof that there is a maximal element is more complex. Consider the family of sets
This is a prefilter, so since is compact ( here carries the Euclidean metric), it has a cluster point . Either will be a maximal element, or we will find some other maximal element. In particular, take any . We are done if is a maximal element; otherwise, pick . By the construction of , for every , we can pick some within a distance of from B. Now, if we show that itself satisfies , it will follow that is maximal.
The idea is to pass from our sequence , with limit , to another sequence lying on a line segment with endpoint . We can use axiom A4, which is a kind of convexity, to control the preference relation on convex combinations of our points , so these are the points that we will construct along a line segment. Once we have this line segment, we can finish by using A3, which is a kind of continuity restricted to line segments, to control itself.
Let be the set of lotteries in the affine span of the set . Then, if we take some index set such that is a maximal affinely independent tuple, it follows that affinely generates . Hence, the convex combination
i.e. the barycenter of the simplex with vertices at , is in the interior of the convex hull of relative to , so we can pick some such that the -ball around relative to is contained in this simplex.
Now, we will see that every lottery in the set satisfies . For any , pick so that is in the -ball around . Since the tangent vector has length less than , the lottery
is in the -ball around , and it is in , so it is in the simplex with vertices . Then, by A4, and by hypothesis. So, applying A4 again,
Using A4 one more time, it follows that every lottery
satisfies , and hence every lottery .
Now we can finish up. If then, using A3 and the fact that , there would have to be some lottery in that is -equivalent to A, but this would contradict what we just concluded. So, , and so B is -maximal.
Proof of Theorem 2. Let be a -minimal and a -maximal element of . First, we will see that preferences are increasing on , and then we will use this fact to construct a function and show that it has the desired properties. Suppose preferences we not increasing; then, there would be such that is closer to while is closer to , and . Then, would be a convex combination of and , but by the maximality of , contradicting A4.
Now we can construct our utility function using A3; for each -class , we have , so there is some[1] such that
Then, let for all . Since preferences are increasing on , it is immediate that if , then . Conversely, if , we have two cases. If , then , so , and so . Finally, if , then by construction.
Finally, since for all we have iff , it follows immediately that is quasiconcave by A4.
Nate mentions using choice in his answer, but here at least the use of choice is removable. Since is monotone on , the intersection of the -class with is a subinterval of , so we can pick based on the midpoint of that interval
Nice, I like this proof also. Maybe there's a clearer way to say thing, but your "unrolling one step" corresponds to my going from to . We somehow need to "look two possible worlds deep".
Here's a simple Kripke frame proof of Payor's lemma.
Let be a Kripke frame over our language, i.e. is a set of possible worlds, is an accessibility relation, and judges that a sentence holds in a world. Now, suppose for contradiction that but that , i.e. does not hold in some world .
A bit of De Morganing tells us that the hypothesis on is equivalent to , so . So, there is some world with such that . But again looking at our equivalent form for , we see that , so , a contradiction.
Both this proof and the proof in the post are very simple, but at least for me I feel like this proof tells me a bit more about what's going on, or at least tells me something about what's going on that the other doesn't. Though in a broader sense there's a lot I don't know about what's going on in modal fixed points.
Kripke frame-style semantics are helpful for thinking about lots of modal logic things. In particular, there are cool inductiony interpretations of the Gödel/Löb theorems. These are more complicated, but I'd be happy to talk about them sometime.
Well, I guess describing a model of a computably enumerable theory, like PA or ZFC counts. We could also ask for a model of PA that's nonstandard in a particular way that we want, e.g. by asking for a model of PA+¬Con(PA), and that works the same way. Describing a reflective oracle has low solutions too, though this is pretty similar to the consistent guessing problem. Another one, which is really just a restatement of the low basis theorem, but perhaps a more evocative one, is as follows. Suppose some oracle machine T has the property that there is some oracle that would cause it to run forever starting from an empty tape. Then, there is a low such oracle.
(Technically, these aren't decision problems, since they don't tell us what the right decision is, but just give us conditions that whatever decisions we make have to satisfy. I don't know what to say instead; this is more general then e.g. promise problems. Maybe I'd use something like decision-class problems?)
All these have a somewhat similar flavour by the nature of the low basis theorem. We can enumerate a set of constraints, but we can't necessarily compute a single object satisfying all the constraints. But the theorem tells us that there's a low such object.
I don't know what the situation is for subsets of the digits of Chaitin's constant. Can it be as hard as the halting problem? You might try to refute this using some sort of incompressibility idea. Can it be low? I'd expect not, at least for computable subsets of indices of positive density. Plausibly computability theorists know about this stuff. They do like constructing posets of Turing degrees of various shapes, and they know about which shapes can be realized between 0 and the halting degree 0′. (E.g. this paper.)