On minimal pairs of quasi-degrees
Abstract In this article, we prove the following results: (i) If c.e. $Q_{1}$-degrees $\textbf{a}$ and $\textbf{b}$ form a minimal pair in the c.e. $Q_{1}$-degrees, then $\textbf{a}$ and $\textbf{b}$ form a minimal pair in the $\varSigma _{2}^{0}$ $Q_{1}$-degrees. (ii) If c.e. $sQ$- ($sQ_{1}$-) degrees $\textbf{a}$ and $\textbf{b}$ form a minimal pair in the c.e. $sQ$- ($sQ_{1}$-) degrees, then $\textbf{a}$ and $\textbf{b}$ form a minimal pair in the $sQ$- ($sQ_{1}$-) degrees. (iii) Let $B$ be a nowhere simple set, then: (1) If $A$ is a simple set, then $\textbf{deg}_{bQ_{1}}(A\oplus B)$ contains neither simple nor nowhere simple set. (2) If $A$ is a hypersimple set, then $\textbf{deg}_{sQ_{1}}(A\oplus B)$ contains neither hypersimple nor nowhere simple set. (3) If $A$ is a hyperhypersimple set, then $\textbf{deg}_{Q_{1}}(A\oplus B)$ contains neither hyperhypersimple nor nowhere simple set. (iv) Let $A$ be a nowhere simple set, then: (1) If $B$ is a simple set, then $\textbf{deg}_{bQ_{1}}(A)$ and $\textbf{deg}_{bQ_{1}}(B)$ form a minimal pair in the c.e. $bQ_{1}$-degrees. (2) If $B$ is a hypersimple set, then $\textbf{deg}_{sQ_{1}}(A)$ and $\textbf{deg}_{sQ_{1}}(B)$ form a minimal pair in the c.e. $sQ_{1}$-degrees. (3) If $B$ is a hyperhypersimple set, then $\textbf{deg}_{Q_{1}}(A)$ and $\textbf{deg}_{Q_{1}}(B)$ form a minimal pair in the c.e. $Q_{1}$-degrees. (v) (1) Every high c.e. $T$-degree contains c.e. sets $A$ and $B$ such that $\textbf{deg}_{Q_{1}}(A)$ and $\textbf{deg}_{Q_{1}}(B)$ form a minimal pair in the c.e. $Q_{1}$-degrees. (2) Every noncomputable c.e $T$-degree contains c.e. sets $A$ and $B$ such that $\textbf{deg}_{sQ_{1}}(A)$ and $\textbf{deg}_{sQ_{1}}(B)$ form a minimal pair in the c.e. $sQ_{1}$-degrees. (3) Every noncomputable c.e $wtt$-degree contains c.e. sets $A$ and $B$ such that $\textbf{deg}_{bQ_{1}}(A)$ and $\textbf{deg}_{bQ_{1}}(B)$ form a minimal pair in the c.e. $bQ_{1}$-degrees.
Authors
- Irakli Chitaia
- R. Sh. Omanadze (ORCID: https://orcid.org/0000-0002-0215-7912)
Institutions
- Tbilisi State University (GE)
Publication Details
- Journal
- Logic Journal of IGPL
- Published
- 2025-09-27
- DOI
- https://doi.org/10.1093/jigpal/jzaf072
- Primary Topic
- Computability, Logic, AI Algorithms
- Type
- article
- Field-Weighted Citation Impact
- 0.00