We study the complexity of the isomorphism relation on classes of computable structures. We use the notion of FF-reducibility introduced in [9] to show completeness of the isomorphism relation on many familiar classes in the context of all ${\mathrm{\Sigma }}_{1}^{1}$ equivalence relations on hyperarithmetical subsets of ω.

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)

On September 3, 2015, the Political Epistemology/ideas, Knowledge, and Politics section of the American Political Science Association sponsored a roundtable on epistemic democracy as part of the APSA’s annual meetings. Chairing the roundtable was Daniel Viehoff, Department of Philosophy, University of Sheffield. The other participants were Jack Knight, Department of Political Science and the Law School, Duke University; Hélène Landemore, Department of Political Science, Yale University; and Nadia Urbinati, Department of Political Science, Columbia University. We thank the participants for permission (...) to republish their remarks, which they edited for clarity after the fact. (shrink)

We give Scott sentences for certain computable groups, and we use index set calculations as a way of checking that our Scott sentences are as simple as possible. We consider finitely generated groups and torsion-free abelian groups of finite rank. For both kinds of groups, the computable ones all have computable \ Scott sentences. Sometimes we can do better. In fact, the computable finitely generated groups that we have studied all have Scott sentences that are “computable d-\” sentence and a (...) computable \ sentence). In [9], this was shown for the finitely generated free groups. Here we show it for all finitely generated abelian groups, and for the infinite dihedral group. Among the computable torsion-free abelian groups of finite rank, we focus on those of rank 1. These are exactly the additive subgroups of \. We show that for some of these groups, the computable \ Scott sentence is best possible, while for others, there is a computable d-\ Scott sentence. (shrink)

The role of imagery in encoding event-based prospective memories has yet to be fully clarified. Herein, it is argued that imagery augments a cue-to-context association that supports event-based prospective memory performance. By this account, imagery encoding not only improves prospective memory performance but also reduces interference to intention-related information that occurs outside of context. In the current study, when lure words occurred outside of the appropriate responding context, the use of imagery encoding strategies resulted in less interference when compared with (...) a standard event-based intention condition. This difference was eliminated when participants were not given a specific context to associate their intention . These results support a cue-to-context association account of how imagery operates in certain event-based prospective memory tasks. (shrink)

Inadequate diet is the leading risk factor for morbidity and mortality worldwide. However, approaches to identifying inadequate diets in clinical practice remain inconsistent, and dietary interventions frequently focus on facilitating ‘healthy choices’, with limited emphasis on structural constraints. We examine the ethical implications of introducing a routine question in the medical history about ability to access food. Not collecting data on food security means that clinicians are unable to identify people who may benefit from support on an individual level, unable (...) to consider relevant dietary risk factors for disease and disease progression and unable to monitor population trends and inequalities in dietary access in order to design effective policy interventions. We argue that the current lack of routine screening for food insecurity is inconsistent with our approach to other health behaviours, as well as with doctors’ frequent informal role as gatekeepers to the food aid system, and recent calls for governmental action on food insecurity and health inequalities from individual clinicians and professional bodies. Potential ethical barriers to asking patients about food security are addressed, including concerns about stigma, limiting autonomy, fair resource allocation, unclear professional remits and clinicians’ ability to offer effective interventions. We suggest that there is an ethical imperative for doctors to ask patients about their ability to access healthy food. Gathering this data provides a valuable first step in re-framing the social determinants of health as modifiable risks, rather than inevitable inequities. No data are available. (shrink)

For a computable structure 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}, there may not be a computable infinitary Scott sentence. When there is a computable infinitary Scott sentence φ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\varphi}$$\end{document}, then the complexity of the index set I\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${I}$$\end{document} is bounded by that of φ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\varphi}$$\end{document}. There are results giving “optimal” Scott sentences for (...) structures of various familiar kinds. These results have been driven by the thesis that the complexity of the index set should match that of an optimal Scott sentence. In this note, it is shown that the thesis does not always hold. For a certain subgroup of Q\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\mathbb{Q}}$$\end{document}, there is no computable d-Σ2\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\Sigma_2}$$\end{document} Scott sentence, even though the index set is d-Σ20\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\Sigma^0_2}$$\end{document}. (shrink)

Classification is an important goal in many branches of mathematics. The idea is to describe the members of some class of mathematical objects, up to isomorphism or other important equivalence, in terms of relatively simple invariants. Where this is impossible, it is useful to have concrete results saying so. In model theory and descriptive set theory, there is a large body of work showing that certain classes of mathematical structures admit classification while others do not. In the present paper, we (...) describe some recent work on classification in computable structure theory.Section 1 gives some background from model theory and descriptive set theory. From model theory, we give sample structure and non-structure theorems for classes that include structures of arbitrary cardinality. We also describe the notion of Scott rank, which is useful in the more restricted setting of countable structures. From descriptive set theory, we describe the basic Polish space of structures for a fixed countable language with fixed countable universe. We give sample structure and non-structure theorems based on the complexity of the isomorphism relation, and on Borel embeddings.Section 2 gives some background on computable structures. We describe three approaches to classification for these structures. The approaches are all equivalent. However, one approach, which involves calculating the complexity of the isomorphism relation, has turned out to be more productive than the others. Section 3 describes results on the isomorphism relation for a number of mathematically interesting classes—various kinds of groups and fields. In Section 4, we consider a setting similar to that in descriptive set theory. We describe an effective analogue of Borel embedding which allows us to make distinctions even among classes of finite structures. Section 5 gives results on computable structures of high Scott rank. Some of these results make use of computable embeddings. Finally, in Section 6, we mention some open problems and possible directions for future work. (shrink)

The first main result isolates some conditions which fail for the class of graphs and hold for the class of Abelian p-groups, the class of Abelian torsion groups, and the special class of "rank-homogeneous" trees. We consider these conditions as a possible definition of what it means for a class of structures to have "Ulm type". The result says that there can be no Turing computable embedding of a class not of Ulm type into one of Ulm type. We apply (...) this result to show that there is no Turing computable embedding of the class of graphs into the class of "rank-homogeneous" trees. The second main result says that there is a Turing computable embedding of the class of rank-homogeneous trees into the class of torsion-free Abelian groups. The third main result says that there is a "rank-preserving" Turing computable embedding of the class of rank-homogeneous trees into the class of Boolean algebras. Using this result, we show that there is a computable Boolean algebra of Scott rank ${\mathrm{\omega }}_{1}^{\mathrm{C}\mathrm{K}}$. (shrink)

Makkai [10] produced an arithmetical structure of Scott rank $\omega _{1}^{\mathit{CK}}$. In [9]. Makkai's example is made computable. Here we show that there are computable trees of Scott rank $\omega _{1}^{\mathit{CK}}$. We introduce a notion of "rank homogeneity". In rank homogeneous trees, orbits of tuples can be understood relatively easily. By using these trees, we avoid the need to pass to the more complicated "group trees" of [10] and [9]. Using the same kind of trees, we obtain one of rank (...) $\omega _{1}^{\mathit{CK}}$ that is "strongly computably approximable". We also develop some technology that may yield further results of this kind. (shrink)

For countable structure, "Scott rank" provides a measure of internal, model-theoretic complexity. For a computable structure, the Scott rank is at most [Formula: see text]. There are familiar examples of computable structures of various computable ranks, and there is an old example of rank [Formula: see text]. In the present paper, we show that there is a computable structure of Scott rank [Formula: see text]. We give two different constructions. The first starts with an arithmetical example due to Makkai, and (...) codes it into a computable structure. The second re-works Makkai's construction, incorporating an idea of Sacks. (shrink)

Russell Hardin produced a body of work of great breadth and richness on essential subjects of the social sciences and political and moral philosophy: collective action, trust, utilitarian ethics, groups and conflict, institutions, and knowledge. The volume of output, the engagement with cross-cutting fields of scholarship and myriad subjects, and his at-times conversational mode of analysis make a succinct encapsulation difficult. In this introduction, we give a brief account of three main areas of Hardin’s work: his distinctive take on the (...) moral and political philosophy of utilitarianism, his accounts of collective action and the nature of social life, and his account of the fundamental idea of trust and social capital. (shrink)

Shepherdson [14] showed that for a discrete ordered ring I, I is a model of IOpen iff I is an integer part of a real closed ordered field. In this paper, we consider integer parts satisfying PA. We show that if a real closed ordered field R has an integer part I that is a nonstandard model of PA (or even IΣ₄), then R must be recursively saturated. In particular, the real closure of I, RC (I), is recursively saturated. We (...) also show that if R is a countable recursively saturated real closed ordered field, then there is an integer part I such that R = RC(I) and I is a nonstandard model of PA. (shrink)

We extend results of Harizanov and Barker. For a relation R on a recursive structure /oA, we give conditions guaranteeing that the image of R in a recursive copy of /oA can be made to have arbitrary ∑α0 degree over Δα0. We give stronger conditions under which the image of R can be made ∑α0 degree as well. The degrees over Δα0 can be replaced by certain more general classes. We also generalize the Friedberg-Muchnik Theorem, giving conditions on a pair (...) of relations R and S under which the images of R and S can be made ∑α0 and independent over Δα0 in a recursive copy of /oA. (shrink)

For countable structure, "Scott rank" provides a measure of internal, model-theoretic complexity. For a computable structure, the Scott rank is at most [Formula: see text]. There are familiar examples of computable structures of various computable ranks, and there is an old example of rank [Formula: see text]. In the present paper, we show that there is a computable structure of Scott rank [Formula: see text]. We give two different constructions. The first starts with an arithmetical example due to Makkai, and (...) codes it into a computable structure. The second re-works Makkai's construction, incorporating an idea of Sacks. (shrink)

Much current work in the social sciences seeks to understand the effects of trust and social capital on economic and political outcomes. However, the sources of trust remain unclear. In this article, the authors articulate a basic theory of the relationship between institutions and trust. The authors apply this theory to industrial districts, geographically concentrated areas of small firm production, which involve extensive cooperation in the production process. Changes in power relations affect patterns of production;the authors suggest that they also (...) have knock-on consequences for trust and cooperation among actors. (shrink)

Let be a recursive structure, and let R be a recursive relation on . Harizanov isolated a syntactical condition which is necessary and sufficient for to have recursive copies in which the image of R is r.e. of arbitrary r.e. degree. We had conjectured that a certain extension of Harizanov's syntactical condition would be necessary and sufficient for to have recursive copies in which the image of R is ∑α0 of arbitrary ∑α0 degree, but this is not the case. Here (...) we give examples illustrating some restrictions on the possible ∑α0 degrees. In these examples, the image of R cannot be ∑α0 of degree d unless d possesses an “α-table”. (shrink)

Ash and Nerode [2] gave natural definability conditions under which a relation is intrinsically r. e. Here we generalize this to arbitrary levels in Ershov's hierarchy of Δmath image sets, giving conditions under which a relation is intrinsically α-r. e.

In [8], the third author defined a reducibility$\le _w^{\rm{*}}$that lets us compare the computing power of structures of any cardinality. In [6], the first two authors showed that the ordered field of reals${\cal R}$lies strictly above certain related structures. In the present paper, we show that$\left \equiv _w^{\rm{*}}{\cal R}$. More generally, for the weak-looking structure${\cal R}$ℚconsisting of the real numbers with just the ordering and constants naming the rationals, allo-minimal expansions of${\cal R}$ℚare equivalent to${\cal R}$. Using this, we show that (...) for any analytic functionf,$\left \equiv _w^{\rm{*}}{\cal R}$. $is noto-minimal.). (shrink)

§0. Introduction. In [16], Barwise described his graduate study at Stanford. He told of his interactions with Kreisel and Scott, and said how he chose Feferman as his advisor. He began working on admissible fragments of infinitary logic after reading and giving seminar talks on two Ph.D. theses which had recently been completed: that of Lopez-Escobar, at Berkeley, on infinitary logic [46], and that of Platek [58], at Stanford, on admissible sets.Barwise's work on infinitary logic and admissible sets is described (...) in his thesis [4], the book [13], and papers [5]—[16]. We do not try to give a systematic review of these papers. Instead, our goal is to give a coherent introduction to infinitary logic and admissible sets. We describe results of Barwise, of course, because he did so much. In addition, we mention some more recent work, to indicate the current importance of Barwise's ideas. Many of the central results are stated without proof, but occasionally we sketch a proof, to indicate how the ideas fit together.Chapters 1 and 2 describe infinitary logic and admissible sets at the time Barwise began his work, circa 1965. From Chapter 3 on, we survey the developments that took place after Barwise appeared on the scene.§1. Background on infinitary logic. In this chapter, we describe the situation in infinitary logic at the time that Barwise began his work. We need some terminology. By a vocabulary, we mean a set L of constant symbols, and relation and operation symbols with finitely many argument places. As usual, by an L-structureM, we mean a universe set M with an interpretation for each symbol of L. (shrink)

There is a Turing computable embedding $\Phi $ of directed graphs $\mathcal {A}$ in undirected graphs. Moreover, there is a fixed tuple of formulas that give a uniform effective interpretation; i.e., for all directed graphs $\mathcal {A}$, these formulas interpret $\mathcal {A}$ in $\Phi $. It follows that $\mathcal {A}$ is Medvedev reducible to $\Phi $ uniformly; i.e., $\mathcal {A}\leq _s\Phi $ with a fixed Turing operator that serves for all $\mathcal {A}$. We observe that there is a graph G (...) that is not Medvedev reducible to any linear ordering. Hence, G is not effectively interpreted in any linear ordering. Similarly, there is a graph that is not interpreted in any linear ordering using computable $\Sigma _2$ formulas. Any graph can be interpreted in a linear ordering using computable $\Sigma _3$ formulas. Friedman and Stanley [4] gave a Turing computable embedding L of directed graphs in linear orderings. We show that there is no fixed tuple of $L_{\omega _1\omega }$ -formulas that, for all G, interpret the input graph G in the output linear ordering $L$. Harrison-Trainor and Montalbán [7] have also shown this, by a quite different proof. (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)

The activity of wildlife viewing rests on an underlying contradiction. Wild animals are generally human-averse; they avoid humans and respond to human encounters by fleeing and retreating to cover. One would therefore expect human viewing of wild animals to be at best unpredictable, intermittent, and fleeting. Yet in recent decades, wildlife viewing has become a major recreational activity for millions of people around the world and has emerged as a thriving commercial industry. How can these two things—widespread wildlife intolerance of (...) humans and large-scale human observation of wildlife—be squared? The answer is that wild animals are only viewed on this scale because they have been made viewable through human intervention. This article examines two kinds of intervention—habituation and attraction—that change wildlife behavior toward humans and render hitherto elusive animals susceptible to regular, proximate, and protracted human viewing. (shrink)

This paper calculates, in a precise way, the complexity of the index sets for three classes of computable structures: the class $K_{\omega _{1}^{\mathit{CK}}}$ of structures of Scott rank $\omega _{1}^{\mathit{CK}}$ , the class $K_{\omega _{1}^{\mathit{CK}}+1}$ of structures of Scott rank $\omega _{1}^{\mathit{CK}}+1$ , and the class K of all structures of non-computable Scott rank. We show that I(K) is m-complete $\Sigma _{1}^{1},\,I(K_{\omega _{1}^{\mathit{CK}}})$ is m-complete $\Pi _{2}^{0}$ relative to Kleen's O, and $I(K_{\omega _{1}^{\mathit{CK}}+1})$ is m-complete $\Sigma _{2}^{0}$ relative to O.

This book reflects on the research and career of political theorist Russell Hardin from scholars of Political Science, Philosophy, Sociology, Economics, and Law, among other disciplines. Contributions address core issues of political theory as perceived by Hardin, starting with his insistence that many of the basic institutions of modern society and their formative historical beginnings can be understood as proceeding primarily from the self-interested motives of the participants. Many of the contributions in this volume struggle with the constraints imposed on (...) political theorizing by the idea of self-interested agents, or homo economicus. Some reject the idea as empirically unfounded. Others try to show that homo economicus is even more versatile than Hardin depicts. And yet others accept the constraints and work within them. But all pay tribute to the lasting intellectual contribution of Russell Hardin and the challenge he poses. The book should appeal to scholars and students interested in collective action, public choice and democracy, moral reasoning and its limits, constitutionalism, liberalism, conventions and coordination, trust, identity politics, social epistemology, and methods in politics philosophy. (shrink)

We study completely decomposable torsion-free abelian groups of the form $\mathcal{G}_S := \oplus_{n \in S} \mathbb{Q}_{p_n}$ for sets $S \subseteq \omega$. We show that $\mathcal{G}_S$has a decidable copy if and only if S is $\Sigma^0_2$and has a computable copy if and only if S is $\Sigma^0_3$.

Increasingly, the role of health research in improving the discrepancies in health outcomes between Indigenous and non-Indigenous populations in developed countries is being recognised. Along with this comes the recognition that health research must be conducted in a manner that is culturally appropriate and ethically sound. Two key documents have been produced in Australia, known as The Road Map and The Guidelines, to provide theoretical and philosophical direction to the ethics of Indigenous health research. These documents identify research themes considered (...) critical to improving the health of the nation’s Indigenous peoples. They also provide values that, from an Indigenous perspective, are foundational to an ethical research process. This paper examines these research themes and values within the context of a current longitudinal birth cohort study of Indigenous infants and children in south-west Sydney: the Gudaga Study. Considerable time and effort have been invested in being true to the values stated in these documents: reciprocity; respect; equality; responsibility; survival and protection; and spirit and integrity. We have learnt that it is vital to be true to these values when conducting Indigenous health research—to quite literally “walk the talk”. (shrink)