Skip to main content

All Questions

Filter by
Sorted by
Tagged with
5 votes
0 answers
158 views

If $\omega_1$ is not inaccessible in $L$, how hard can it be to find a non-measurable $\Sigma^1_3$ set of reals?

In his wonderfully titled paper Can you take Solovay's inaccessible away? Shelah showed that if every $\mathbf{\Sigma}^1_3$ set of reals is Lebesgue measurable, then $\omega_1$ is an inaccessible ...
James E Hanson's user avatar
2 votes
1 answer
161 views

Are Cohen Generics Minimal Covers?

Are Cohen generics (in $2^\omega$) minimal covers? I'm ultimately interested in this question for some more effective notion of forcing but I realized I wasn't sure how to show this even assuming full ...
Peter Gerdes's user avatar
  • 3,029
1 vote
0 answers
108 views

Name For Effective Cantor-Bendixsonish Derivitive

When dealing with a tree (substring closed subset of $\omega^{< \omega})$ a useful operation will frequently be to remove any nodes with finite ordinal rank (i.e., all nodes whose extensions on the ...
Peter Gerdes's user avatar
  • 3,029
2 votes
0 answers
118 views

Uniformization and functions on Turing degrees

Assuming Martin's Conjecture on functions between Turing degrees, is AD + DC consistent with existence of an $f:\mathcal{D}_t → \mathcal{D}_t$ of rank $Θ$ ? $\mathcal{D}_t$ is the set of Turing ...
Dmytro Taranovsky's user avatar
4 votes
3 answers
406 views

Hyperarithmetically least elements in $\Pi^1_1$ sets

My question is: Do we have a hyperarithmetically $\le_H$-least real in any $\Pi^1_1$ set? That is Question. Suppose that $A$ is a non-empty $\Pi^1_1$ set. Then can we find a real $a\in A$ such that $...
Hanul Jeon's user avatar
  • 3,042
3 votes
1 answer
134 views

A $\Pi^0_1$ class of $\alpha$-subgenerics for all $\alpha < w_1^{CK}$

In Harrington's mimeographed notes (see here) solving McLaughlin's conjecture he builds reals $f \in \omega^\omega$ which have the property of being $\alpha$-subgeneric defined as follows. He does ...
Peter Gerdes's user avatar
  • 3,029
1 vote
1 answer
98 views

Intersection of (relativized/preimage) measure 0 with every hyperarithmetic perfect set

Given a perfect tree $T$ on $2^{<\omega}$ viewed as a function from $2^{<\omega}$ to $2^{<\omega}$ define the measure of a subset of $[T]$ to be the measure of it's preimage under the usual ...
Peter Gerdes's user avatar
  • 3,029
4 votes
1 answer
533 views

Complexity of |a| < |b| for ordinal notations?

What is the complexity (e.g. is it $\Sigma^0_1$, arithmetic, fully $\Pi^1_1$) of the relation $|a| < |b|$ given two notations $a, b \in \mathscr{O}$ (Kleene's O)? What about the case where only one ...
Peter Gerdes's user avatar
  • 3,029
2 votes
1 answer
118 views

$\Pi^0_2$ singleton forming minimal pair with $0''$

Is there a $\Pi^0_2$ singleton that forms a minimal pair with $0''$? That is, is there a set $X$ such that $X$ is the unique solution to $\forall x \exists y \phi(X|_y, x)$, $X$ and $0''$ are ...
Peter Gerdes's user avatar
  • 3,029
4 votes
1 answer
142 views

Does the set of infinite random strings satisfy an analogue of immune sets?

Let $K(x)$ denote the Kolmogorov complexity of a finite binary string $x$. A finite binary string $x$ is called Kolmogorov random if $K(x) \geq |x|$. And an infinite binary sequence is called Martin-...
Keshav Srinivasan's user avatar
6 votes
0 answers
117 views

Reverse mathematics of Banach-Mazur games

Given $\mathcal{A}\subseteq\omega^\omega$, the Banach-Mazur game with payoff set $\mathcal{A}$ consists of players $1$ and $2$ alternately playing nonempty finite strings of naturals with player $1$ ...
Noah Schweber's user avatar
6 votes
0 answers
151 views

Complexity of constructive arithmetical truth vs second order arithmetic

Let us say that an arithmetic statement is constructively true iff it is realized by a computable function under Kleene's function realizability. Does the set of constructively true (first order) ...
Dmytro Taranovsky's user avatar
3 votes
0 answers
203 views

Set-theoretic hierarchy using the uniqueness quantification

Has an equivalent of the set-theoretic hierarchies (arithmetical, hyperarithmetical, Levy etc.) that uses the uniqueness quantification, $\exists !$ (and its dual, $\neg\exists!\neg$) been studied ...
Johan's user avatar
  • 531
7 votes
0 answers
304 views

Which countable ordinals are "Barwise compact" for $\mathcal{L}_{\infty,\omega_1}$?

Barwise compactness says (as a special case) that whenever $\alpha$ is countable and admissible, $T\subseteq\mathcal{L}_{\infty,\omega}\cap L_\alpha$ is $\alpha$-c.e., and every subset of $T$ which is ...
Noah Schweber's user avatar
7 votes
0 answers
471 views

Infinite time Turing machines, semi-decidable sets and descriptive set theory

Definition A set of reals $A$ is said to be ittm-eventually-semi-decidable if there is an Infinite Time Turing Machine programme $P_e$ so that $x\in A$ iff $P_e(x)$ has converged on “1” on its ...
Philip Welch's user avatar
  • 4,839
3 votes
0 answers
223 views

Bimodal determinacy logic for Borel games

This question is intended to be a first step towards answering this old question of mine. Let $K$ be the set of pairs $(\Sigma,\Pi)$ of quasistrategies, in the usual sense of games on $\omega$, for ...
Noah Schweber's user avatar
2 votes
0 answers
258 views

Can we have a "very strong" cone phenomenon in the Turing degrees (and a related question)?

By Borel determinacy + Martin's cone theorem, for every countable fragment $\mathcal{A}$ of $\mathcal{L}_{\omega_1,\omega}$ there is a turing degree ${\bf c}$ such that for all ${\bf d}\ge_T{\bf c}$ ...
Noah Schweber's user avatar
8 votes
1 answer
514 views

How big is the least non-$\Sigma^1_1$-pointwise-definable ordinal?

There's a large countable ordinal which has cropped up (as a lower bound!) in a computable structure theory problem I'm playing with. At present I don't really understand how big it is, and I'm ...
Noah Schweber's user avatar
9 votes
1 answer
495 views

Can two versions of $\omega_1^{CK}(\mathsf{Ord})$ ever coincide?

The goal of this question is to fill in the gap in this old answer of mine. For a transitive set $M$, thought of as an $\{\in\}$-structure, we define the following ordinals (this is not the notation ...
Noah Schweber's user avatar
10 votes
1 answer
287 views

Complexity of the set of models of TA

Recall that the theory of true arithmetic $TA$ is the theory of standard model of arithmetic $\mathcal N$. I am interested in the complexity of the set of countable models of $TA$ in the lightface or ...
Dino Rossegger's user avatar
9 votes
1 answer
610 views

Does every cofinal branch through Kleene's O compute true arithmetic?

My question concerns cofinal branches through Kleene's $O$, which is a set of natural numbers and a computably enumerable relation $<_O$ on this set that provides ordinal denotations for any ...
Joel David Hamkins's user avatar
4 votes
0 answers
177 views

When is validity definable in $L_\alpha$?

Below, $\alpha$ is a countable p.r.-closed ordinal $>\omega$. Let $\mathcal{L}_\alpha=\mathcal{L}_{\infty,\omega}\cap L_\alpha$ (note that this is not the same as $\mathcal{L}_{\omega_1,\omega}\...
Noah Schweber's user avatar
2 votes
1 answer
184 views

Detecting comprehension topologically

This question basically follows this earlier question of mine but shifting from standard systems of nonstandard models of $PA$ to $\omega$-models of $RCA_0$. For $X$ a Turing ideal we get the map $c_X$...
Noah Schweber's user avatar
0 votes
1 answer
87 views

Kurtz randomness and supermartingales with infinite *limit*

Suppose you replace the usual success conditions for a supermartingale (lim sup is infinite) with the requirement that the actual limit is infinite, e.g. a supermartingale $B$ succeeds on $X \in 2^\...
Peter Gerdes's user avatar
  • 3,029
7 votes
1 answer
490 views

"Robinson arithmetic" for (some) levels of $L$?

I'll write "$\mathcal{L}_\alpha$" for the fragment $\mathcal{L}_{\infty,\omega}\cap L_\alpha$. Say that a countable admissible $\alpha$ is Robinsonian if there is some sentence $\varphi\in\mathcal{L}...
Noah Schweber's user avatar
6 votes
1 answer
503 views

Regularity properties of Turing-invariant and arbitrary sets of reals

The question whether Turing determinacy implies $AD$ is a well-known open problem. I was wondering if anything is known about the following analogous question: Let $\Gamma$ be a regularity property (...
Haim's user avatar
  • 391
5 votes
0 answers
196 views

A slight extension of Sacks theorem

Sacks proves the following theorem first. Theorem 1: If $\alpha$ is a countable admissible ordinal, then there is a real $x$ so that $\omega_1^x=\alpha$. Anyone knows who proves the following ...
喻 良's user avatar
  • 4,201
7 votes
1 answer
303 views

Variously pointed closed sets

A tree $A\subseteq \omega^{<\omega}$ - possibly with dead ends - is pointed iff every path $p\in[A]$ has $p\ge_TA$. This lifts to two distinct notions of pointedness for closed sets in Baire space: ...
Noah Schweber's user avatar
6 votes
0 answers
806 views

A strong plus-one hypothesis

To make this more easily readable, I'll start with the question and then give the explanation/motivation. Question. Is the following principle (or its weakening, with "for every real $r$" ...
Noah Schweber's user avatar
7 votes
0 answers
284 views

Co-cones in the Turing degrees

Let the cocone of a Turing degree ${\bf d}$ be the set $cc({\bf d}):\{{\bf c}: {\bf c}\not\ge_T {\bf d}\}$. I'm curious what's known about the various partial orders (isomorphic to ones) of the form $...
Noah Schweber's user avatar
9 votes
1 answer
739 views

Can the Turing degrees be linearly ordered?

Assuming the axiom of choice, every set can be linearly (indeed, well-) ordered. However, without choice this can fail, as witnessed most drastically by the consistency of amorphous sets. More ...
Noah Schweber's user avatar
5 votes
1 answer
292 views

A game with boldface strength

This is a problem which has been bothering me for a while now; it doesn't seem inherently too hard, but I haven't been able to make any real headway, so I'm putting it out in the open since at this ...
Noah Schweber's user avatar
15 votes
1 answer
616 views

Does Kechris' conjecture contradict both parts of Martin's conjecture, or just part 1?

By Kechris' conjecture (KC) I mean the assertion that Turing equivalence $\equiv_T$ is a universal countable Borel equivalence relation. On the other hand, Martin's conjecture (MC) is a long-lasting ...
V. Bard's user avatar
  • 151
6 votes
1 answer
433 views

Reference request: a version of $\Sigma^1_1$ bounding for structures

There's a (fairly basic) fact I want to use in a paper I'm writing; it's not entirely trivial, so I don't feel comfortable just stating the result and moving on, but I don't have a citation for it. ...
Noah Schweber's user avatar
8 votes
0 answers
451 views

The cone property in the enumeration degrees

A Borel partial order is the partial order corresponding to a Borel preorder of some Polish space. For example, the Turing and enumeration degrees, $\mathcal{D}$ and $\mathcal{E}$ respectively, are ...
Noah Schweber's user avatar
8 votes
1 answer
432 views

Which reals are "hyperarithmetic modulo ordinals"?

The context for this question is the theory ZFC + a measurable cardinal, although answers not in this context would also be interesting to me. In a project I'm working on, the following class of ...
Noah Schweber's user avatar
9 votes
0 answers
471 views

(A little bit) Beyond the E-recursive

The E-recursive functions are a particular generalization of classical recursion theory to the entire set-theoretic universe, $V$. They are defined via a schemes: see Sacks' $E$-recursive intuitions. ...
Noah Schweber's user avatar
14 votes
2 answers
719 views

Woodin on Posner-Robinson for the hyperjump and sharp

The Posner-Robinson theorem states that, if $X$ is noncomputable, there is some $G$ such that $X\oplus G=G'$; that is, even though genuine jump inversion only works above $0'$, every (nontrivial) $X$ ...
Noah Schweber's user avatar
10 votes
1 answer
411 views

The least admissible above a dominating real

Let $\mathbb{P}$ be the usual forcing which adds a dominating real: conditions in $\mathbb{P}$ are pairs $(p, f)$ with $p:\omega\rightarrow\omega$ finite partial and $f:\omega\rightarrow\omega$ total, ...
Noah Schweber's user avatar
2 votes
2 answers
245 views

Precise interpretability strength of $\mathcal P_{DF}(\omega)$ and $L_{\omega_1^{CK}}$

I am curious about the relationship between the definable power set of $\omega$ and the $\omega_1^{CK}$th level of the constructible sets $L$. In short, $\omega_1^{CK}$ is the least nonrecursive ...
tww's user avatar
  • 29
7 votes
2 answers
657 views

Topological tameness beyond the Gandy-Harrington topology

The Gandy-Harrington topology on $\omega^\omega$ is the topology generated by all lightface $\Sigma^1_1$ sets; that is, all sets which are continuous-in-the-usual-sense images of $\omega^\omega$. ...
Noah Schweber's user avatar
6 votes
1 answer
259 views

Degree of unsolvability of finding a open approximation to a Borel set, given its Borel code

It is well known that every Borel set has the property of Baire. That is, for every Borel set $B$, there is an open set $U$ and a sequence of dense open sets $D_n$ such that for every $x\in \cap_n ...
Linda Brown Westrick's user avatar
14 votes
2 answers
1k views

Does Turing determinacy imply full determinacy?

The axiom of Turing determinacy is a weakening of the full axiom of determinacy, $AD$, in which only games with payoff sets which are $\equiv_T$-invariant are demanded to be determined. In "...
Noah Schweber's user avatar
15 votes
1 answer
1k views

Higher recursion theory and reverse mathematics: What is to $\Pi^1_1$-$CA_0$ as $RCA_0$ is to $ACA_0$?

There is an extremely rich and well-understood analogy between "recursively enumerable" and "$\Pi^1_1$" – indeed, this is the starting point of metarecursion theory, and $\alpha$-...
Noah Schweber's user avatar
11 votes
1 answer
441 views

Concerning Silver's result

Jack Silver proved that if $x$ is a real so that every $x$-admissible ordinal is a cardinal in $L$, then $0^{\sharp}$ exists. I wonder whether various weaker or stronger versions of Silver's result ...
喻 良's user avatar
  • 4,201
7 votes
1 answer
1k views

Is the equivalence between a $\Sigma^0_1$ and a $\Pi^0_1$ formula defining the same recursive set provable in a sufficiently strong arithmetic ?

Let $A$ be a recursive set. $A$ is recursively enumerable, so $A$ may be defined by a $\Sigma^0_1$ formula, i.e. by $\exists \overrightarrow{a} \phi (\overrightarrow{a}, n)$, where $\phi$ contains no ...
Dabs's user avatar
  • 73
32 votes
1 answer
2k views

Godel on recursion-theoretic hierarchies

At the end of his excellent article, "The Emergence of Descriptive Set Theory" (http://math.bu.edu/people/aki/2.pdf), Kanamori writes: "Another mathematical eternal return: Toward the end of his ...
Noah Schweber's user avatar
4 votes
1 answer
319 views

Complexity of winning strategies for open games (for open player)

If $G\subseteq\omega^{<\omega}$ is a computable clopen game, then $G$ has a winning strategy which is hyperarithmetic $(\Delta^1_1)$, by an inductive ranking process. The key observation here is ...
Noah Schweber's user avatar
5 votes
1 answer
231 views

When do substructures have computable copies?

Say that a class $\mathcal{C}$ of countable first-order structures in some finite signature has the effective substructure property if $\mathcal{C}$ is closed under isomorphism and whenever $A\in \...
Noah Schweber's user avatar
9 votes
1 answer
334 views

Ensuring nonempty lightface Borel sets have elements via theories of second-order arithmetic

This question is an outgrowth of this MathSE question: https://math.stackexchange.com/questions/276068/members-of-lightface-borel-sets. A Borel set $X\subseteq 2^\omega$ is a member of the smallest ...
Noah Schweber's user avatar