- New
-
Topics
- All Categories
- Metaphysics and Epistemology
- Value Theory
- Science, Logic, and Mathematics
- Science, Logic, and Mathematics
- Logic and Philosophy of Logic
- Philosophy of Biology
- Philosophy of Cognitive Science
- Philosophy of Computing and Information
- Philosophy of Mathematics
- Philosophy of Physical Science
- Philosophy of Social Science
- Philosophy of Probability
- General Philosophy of Science
- Philosophy of Science, Misc
- History of Western Philosophy
- Philosophical Traditions
- Philosophy, Misc
- Other Academic Areas
- Journals
- Submit material
- More
The theory of the recursively enumerable weak truth-table degrees is undecidable
Journal of Symbolic Logic 57 (3):864-874 (1992)
Abstract
We show that the partial order of Σ0 3-sets under inclusion is elementarily definable with parameters in the semilattice of r.e. wtt-degrees. Using a result of E. Herrmann, we can deduce that this semilattice has an undecidable theory, thereby solving an open problem of P. OdifreddiLinks
PhilArchive
External links
(no proxy)
Setup an account with your affiliations in order to access resources via your University's proxy server
Through your library
- Sign in / register and customize your OpenURL resolver
- Configure custom resolver
My notes
Similar books and articles
On the orbits of hyperhypersimple sets.Wolfgang Maass - 1984 - Journal of Symbolic Logic 49 (1):51-62.
On the structures inside truth-table degrees.Frank Stephan - 2001 - Journal of Symbolic Logic 66 (2):731-770.
Pairs without infimum in the recursively enumerable weak truth table degrees.Paul Fischer - 1986 - Journal of Symbolic Logic 51 (1):117-129.
Infima in the Recursively Enumerable Weak Truth Table Degrees.Rich Blaylock, Rod Downey & Steffen Lempp - 1997 - Notre Dame Journal of Formal Logic 38 (3):406-418.
Complementation in the Turing degrees.Theodore A. Slaman & John R. Steel - 1989 - Journal of Symbolic Logic 54 (1):160-176.
Infima of recursively enumerable truth table degrees.Peter A. Fejer & Richard A. Shore - 1988 - Notre Dame Journal of Formal Logic 29 (3):420-437.
The Π₃-Theory of the $\Sigma _{2}^{0}$ -Enumeration Degrees Is Undecidable.Thomas F. Kent - 2006 - Journal of Symbolic Logic 71 (4):1284 - 1302.
The role of true finiteness in the admissible recursively enumerable degrees.Noam Greenberg - 2005 - Bulletin of Symbolic Logic 11 (3):398-410.
Definability in the recursively enumerable degrees.André Nies, Richard A. Shore & Theodore A. Slaman - 1996 - Bulletin of Symbolic Logic 2 (4):392-404.
Decidability of the two-quantifier theory of the recursively enumerable weak truth-table degrees and other distributive upper semi-lattices.Klaus Ambos-Spies, Peter A. Fejer, Steffen Lempp & Manuel Lerman - 1996 - Journal of Symbolic Logic 61 (3):880-905.
Analytics
Added to PP
2009-01-28
Downloads
56 (#274,303)
6 months
15 (#145,565)
2009-01-28
Downloads
56 (#274,303)
6 months
15 (#145,565)
Historical graph of downloads
Citations of this work
Splitting theorems in recursion theory.Rod Downey & Michael Stob - 1993 - Annals of Pure and Applied Logic 65 (1):1-106.
Interpreting true arithmetic in the theory of the r.e. truth table degrees.André Nies & Richard A. Shore - 1995 - Annals of Pure and Applied Logic 75 (3):269-311.
Interpreting N in the computably enumerable weak truth table degrees.André Nies - 2001 - Annals of Pure and Applied Logic 107 (1-3):35-48.
Classes bounded by incomplete sets.Kejia Ho & Frank Stephan - 2002 - Annals of Pure and Applied Logic 116 (1-3):273-295.
Computably Enumerable Reals and Uniformly Presentable Ideals.S. A. Terwijn & R. Downey - 2002 - Mathematical Logic Quarterly 48 (S1):29-40.
References found in this work
The weak truth table degrees of recursively enumerable sets.Richard E. Ladner & Leonard P. Sasso - 1975 - Annals of Mathematical Logic 8 (4):429-448.
Classical Recursion Theory. The Theory of Functions and Sets of Natural Numbers.Peter G. Hinman - 1990 - Journal of Symbolic Logic 55 (3):1307-1308.
The recursively enumerable degrees have infinitely many one-types.Klaus Ambos-Spies & Robert I. Soare - 1989 - Annals of Pure and Applied Logic 44 (1-2):1-23.
Recursively Enumerable Sets and Degrees. A Study of Computable Functions and Computably Generated Sets.Robert I. Soare - 1990 - Journal of Symbolic Logic 55 (1):356-357.
PhilPapers logo by Andrea Andrews and Meghan Driscoll.
This site uses cookies and Google Analytics (see our terms & conditions for details regarding the privacy implications). Use of this site is subject to terms & conditions.
All rights reserved by The PhilPapers Foundation
Server: philpapers-web-7c76586df8-5tf24 uwo