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}$.

A Minimal Pair of Turing Degrees

CINTIOLI, Patrizio
2014-01-01

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}$.
2014
262
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11581/301981
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus ND
  • ???jsp.display-item.citation.isi??? ND
social impact