On definable filters in computably enumerable degrees

DOI10.1016/J.APAL.2007.03.003MaRDI QIDQ2370372zbMATH OpenOpenAlexFDO

Authors Wei Wang, Decheng Ding

Publication date 25 June 2007

Published in Annals of Pure and Applied Logic (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.apal.2007.03.003

zbMATH Keywords

computably enumerable degreesdefinable filters

Mathematics Subject Classification ID

Recursively (computably) enumerable sets and degrees (03D25)

Review text

Shore had posed the problem of the existence of (naturally) definable filters in the structure of c.e. degrees, other than the known example of \textbf{NC}, the set of noncappable c.e. degrees. He also posed a parallel question regarding ideals, which Nies subsequently addressed. The present paper adapts Nies' results to show that filters generated by definable sets are themselves definable. In particular, let \({\mathcal F}_1\) denote the filter generated by the set of c.e. degrees that can be cupped to \({\mathbf 0'}\) by a cappable degree, and let \({\mathcal F}_2\) denote the filter generated by the set of Lachlan-Harrington nonsplitting bases. Then \({\mathcal F}_1\) and \({\mathcal F}_2\) are definable. The authors prove that \({\mathcal F}_1\), \({\mathcal F}_2\), and indeed the filter generated by their union are proper subfilters of~\textbf{NC}. They further show that \({\mathcal F}_1\not\subseteq{\mathcal F}_2\), leaving the possibility of \({\mathcal F}_2\subset{\mathcal F}_1\) as an open question.

Recommendations

• On the definable ideal generated by nonbounding c.e. degrees
• Definable Filters in the Structure of Bounded Turing Reductions
• scientific article; zbMATH DE number 1531930
• On the definable ideal generated by the plus cupping c.e. degrees
• Computably enumerable sets and related issues

Cites work

• A recursively enumerable degree which will not split over all lesser ones
• An Algebraic Decomposition of the Recursively Enumerable Degrees and the Coincidence of Several Degree Classes with the Promptly Simple Degrees
• An extension of the nondiamond theorem in classical and α-recursion theory
• Generalized nonsplitting in the recursively enumerable degrees
• scientific article; zbMATH DE number 4091484 (Why is no real title available?)
• scientific article; zbMATH DE number 3598539 (Why is no real title available?)
• scientific article; zbMATH DE number 1531934 (Why is no real title available?)
• scientific article; zbMATH DE number 218585 (Why is no real title available?)
• Interpolation and embedding in the recursively enumerable degrees
• Lattice Embeddings into the R.E. Degrees Preserving 0 and 1
• On the definable ideal generated by nonbounding c.e. degrees
• On the definable ideal generated by the plus cupping c.e. degrees
• PARAMETER DEFINABILITY IN THE RECURSIVELY ENUMERABLE DEGREES

Cited in

(4)

• Definable Filters in the Structure of Bounded Turing Reductions
• scientific article; zbMATH DE number 3895052 (Why is no real title available?)
• On the filter of computably enumerable supersets of an r-maximal set
• Computably enumerable sets and related issues

This page was built for publication: On definable filters in computably enumerable degrees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2370372)