This book presents a unifying framework for using priority arguments to prove theorems in computability. Priority arguments provide the most powerful theorem-proving technique in the field, but most of the applications of this technique are ad hoc, masking the unifying principles used in the proofs. The proposed framework presented isolates many of these unifying combinatorial principles and uses them to give shorter and easier-to-follow proofs of computability-theoretic theorems. Standard theorems of priority levels 1, 2, and 3 are chosen to demonstrate (...) the framework's use, with all proofs following the same pattern. The last section features a new example requiring priority at all finite levels. The book will serve as a resource and reference for researchers in logic and computability, helping them to prove theorems in a shorter and more transparent manner"--Provided by publisher. (shrink)

I first seriously contemplated writing a book on degree theory in 1976 while I was visiting the University of Illinois at Chicago Circle. There was, at that time, some interest in ann-series book about degree theory, and through the encouragement of Bob Soare, I decided to make a proposal to write such a book. Degree theory had, at that time, matured to the point where the local structure results which had been the mainstay of the earlier papers in the area (...) were finding a steadily increasing number of applications to global degree theory. Michael Yates was the first to realize that the time had come for a systematic study of the interaction between local and global degree theory, and his papers had a considerable influence on the content of this book. During the time that the book was being written and rewritten, there was an explosion in the number of global theorems about the degrees which were proved as applications of local theorems. The global results, in turn, pointed the way to new local theorems which were needed in order to make further progress. I have tried to update the book continuously, in order to be able to present some of the more recent results. It is my hope to introduce the reader to some of the fascinat ing combinatorial methods of Recursion Theory while simultaneously showing how to use these methods to prove some beautiful global theorems about the degrees. (shrink)

In recent years, there has been a substantial amount of work in reverse mathematics concerning natural mathematical principles that are provable from RT, Ramsey's Theorem for Pairs. These principles tend to fall outside of the "big five" systems of reverse mathematics and a complicated picture of subsystems below RT has emerged. In this paper, we answer two open questions concerning these subsystems, specifically that ADS is not equivalent to CAC and that EM is not equivalent to RT.

We exhibit a finite lattice without critical triple that cannot be embedded into the enumerable Turing degrees. Our method promises to lead to a full characterization of the finite lattices embeddable into the enumerable Turing degrees.

We investigate homomorphisms of degree structures with various relations, functions and constants. Our main emphasis is on pseudolattices, i.e., partially ordered sets with a join operation and relations simulating the meet operation. We show that there are no finite quotients of the pseudolattice of degrees or of the pseudolattice of degrees 0′, but that many finite distributive lattices are pseudolattice quotients of the pseudolattice of computably enumerable degrees.

A choice set for a computable linear ordering is a set which contains one element from each maximal block of the ordering. We obtain a partial characterization of the computable linear order-types for which each computable model has a computable choice set, and a full characterization in the relativized case; Every model of the linear order-type α of degree ≤ d has a choice set of degree ≤ d iff α can written as a finite sum of order-types, each of (...) which either has finitely many blocks, or has order-type n · η for some integer n. (shrink)

Martin [4, Theorems 1 and 2] proved that a Turing degree a is the degree of a maximal set if, and only if, a′ = 0″. Lachlan has shown that maximal sets have minimal many-one degrees [2, §1] and that every nonrecursive r.e. Turing degree contains a minimal many-one degree [2, Theorem 4]. Our aim here is to show that any r.e. Turing degree a of a maximal set contains an infinite number of maximal sets whose many-one degrees are pairwise (...) incomparable; hence such Turing degrees contain an infinite number of distinct minimal many-one degrees. This theorem has been proved by Yates [6, Theorem 5] in the case when a = 0′. The need for this theorem first came to our attention as a result of work done by the author [3, Theorem 2.3]. There we looked at the structure / obtained from the recursive functions of one variable under the equivalence relation f ~ g if, and only if, f(x) = g(x) a.e., that is, for all but finitely many x ∈, where M is a maximal set, and M is its complement. We showed that / 1 ≡ / 2 if, and only if, 1 = m 2, i.e., 1. and 2 have the same many-one degree. However, it might be possible that some Turing degree of a maximal set contains exactly one many-one degree of a maximal set. Theorem 1 was proved to show that this was not the case, and hence that the theory of / is not an invariant of Turing degree. (shrink)

The degrees of unsolvability were introduced in the ground-breaking papers of Post [20] and Kleene and Post [7] as an attempt to measure theinformation contentof sets of natural numbers. Kleene and Post were interested in the relative complexity of decision problems arising naturally in mathematics; in particular, they wished to know when a solution to one decision problem contained the information necessary to solve a second decision problem. As decision problems can be coded by sets of natural numbers, this question (...) is equivalent to: Given a computer with access to an oracle which will answer membership questions about a setA, can a program be written which will correctly compute the answers to all membership questions about a setB? If the answer is yes, then we say thatBisTuring reducibletoAand writeB≤TA. We say thatB≡TAifB≤TAandA≤TB. ≡Tis an equivalence relation, and ≤Tinduces a partial ordering on the corresponding equivalence classes; the poset obtained in this way is called thedegrees of unsolvability, and elements of this poset are calleddegrees.Post was particularly interested in computability from sets which are partially generated by a computer, namely, those for which the elements of the set can be enumerated by a computer. (shrink)

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.

We describe the motivation for the construction of a general framework for priority arguments, the ideas incorporated into the construction of the framework, and the use of the framework to prove theorems in computability theory which require priority arguments.

We show that the lattice L 20 is not embeddable into the lattice of ideals of computably enumerable Turing degrees (J). We define a structure called a pseudolattice that generalizes the notion of a lattice, and show that there is a Π 2 necessary and sufficient condition for embedding a finite pseudolattice into J.

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 (...) antichain. Our hardest result is that there is an infinite computable weakly stable poset with no infinite $\Pi _1^0 $ chains or antichains. On the other hand, it is easily seen that every infinite computable stable poset contains an infinite computable chain or an infinite $\Pi _1^0 $ antichain. In Reverse Mathematics, we show that SCAC, the principle that every infinite stable poset contains an infinite chain or antichain, is equivalent over RCA₀ to WSCAC, the corresponding principle for weakly stable posets. (shrink)

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 (...) disjoint. We formulate general criteria that allow one to conclude that a distributive upper semi-lattice has a decidable two-quantifier theory. These criteria are applied not only to the weak truth-table degrees of the recursively enumerable sets but also to various substructures of the polynomial many-one (pm) degrees of the recursive sets. These applications to the pm degrees require no new complexity-theoretic results. The fact that the pm-degrees of the recursive sets have a decidable two-quantifier theory answers a question raised by Shore and Slaman in [21]. (shrink)

We divide the class of infinite computable trees into three types. For the first and second types, 0' computes a nontrivial self-embedding while for the third type 0'' computes a nontrivial self-embedding. These results are optimal and we obtain partial results concerning the complexity of nontrivial self-embeddings of infinite computable trees considered up to isomorphism. We show that every infinite computable tree must have either an infinite computable chain or an infinite Π01 antichain. This result is optimal and has connections (...) to the program of reverse mathematics. (shrink)

I deal here with one of Boghossian’s arguments against content externalism, related to ourinferential rationality(to use his term). According to his reasoning, the apriority of our logical abilities is inconsistent with certain externalist assumptions. Nevertheless, the problem constitutes an important challenge foranytheory of content, not just for externalism. Furthermore, when we examine what internalists may propose to solve the problem, we see that externalists have at their disposal a more promising repertoire of possible replies than internalists. In that sense, insofar (...) as Boghossian’s scenario is relevant to the debate externalism/internalism, it can be seen (against Boghossian’s original intention) as providing additional evidence for content externalism. (shrink)

A satisfactory construal of the subject matter of free will debates must allow for disagreements along two axes. First, it must allow for the possibility of higher order disagreements, or disagreements about what concepts, phenomena, or practices an account of free will is supposed to capture or explain. Second, it must allow for the fact of variation in the extent to which theories are bound by antecedent pre-philosophical thought, talk, and practices. A promising way of accommodating these two thoughts is (...) to treat free will in broadly functionalist terms. On the account proposed here, free will is a power that makes sense of everyday responsibility practices. This construal is not widely shared, but it allows for the possibility that we might have false beliefs about the nature of free will, while still making sense of central philosophical debates about free will. (shrink)

The rise of foundational dualism and the eclipse of the body -- "Body am I entirely, and nothing else": non-reductive materialism and the struggle against dualism -- Toward a materialist phenomenology of religion -- The phenomenology of embodiment and the study of religion -- Religious bodies as social artifacts -- Holding social constructionism in check: the recovery of the active, lived body -- A cultural neurophenomenology of religion: enter the embodied mind -- The eclipse of practice: textualism at large -- (...) "Ceci n'est pas un texte": from textualism to practice -- Expanding the conversation on emplaced religion -- Mobility, networks, and ecology. (shrink)

La pena natural es una situación paradójica que se puede presentar cuando el autor de un delito, al cometerlo o a causa de éste, ha sufrido un daño igual o mayor al que padecería si el juez de la causa le aplicara la pena estatal prevista para tal conducta. Se da con frecuencia al juzgar ciertos accidentes viales, cuando el acusado ya carga el peso de ser quien, por imprudencia, mató a su pareja o familiar cercano, por ejemplo. Pero ¿en (...) qué situaciones y cómo cabe recurrir a la pena natural? En esta investigación, Manuel Serrano explora las diversas aristas y posturas en pugna que atraviesan este tema, donde se cruzan cuestiones como la idea de la “culpa compensada”, la prohibición de aplicar castigo doble por un mismo hecho (non bis in idem) y la clemencia judicial. El autor desmonta la estructura conceptual de la pena natural, estudia jurisprudencia argentina y recorre producciones teóricas de juristas que se han preocupado por este asunto complejo, profundo y poco abordado del derecho penal. (shrink)

Perceptual experience, that paradigm of subjectivity, constitutes our most immediate and fundamental access to the objective world. At least, this would seem to be so if commonsense realism is correct — if perceptual experience is (in general) an immediate awareness of mind-independent objects, and a source of direct knowledge of what such objects are like. Commonsense realism raises many questions. First, can we be more precise about its commitments? Does it entail any particular conception of the nature of perceptual experience (...) and its relation to perceived objects, or any particular view of the way perception yields knowledge? Second, what explains the apparent intuitive appeal of commonsense realism? Should we think of it as a kind of folk theory held by most human adults or is there a sense in which we are pre-theoretically committed to it — in virtue of the experience we enjoy or in virtue of the concepts we use or in virtue of the explanations we give? Third, is commonsense realism defensible, in the face of formidable challenges from epistemology, metaphysics and cognitive science? The project of the present volume is to advance our understanding of these issues and thus to shed light on the commitments and credentials of commonsense realism. As you may have guessed from the title, the volume also aims to highlight the key role the concept of causation plays in these debates. Central issues to be addressed include the status and nature of causal requirements on perception, the causal role of perceptual experience, and the relation between objective perception and causal thinking — issues that, as many chapters in the volume bring out, are inseparable from concerns with the very nature of causation. (shrink)

The Luck Problem has existed in one form or another since David Hume, at least. It is perhaps as old as Stoic objections to the Epicurean swerve. Although the general issue admits of different formulations with subtly different emphases, the characterization of it that will serve as my target focuses on “cross-worlds” luck, a kind of luck that arises when the decision-making of agents is indeterministic.

Wittgenstein distinguished between two uses of “I”, one “as object” and the other “as subject”, a distinction that Shoemaker elucidated in terms of a notion of immunity to error through misidentification (“IEM”); first-personal claims are IEM in the use “as subject”, but not in the other use. Shoemaker argued that memory judgments based on “personal”, episodic memory are not strictly speaking IEM; Gareth Evans disputed this. Similar issues have been debated regarding self-ascriptions of conscious thoughts based on first-personal awareness, in (...) the light of claims of “thought insertion” in schizophrenic patients. The paper aims to defend a Shoemaker-like line by critically engaging with some compelling recent contributions. Methodologically, the paper argues that to properly address these issues the all-inclusive term “thought” should be avoided, and specific types of thoughts countenanced. (shrink)

El trabajo consiste en una elucidación de los elementos que conforman el concepto de pena natural (poena naturalis) en el Derecho penal. Se puede caracterizar la pena natural como el daño o sufrimiento que recae sobre el autor de un delito, producto de la comisión del mismo, que debe ser descontado de la pena legal que ha de aplicársele. Si bien existe un mínimo acuerdo sobre esto, tanto en la jurisprudencia como en la doctrina penal se observan serios desacuerdos acerca (...) de los requisitos que se deben cumplir para reconocer que se está frente a una pena natural. Para elucidar los elementos, se utilizará el constructivismo conceptual de Ronald Dworkin, a fin de describir el desacuerdo y sus implicancias, reconocer los elementos principales de la pena natural y justificarlos bajo su mejor luz moral. ABSTRACT This study focuses on the clarification of the conceptual elements of poena naturalis in criminal law settings. The poena naturalis is the damage or suffering that falls on the convict for its commission. This damage must be deducted from the poena forensis to be applied. Although there is a minimum agreement about the concept of poena naturalis, in the jurisprudence and among legal scholars, there are serious disagreements about the elements of poena naturalis. To elucidate the elements, I will adopt Ronald Dworkin’s conceptual constructivism to describe the disagreement and its implications. At last, I will justify the main elements of the poena naturalis by their best moral light. (shrink)