45 found
Sort by:
  1. Anuj Dawar Colyvan, Steffen Lempp, Rahim Moosa, Ernest Schimmerling & Alex Simpson (2013). Copies of Books to Asl, Box 742, Vassar College, 124 Raymond Avenue, Poughkeepsie, Ny 12604, Usa. In a Review, a Reference “Jsl Xliii 148,” for Example, Refers Either to the Publication Reviewed on Page 148 of Volume 43 of the Journal, or to the Review Itself (Which Contains Full Bibliographical Information for the Reviewed Publication). Analogously, a Reference. [REVIEW] Bulletin of Symbolic Logic 19 (2).
    Direct download  
     
    My bibliography  
     
    Export citation  
  2. Marat M. Arslanov, Iskander Sh Kalimullin & Steffen Lempp (2010). On Downey's Conjecture. Journal of Symbolic Logic 75 (2):401-441.
    We prove that the degree structures of the d.c.e. and the 3-c.e. Turing degrees are not elementarily equivalent, thus refuting a conjecture of Downey. More specifically, we show that the following statement fails in the former but holds in the latter structure: There are degrees f > e > d > 0 such that any degree u ≤ f is either comparable with both e and d, or incomparable with both.
    Direct download (5 more)  
     
    My bibliography  
     
    Export citation  
  3. Rod Downey, Steffen Lempp & Guohua Wu (2010). On the Complexity of the Successivity Relation in Computable Linear Orderings. Journal of Mathematical Logic 10 (01n02):83-99.
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  4. Serikzhan A. Badaev & Steffen Lempp (2009). A Decomposition of the Rogers Semilattice of a Family of D.C.E. Sets. Journal of Symbolic Logic 74 (2):618-640.
    Khutoretskii's Theorem states that the Rogers semilattice of any family of c.e. sets has either at most one or infinitely many elements. A lemma in the inductive step of the proof shows that no Rogers semilattice can be partitioned into a principal ideal and a principal filter. We show that such a partitioning is possible for some family of d.c.e. sets. In fact, we construct a family of c.e. sets which, when viewed as a family of d.c.e. sets, has (up (...)
    Direct download (5 more)  
     
    My bibliography  
     
    Export citation  
  5. Rodney G. Downey, Bart Kastermans & Steffen Lempp (2009). On Computable Self-Embeddings of Computable Linear Orderings. Journal of Symbolic Logic 74 (4):1352 - 1366.
    We solve a longstanding question of Rosenstein, and make progress toward solving a longstanding open problem in the area of computable linear orderings by showing that every computable ƞ-like linear ordering without an infinite strongly ƞ-like interval has a computable copy without nontrivial computable self-embedding. The precise characterization of those computable linear orderings which have computable copies without nontrivial computable self-embedding remains open.
    Direct download (5 more)  
     
    My bibliography  
     
    Export citation  
  6. Carl G. Jockusch Jr, Bart Kastermans, Steffen Lempp, Manuel Lerman & Reed Solomon (2009). Stability and Posets. Journal of Symbolic Logic 74 (2):693 - 711.
    Hirschfeldt and Shore have introduced a notion of stability for infinite posets. We define an arguably more natural notion called weak stability, and we study the existence of infinite computable or low chains or antichains, and of infinite $\Pi _1^0 $ chains and antichains, in infinite computable stable and weakly stable posets. For example, we extend a result of Hirschfeldt and Shore to show that every infinite computable weakly stable poset contains either an infinite low chain or an infinite computable (...)
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  7. Verónica Becher, C. T. Chong, Rod Downey, Noam Greenberg, Antonin Kucera, Bjørn Kjos-Hanssen, Steffen Lempp, Antonio Montalbán, Jan Reimann & Stephen Simpson (2008). Conference on Computability, Complexity and Randomness. Bulletin of Symbolic Logic 14 (4).
    Direct download  
     
    My bibliography  
     
    Export citation  
  8. Yiannis Moschovakis, Richmond H. Thomason, Steffen Lempp, Steve Awodey, Jean-Pierre Marquis & William Tait (2007). The Palmer House Hilton Hotel, Chicago, Illinois April 19–21, 2007. Bulletin of Symbolic Logic 13 (4).
    Direct download (2 more)  
     
    My bibliography  
     
    Export citation  
  9. Steffen Lempp & Carl Mummert (2006). Filters on Computable Posets. Notre Dame Journal of Formal Logic 47 (4):479-485.
    We explore the problem of constructing maximal and unbounded filters on computable posets. We obtain both computability results and reverse mathematics results. A maximal filter is one that does not extend to a larger filter. We show that every computable poset has a \Delta^0_2 maximal filter, and there is a computable poset with no \Pi^0_1 or \Sigma^0_1 maximal filter. There is a computable poset on which every maximal filter is Turing complete. We obtain the reverse mathematics result that the principle (...)
    Direct download (6 more)  
     
    My bibliography  
     
    Export citation  
  10. Steffen Lempp, Charles McCoy, Russell Miller & Reed Solomon (2005). Computable Categoricity of Trees of Finite Height. Journal of Symbolic Logic 70 (1):151-215.
    We characterize the structure of computably categorical trees of finite height, and prove that our criterion is both necessary and sufficient. Intuitively, the characterization is easiest to express in terms of isomorphisms of (possibly infinite) trees, but in fact it is equivalent to a Σ03-condition. We show that all trees which are not computably categorical have computable dimension ω. Finally, we prove that for every n≥ 1 in ω, there exists a computable tree of finite height which is δ0n+1-categorical but (...)
    Direct download (5 more)  
     
    My bibliography  
     
    Export citation  
  11. Steffen Lempp, Theodore A. Slaman & Andrea Sorbi (2005). On Extensions of Embeddings Into the Enumeration Degrees of the -Sets. Journal of Mathematical Logic 5 (02):247-298.
    Direct download (5 more)  
     
    My bibliography  
     
    Export citation  
  12. Klaus Ambos-Spies, Bj�Rn Kjos-Hanssen, Steffen Lempp & Theodore A. Slaman (2004). Comparing DNR and WWKL. Journal of Symbolic Logic 69 (4):1089 - 1104.
    In Reverse Mathematics, the axiom system DNR, asserting the existence of diagonally nonrecursive functions, is strictly weaker than WWKL₀ (weak weak König's Lemma).
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  13. Matthew Foreman, Steve Jackson, Julia Knight, R. W. Knight, Steffen Lempp, Françoise Point, Kobi Peterzil, Leonard Schulman, Slawomir Solecki & Carol Wood (2004). Phoenix Civic Plaza, Phoenix, Arizona, January 9–10, 2004. Bulletin of Symbolic Logic 10 (2).
    Direct download  
     
    My bibliography  
     
    Export citation  
  14. Rodney G. Downey & Steffen Lempp (2002). Contiguity and Distributivity in the Enumerable Turing Degrees: Corrigendum. Journal of Symbolic Logic 67 (4):1579-1580.
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  15. Rodney G. Downey & Steffen Lempp (2002). Corrigendum: ``Contiguity and Distributivity in the Enumerable Turing Degrees''. Journal of Symbolic Logic 67 (4):1579-1580.
    Translate to English
    | Direct download (2 more)  
     
    My bibliography  
     
    Export citation  
  16. Steffen Lempp, Mikhail Peretyat'kin & Reed Solomon (2002). The Lindenbaum Algebra of the Theory of the Class of All Finite Models. Journal of Mathematical Logic 2 (02):145-225.
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  17. Steffen Lempp & Andrea Sorbi (2002). Embedding Finite Lattices Into the Σ02 Enumeration Degrees. Journal of Symbolic Logic 67 (1):69 - 90.
    We show that every finite lattice is embeddable into the Σ 0 2 enumeration degrees via a lattice-theoretic embedding which preserves 0 and 1.
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  18. Steffen Lempp & Andrea Sorbi (2002). Embedding Finite Lattices Into the {$\Sigma\Sp 0\Sb 2$} Enumeration Degrees. Journal of Symbolic Logic 67 (1):69-90.
    Direct download (2 more)  
     
    My bibliography  
     
    Export citation  
  19. Rod Downey, Denis R. Hirschfeldt, Steffen Lempp & Reed Solomon (2001). A Δ02 Set with No Infinite Low Subset in Either It or its Complement. Journal of Symbolic Logic 66 (3):1371 - 1381.
    We construct the set of the title, answering a question of Cholak, Jockusch, and Slaman [1], and discuss its connections with the study of the proof-theoretic strength and effective content of versions of Ramsey's Theorem. In particular, our result implies that every ω-model of RCA 0 + SRT 2 2 must contain a nonlow set.
    Direct download (6 more)  
     
    My bibliography  
     
    Export citation  
  20. Steffen Lempp, André Nies & D. Reed Solomon (2001). On the Filter of Computably Enumerable Supersets of an R-Maximal Set. Archive for Mathematical Logic 40 (6):415-423.
    We study the filter ℒ*(A) of computably enumerable supersets (modulo finite sets) of an r-maximal set A and show that, for some such set A, the property of being cofinite in ℒ*(A) is still Σ0 3-complete. This implies that for this A, there is no uniformly computably enumerable “tower” of sets exhausting exactly the coinfinite sets in ℒ*(A).
    No categories
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  21. M. M. Arslanov & Steffen Lempp (eds.) (1999). Recursion Theory and Complexity: Proceedings of the Kazan '97 Workshop, Kazan, Russia, July 14-19, 1997. W. De Gruyter.
    No categories
     
    My bibliography  
     
    Export citation  
  22. Rod Downey, Geoffrey Laforte & Steffen Lempp (1999). A $Delta^02$ Set with Barely $Sigma^02$ Degree. Journal of Symbolic Logic 64 (4):1700-1718.
    We construct a $\Delta^0_2$ degree which fails to be computably enumerable in any computably enumerable set strictly below $\emptyset'$.
    Direct download (2 more)  
     
    My bibliography  
     
    Export citation  
  23. Rod Downey, Geoffrey Laforte & Steffen Lempp (1999). A Δ02 Set with Barely Σ02 Degree. Journal of Symbolic Logic 64 (4):1700 - 1718.
    We construct a Δ 0 2 degree which fails to be computably enumerable in any computably enumerable set strictly below $\emptyset'$.
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  24. Julia F. Knight, Steffen Lempp, Toniann Pitassi, Hans Schoutens, Simon Thomas, Victor Vianu & Jindrich Zapletal (1999). University of California, San Diego, March 20–23, 1999. Bulletin of Symbolic Logic 5 (3).
    Direct download  
     
    My bibliography  
     
    Export citation  
  25. Rich Blaylock, Rod Downey & Steffen Lempp (1997). Infima in the Recursively Enumerable Weak Truth Table Degrees. Notre Dame Journal of Formal Logic 38 (3):406-418.
    We show that for every nontrivial r.e. wtt-degree a, there are r.e. wtt-degrees b and c incomparable to a such that the infimum of a and b exists but the infimum of a and c fails to exist. This shows in particular that there are no strongly noncappable r.e. wtt-degrees, in contrast to the situation in the r.e. Turing degrees.
    Direct download (6 more)  
     
    My bibliography  
     
    Export citation  
  26. Rodney G. Downey & Steffen Lempp (1997). Contiguity and Distributivity in the Enumerable Turing Degrees. Journal of Symbolic Logic 62 (4):1215-1240.
    We prove that a (recursively) enumerable degree is contiguous iff it is locally distributive. This settles a twenty-year old question going back to Ladner and Sasso. We also prove that strong contiguity and contiguity coincide, settling a question of the first author, and prove that no m-topped degree is contiguous, settling a question of the first author and Carl Jockusch [11]. Finally, we prove some results concerning local distributivity and relativized weak truth table reducibility.
    Direct download (7 more)  
     
    My bibliography  
     
    Export citation  
  27. Steffen Lempp & Manuel Lerman (1997). A Finite Lattice Without Critical Triple That Cannot Be Embedded Into the Enumerable Turing Degrees. Annals of Pure and Applied Logic 87 (2):167-185.
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  28. Steffen Lempp & Manuel Lerman (1997). Iterated Trees of Strategies and Priority Arguments. Archive for Mathematical Logic 36 (4-5):297-312.
    No categories
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  29. Klaus Ambos-Spies, Peter A. Fejer, Steffen Lempp & Manuel Lerman (1996). Decidability of the Two-Quantifier Theory of the Recursively Enumerable Weak Truth-Table Degrees and Other Distributive Upper Semi-Lattices. Journal of Symbolic Logic 61 (3):880-905.
    We give a decision procedure for the ∀∃-theory of the weak truth-table (wtt) degrees of the recursively enumerable sets. The key to this decision procedure is a characterization of the finite lattices which can be embedded into the r.e. wtt-degrees by a map which preserves the least and greatest elements: a finite lattice has such an embedding if and only if it is distributive and the ideal generated by its cappable elements and the filter generated by its cuppable elements are (...)
    Direct download (8 more)  
     
    My bibliography  
     
    Export citation  
  30. Marat Arslanov, Steffen Lempp & Richard A. Shore (1996). Interpolating D-R.E. And REA Degrees Between R.E. Degrees. Annals of Pure and Applied Logic 78 (1-3):29-56.
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  31. Jeffry L. Hirst & Steffen Lempp (1996). Infinite Versions of Some Problems From Finite Complexity Theory. Notre Dame Journal of Formal Logic 37 (4):545-553.
    Recently, several authors have explored the connections between NP-complete problems for finite objects and the complexity of their analogs for infinite objects. In this paper, we will categorize infinite versions of several problems arising from finite complexity theory in terms of their recursion theoretic complexity and proof theoretic strength. These infinite analogs can behave in a variety of unexpected ways.
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  32. Steffen Lempp & Sui Yuefei (1996). An Extended Lachlan Splitting Theorem. Annals of Pure and Applied Logic 79 (1):53-59.
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  33. Steffen Lempp (1995). Ebbinghaus Heinz-Dieter, Flum Jörg, and Thomas Wolfgang. Einführung in Die Mathematische Logik. Die Mathematik. Wissenschaftliche Buchgesellschaft, Darmstadt 1978, Ix+ 288 Pp. Ebbinghaus H.-D., Flum J., and Thomas W.. Mathematical Logic. Revised English Translation by Ann S. Ferebee of the Preceding. Undergraduate Texts in Mathematics. Springer-Verlag, New York, Berlin, Heidelberg, and Tokyo, 1984, Ix+ 216 Pp. Ebbinghaus Heinz-Dieter, Flum Jörg, and Thomas Wolfgang. Einführung in Die Mathematische Logik ... [REVIEW] Journal of Symbolic Logic 60 (3):1013-1014.
    Direct download  
     
    My bibliography  
     
    Export citation  
  34. Steffen Lempp & Manuel Lerman (1995). A General Framework for Priority Arguments. Bulletin of Symbolic Logic 1 (2):189-201.
    Direct download (7 more)  
     
    My bibliography  
     
    Export citation  
  35. Steffen Lempp & André Nies (1995). The Undecidability of the II4 Theory for the R. E. Wtt and Turing Degrees. Journal of Symbolic Logic 60 (4):1118 - 1136.
    We show that the Π 4 -theory of the partial order of recursively enumerable weak truth-table degrees is undecidable, and give a new proof of the similar fact for r.e. T-degrees. This is accomplished by introducing a new coding scheme which consists in defining the class of finite bipartite graphs with parameters.
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  36. Steffen Lempp & Andre Nies (1995). The Undecidability of the II$^_4$ Theory for the R. E. Wtt and Turing Degrees. Journal of Symbolic Logic 60 (4):1118-1136.
    We show that the $\Pi_4$-theory of the partial order of recursively enumerable weak truth-table degrees is undecidable, and give a new proof of the similar fact for r.e. T-degrees. This is accomplished by introducing a new coding scheme which consists in defining the class of finite bipartite graphs with parameters.
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  37. Rodney G. Downey & Steffen Lempp (1994). There is No Plus-Capping Degree. Archive for Mathematical Logic 33 (2):109-119.
    Answering a question of Per Lindström, we show that there is no “plus-capping” degree, i.e. that for any incomplete r.e. degreew, there is an incomplete r.e. degreea>w such that there is no r.e. degreev>w witha∩v=w.
    No categories
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  38. Steffen Lempp (1994). Review: Joseph R. Shoenfield, Recursion Theory. [REVIEW] Journal of Symbolic Logic 59 (3):1105-1105.
    Direct download (2 more)  
     
    My bibliography  
     
    Export citation  
  39. Steffen Lempp (1994). Winter Meeting of the Association for Symbolic Logic: San Antonio, 1993. Journal of Symbolic Logic 59 (2):720-729.
    Direct download (6 more)  
     
    My bibliography  
     
    Export citation  
  40. Rodney G. Downey, Steffen Lempp & Richard A. Shore (1993). Highness and Bounding Minimal Pairs. Mathematical Logic Quarterly 39 (1):475-491.
    No categories
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  41. Steffen Lempp & Manuel Lerman (1992). The Existential Theory of the Poset of R.E. Degrees with a Predicate for Single Jump Reducibility. Journal of Symbolic Logic 57 (3):1120-1130.
    We show the decidability of the existential theory of the recursively enumerable degrees in the language of Turing reducibility, Turing reducibility of the Turing jumps, and least and greatest element.
    Direct download (6 more)  
     
    My bibliography  
     
    Export citation  
  42. S. Barry Cooper, Leo Harrington, Alistair H. Lachlan, Steffen Lempp & Robert I. Soare (1991). The D.R.E. Degrees Are Not Dense. Annals of Pure and Applied Logic 55 (2):125-151.
    Direct download (3 more)  
     
    My bibliography  
     
    Export citation  
  43. Michael A. Ingrassia & Steffen Lempp (1990). Jumps of Nontrivial Splittings of Recursively Enumerable Sets. Mathematical Logic Quarterly 36 (4):285-292.
    No categories
    Direct download (4 more)  
     
    My bibliography  
     
    Export citation  
  44. Steffen Lempp & Theodore A. Slaman (1989). A Limit on Relative Genericity in the Recursively Enumerable Sets. 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 (5 more)  
     
    My bibliography  
     
    Export citation  
  45. Steffen Lempp (1988). A High Strongly Noncappable Degree. Journal of Symbolic Logic 53 (1):174-187.
    An r.e. degree a ≠ 0, 0' is called strongly noncappable if it has no inf with any incomparable r.e. degree. We show the existence of a high strongly noncappable degree.
    Direct download (6 more)  
     
    My bibliography  
     
    Export citation