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)

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)

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)

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.

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)

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.

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 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)

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.

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)

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.

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 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)

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)

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)

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)

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.

This article contains an analysis of the concept of hospitality as defined in the thinking of Jacques Derrida, who applies the concept of an unsolvable aporia. Thinking about the ethics of hospitality takes place between the right hospitality described by Kant, and the decision to open up to the Other, revealing the infinite hospitality of ethics. Questions posed by Derrida result from a combination of two different traditions of thought: first, how to reconcile Kantian universal law with the particularity of (...) political thinking, and second, how to introduce unconditional hospitality into a project of global governance. The author traces the efforts made to intersect the Kantian universalism with Lévinas’s ethical vision. She also analyses how this hospitality may refer to the political practice that is governed by general laws. (shrink)

The aim of the present study, which involved preschool teachers, was to explore the area of working with musically gifted children. In particular, we focused on the identification of musically gifted children and monitoring of their musical development, preschool teachers’ competence for working with children, and evaluation of factors important for the development of musically gifted children. Research results showed that the majority of preschool teachers: were able to identify musically gifted children; rarely monitored and documented children’s musical development systematically (...) and did not acquire enough knowledge for working with musically gifted children during their formal and informal education. Among the important factors influencing the development of musically gifted children, preschool teachers pointed out motivation to work with musically gifted children, identification of musically gifted children, cooperation with music experts and parents, and implementation of additional musical activities. Cilj ovog istraživanja, koje je uključivalo odgojitelje u vrtiću, bio je istražiti područje rada s glazbeno nadarenom djecom. Posebno smo se usredotočili na otkrivanje glazbeno nadarene djece i praćenje njihovog glazbenog napretka, kompetencije odgojitelja za rad s djecom i procjenom čimbenika važnih za razvoj glazbeno nadarene djece. Rezultati istraživanja pokazali su da je većina odgojitelja: uspjela otkriti glazbeno nadarenu djecu; rijetko su sustavno pratili i dokumentirali glazbeni napredak djece i nisu stekli dovoljno znanja za rad s glazbeno nadarenom djecom tijekom svog formalnog i neformalnog obrazovanja. Među važnim čimbenicima koji utječu na razvoj glazbeno nadarene djece odgojitelji su istaknuli motivaciju za rad s glazbeno nadarenom djecom, otkrivanje glazbeno nadarene djece, suradnju s glazbenim stručnjacima i roditeljima te provedbu dodatnih glazbenih aktivnosti. (shrink)

In this essay we expand the notion of thinking by emphasizing the provocation and urgency to think and by reconceptualizing thinking as an embodied practice. The aim is to expand Lipman and Sharp’s approach to philosophical inquiry with children and show how other ways of thinking can be included. We strive to unfold a way of “thinking” that is both different from rationality (critical thinking) as well as from creative and caring thinking. In the first part of the paper, we (...) discuss the merits of Lipman and Sharp’s critical, creative and caring thinking within the Community of Philosophical Inquiry (CPI). We then expand Lipman/Sharp’s philosophical method through Ekkehart Marten’s Five-finger Model, which allows for different philosophical approaches. In the second half of the paper, we draw on Martin Heidegger’s What is called thinking? to develop his concept of the “call” to think together with its related notions of provocation and urgency. Building on this, we draw on Maurice Merleau-Ponty to show how this call is not an intellectual activity or mere exercise of the “mind” but rather affects our entire existence. As such, thinking becomes a response to an existential urgency that is an embodied practice. Using concepts like embodiment, affect, and sensibility, we try to widen our conception of thinking in a CPI. Finally, we hope this will allow facilitators to hear the unique voice of every child so that no one is left unheard. (shrink)

Music training is associated with enhanced executive function but little is known about the extent to which harmonic aspects of musical training are associated with components of executive function. In the current study, an array of cognitive tests associated with one or more components of executive function, was administered to young adult musicians and non-musicians. To investigate how harmonic aspects of musical training relate to executive function, a test of the ability to compose a four-part harmony was developed and administered (...) to musicians. We tested the working hypothesis that musicians would outperform non-musicians on measures of executive function, and that among musicians, the ability to harmonize would correlate positively with measures of executive function. Results indicate that musicians outperformed non-musicians on the Tower of London task, a measure of planning and problem-solving. Group differences were not detected on tasks more selective for inhibitory control, conflict resolution, or working memory. Among musicians, scores on the harmony assessment were positively correlated with performance of the Tower of London task. Taken together, the current results support a strong relationship between musicianship and planning and problem solving abilities, and indicate that the ability to harmonize is associated with components of executive function contributing to planning and problem solving. (shrink)

Este artículo rastrea los orígenes del choque de ideas que vertebra el debate que Michael Ruse y Robert J. Richards llevan a cabo en Debating Darwin. En esta obra, los autores discuten sobre el contexto sociocultural que alimentó la teoría de la evolución de Charles Darwin para reconocer las similitudes conceptuales que comparte con dicotomías clásicas sobre las formas humanística o científica de percibir e interpretar el mundo. El objetivo de este artículo es, pues, reflexionar, a la luz de las (...) tesis del desencantamiento del mundo y de la incidencia del conocimiento científico en las imágenes del mundo, sobre la raíz de la que brota el malestar cultural que fundamenta estas formas duales de percepción y descripción del mundo en la historia de las ideas: la supuesta incapacidad de la concepción científica del mundo para satisfacer impulsos estético-existenciales básicos de la naturaleza humana. (shrink)

In this essay I defend functional explanations in sociobiology against the charge that they are exercises in speculative story-telling. I distinguish proximate and ultimate biological functions, and discuss their role in functional explanations. I characterize functional explanations as a kind of "consequence explanation", and argue that sociobiologists need to justify a "functional fact" in addition to a "consequence law". Two methods used to supply evidence for functional hypotheses, the technique of optimality analyses and the comparative method, are discussed and illustrated (...) with examples. I argue that adequate evidence for hypothesis about the function of a trait can be provided by the method of comparison, but not by optimality analyses. The comparative method contains an inductive phase that provides independent warrant for, and so serves to establish the high probability of, functional hypotheses. Independent warrant cannot be provided by optimality analyses alone: the model-building approach itself mandates the sacrifice of the truth of a hypothesis to its predictive power. I conclude that while the sociobiologist may wish to employ the optimality analysis as a heuristic strategy, reliable functional explanations are better sought through the use of the comparative method. (shrink)

We argue that dominant research approaches concerning mental illness, which are centered on traditional categories of psychiatric classification as codified in the DSM-IV, have serious empirical, conceptual, and foundational problems. These problems have led to a classification scheme and body of research findings that provide a very poor map of the domain of mental illness, a map that, in turn, undermines clinical and research pursuits. We discuss some current efforts to respond to these problems and argue that the DSM-5 revision (...) process is not very promising, whereas the NIMH Research Domain Criteria initiative and some recent research in cognitive neuroscience fares better, although the latter remains potentially compromised by residual influences of the DSM-based approach. We conclude with some lessons and suggestions for the pursuit of alternative research pathways. (shrink)

Delivering high quality genomics-informed care to patients requires accurate test results whose clinical implications are understood. While other actors, including state agencies, professional organizations, and clinicians, are involved, this article focuses on the extent to which the federal agencies that play the most prominent roles — the Centers for Medicare and Medicaid Services enforcing CLIA and the FDA — effectively ensure that these elements are met and concludes by suggesting possible ways to improve their oversight of genomic testing.

Richard Rorty's rejection of prevailing interior-mirror understandings of the presumed relationship between “minds” and “nature,” along with his promotion of nonrepresentational accounts of knowledge, truth, and science, participates in a rich tradition of jointly pragmatist and constructivist views that spans the twentieth century. This contribution to the symposium “Whatever Happened to Richard Rorty?” considers Rorty's complex and ambivalent relation to that tradition, particularly to the work of his American pragmatist predecessors, William James and John Dewey, and to subsequent pragmatist-constructivist antirepresentationalism (...) in contemporary science and technology studies (STS) and “4E” (embodied, embedded, extended, enactive) cognitive theory. A final section on Nicholas Gaskill's contribution to the symposium questions his sense of Rorty's rhetorical recklessness and suggests that his worries over relativism, in Rorty's texts and more generally, are misplaced. (shrink)

Clinician scientists have gained institutional support in the era of translational research, as the key solution to closing the ‘translational gap’ between biomedical research and medical practice. However, clinician scientists remain an ‘endangered species’ in search of a secure niche, while new grants and training programs attempt to counteract their measurable decline in numbers over the past decades. Our study asks how an occupational space for clinician scientists is currently situated between the politics of translation, professional dynamics, and the specialization (...) of academic disciplines. We interviewed clinician scientists, their adjacent professions—clinicians and biomedical researchers—, and contrast their views with expectations from the discourse on clinician scientists in the biomedical and policy literature. We identify professionalizable work and tasks that relate to, first, being able to speak the two languages of both clinic and research, second, translating patients’ needs and clinical experience for further research, and third, counteracting the trends towards specialization by providing an inclusive point of view. We find that clinician scientists are overburdened with fulfilling a hybrid role of simultaneously being clinicians and scientists. Based on these findings, we suggest a path for the future professional development of clinician scientists towards the role of a translator. (shrink)

Understanding what numbers are means knowing several things. It means knowing how counting relates to numbers (called the cardinal principle or cardinality); it means knowing that each number is generated by adding one to the previous number (called the successor function or succession), and it means knowing that all and only sets whose members can be placed in one-to-one correspondence have the same number of items (called exact equality or equinumerosity). A previous study (Sarnecka & Carey, 2008) linked children's understanding (...) of cardinality to their understanding of succession for the numbers five and six. This study investigates the link between cardinality and equinumerosity for these numbers, finding that children either understand both cardinality and equinumerosity or they understand neither. This suggests that cardinality and equinumerosity (along with succession) are interrelated facets of the concepts five and six, the acquisition of which is an important conceptual achievement of early childhood. (shrink)