New answers tagged

0 votes

$\Pi^0_2$ singleton of minimal arithmetic degree?

Less an answer than a potential sketch at an approach right now but I wanted to put it up here just in case it was right (but it's way too simple to be right) Let $A$ be a non-arithmetic $\Pi^0_2$ ...
user avatar
  • 1,515
0 votes

How large is the supremum of halting times of Infinite Time Turing Machines, assuming that halting times are bounded and inputs are arbitrary?

This and related questions about decision times of ITTMs are addressed in this paper: "Decision times of infinite computations" https://arxiv.org/abs/2011.04942 The ordinal you are asking ...
user avatar
  • 1
7 votes

Does permission always work?

Dan's answer is very nice and should be the accepted answer. However, I thought it might be worth pointing out that there's a much easier counterexample to your first question (with the stricter ...
user avatar
9 votes
Accepted

Does permission always work?

No, there is a counterexample. The idea is that the use of the computation $X \le_T ran(g)$ can be much worse than identity, and since we only care about the reduction in one direction, we can drive ...
user avatar
  • 2,159
3 votes
Accepted

Existence of an inseparable minimal pair

Here's a construction of a computably inseparable minimal pair. I believe that it is not hard to modify this construction to give c.e. sets by using a priority construction. However, I have not ...
user avatar
8 votes
Accepted

How often are forcing extensions of countable computably saturated models of $\mathsf{ZFC}$ computably saturated?

The answer to Question 1 is positive (thus the answer to Question 2 is also positive). More explicitly, the positive answer to Question 1 follows from the following well-known facts: Lemma 1. $(M,\...
user avatar
  • 14.5k
4 votes

Comprehension axiom who helps in the opposite direction

There are many such examples in higher-order Reverse Mathematics. I discuss a couple and indicate a relevant paper of mine related to David's. As usual, let RCA$_0^\omega$ be Kohlenbach's base theory ...
user avatar
  • 1,859
9 votes
Accepted

Comprehension axiom who helps in the opposite direction

David Belanger's work is relevant. The principle $\mathsf{WKL_0}$ (= "Every infinite subtree of $2^{<\omega}$ has an infinite path") is not literally a comprehension principle, so its ...
user avatar
1 vote
Accepted

Natural strong logic with Barwise compactness property

A very nice family of examples is provided by Harrington's 1980 paper Extensions of countable infinitary logic which preserve most of its nice properties. Harrington shows that if we expand $\mathcal{...
user avatar

Top 50 recent answers are included