We prove that no computable tree of infinite height is computably categorical, and indeed that all such trees have computable dimension ω. Moreover, this dimension is effectively ω, in the sense that given any effective listing of computable presentations of the same tree, we can effectively find another computable presentation of it which is not computably isomorphic to any of the presentations on the list.

Fried and Kollár constructed a fully faithful functor from the category of graphs to the category of fields. We give a new construction of such a functor and use it to resolve a longstanding open problem in computable model theory, by showing that for every nontrivial countable structure${\cal S}$, there exists a countable field${\cal F}$of arbitrary characteristic with the same essential computable-model-theoretic properties as${\cal S}$. Along the way, we develop a new “computable category theory”, and prove that our functor and (...) its partially defined inverse are computable functors. (shrink)

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 (...) not δ0n-categorical. (shrink)

We use the Low Basis Theorem of Jockusch and Soare to show that all computable algebraic fields are d-computably categorical for a particular Turing degree d with d' = θ", but that not all such fields are 0'-computably categorical. We also prove related results about algebraic fields with splitting algorithms, and fields of finite transcendence degree over ℚ.

We study the relative complexity of equivalence relations and preorders from computability theory and complexity theory. Given binary relationsR,S, a componentwise reducibility is defined byR≤S⇔ ∃f∀x, y[x R y↔fS f].Here,fis taken from a suitable class of effective functions. For us the relations will be on natural numbers, andfmust be computable. We show that there is a${\rm{\Pi }}_1^0$-complete equivalence relation, but no${\rm{\Pi }}_k^0$-complete fork≥ 2. We show that${\rm{\Sigma }}_k^0$preorders arising naturally in the above-mentioned areas are${\rm{\Sigma }}_k^0$-complete. This includes polynomial timem-reducibility on (...) exponential time sets, which is${\rm{\Sigma }}_2^0$, almost inclusion on r.e. sets, which is${\rm{\Sigma }}_3^0$, and Turing reducibility on r.e. sets, which is${\rm{\Sigma }}_4^0$. (shrink)

We consider embeddings of structures which preserve spectra: if g: M → S with S computable, then M should have the same Turing degree spectrum (as a structure) that g(M) has (as a relation on S). We show that the computable dense linear order L is universal for all countable linear orders under this notion of embedding, and we establish a similar result for the computable random graph G. Such structures are said to be spectrally universal. We use our results (...) to answer a question of Goncharov, and also to characterize the possible spectra of structures as precisely the spectra of unary relations on G. Finally, we consider the extent to which all spectra of unary relations on the structure L may be realized by such embeddings, offering partial results and building the first known example of a structure whose spectrum contains precisely those degrees c with c′ ≥T 0″. (shrink)

Slaman and Wehner have constructed structures which distinguish the computable Turing degree 0 from the noncomputable degrees, in the sense that the spectrum of each structure consists precisely of the noncomputable degrees. Downey has asked if this can be done for an ordinary type of structure such as a linear order. We show that there exists a linear order whose spectrum includes every noncomputable Δ 0 2 degree, but not 0. Since our argument requires the technique of permitting below a (...) Δ 0 2 set, we include a detailed explanation of the mechanics and intuition behind this type of permitting. (shrink)

We give a straightforward computable-model-theoretic definition of a property of \Delta^0_2 sets called order-computability. We then prove various results about these sets which suggest that, simple though the definition is, the property defies any easy characterization in pure computability theory. The most striking example is the construction of two computably isomorphic c.e. sets, one of which is order-computable and the other not.

Forgiveness theorists focus a good deal on explicating the content of what they take to be a shared folk concept of forgiveness. Our empirical research, however, suggests that there is a range of concepts of forgiveness present in the population, and therefore that we should be folk conceptual pluralists about forgiveness. We suggest two possible responses on the part of forgiveness theorists: (1) to deny folk conceptual pluralism by arguing that forgiveness is a functional concept and (2) to accept folk (...) conceptual pluralism and focus on a revisionary conceptual ethics project. (shrink)

The principles for universal reading models proposed by Frost correspond to developmental theories, in which neurocognitive constraints and cultural experiences shape development. We question his contention that Hebrew word identification is fundamentally about roots, excluding verbal and nominal word-pattern morphemes; and we propose that readers use all information available in stimuli, adjusting for volume and usefulness.

We study the implications of model completeness of a theory for the effectiveness of presentations of models of that theory. It is immediate that for a computable model A\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal {A}$$\end{document} of a computably enumerable, model complete theory, the entire elementary diagram E\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$E$$\end{document} must be decidable. We prove that indeed a c.e. theory T is model complete if and only if there is a (...) uniform procedure that succeeds in deciding E\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$E$$\end{document} from the atomic diagram Δ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\varDelta $$\end{document} for all countable models A\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal {A}$$\end{document} of T. Moreover, if every presentation of a single isomorphism type A\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathcal {A}$$\end{document} has this property of relative decidability, then there must be a procedure with succeeds uniformly for all presentations of an expansion \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$$$\end{document} by finitely many new constants. (shrink)

Let K be a family of structures, closed under isomorphism, in a fixed computable language. We consider effective lists of structures from K such that every structure in K is isomorphic to exactly one structure on the list. Such a list is called a computable classification of K, up to isomorphism. Using the technique of Friedberg enumeration, we show that there is a computable classification of the family of computable algebraic fields and that with a 0'-oracle, we can obtain similar (...) classifications of the families of computable equivalence structures and of computable finite-branching trees. However, there is no computable classification of the latter, nor of the family of computable torsion-free abelian groups of rank 1, even though these families are both closely allied with computable algebraic fields. (shrink)

We provide a positive solution for Post’s Problem for ordinal register machines, and also prove that these machines and ordinal Turing machines compute precisely the same partial functions on ordinals. To do so, we construct ordinal register machine programs which compute the necessary functions. In addition, we show that any set of ordinals solving Post’s Problem must be unbounded in the writable ordinals.

We define a property R(A 0 , A 1 ) in the partial order E of computably enumerable sets under inclusion, and prove that R implies that A 0 is noncomputable and incomplete. Moreover, the property is nonvacuous, and the A 0 and A 1 which we build satisfying R form a Friedberg splitting of their union A, with A 1 prompt and A promptly simple. We conclude that A 0 and A 1 lie in distinct orbits under automorphisms of (...) E, yielding a strong answer to a question previously explored by Downey, Stob, and Soare about whether halves of Friedberg splittings must lie in the same orbit. (shrink)

Several researchers have recently established that for every Turing degree \, the real closed field of all \-computable real numbers has spectrum \. We investigate the spectra of real closed fields further, focusing first on subfields of the field \ of computable real numbers, then on archimedean real closed fields more generally, and finally on non-archimedean real closed fields. For each noncomputable, computably enumerable set C, we produce a real closed C-computable subfield of \ with no computable copy. Then we (...) build an archimedean real closed field with no computable copy but with a computable enumeration of the Dedekind cuts it realizes, and a computably presentable nonarchimedean real closed field whose residue field has no computable presentation. (shrink)

For a ring R, Hilbert’s Tenth Problem $HTP$ is the set of polynomial equations over R, in several variables, with solutions in R. We view $HTP$ as an enumeration operator, mapping each set W of prime numbers to $HTP$, which is naturally viewed as a set of polynomials in $\mathbb {Z}[X_1,X_2,\ldots ]$. It is known that for almost all W, the jump $W'$ does not $1$ -reduce to $HTP$. In contrast, we show that every Turing degree contains a set W (...) for which such a $1$ -reduction does hold: these W are said to be HTP-complete. Continuing, we derive additional results regarding the impossibility that a decision procedure for $W'$ from $HTP$ can succeed uniformly on a set of measure $1$, and regarding the consequences for the boundary sets of the $HTP$ operator in case $\mathbb {Z}$ has an existential definition in $\mathbb {Q}$. (shrink)

It is known that the spectrum of a Boolean algebra cannot contain a low₄ degree unless it also contains the degree 0; it remains open whether the same holds for low₅ degrees. We address the question differently, by considering Boolean subalgebras of the computable atomless Boolean algebra B. For such subalgebras A, we show that it is possible for the spectrum of the unary relation A on B to contain a low₅ degree without containing 0.

We investigate the orbit of a low computably enumerable set under automorphisms of the partial order of c.e. sets under inclusion. Given an arbitrary low c.e. set A and an arbitrary noncomputable c.e. set C, we use the New Extension Theorem of Soare to construct an automorphism of mapping A to a set B such that CTB. Thus, the orbit in of the low set A cannot be contained in the upper cone above C. This complements a result of Harrington, (...) who showed that the orbit of a noncomputable c.e. set cannot be contained in the lower cone below any incomplete c.e. set. (shrink)

Slaman and Wehner have constructed structures which distinguish the computable Turing degree 0 from the noncomputable degrees, in the sense that the spectrum of each structure consists precisely of the noncomputable degrees. Downey has asked if this can be done for an ordinary type of structure such as a linear order. We show that there exists a linear order whose spectrum includes every noncomputable $\Delta^0_2$ degree, but not 0. Since our argument requires the technique of permitting below a $\Delta^0_2$ set, (...) we include a detailed explanation of the mechanics and intuition behind this type of permitting. (shrink)

Defining the degree of categoricity of a computable structure ${\mathcal{M}}$ to be the least degree d for which ${\mathcal{M}}$ is d-computably categorical, we investigate which Turing degrees can be realized as degrees of categoricity. We show that for all n, degrees d.c.e. in and above 0 (n) can be so realized, as can the degree 0 (ω).

Infinite time register machines (ITRMs) are register machines which act on natural numbers and which are allowed to run for arbitrarily many ordinal steps. Successor steps are determined by standard register machine commands. At limit times register contents are defined by appropriate limit operations. In this paper, we examine the ITRMs introduced by the third and fourth author (Koepke and Miller in Logic and Theory of Algorithms LNCS, pp. 306–315, 2008), where a register content at a limit time is (...) set to the lim inf of previous register contents if that limit is finite; otherwise the register is reset to 0. The theory of these machines has several similarities to the infinite time Turing machines (ITTMs) of Hamkins and Lewis. The machines can decide all ${\Pi^1_1}$ sets, yet are strictly weaker than ITTMs. As in the ITTM situation, we introduce a notion of ITRM-clockable ordinals corresponding to the running times of computations. These form a transitive initial segment of the ordinals. Furthermore we prove a Lost Melody theorem: there is a real r such that there is a program P that halts on the empty input for all oracle contents and outputs 1 iff the oracle number is r, but no program can decide for every natural number n whether or not ${n \in r}$ with the empty oracle. In an earlier paper, the third author considered another type of machines where registers were not reset at infinite lim inf’s and he called them infinite time register machines. Because the resetting machines correspond much better to ITTMs we hold that in future the resetting register machines should be called ITRMs. (shrink)

We exploit properties of certain directed graphs, obtained from the families of sets with special effective enumeration properties, to generalize several results in computable model theory to higher levels of the hyperarithmetical hierarchy. Families of sets with such enumeration features were previously built by Selivanov, Goncharov, and Wehner. For a computable successor ordinal α, we transform a countable directed graph into a structure such that has a isomorphic copy if and only if has a computable isomorphic copy.A computable structure is (...) categorical if for all computable isomorphic copies of , there is an isomorphism from onto , which is . We prove that for every computable successor ordinal α, there is a computable, categorical structure, which is not relatively categorical. This generalizes the result of Goncharov that there is a computable, computably categorical structure, which is not relatively computably categorical.An additional relation R on the domain of a computable structure is intrinsically on if in all computable isomorphic copies of , the image of R is . We prove that for every computable successor ordinal α, there is an intrinsically relation on a computable structure, which not relatively intrinsically . This generalizes the result of Manasse that there is an intrinsically computably enumerable relation on a computable structure, which is not relatively intrinsically computably enumerable.The dimension of a structure is the number of computable isomorphic copies, up to isomorphisms. We prove that for every computable successor ordinal α and every n≥1, there is a computable structure with dimension n. This generalizes the result of Goncharov that there is a structure of computable dimension n for every n≥1.Finally, we prove that for every computable successor ordinal α, there is a countable structure with isomorphic copies in just the Turing degrees of sets X such that relative to X is not . In particular, for every finite n, there is a structure with isomorphic copies in exactly the non- Turing degrees. This generalizes the result obtained by Wehner, and independently by Slaman, that there is a structure with isomorphic copies in exactly the nonzero Turing degrees. (shrink)

Varieties of Ethical Reflection brings together new cultural and religious perspectives—drawn from non-Western, primarily Asian, philosophical sources—to globalize the contemporary discussion of theoretical and applied ethics.

We improve on and generalize a 1960 result of Maltsev. For a field F, we denote by $H(F)$ the Heisenberg group with entries in F. Maltsev showed that there is a copy of F defined in $H(F)$, using existential formulas with an arbitrary non-commuting pair of elements as parameters. We show that F is interpreted in $H(F)$ using computable $\Sigma _1$ formulas with no parameters. We give two proofs. The first is an existence proof, relying on a result of Harrison-Trainor, (...) Melnikov, R. Miller, and Montalbán. This proof allows the possibility that the elements of F are represented by tuples in $H(F)$ of no fixed arity. The second proof is direct, giving explicit finitary existential formulas that define the interpretation, with elements of F represented by triples in $H(F)$. Looking at what was used to arrive at this parameter-free interpretation of F in $H(F)$, we give general conditions sufficient to eliminate parameters from interpretations. (shrink)

Fraïssé studied countable structures S through analysis of the age of S i.e., the set of all finitely generated substructures of S. We investigate the effectiveness of his analysis, considering effectively presented lists of finitely generated structures and asking when such a list is the age of a computable structure. We focus particularly on the Fraïssé limit. We also show that degree spectra of relations on a sufficiently nice Fraïssé limit are always upward closed unless the relation is definable by (...) a quantifier-free formula. We give some sufficient or necessary conditions for a Fraïssé limit to be spectrally universal. As an application, we prove that the computable atomless Boolean algebra is spectrally universal. (shrink)

In early March 2014, some of the members of Culture on the Edge—a scholarly research collaboration of seven scholars of religion, interested in more theoretically sophisticated studies of identity, and all of whom are at different career stages and at a variety of North American institutions—had a conversation online on the use of the terms “critique” and “critical,” terms widely used in the field today but employed in such a variety of ways that the members of the group thought it (...) worthwhile to focus some attention on them. What follows is the transcript of their conversation. (shrink)

Despite the supreme political and economic significance of boundaries--and ongoing challenges to existing national boundaries--scant attention has been paid to their ethics. This volume explores how diverse ethical traditions understand the political and property rights reflected in territorial and jurisdictional boundaries. It is the first book to bring together thinkers from a range of traditions, both religious and secular, to discuss the ethics of boundaries. Each contributor represents a tradition's views on questions surrounding the use of boundaries to delimit property (...) and political rights. What does it mean to own something? What resources should not be privately owned? What justifies the erection of political boundaries between one people and another? How ''hard'' should such boundaries be? What rights extend to minorities within a state? Should territorial boundaries coincide with social ones? Does national autonomy have an ethical basis, or is it an aspect of modern power politics? Should we aim for a more inclusive community than that afforded by modern nation-states? Cross-chapter dialogue and a substantive conclusion draw out similarities and differences among the traditions represented, traditions that include Christianity, classical liberalism, Confucianism, international law, Islam, Judaism, liberal egalitarianism, and natural law. In addition to the editors, the contributors are Nigel Biggar, Joseph Boyle, Joseph Chan, Russell Hardin, Will Kymlicka, Loren Lomasky, Robert McCorquodale, Richard B. Miller, David Novak, Sulayman Nyang, Michael Nylan, Raul C. Pangalangan, Daniel Philpott, Jeremy Rabkin, Hillel Steiner, M. Raquibuz Zaman, and Noam J. Zohar. (shrink)

In this article we critique the collectivist approach to collective moral responsibility. According to philosophers of a collectivist persuasion, a central notion of collective moral responsibility is moral responsibility assigned to a collective as a single entity. In our critique, we proceed by way of discussing the accounts and arguments of three prominent representatives of the collectivist approach with respect to collective responsibility: Margaret Gilbert, Russell Hardin, and Philip Pettit. Our aims are mainly critical; however, this should not be (...) taken to imply that we do not ourselves support an alternative account of collective responsibility. We advocate an individualist account of collective responsibility. On this view of collective responsibility as joint responsibility, collective responsibility is ascribed to individuals. Each member of the group is individually morally responsible for the outcome of the joint action, but each is individually responsible jointly with the others. (shrink)

The fact that statements about "nothing" are, or are always equivalent to, a universal statement raises the question of a non-universalizable, non-completable nothing. Lacan’s pas-tout is an attempt to logically capture this incompleteness that can never be completed. While the pas-tout is relevant to the field of sexuation, its logic can be considered independent of it. This logic is, of course, a "deviant" logic, and for this reason raises questions about how it is to be interpreted. Alain Badiou criticizes Lacan (...) for adopting a pre-Cantorian attitude towards the infinite and for advocating the strictures of intuitionism. I argue that Lacan is not an intuitionist but a constructivist about mathematics. I also consider Jacques-Alain Miller’s suggestion that Lacan’s pastout can be considered a variant of the Aristotelian negative particular statement, "Not all As are B" or "Not every A is B". (shrink)

Buddhist Studies. Selected Essays of J. W. de Jong. Ed. Gregory Schopen. Asian Humanities Press-a division of Lancaster-Miller Publishers, Berkeley, California 1979. ix+717 pp. $35.00.

This is a response paper to Daniel Russell's paper in the same volume. I raise some challenges to Russell's model of virtue acquisition which draws extensively on the CAPS model in psychology and on parallels between virtues and skills.

Starting with Gottlob Frege's foundational theories of sense and reference, Miller provides a useful introduction to the formal logic used in all subsequent philosophy of language. He communicates a sense of active philosophical debate by confronting the views of the early theorists concerned with building systematic theories - such as Frege, Bertrand Russell, and the logical positivists - with the attacks mounted by sceptics - such as W.O. Quine, Saul Kripke, and Ludwig Wittgenstein. This leads to important excursions (...) into related areas of metaphysics, philosophy of mind, and cognitive science that present the more recent attempts to save the notions of sense and meaning by philosophers such as Paul Grice, John Searle, Jerry Fodor, Colin McGinn, and Crispin Wright. Miller then returns to the systematic program by examining the formal theories of Donald Davidson, concluding with a chapter surveying the relevance of philosophy of language to the broader metaphysical debates between realists and anti-realists. Miller's clear, engaged, and coherently structured approach makes Philosophy of Language an ideal text for undergraduate courses. The guides to further reading provided in each chapter help the reader pursue interesting topics further and facilitate using the book in conjunction with primary sources. (shrink)

According to a fairly standard view, there are several reasons for denying that existence is a real property of individuals. One is that 'exists' cannot be predicated of individuals, and another is that first-level properties are parasitic on individuals for their actuality, which is something that existence could never be. A third is that existence adds nothing to individuals. Moreover, even if existence were to survive all three counter-indications, it would be merely the most vacuous of properties. _The Fullness of (...) Being_, however, argues that this view of existence is seriously awry. In this brilliant book, Barry Miller argues that existence is not merely a real property of individuals, but by far the richest of their properties. The commonly accepted view of existence is testimony, contends Miller, to what happens when wrong questions are asked, false assumptions are made, and the possibility of a new paradigm for existence is dismissed without consideration. They bear witness to the substantial flaws underlying the familiar claim 'existence is not a predicate' and the Frege-Russell-Quine view not only of 'exists' as exclusively a second-level predicate, but of existence as no more than a Cambridge property of individuals. By way of contrast, _The Fullness of Being_ is an account of what happens when different questions are asked, when false assumptions are eschewed, and when the possibility of a radically different paradigm for existence is actively explored rather than completely ignored. What began for Miller as an exercise in philosophical logic to determine whether 'exists' is predicable of individuals, ends in an argument with groundbreaking consequences for ontology. "_The Fullness of Being_ is a brilliant and original account of existence. It will be required reading for those philosophers interested in the topic." —_Peter Forrest, professor of philosophy, University of New England, Australia_. (shrink)

According to a fairly standard view, there are several reasons for denying that existence is a real property of individuals. One is that 'exists' cannot be predicated of individuals, and another is that first-level properties are parasitic on individuals for their actuality, which is something that existence could never be. A third is that existence adds nothing to individuals. Moreover, even if existence were to survive all three counter-indications, it would be merely the most vacuous of properties. _The Fullness of (...) Being_, however, argues that this view of existence is seriously awry. In this brilliant book, Barry Miller argues that existence is not merely a real property of individuals, but by far the richest of their properties. The commonly accepted view of existence is testimony, contends Miller, to what happens when wrong questions are asked, false assumptions are made, and the possibility of a new paradigm for existence is dismissed without consideration. They bear witness to the substantial flaws underlying the familiar claim 'existence is not a predicate' and the Frege-Russell-Quine view not only of 'exists' as exclusively a second-level predicate, but of existence as no more than a Cambridge property of individuals. By way of contrast, _The Fullness of Being_ is an account of what happens when different questions are asked, when false assumptions are eschewed, and when the possibility of a radically different paradigm for existence is actively explored rather than completely ignored. What began for Miller as an exercise in philosophical logic to determine whether 'exists' is predicable of individuals, ends in an argument with groundbreaking consequences for ontology. "_The Fullness of Being_ is a brilliant and original account of existence. It will be required reading for those philosophers interested in the topic." —_Peter Forrest, professor of philosophy, University of New England, Australia_. (shrink)

The most basic requirement of any theory of concrete individuals is that it do justice to the fact that, unlike universals, individuals are non-instantiable. The bundle theories of Russell and Goodman, the Guise Theory of Castaneda and the Trope Theory of D.C.Williams each breach this requirement by implicity allowing an individual to be instantiable either after it has ceased to exist or both before and after it has ceased to exist. Underlying this flaw in all four theories is the (...) tacit assumption that individuals are ontologically prior to their constituents. That is to say, an individual's constituents do not individuate it, but are individuated by it somewhat after the manner of the non-substantial particulars of Aristotle or the individualized forms of Aquinas. (shrink)