Questions tagged [arithmetic-degree]
Use to describe questions about the structure of the arithmetic degrees (subsets of N under the relation of relative arithmetic definability) as used in higher computability theory.
11 questions
2
votes
0
answers
102
views
Direct construction of an arithmetically high degree below $0^{(\omega)}$
The existence of a high arithmetic degree (meaning the degrees induced by the notion of relative arithmetic definability) below $0^\omega$ can be established by using Harrington/Simpson's ...
6
votes
1
answer
1k
views
Degree of the preimage of a variety
Let $V\subset \mathbb{A}^m$ and $W\subset \mathbb{A}^n$ be affine varieties defined over an arbitrary field. Let $f:V\to \mathbb{A}^n$ be a morphism given by polynomials of degree $\leq D$.
Is it true ...
6
votes
3
answers
444
views
Is $0^{(\omega)}$ a minimal cover in the arithmetic degrees
Is it known if $0^{(\omega)}$ a minimal cover in the arithmetic degrees? In the Turing degrees to show that $0'$ (indeed $0^{(n)}$) isn't a minimal cover one uses the density of r.e. degrees. ...
4
votes
1
answer
71
views
Effectively non-arithmetic $\omega$-REA degrees
Say that a function $f \in \omega^\omega$ witnesses that an $\omega$-REA set $A = \bigoplus_{i \in \omega} A^{[i]}$ is non-arithmetic if $A^{[\leq f(n)]} \not\leq_T 0^n$. Say that $A$ is effectively ...
1
vote
0
answers
48
views
Is $0^{\omega}$ a minimal cover of a minimal arithmetic degree?
Is there a minimal arithmetic degree $d <_a 0^{\omega}$ such that $0^{\omega}$ is a minimal cover of $d$ in the arithmetic degrees? [1]
While whether or not $0^{\omega}$ is a minimal cover at all (...
1
vote
0
answers
37
views
Are the $\omega$-generic arithmetic degrees downward closed
A degree is $\alpha$-generic if it has representative that is $\alpha$-generic. Are the $\omega$-generic arithmetic degrees (i.e. the degree structure induced by arithmetic reproducibility) downward ...
3
votes
1
answer
92
views
Does every arithmetic degree below $0^\omega$ have a representative computable in $0^\omega$?
Suppose that $A \leq_a 0^\omega$ (i.e. $A$ is arithmetic in $0^\omega$) does there exist $\widehat{A} \equiv_a A$ with $\widehat{A} \leq_T 0^\omega$ [1]?
More generally, say that a set $X$ is aT-...
2
votes
1
answer
123
views
Arithmetically-hyperimmune-free degrees are comeager
I think proposition XIII.1.22 of Odifreddi is false but I wanted to check I wasn't being dumb. Here's the claim.
Definition: The set$^1$ $A$ is arithmetically-hyperimmune-free if every function $f$ ...
1
vote
0
answers
44
views
Base of cone of arithmetic minimal covers
By Borel determinacy (exercisce XIII.1.7 in Odifreddi) there is a cone of minimal covers in the arithmetic degrees. Is the base of such a cone known? A minimal such base?
For that matter, is it even ...
1
vote
0
answers
43
views
No arithmetic degree that always joins to arithmetic minimal cover
Is there (I strongly presume not but not seeing how to show it) a (non-zero) arithmetic degree $a$ such that for all arithmetic degrees $e \not\geq_a a$ we have $e \oplus a$ is a minimal cover of $e$ ...
7
votes
0
answers
221
views
$\Pi^0_2$ singleton of minimal arithmetic degree?
Is it known if there is a $\Pi^0_2$ singleton of minimal arithmetic degree?
To elaborate a bit, this is asking whether there is a non-arithmetic set $X$ such that for any $Y$ arithmetic in $X$ either ...