We study arithmetic and hyperarithmetic degrees of categoricity. We extend a result of E. Fokina, I. Kalimullin, and R. Miller to show that for every computable ordinal $\alpha$, $\mathbf{0}^{}$ is the degree of categoricity of some computable structure $\mathcal{A}$. We show additionally that for $\alpha$ a computable successor ordinal, every degree $2$-c.e. in and above $\mathbf{0}^{}$ is a degree of categoricity. We further prove that every degree of categoricity is hyperarithmetic and show that the index set of structures with degrees (...) of categoricity is $\Pi_{1}^{1}$-complete. (shrink)

We study for each computably bounded $\Pi ^0_1$ class P the set of degrees of c.e. paths in P. We show, amongst other results, that for every c.e. degree a there is a perfect $\Pi ^0_1$ class where all c.e. members have degree a. We also show that every $\Pi ^0_1$ set of c.e. indices is realized in some perfect $\Pi ^0_1$ class, and classify the sets of c.e. degrees which can be realized in some $\Pi ^0_1$ class as exactly (...) those with a computable representation. (shrink)

The Rainbow Ramsey Theorem is essentially an "anti-Ramsey" theorem which states that certain types of colorings must be injective on a large subset (rather than constant on a large subset). Surprisingly, this version follows easily from Ramsey's Theorem, even in the weak system RCA₀ of reverse mathematics. We answer the question of the converse implication for pairs, showing that the Rainbow Ramsey Theorem for pairs is in fact strictly weaker than Ramsey's Theorem for pairs over RCA₀. The separation involves techniques (...) from the theory of randomness by showing that every 2-random bounds an ω-model of the Rainbow Ramsey Theorem for pairs. These results also provide as a corollary a new proof of Martin's theorem that the hyperimmune degrees have measure one. (shrink)

We investigate the complexity of isomorphisms of computable structures on cones in the Turing degrees. We show that, on a cone, every structure has a strong degree of categoricity, and that degree of categoricity is${\rm{\Delta }}_\alpha ^0 $-complete for someα. To prove this, we extend Montalbán’sη-system framework to deal with limit ordinals in a more general way. We also show that, for any fixed computable structure, there is an ordinalαand a cone in the Turing degrees such that the exact complexity (...) of computing an isomorphism between the given structure and another copy${\cal B}$in the cone is a c.e. degree in${\rm{\Delta }}_\alpha ^0\left$. In each of our theorems the cone in question is clearly described in the beginning of the proof, so it is easy to see how the theorems can be viewed as general theorems with certain effectiveness conditions. (shrink)

To each computable enumerable (c.e.) set A with a particular enumeration {As}s∈ω, there is associated a settling function mA(x), where mA(x) is the last stage when a number less than or equal to x was enumerated into A. One c.e. set A is settling time dominated by another set B (B >st A) if for every computable function f, for all but finitely many x, mB(x) > f(m₄(x)). This settling-time ordering, which is a natural extension to an ordering of the (...) idea of domination, was first introduced by Nabutovsky and Weinberger in [3] and Soare [6]. They desired a sequence of sets descending in this relationship to give results in differential geometry. In this paper we examine properties of the <st ordering. We show that it is not invariant under computable isomorphism, that any countable partial ordering embeds into it, that there are maximal and minimal sets, and that two c.e. sets need not have an inf or sup in the ordering. We also examine a related ordering, the strong settling-time ordering where we require for all computable f and g, for almost all x, mB(x) > f(mA(g(x))). (shrink)

We show that Sacks' and Shoenfield's analogs of jump inversion fail for both tt- and wtt-reducibilities in a strong way. In particular we show that there is a ${\mathrm{\Delta }}_{2}^{0}$ set B > tt ∅′ such that there is no c.e. set A with A′ ≡ wtt B. We also show that there is a ${\mathrm{\Sigma }}_{2}^{0}$ set C > tt ∅′ such that there is no ${\mathrm{\Delta }}_{2}^{0}$ set D with D′ ≡ wtt C.

We analyze the degree spectra of structures in which different types of immunity conditions are encoded. In particular, we give an example of a structure whose degree spectrum coincides with the hyperimmune degrees. As a corollary, this shows the existence of an almost computable structure of which the complement of the degree spectrum is uncountable.

A set X is prime bounding if for every complete atomic decidable (CAD) theory T there is a prime model U of T decidable in X. It is easy to see that $X = 0\prime$ is prime bounding. Denisov claimed that every $X <_{T} 0\prime$ is not prime bounding, but we discovered this to be incorrect. Here we give the correct characterization that the prime bounding sets $X \leq_{T} 0\prime$ are exactly the sets which are not $low_2$ . Recall that (...) X is $low_2$ if $X\prime\prime$ $\leq_{T} 0\prime$ . To prove that a $low_2$ set X is not prime bounding we use a $0\prime$ -computable listing of the array of sets { Y : Y $\leq_{T}$ X } to build a CAD theory T which diagonalizes against all potential X-decidable prime models U of T. To prove that any $non-low_{2}$ ; X is indeed prime bounding, we fix a function f $\leq_T$ X that is not dominated by a certain $0\prime$ -computable function that picks out generators of principal types. Given a CAD theory T. we use f to eventually find, for every formula $\varphi (\bar{x})$ consistent with T, a principal type which contains it, and hence to build an X-decidable prime model of T. We prove the prime bounding property equivalent to several other combinatorial properties, including some related to the limitwise monotonic functions which have been introduced elsewhere in computable model theory. (shrink)

Topologists Nabutovsky and Weinberger discovered how to embed computably enumerable (c.e.) sets into the geometry of Riemannian metrics modulo diffeomorphisms. They used the complexity of the settling times of the c.e. sets to exhibit a much greater complexity of the depth and density of local minima for the diameter function than previously imagined. Their results depended on the existence of certain sequences of c.e. sets, constructed at their request by Csima and Soare, whose settling times had the necessary dominating (...) properties. Although these computability results had been announced earlier, their proofs have been deferred until this paper. Computably enumerable sets have long been used to prove undecidability of mathematical problems such as the word problem for groups and Hilbert's Tenth Problem. However, this example by Nabutovsky and Weinberger is perhaps the first example of the use of c.e. sets to demonstrate specific mathematical or geometric complexity of a mathematical structure such as the depth and distribution of local minima. (shrink)

We consider the Turing degrees of prime models of complete decidable theories. In particular we show that every complete decidable atomic theory has a prime model whose elementary diagram is low. We combine the construction used in the proof with other constructions to show that complete decidable atomic theories have low prime models with added properties. If we have a complete decidable atomic theory with all types of the theory computable, we show that for every degree d with 0 0, (...) T has a d-decidable model omitting the nonprincipal types listed by L. (shrink)

Tarski defined a way of assigning to each Boolean algebra, B, an invariant inv(B) ∈ In, where In is a set of triples from ℕ, such that two Boolean algebras have the same invariant if and only if they are elementarily equivalent. Moreover, given the invariant of a Boolean algebra, there is a computable procedure that decides its elementary theory. If we restrict our attention to dense Boolean algebras, these invariants determine the algebra up to isomorphism. In this paper we (...) analyze the complexity of the question "Does B have invariant x?" For each x ∈ In we define a complexity class Γx that could be either Σⁿ, Πⁿ, Σⁿ ∧ Πⁿ, or Πω+1 depending on x, and we prove that the set of indices for computable Boolean algebras with invariant x is complete for the class Γx. Analogs of many of these results for computably enumerable Boolean algebras were proven in earlier works by Selivanov. In a more recent work, he showed that similar methods can be used to obtain the results for computable ones. Our methods are quite different and give new results as well. As the algebras we construct to witness hardness are all dense, we establish new similar results for the complexity of various isomorphism problems for dense Boolean algebras. (shrink)

In this paper, we give a characterization of the strong degrees of categoricity of computable structures greater or equal to [Formula: see text]. They are precisely the treeable degrees — the least degrees of paths through computable trees — that compute [Formula: see text]. As a corollary, we obtain several new examples of degrees of categoricity. Among them we show that every degree [Formula: see text] with [Formula: see text] for [Formula: see text] a computable ordinal greater than [Formula: see (...) text] is the strong degree of categoricity of a rigid structure. Using quite different techniques we show that every degree [Formula: see text] with [Formula: see text] is the strong degree of categoricity of a structure. Together with the above example this answers a question of Csima and Ng. To complete the picture we show that there is a degree [Formula: see text] with [Formula: see text] that is not the degree of categoricity of a rigid structure. (shrink)

A Turing degree d is homogeneous bounding if every complete decidable (CD) theory has a d-decidable homogeneous model A, i.e., the elementary diagram De (A) has degree d. It follows from results of Macintyre and Marker that every PA degree (i.e., every degree of a complete extension of Peano Arithmetic) is homogeneous bounding. We prove that in fact a degree is homogeneous bounding if and only if it is a PA degree. We do this by showing that there is a (...) single CD theory T such that every homogeneous model of T has a PA degree. (shrink)

A real is called properly n-generic if it is n-generic but not n+1-generic. We show that every 1-generic real computes a properly 1-generic real. On the other hand, if m > n ≥ 2 then an m-generic real cannot compute a properly n-generic real.

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)

A strong degree of categoricity is a Turing degree [Formula: see text] such that there is a computable structure [Formula: see text] that is [Formula: see text]-computably categorical (there is a [Formula: see text]-computable isomorphism between any two computable copies of [Formula: see text]), and such that there exist two computable copies of [Formula: see text] between which every isomorphism computes [Formula: see text]. The question of whether every [Formula: see text] degree is a strong degree of categoricity has been (...) of interest since the first paper on this subject. We answer the question in the affirmative, by constructing an example. (shrink)

The terms of the upper and lower central series of a nilpotent computable group have computably enumerable Turing degree. We show that the Turing degrees of these terms are independent even when restricted to groups which admit computable orders.

We consider certain linear orders with a function on them, and discuss for which types of functions the resulting structure is or is not computably categorical. Particularly, we consider computable copies of the rationals with a fixed-point free automorphism, and also ω with a non-decreasing function.

When classes of structures are not first-order definable, we might still try to find a nice description. There are two common ways for doing this. One is to expand the language, leading to notions of pseudo-elementary classes, and the other is to allow infinite conjuncts and disjuncts. In this paper we examine the intersection. Namely, we address the question: Which classes of structures are both pseudo-elementary and ${\mathcal {L}}_{\omega _1, \omega }$ -elementary? We find that these are exactly the classes (...) that can be defined by an infinitary formula that has no infinitary disjunctions. (shrink)

A computable structure $\mathcal {A}$ is $\mathbf {x}$-computably categorical for some Turing degree $\mathbf {x}$ if for every computable structure $\mathcal {B}\cong\mathcal {A}$ there is an isomorphism $f:\mathcal {B}\to\mathcal {A}$ with $f\leq_{T}\mathbf {x}$. A degree $\mathbf {x}$ is a degree of categoricity if there is a computable structure $\mathcal {A}$ such that $\mathcal {A}$ is $\mathbf {x}$-computably categorical, and for all $\mathbf {y}$, if $\mathcal {A}$ is $\mathbf {y}$-computably categorical, then $\mathbf {x}\leq_{T}\mathbf {y}$. We construct a $\Sigma^{0}_{2}$ set whose degree (...) is not a degree of categoricity. We also demonstrate a large class of degrees that are not degrees of categoricity by showing that every degree of a set which is 2-generic relative to some perfect tree is not a degree of categoricity. Finally, we prove that every noncomputable hyperimmune-free degree is not a degree of categoricity. (shrink)

Anderson and Csima :245–264, 2014) defined a jump operator, the bounded jump, with respect to bounded Turing reducibility. They showed that the bounded jump is closely related to the Ershov hierarchy and that it satisfies an analogue of Shoenfield jump inversion. We show that there are high bounded low sets and low bounded high sets. Thus, the information coded in the bounded jump is quite different from that of the standard jump. We also consider whether the analogue of the (...) Jump Theorem holds for the bounded jump: do we have A≤bTB\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$A \le _{bT}B$$\end{document} if and only if Ab≤1Bb\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$A^b \le _1 B^b$$\end{document}? We show the forward direction holds but not the reverse. (shrink)

We define the bounded jump of $A$ by $A^{b}=\{x\in \omega \mid \exists i\leq x[\varphi_{i}\downarrow \wedge\Phi_{x}^{A\upharpoonright \!\!\!\upharpoonright \varphi_{i}}\downarrow ]\}$ and let $A^{nb}$ denote the $n$th bounded jump. We demonstrate several properties of the bounded jump, including the fact that it is strictly increasing and order-preserving on the bounded Turing degrees. We show that the bounded jump is related to the Ershov hierarchy. Indeed, for $n\geq2$ we have $X\leq_{bT}\emptyset ^{nb}\iff X$ is $\omega^{n}$-c.e. $\iff X\leq_{1}\emptyset ^{nb}$, extending the classical result that $X\leq_{bT}\emptyset '\iff (...) X$ is $\omega$-c.e. Finally, we prove that the analogue of Shoenfield inversion holds for the bounded jump on the bounded Turing degrees. That is, for every $X$ such that $\emptyset ^{b}\leq_{bT}X\leq_{bT}\emptyset ^{2b}$, there is a $Y\leq_{bT}\emptyset ^{b}$ such that $Y^{b}\equiv_{bT}X$. (shrink)

The $\Omega $ numbers—the halting probabilities of universal prefix-free machines—are known to be exactly the Martin-Löf random left-c.e. reals. We show that one cannot uniformly produce, from a Martin-Löf random left-c.e. real $\alpha $, a universal prefix-free machine U whose halting probability is $\alpha $. We also answer a question of Barmpalias and Lewis-Pye by showing that given a left-c.e. real $\alpha $, one cannot uniformly produce a left-c.e. real $\beta $ such that $\alpha - \beta $ is neither left-c.e. (...) nor right-c.e. (shrink)

Physicalism is thought to entail that mental properties supervene on microphysical properties, or in other words that all God had to do was to create the fundamental physical properties and the rest came along for free. In this paper, we question the all-god-had-to-do reflex.

This article provides a concise overview of the history of scholarship on solidarity in Europe and North America. While recent decades have seen an increase in conceptual and scholarly interest in solidarity in North America and other parts of the Anglo-Saxon world, the concept is much more strongly anchored in Europe. Continental European politics in particular have given rise to two of the most influential traditions of solidarity, namely, socialism and Christian ethics. Solidarity has also guided important public instruments and (...) institutions in Europe. Despite the much stronger affinity of continental European societies to solidaristic thinking, we argue that solidarity has much to offer for addressing societal challenges on both sides of the Atlantic and beyond. After proposing a working definition of solidarity that highlights its utility for guiding policy and practice, we give an example of how a solidarity-based perspective can shape instruments for the governance of data use. (shrink)

This book examines the birth of the scientific understanding of motion. It investigates which logical tools and methodological principles had to be in place to give a consistent account of motion, and which mathematical notions were introduced to gain control over conceptual problems of motion. It shows how the idea of motion raised two fundamental problems in the 5th and 4th century BCE: bringing together being and non-being, and bringing together time and space. The first problem leads to the exclusion (...) of motion from the realm of rational investigation in Parmenides, the second to Zeno's paradoxes of motion. Methodological and logical developments reacting to these puzzles are shown to be present implicitly in the atomists, and explicitly in Plato who also employs mathematical structures to make motion intelligible. With Aristotle we finally see the first outline of the fundamental framework with which we conceptualise motion today. (shrink)

When thought overwhelms the mind, the mind uses the body and the world. Several studies reveal ways that people alone or together use gesture and marks on paper to structure and augment their thought for comprehension, inference, and discovery. The studies show that the mapping of thought to gesture or the page is more direct than the arbitrary mapping to language and suggest that these forms of visual/spatial/action representation are used to “translate” language into mental representations. It is argued that (...) actions in space create patterns in the world that reflect abstractions, that the actions are incorporated into gestures and the patterns into diagrams, a network that integrates gesture, action, the designed world, and abstraction dubbed spraction. (shrink)

When thought overwhelms the mind, the mind uses the body and the world. Several studies reveal ways that people alone or together use gesture and marks on paper to structure and augment their thought for comprehension, inference, and discovery. The studies show that the mapping of thought to gesture or the page is more direct than the arbitrary mapping to language and suggest that these forms of visual/spatial/action representation are used to “translate” language into mental representations. It is argued that (...) actions in space create patterns in the world that reflect abstractions, that the actions are incorporated into gestures and the patterns into diagrams, a network that integrates gesture, action, the designed world, and abstraction dubbed spraction. (shrink)

Essays by Jurgen Habermas on truth, objectivity, normativity, naturalism, and realism after the linguistic turn.

Being White, Being Good focuses on white complicity and white complicity pedagogy. It examines the shifts in our conceptualization of the subject, language and moral responsibility that are required for understanding white complicity and draws out implications for social justice pedagogy.

This article argues that individuals paradigms have predominated social scientific explanations for gendered behavior in intimate relationships but that a microstructural paradigm adds necessary additional information. The results of a study designed to test the relative strengths of individualist and microstructural explanations for “mothering behavior” are presented. The microstructural hypothesis is that single fathers will adopt parental behavior that more closely resembles that of women who mother than that of married fathers. Parenting behaviors of single fathers, single mothers, married parents (...) with mothers at home, and married two-paycheck couples are compared. Overall, the hypothesis is supported. The article ends with a discussion of the implications of the microstructural perspective for social change in a feminist direction. (shrink)

An extended analysis and account of the psychological/social/cognitive dynamics of intellectual controversy. The immediate focus is the recurrent failure of intellectual engagement, in encounters having to do with with truth, knowledge, language, science, and/or objectivity, between, on the one hand, rationalist-realist-objectivist philosophers and/or those they have instructed and, on the other hand, constructivist-pragmatist ("postmodern") theorists and/or those persuaded by their critiques and/or alternative views. Individual chapters examine critiques and defenses of objectivist-rationalist views in law, politics, literary studies, ethics, communication theory, (...) and philosophy of science. Theorists whose views are discussed critically at some length include legal scholar Robin West and philosophers Jürgen Habermas, Karl-Otto Apel, and Philip Kitcher. (shrink)

There is a growing body of literature which argues that the two major theories of liberal citizenship (those of John Locke and J.S. Mill) were deeply enmeshed with both colonization (the processes by which the imperial state takes over the land and/or sovereignty of another country) and colonialism (the theoretical framework by which colonization is justified). This article, builds upon this literature but asks whether the existence of hundreds of domestic colonies within (as opposed to outside) the borders of Britain (...) and British settler states for citizens (as opposed to foreigners) at the turn of the twentieth century challenges the scope and definition of 'colonialism' in previous literature. Liberal colonialism, it is argued, seeks to transform those deemed to be 'idle', 'irrational' and/or custom bound, both at home and abroad, into 'industrious and rational' citizens. Domestically this meant housing the idle poor and mentally ill/disabled in labour and farm colonies, respectively in order to break them free through segregation from their bad customs/habits and teaching them, through education and agrarian labour, to become proper citizens. Ultimately, it is hoped that this analysis will help to explain how liberal states could come to embrace rather than reject within their own borders such deeply illiberal practises as segregation and assimilation against 'internal' others well into the twentieth century. (shrink)

Increasing attention is being paid to spirituality in nursing practice. Much of the literature on spiritual care uses the nursing process to describe this aspect of care. However, the use of the nursing process in the area of spirituality may be problematic, depending upon the understandings of the nature and intent of this process. Is it primarily a descriptive process meant to make visible the nursing actions to provide spiritual support, or is it a prescriptive process meant to guide nursing (...) actions for intervening in the spirituality of patients? A prescriptive nursing process approach implies influencing, and in some cases reframing, the spirituality of patients and thereby extends beyond general notions of spiritual support. In this paper we discuss four problematic assumptions that form the basis for a prescriptive approach to spiritual care. We conclude that this approach extends the nursing role beyond appropriate professional boundaries, making it ethically problematic. (shrink)

Forrest and Gross expose the scientific failure, the religious essence, and the political ambitions of "intelligent design" creationism. They examine the movement's "Wedge Strategy," which has advanced and is succeeding through public relations rather than through scientific research. Analyzing the content and character of "intelligent design theory," they highlight its threat to public education and to the separation of church and state.

Every day we are confronted with numerous alienating phenomena and equally alienating ways of dealing with them. The question is: How we can deal with them in a positive way? In his latest book, Bernhard Waldenfels powerfully demonstrates that it is not enough to only examine the otherness of the other if we disregard the stranger in ourselves. He argues for a responsive stance that dares to confront the uncanniness of our experience. How valuable this is—for psychiatric contexts, sociopolitical challenges (...) and also for philosophy itself—clearly shows in the contributions to this discursive volume, which attempt a response from their own perspectives. (shrink)

A rare systematic thinker, Habermas has furthered our understanding of modernity, social interaction and linguistic practice, societal institutions, rationality, morality, the law, globalization, and the role of religion in multicultural societies. He has helped shape discussions of truth, objectivity, normativity, and the relationship between the human and the natural sciences. This volume provides an accessible and comprehensive conceptual map of Habermas' theoretical framework and its key concepts, including the theory of communicative action, discourse ethics, his social-political philosophy and their applications (...) to contemporary issues. It will be an invaluable resource for both novice readers of Habermas and those interested in a more refined understanding of particular aspects of his work. (shrink)

Despite three major reform movements over the last 300 years, the mental health system has been remarkably resistant to change. Today, another period of reform is underway, only this time, new players - dissatisfied ex-psychiatric patients - are organizing to affect the process of change. This paper discusses characteristics of previous movements and examines their similarity to and difference from the present consumer and psychiatric survivor movement. It appears that the new participants have shaped the rhetoric of reform but it (...) remains to be seen if they can affect the reality. (shrink)