A Minimal Pair of Turing Degrees

Patrizio Cintioli

Abstract


Let $P(A)$ be the following property, where $A$ is any infinite set of natural numbers:
\begin{displaymath}
(\forall X)[X\subseteq A\wedge |A-X|=\infty\Rightarrow A\not\le_m X].
\end{displaymath}
Let $({\bf R}, \le)$ be the partial ordering of all the r.e. Turing degrees. We propose the study of the order theoretic properties of the substructure $({\bf S}_{m},\le_{{\bf S}_m})$, where ${\bf S}_{m}=_{\rm dfn}\{{\bf a}\in {\bf R}$: ${\bf a}$ contains an infinite set $A$ such that P(A) is true$\}$, and $\le_{{\bf S}_m}$ is the restriction of $\le$ to ${\bf S}_m$.
In this paper we start by studying the existence of minimal pairs in ${\bf S}_{m}$.

Full Text: PDF DOI: 10.5539/jmr.v6n1p76

Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.

Journal of Mathematics Research   ISSN 1916-9795 (Print)   ISSN 1916-9809 (Online)

Copyright © Canadian Center of Science and Education

To make sure that you can receive messages from us, please add the 'ccsenet.org' domain to your e-mail 'safe list'. If you do not receive e-mail in your 'inbox', check your 'bulk mail' or 'junk mail' folders.