53 found
Order:
Disambiguations
Theodore A. Slaman [46]Theodore Slaman [20]
  1. On the Strength of Ramsey's Theorem for Pairs.Peter A. Cholak, Carl G. Jockusch & Theodore A. Slaman - 2001 - Journal of Symbolic Logic 66 (1):1-55.
    We study the proof-theoretic strength and effective content of the infinite form of Ramsey's theorem for pairs. Let RT n k denote Ramsey's theorem for k-colorings of n-element sets, and let RT $^n_{ denote (∀ k)RT n k . Our main result on computability is: For any n ≥ 2 and any computable (recursive) k-coloring of the n-element sets of natural numbers, there is an infinite homogeneous set X with X'' ≤ T 0 (n) . Let IΣ n and BΣ (...)
    Direct download (9 more)  
     
    Export citation  
     
    Bookmark   26 citations  
  2. On Extensions of Embeddings Into the Enumeration Degrees of the -Sets.Steffen Lempp, Theodore A. Slaman & Andrea Sorbi - 2005 - Journal of Mathematical Logic 5 (02):247-298.
  3.  15
    Generic Copies of Countable Structures.Chris Ash, Julia Knight, Mark Manasse & Theodore Slaman - 1989 - Annals of Pure and Applied Logic 42 (3):195-205.
  4.  40
    On the Strength of Ramsey's Theorem.David Seetapun & Theodore A. Slaman - 1995 - Notre Dame Journal of Formal Logic 36 (4):570-582.
    We show that, for every partition F of the pairs of natural numbers and for every set C, if C is not recursive in F then there is an infinite set H, such that H is homogeneous for F and C is not recursive in H. We conclude that the formal statement of Ramsey's Theorem for Pairs is not strong enough to prove , the comprehension scheme for arithmetical formulas, within the base theory , the comprehension scheme for recursive formulas. (...)
    Direct download (7 more)  
     
    Export citation  
     
    Bookmark   16 citations  
  5.  2
    The Density of Infima in the Recursively Enumerable Degrees.Theodore A. Slaman - 1991 - Annals of Pure and Applied Logic 52 (1-2):155-179.
    We show that every nontrivial interval in the recursively enumerable degrees contains an incomparable pair which have an infimum in the recursively enumerable degrees.
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   13 citations  
  6.  21
    Working Below a Low2 Recursively Enumerably Degree.Richard A. Shore & Theodore A. Slaman - 1990 - Archive for Mathematical Logic 29 (3):201-211.
  7.  18
    Random Reals, the Rainbow Ramsey Theorem, and Arithmetic Conservation.Chris J. Conidis & Theodore A. Slaman - 2013 - Journal of Symbolic Logic 78 (1):195-206.
    We investigate the question “To what extent can random reals be used as a tool to establish number theoretic facts?” Let $\text{2-\textit{RAN\/}}$ be the principle that for every real $X$ there is a real $R$ which is 2-random relative to $X$. In Section 2, we observe that the arguments of Csima and Mileti [3] can be implemented in the base theory $\text{\textit{RCA}}_0$ and so $\text{\textit{RCA}}_0+\text{2-\textit{RAN\/}}$ implies the Rainbow Ramsey Theorem. In Section 3, we show that the Rainbow Ramsey Theorem is (...)
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  8.  25
    Low Upper Bounds of Ideals.Antonín Kučera & Theodore A. Slaman - 2009 - Journal of Symbolic Logic 74 (2):517-534.
    We show that there is a low T-upper bound for the class of K-trivial sets, namely those which are weak from the point of view of algorithmic randomness. This result is a special case of a more general characterization of ideals in $\Delta _2^0 $ T-degrees for which there is a low T-upper bound.
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark   3 citations  
  9.  21
    Definability in the Enumeration Degrees.Theodore A. Slaman & W. Hugh Woodin - 1997 - Archive for Mathematical Logic 36 (4-5):255-267.
  10.  20
    Working Below a High Recursively Enumerable Degree.Richard A. Shore & Theodore A. Slaman - 1993 - Journal of Symbolic Logic 58 (3):824-859.
  11. Definability in the Recursively Enumerable Degrees.André Nies, Richard A. Shore & Theodore A. Slaman - 1996 - Bulletin of Symbolic Logic 2 (4):392-404.
  12. Differences Between Resource Bounded Degree Structures.Michael E. Mytilinaios & Theodore A. Slaman - 2003 - Notre Dame Journal of Formal Logic 44 (1):1-12.
    We exhibit a structural difference between the truth-table degrees of the sets which are truth-table above 0′ and the PTIME-Turing degrees of all sets. Though the structures do not have the same isomorphism type, demonstrating this fact relies on developing their common theory.
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  13.  44
    An Almost Deep Degree.Peter Cholak, Marcia Groszek & Theodore Slaman - 2001 - Journal of Symbolic Logic 66 (2):881-901.
    We show there is a non-recursive r.e. set A such that if W is any low r.e. set, then the join W $\oplus$ A is also low. That is, A is "almost deep". This answers a question of Jockusch. The almost deep degrees form an definable ideal in the r.e. degrees (with jump.).
    Direct download (8 more)  
     
    Export citation  
     
    Bookmark   4 citations  
  14.  13
    Σ2-Collection and the Infinite Injury Priority Method.Michael E. Mytilinaios & Theodore A. Slaman - 1988 - Journal of Symbolic Logic 53 (1):212 - 221.
    We show that the existence of a recursively enumerable set whose Turing degree is neither low nor complete cannot be proven from the basic axioms of first order arithmetic (P -) together with Σ 2 -collection (BΣ 2 ). In contrast, a high (hence, not low) incomplete recursively enumerable set can be assembled by a standard application of the infinite injury priority method. Similarly, for each n, the existence of an incomplete recursively enumerable set that is neither low n nor (...)
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark   6 citations  
  15.  27
    Comparing DNR and WWKL.Klaus Ambos-Spies, Bjørn Kjos-Hanssen, Steffen Lempp & Theodore Slaman - 2004 - Journal of Symbolic Logic 69 (4):1089-1104.
    In Reverse Mathematics, the axiom system DNR, asserting the existence of diagonally non-recursive functions, is strictly weaker than WWKL0.
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  16.  10
    Relative to Any Non-Hyperarithmetic Set.Noam Greenberg, Antonio Montalbán & Theodore A. Slaman - 2013 - Journal of Mathematical Logic 13 (1):1250007.
  17.  15
    Complementation in the Turing Degrees.Theodore A. Slaman & John R. Steel - 1989 - Journal of Symbolic Logic 54 (1):160-176.
    Posner [6] has shown, by a nonuniform proof, that every ▵ 0 2 degree has a complement below 0'. We show that a 1-generic complement for each ▵ 0 2 set of degree between 0 and 0' can be found uniformly. Moreover, the methods just as easily can be used to produce a complement whose jump has the degree of any real recursively enumerable in and above $\varnothing'$ . In the second half of the paper, we show that the complementation (...)
    Direct download (7 more)  
     
    Export citation  
     
    Bookmark   4 citations  
  18.  15
    A Basis Theorem for Perfect Sets.Marcia J. Groszek & Theodore A. Slaman - 1998 - Bulletin of Symbolic Logic 4 (2):204-209.
    We show that if there is a nonconstructible real, then every perfect set has a nonconstructible element, answering a question of K. Prikry. This is a specific instance of a more general theorem giving a sufficient condition on a pair $M\subset N$ of models of set theory implying that every perfect set in N has an element in N which is not in M.
    Direct download (10 more)  
     
    Export citation  
     
    Bookmark   3 citations  
  19.  60
    Extending Partial Orders to Dense Linear Orders.Theodore A. Slaman & W. Hugh Woodin - 1998 - Annals of Pure and Applied Logic 94 (1-3):253-261.
    J. Łoś raised the following question: Under what conditions can a countable partially ordered set be extended to a dense linear order merely by adding instances of comparability ? We show that having such an extension is a Σ 1 l -complete property and so there is no Borel answer to Łoś's question. Additionally, we show that there is a natural Π 1 l -norm on the partial orders which cannot be so extended and calculate some natural ranks in that (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark  
  20.  15
    A Limit on Relative Genericity in the Recursively Enumerable Sets.Steffen Lempp & Theodore A. Slaman - 1989 - Journal of Symbolic Logic 54 (2):376-395.
    Work in the setting of the recursively enumerable sets and their Turing degrees. A set X is low if X', its Turning jump, is recursive in $\varnothing'$ and high if X' computes $\varnothing''$ . Attempting to find a property between being low and being recursive, Bickford and Mills produced the following definition. W is deep, if for each recursively enumerable set A, the jump of $A \bigoplus W$ is recursive in the jump of A. We prove that there are no (...)
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark   3 citations  
  21.  40
    Recursive in a Generic Real.Juichi Shinoda & Theodore A. Slaman - 2000 - Journal of Symbolic Logic 65 (1):164-172.
    There is a comeager set C contained in the set of 1-generic reals and a first order structure M such that for any real number X, there is an element of C which is recursive in X if and only if there is a presentation of M which is recursive in X.
    Direct download (8 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  22.  29
    Reflection and Forcing in< I> E_-Recursion Theory.Theodore A. Slaman - 1985 - Annals of Pure and Applied Logic 29 (1):79-106.
    E -recursive enumerability is compared via forcing to Σ 1 definability. It is shown that for every countable E -closed ordinal κ there is a set of reals, X , so that L κ [ X ] is the least E -closed structure over X.
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  23.  12
    Relative Enumerability in the Difference Hierarchy.Marat M. Arslanov, Geoffrey L. Laforte & Theodore A. Slaman - 1998 - Journal of Symbolic Logic 63 (2):411-420.
    We show that the intersection of the class of 2-REA degrees with that of the ω-r.e. degrees consists precisely of the class of d.r.e. degrees. We also include some applications and show that there is no natural generalization of this result to higher levels of the REA hierarchy.
    Direct download (8 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  24.  12
    The Sacks Density Theorem and Σ2-Bounding.Marcia J. Groszek, Michael E. Mytilinaios & Theodore A. Slaman - 1996 - Journal of Symbolic Logic 61 (2):450 - 467.
    The Sacks Density Theorem [7] states that the Turing degrees of the recursively enumerable sets are dense. We show that the Density Theorem holds in every model of P - + BΣ 2 . The proof has two components: a lemma that in any model of P - + BΣ 2 , if B is recursively enumerable and incomplete then IΣ 1 holds relative to B and an adaptation of Shore's [9] blocking technique in α-recursion theory to models of arithmetic.
    Direct download (7 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  25.  69
    The N-R.E. Degrees: Undecidability and Σ1substructures.Mingzhong Cai, Richard A. Shore & Theodore A. Slaman - 2012 - Journal of Mathematical Logic 12 (1):1250005-.
  26.  10
    Extremes in the Degrees of Inferability.Lance Fortnow, William Gasarch, Sanjay Jain, Efim Kinber, Martin Kummer, Stuart Kurtz, Mark Pleszkovich, Theodore Slaman, Robert Solovay & Frank Stephan - 1994 - Annals of Pure and Applied Logic 66 (3):231-276.
    Most theories of learning consider inferring a function f from either observations about f or, questions about f. We consider a scenario whereby the learner observes f and asks queries to some set A. If I is a notion of learning then I[A] is the set of concept classes I-learnable by an inductive inference machine with oracle A. A and B are I-equivalent if I[A] = I[B]. The equivalence classes induced are the degrees of inferability. We prove several results about (...)
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark   2 citations  
  27.  5
    Jump Embeddings in the Turing Degrees.Peter G. Hinman & Theodore A. Slaman - 1991 - Journal of Symbolic Logic 56 (2):563-591.
  28.  9
    Differences Between Resource Bounded Degree Structures.Theodore A. Slaman & Michael~E. Mytilinaios - 2003 - Notre Dame Journal of Formal Logic 44 (1):1-12.
    We exhibit a structural difference between the truth-table degrees of the sets which are truth-table above 0′ and the PTIME-Turing degrees of all sets. Though the structures do not have the same isomorphism type, demonstrating this fact relies on developing their common theory.
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  29.  15
    Automorphisms in the PTIME-Turing Degrees of Recursive Sets.Christine Ann Haught & Theodore A. Slaman - 1997 - Annals of Pure and Applied Logic 84 (1):139-152.
    We consider questions related to the rigidity of the structure R, the PTIME-Turing degrees of recursive sets of strings together with PTIME-Turing reducibility, pT, and related structures; do these structures have nontrivial automorphisms? We prove that there is a nontrivial automorphism of an ideal of R. This can be rephrased in terms of partial relativizations. We consider the sets which are PTIME-Turing computable from a set A, and call this class PTIMEA. Our result can be stated as follows: There is (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  30.  12
    On the Σ2-Theory of the Upper Semilattice of Turing Degrees.Carl G. Jockusch Jr & Theodore A. Slaman - 1993 - Journal of Symbolic Logic 58 (1):193 - 204.
  31.  11
    The Π02 Enumeration Degrees Are Not Dense.William C. Calhoun & Theodore A. Slaman - 1996 - Journal of Symbolic Logic 61 (4):1364 - 1379.
    We show that the Π 0 2 enumeration degrees are not dense. This answers a question posed by Cooper.
    Direct download (6 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  32.  24
    On the Existence of a Strong Minimal Pair.George Barmpalias, Mingzhong Cai, Steffen Lempp & Theodore A. Slaman - 2015 - Journal of Mathematical Logic 15 (1):1550003.
    Direct download (7 more)  
     
    Export citation  
     
    Bookmark  
  33.  27
    P 0 1 \Pi^0_1 -Presentations of Algebras.Bakhadyr Khoussainov, Theodore Slaman & Pavel Semukhin - 2006 - Archive for Mathematical Logic 45 (6):769-781.
  34.  1
    The Strength of Ramsey’s Theorem for Pairs and Arbitrarily Many Colors.Theodore A. Slaman & Keita Yokoyama - 2018 - Journal of Symbolic Logic 83 (4):1610-1617.
    Direct download (2 more)  
     
    Export citation  
     
    Bookmark  
  35.  25
    On the Kleene Degrees of Π11 Sets.Theodore A. Slaman - 1986 - Journal of Symbolic Logic 51 (2):352 - 359.
    Let A and B be subsets of the reals. Say that A κ ≥ B, if there is a real a such that the relation "x ∈ B" is uniformly Δ 1 (a, A) in L[ ω x,a,A 1 , x,a,A]. This reducibility induces an equivalence relation $\equiv_\kappa$ on the sets of reals; the $\equiv_\kappa$ -equivalence class of a set is called its Kleene degree. Let K be the structure that consists of the Kleene degrees and the induced partial order (...)
    Direct download (5 more)  
     
    Export citation  
     
    Bookmark  
  36.  7
    On Co-Simple Isols and Their Intersection Types.Rod Downey & Theodore A. Slaman - 1992 - Annals of Pure and Applied Logic 56 (1-3):221-237.
    We solve a question of McLaughlin by showing that if A is a regressive co-simple isol, there is a co-simple regressive isol B such that the intersection type of A and B is trivial. The proof is a nonuniform 0 priority argument that can be viewed as the execution of a single strategy from a 0-argument. We establish some limit on the properties of such pairs by showing that if AxB has low degree, then the intersection type of A and (...)
    Direct download (4 more)  
     
    Export citation  
     
    Bookmark   1 citation  
  37.  19
    Mathematical Definability.Theodore A. Slaman - 1998 - In H. G. Dales & Gianluigi Oliveri (eds.), Truth in Mathematics. Oxford University Press, Usa. pp. 233.
  38.  11
    $$\Pi^0_1$$ -Presentations of Algebras.Bakhadyr Khoussainov, Theodore Slaman & Pavel Semukhin - 2006 - Archive for Mathematical Logic 45 (6):769-781.
    In this paper we study the question as to which computable algebras are isomorphic to non-computable $\Pi_{1}^{0}$ -algebras. We show that many known algebras such as the standard model of arithmetic, term algebras, fields, vector spaces and torsion-free abelian groups have non-computable $\Pi_{1}^{0}$ -presentations. On the other hand, many of this structures fail to have non-computable $\Sigma_{1}^{0}$ -presentation.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  39.  11
    Preface.Klaus Ambos-Spies, Theodore A. Slaman & Robert I. Soare - 1998 - Annals of Pure and Applied Logic 94 (1-3):1.
  40.  10
    University of California, Irvine Irvine, California March 27–30, 2008.Sam Buss, Stephen Cook, José Ferreirós, David Marker, Theodore Slaman & Jamie Tappenden - 2008 - Bulletin of Symbolic Logic 14 (3).
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  41.  7
    < I> Π_< Sub> 1< Sup> 0 Classes and Minimal Degrees.Marcia J. Groszek & Theodore A. Slaman - 1997 - Annals of Pure and Applied Logic 87 (2):117-144.
  42. University of Nevada, Las Vegas, Las Vegas, Nevada June 1–4, 2002.Scot Adams, Shaughan Lavine, Zlil Sela, Natarajan Shankar, Stephen Simpson, Stevo Todorcevic & Theodore A. Slaman - 2003 - Bulletin of Symbolic Logic 9 (1).
     
    Export citation  
     
    Bookmark  
  43.  5
    Σ2 -Collection and the Infinite Injury Priority Method.Michael E. Mytilinaios & Theodore A. Slaman - 1988 - Journal of Symbolic Logic 53 (1):212-221.
  44.  5
    Córdoba, Argentina September 20–24, 2004.Joos Heintz, Antonın Kucera, Joseph Miller, André Nies, Jan Reimann, Theodore Slaman, Diego Vaggione, Paul Vitányi & Verónica Becher - 2005 - Bulletin of Symbolic Logic 11 (4).
    Direct download  
     
    Export citation  
     
    Bookmark  
  45.  5
    The Theory of the Metarecursively Enumerable Degrees.Noam Greenberg, Richard A. Shore & Theodore A. Slaman - 2006 - Journal of Mathematical Logic 6 (01):49-68.
  46.  6
    Π10 Classes and Minimal Degrees.Marcia J. Groszek & Theodore A. Slaman - 1997 - Annals of Pure and Applied Logic 87 (2):117-144.
    Theorem. There is a non-empty Π10 class of reals, each of which computes a real of minimal degree. Corollary. WKL “there is a minimal Turing degree”. This answers a question of H. Friedman and S. Simpson.
    Direct download (3 more)  
     
    Export citation  
     
    Bookmark  
  47.  3
    A Note on Initial Segments of the Enumeration Degrees.Theodore A. Slaman & Andrea Sorbi - 2014 - Journal of Symbolic Logic 79 (2):633-643.
  48.  3
    Are Dense.Theodore A. Slaman - 1985 - In Anil Nerode & Richard A. Shore (eds.), Recursion Theory. American Mathematical Society. pp. 42--195.
    Direct download  
     
    Export citation  
     
    Bookmark  
  49.  2
    Corrigendum To: “On the Strength of Ramsey's Theorem for Pairs”.Peter Cholak, Jr} {Jockusch & Theodore A. Slaman - 2009 - Journal of Symbolic Logic 74 (4):1438-1439.
  50.  1
    On the Kleene Degrees of Π 1 1 Sets.Theodore A. Slaman - 1986 - Journal of Symbolic Logic 51 (2):352-359.
1 — 50 / 53