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.

It is natural to wish to study miniaturisations of Cohen forcing suitable to sets of low arithmetic complexity. We consider extensions of the work of Schaeffer [9] and Jockusch and Posner [6] by looking at genericity notions within the Δ2 sets. Different equivalent characterisations of 1-genericity suggest different ways in which the definition might be generalised. There are two natural ways of casting the notion of 1-genericity: in terms of sets of strings and in terms of density functions, as we (...) will see here. While these definitions coincide at the first level of the difference hierarchy, they turn out to differ at other levels. Furthermore, these differences remain when the remainder of the Δ02 sets are considered. While the string characterization of 1-genericity collapses at the second level of the difference hierarchy to 2-genericity, the density function definition gives a very interesting hierarchy at level w and above. Both of these results point towards the deep similarities exhibited by the n-c.e. degrees for n ≥ 2. (shrink)

The topological arithmetical hierarchy is the effective version of the Borel hierarchy. Its class Δta 2 is just large enough to include several types of pointsets in Euclidean spaces ℝ k which are fundamental in computable analysis. As a crossbreed of Hausdorff's difference hierarchy in the Borel class ΔB 2 and Ershov's hierarchy in the class Δ0 2 of the arithmetical hierarchy, the Hausdorff-Ershov hierarchy introduced in this paper gives a powerful classification within (...) Δta 2. This is based on suitable characterizations of the sets from Δta 2 which are obtained in a close analogy to those of the ΔB 2 sets as well as those of the Δ0 2 sets. A helpful tool in dealing with resolvable sets is contributed by the technique of depth analysis. On this basis, the hierarchy properties, in particular the strict inclusions between classes of different levels, can be shown by direct constructions of witness sets. The Hausdorff-Ershov hierarchy runs properly over all constructive ordinals, in contrast to Ershov's hierarchy whose denotation-independent version collapses at level ω 2. Also, some new characterizations of concepts of decidability for pointsets in Euclidean spaces are presented. (shrink)

Let a be a Kleene's ordinal notation of a nonzero computable ordinal. We give a sufficient condition on a, so that for every \documentclass{article}\usepackage{amssymb}\begin{document}\pagestyle{empty}$\Sigma ^{-1}_a$\end{document}‐computable family of two embedded sets, i.e., two sets A, B, with A properly contained in B, the Rogers semilattice of the family is infinite. This condition is satisfied by every notation of ω; moreover every nonzero computable ordinal that is not sum of any two smaller ordinals has a notation that satisfies this condition. On the (...) other hand, we also give a sufficient condition on a, that yields that there is a \documentclass{article}\usepackage{amssymb}\begin{document}\pagestyle{empty}$\Sigma ^{-1}_a$\end{document}‐computable family of two embedded sets, whose Rogers semilattice consists of exactly one element; this condition is satisfied by all notations of every successor ordinal bigger than 1, and by all notations of the ordinal ω + ω; moreover every computable ordinal that is sum of two smaller ordinals has a notation that satisfies this condition. We also show that for every nonzero n ∈ ω, or n = ω, and every notation a of a nonzero ordinal there exists a \documentclass{article}\usepackage{amssymb}\begin{document}\pagestyle{empty}$\Sigma ^{-1}_a$\end{document}‐computable family of cardinality n, whose Rogers semilattice consists of exactly one element. (shrink)

We present some characterizations of the members of Δta2, that class of the topological arithmetical hierarchy which is just large enough to include several fundamental types of sets of points in Euclidean spaces ℝk. The limit characterization serves as a basic tool in further investigations. The characterization by effective difference chains of effectively exhaustible sets yields only a hierarchy within a subfield of Δta2. Effective difference chains of transfinite (but constructive) order types, consisting of complements of effectively exhaustible (...) sets, as well as another closely related concept, yield a rich hierarchy within the whole class Δta2. The presentation always first reports analogies between Hausdorff's difference hierarchy within the Borel class ΔB2 and Ershov's hierarchy within the class Δ02 of the arithmetical hierarchy; after that the counterparts for Δta2 are developed. (© 2004 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim). (shrink)

Computability theory concerns information with a causal–typically algorithmic–structure. As such, it provides a schematic analysis of many naturally occurring situations. Emil Post was the first to focus on the close relationship between information, coded as real numbers, and its algorithmic infrastructure. Having characterised the close connection between the quantifier type of a real and the Turing jump operation, he looked for more subtle ways in which information entails a particular causal context. Specifically, he wanted to find simple relations on reals (...) which produced richness of local computability-theoretic structure. To this extent, he was not just interested in causal structure as an abstraction, but in the way in which this structure emerges in natural contexts. Post’s programme was the genesis of a more far reaching research project. In this article we will firstly review the history of Post’s programme, and look at two interesting developments of Post’s approach. The first of these developments concerns the extension of the core programme, initially restricted to the Turing structure of the computably enumerable sets of natural numbers, to the Ershov hierarchy of sets. The second looks at how new types of information coming from the recent growth of research into randomness, and the revealing of unexpected new computability-theoretic infrastructure. We will conclude by viewing Post’s programme from a more general perspective. We will look at how algorithmic structure does not just emerge mathematically from information, but how that emergent structure can model the emergence of very basic aspects of the real world. (shrink)

The computability of reals was introduced by Alan Turing [20] by means of decimal representations. But the equivalent notion can also be introduced accordingly if the binary expansion, Dedekind cut or Cauchy sequence representations are considered instead. In other words, the computability of reals is independent of their representations. However, as it is shown by Specker [19] and Ko [9], the primitive recursiveness and polynomial time computability of the reals do depend on the representation. In this paper, we explore how (...) the weak computability of reals depends on the representation. To this end, we introduce three notions of weak computability in a way similar to the Ershov's hierarchy of Δ02-sets of natural numbers based on the binary expansion, Dedekind cut and Cauchy sequence, respectively. This leads to a series of classes of reals with different levels of computability. We investigate systematically questions as on which level these notions are equivalent. We also compare them with other known classes of reals like c. e. and d-c. e. reals. (shrink)

It is shown that the classes of discrete parts, A ∩ ℕk, of approximately resp. weakly decidable subsets of Euclidean spaces, A ⊆ ℝk, coincide and are equal to the class of ω-r. e. sets which is well-known as the first transfinite level in Ershov's hierarchy exhausting Δ02.

Computability theory concerns information with a causal–typically algorithmic–structure. As such, it provides a schematic analysis of many naturally occurring situations. Emil Post was the first to focus on the close relationship between information, coded as real numbers, and its algorithmic infrastructure. Having characterised the close connection between the quantifier type of a real and the Turing jump operation, he looked for more subtle ways in which information entails a particular causal context. Specifically, he wanted to find simple relations on reals (...) which produced richness of local computability-theoretic structure. To this extent, he was not just interested in causal structure as an abstraction, but in the way in which this structure emerges in natural contexts. Post’s programme was the genesis of a more far reaching research project. In this article we will firstly review the history of Post’s programme, and look at two interesting developments of Post’s approach. The first of these developments concerns the extension of the core programme, initially restricted to the Turing structure of the computably enumerable sets of natural numbers, to the Ershov hierarchy of sets. The second looks at how new types of information coming from the recent growth of research into randomness, and the revealing of unexpected new computability-theoretic infrastructure. We will conclude by viewing Post’s programme from a more general perspective. We will look at how algorithmic structure does not just emerge mathematically from information, but how that emergent structure can model the emergence of very basic aspects of the real world. (shrink)

We present some characterizations of the members of Δta2, that class of the topological arithmetical hierarchy which is just large enough to include several fundamental types of sets of points in Euclidean spaces ℝk. The limit characterization serves as a basic tool in further investigations. The characterization by effective difference chains of effectively exhaustible sets yields only a hierarchy within a subfield of Δta2. Effective difference chains of transfinite order types, consisting of complements of effectively exhaustible sets, as (...) well as another closely related concept, yield a rich hierarchy within the whole class Δta2. The presentation always first reports analogies between Hausdorff's difference hierarchy within the Borel class ΔB2 and Ershov's hierarchy within the class Δ02 of the arithmetical hierarchy; after that the counterparts for Δta2 are developed. (shrink)

Lachlan observed that any nonzero d.c.e. degree bounds a nonzero c.e. degree. In this paper, we study the c.e. predecessors of d.c.e. degrees, and prove that given a nonzero d.c.e. degree , there is a c.e. degree below and a high d.c.e. degree such that bounds all the c.e. degrees below . This result gives a unified approach to some seemingly unrelated results. In particular, it has the following two known theorems as corollaries: there is a low c.e. degree isolating (...) a high d.c.e. degree [S. Ishmukhametov, G. Wu, Isolation and the high/low hierarchy, Arch. Math. Logic 41 259–266]; there is a high d.c.e. degree bounding no minimal pairs [C.T. Chong, A. Li, Y. Yang, The existence of high nonbounding degrees in the difference hierarchy, Ann. Pure Appl. Logic 138 31–51]. (shrink)

We examine the effective categoricity of equivalence structures via Ershov's difference hierarchy. We explore various kinds of categoricity available by distinguishing three different notions of isomorphism available in this hierarchy. We prove several results relating our notions of categoricity to computable equivalence relations: for example, we show that, for such relations, computable categoricity is equivalent to our notion of weak ω-c.e. categoricity, and that $\Delta _2^0 $ -categoricity is equivalent to our notion of graph-ω-c.e. categoricity.

The article deals with the problem of the cyclical nature of socio-historical development. Cyclicity is positioned as a universal feature of social development, making it possible to use the “lessons of history” in forecasting the future. Particular attention is paid to analyzing the causes of chronic disruptions in Russia’s modernization. The specificity of the Russian history cyclical nature is seen in the action of the institutional matrix, which unites authoritarianism and the suppression of private property into a monolithic whole.

It is the focus of this paper to tackle the topic of how consumers affect their surrounding environment and, more specifically, how they can affect animal welfare. Through comparisons with the Darwinist survivalist consumption habits and Maslow´s hierarchy, our modern society´s needs and habits are evaluated. Finally a Utilitarian approach, with the goal of the rise of the conscious consumer, is suggested for our so-called advanced societies.

The aim of this talk/paper is to briefly describe the influences on a human being that result in the feelings of helplessness, selfish attachment to objects and/or people, indifference, and a tendency to seek refuge in political, corporate, or religious hierarchies. Man as a social being is today faced with a situation of having to realize his or her personality within a “sick society” that neglects its members and overemphasizes hierarchical structures. The paper also aims at detecting the impact of (...) the media on the production of depressive passivity that prevents empathy and creates a “prison without walls.” A special dimension of the presentation has been to connect Freud’s interpretation of narcissism with the contemporary spread of this phenomenon due to the powerful influence of modern mass media. Narcissism as a phenomenon goes beyond the field of psychology and becomes a kind of behavioural matrix that can have far-reaching effects on all dimensions and forms of organizing social communities. (shrink)

We empirically tested Hemelrijk’s agent-based model, in which dyadic agonistic interaction between primate-group subjects determines their spatial distribution and whether or not the dominant subject has a central position with respect to the other subjects. We studied a group of captive red-capped mangabeys that met the optimal conditions for testing this model. We analyzed the spatial distribution of the subjects in relation to their rank in the dominance hierarchy and the results confirmed the validity of this model. In accordance (...) with Hemelrijk’s model, the group studied showed an ambiguity-reducing strategy that led to non-central spatial positioning on the part of the dominant subject, thus confirming the model indirectly. Nevertheless, for the model to be confirmed directly, the group has to adopt a risk-sensitive strategy so that observers can study whether dominant subjects develop spatial centrality. Our study also demonstrated that agent-based models are a good tool for the study of certain complex behaviors observed in primates because these explanatory models can help formulate suggestive hypotheses for exploring new lines of research in primatology. Keywords: Dominance-hierarchy rank; spatial distribution;Cercocebus torquatus; agent-based models. (shrink)

A British coffee chain’s fundraising practices constitute a background for this study to examine ideological discourses behind British charitable giving. The charity executes projects in coffee growing communities by providing education for children in disadvantaged neighbourhoods. The study takes a critical stance from a discursive paradigmatic perspective to analyse visual contents used by the charity. The applied visual critical discourse analysis was inspired by Barthes’ semiotic theory. Findings suggest that the adverts’ interpretative repertoires can serve ideologies that sustain the donors’ (...) social-cultural dominance over the recipients by justifying group-based social hierarchies. The chains of signifiers do not question the spectators’ moral position but rationalise status quo and maintain undisturbed consumption. Findings suggest the possibility that the discourses of prosocial behaviour incited under consuming conditions do not challenge but may even justify global inequality. This finding presents challenges facing charitable organisations balancing their work within wider commercial and cultural contexts. (shrink)

We empirically tested Hemelrijk's agent-based model, in which dyadic agonistic interaction between primate-group subjects determines their spatial distribution and whether or not the dominant subject has a central position with respect to the other subjects. We studied a group of captive red-capped mangabeys that met the optimal conditions for testing this model. We analyzed the spatial distribution of the subjects in relation to their rank in the dominance hierarchy and the results confirmed the validity of this model. In accordance (...) with Hemelrijk's model, the group studied showed an ambiguity-reducing strategy that led to non-central spatial positioning on the part of the dominant subject, thus confirming the model indirectly. Nevertheless, for the model to be confirmed directly, the group has to adopt a risk-sensitive strategy so that observers can study whether dominant subjects develop spatial centrality. Our study also demonstrated that agent-based models are a good tool for the study of certain complex behaviors observed in primates because these explanatory models can help formulate suggestive hypotheses for exploring new lines of research in primatology. Keywords: Dominance-hierarchy rank; spatial distribution; Cercocebus torquatus ; agent-based models. (shrink)

Cause and effect relationships play a central role in how we perceive and make sense of the world around us, how we act upon it, and ultimately, how we understand ourselves. Almost two decades ago, computer scientist Judea Pearl made a breakthrough in understanding causality by discovering and systematically studying the “Ladder of Causation” [Pearl and Mackenzie 2018], a framework that highlights the distinct roles of seeing, doing, and imagining. In honor of this landmark discovery, we name this the Pearl (...) Causal Hierarchy (PCH). In this chapter, we develop a novel and comprehensive treatment of the PCH through two complementary lenses, one logical-probabilistic and another inferential-graphical. Following Pearl’s own presentation of the hierarchy, we begin by showing how the PCH organically emerges from a well-specified collection of causal mechanisms (a structural causal model, or SCM). We then turn to the logical lens. Our first result, the Causal Hierarchy Theorem (CHT), demonstrates that the three layers of the hierarchy almost always separate in a measure theoretic sense. Roughly speaking, the CHT says that data at one layer virtually always underdetermines information at higher layers. Since in most practical settings the scientist does not have access to the precise form of the underlying causal mechanisms – only to data generated by them with respect to some of PCH’s layers – this motivates us to study inferences within the PCH through the graphical lens. Specifically, we explore a set of methods known as causal inference that enable inferences bridging PCH’s layers given a partial specification of the SCM. For instance, one may want to infer what would happen had an intervention been performed in the environment (second-layer statement) when only passive observations (first-layer data) are available. We introduce a family of graphical models that allows the scientist to represent such a partial specification of the SCM in a cognitively meaningful and parsimonious way. Finally, we investigate an inferential system known as docalculus, showing how it can be sufficient, and in many cases necessary, to allow inferences across PCH’s layers. We believe that connecting with the essential dimensions of human experience as delineated by the PCH is a critical step towards creating the next generation of AI systems that will be safe, robust, human-compatible, and aligned with the social good. (shrink)

Atran argues that an autonomous ethnobiological information-processing module exists. This module imputes a “deep causal essence” to folk-biological taxa and uses a hierarchy of taxonomic ranks. I argue that Atran's own data suggest that rank is not an essential feature of the ethnobiological module, and that ethnobiological causal essences may be generalized to other domains and vice versa, limiting its autonomy.

A hypothesis on the evolutionary origin of the genetic pathway of sex determination in the nematode Caenorhabditis elegans is presented here. It is suggested that the pathway arose in steps, driven by frequency‐dependent selection for the minority sex at each step, and involving the sequential acquisition of dominant negative, neomorphic genetic switches, each one reversing the action of the previous one. A central implication is that the genetic pathway evolved in reverse order from the final step in the hierarchy (...) up to the first. The possible applicability of the model to the other well‐characterized sex determination pathway, that of Drosophila melanogaster, and to sex determination in mammals, is discussed, along with some potential implications for pathway evolution in general. Finally, the specific molecular and population genetic questions that the model raises are described and some tests are proposed. (shrink)

In his 1953's paper, Grzegorczyk proved that a certain kind of relation classes of Grzegorczyk's hierarchy could be characterized inductively. We give a simpler version of this characterization.

We empirically tested Hemelrijk’s agent-based model, in which dyadic agonistic interaction between primate-group subjects determines their spatial distribution and whether or not the dominant subject has a central position with respect to the other subjects. We studied a group of captive red-capped mangabeys that met the optimal conditions for testing this model. We analyzed the spatial distribution of the subjects in relation to their rank in the dominance hierarchy and the results confirmed the validity of this model. In accordance (...) with Hemelrijk’s model, the group studied showed an ambiguity-reducing strategy that led to non-central spatial positioning on the part of the dominant subject, thus confirming the model indirectly. Nevertheless, for the model to be confirmed directly, the group has to adopt a risk-sensitive strategy so that observers can study whether dominant subjects develop spatial centrality. Our study also demonstrated that agent-based models are a good tool for the study of certain complex behaviors observed in primates because these explanatory models can help formulate suggestive hypotheses for exploring new lines of research in primatology. Keywords: Dominance-hierarchy rank; spatial distribution; Cercocebus torquatus; agent-based models. (shrink)

We investigate a new paradigm in the context of learning in the limit, namely, learning correction grammars for classes of computably enumerable (c.e.) languages. Knowing a language may feature a representation of it in terms of two grammars. The second grammar is used to make corrections to the first grammar. Such a pair of grammars can be seen as a single description of (or grammar for) the language. We call such grammars correction grammars. Correction grammars capture the observable fact that (...) people do correct their linguistic utterances during their usual linguistic activities. We show that learning correction grammars for classes of c.e. languages in the TxtEx-model (i.e., converging to a single correct correction grammar in the limit) is sometimes more powerful than learning ordinary grammars even in the TxtBe-model (where the learner is allowed to converge to infinitely many syntactically distinct but correct conjectures in the limit). For each n ≥ 0, there is a similar learning advantage, again in learning correction grammars for classes of c.e. languages, but where we compare learning correction grammars that make n + 1 corrections to those that make n corrections. The concept of a correction grammar can be extended into the constructive transfinite, using the idea of counting-down from notations for transfinite constructive ordinals. This transfinite extension can also be conceptualized as being about learning Ershov-descriptions for c.e. languages. For u a notation in Kleene's general system $(O,\, < _o )$ of ordinal notations for constructive ordinals, we introduce the concept of an u-correction grammar, where u is used to bound the number of corrections that the grammar is allowed to make. We prove a general hierarchy result: if u and v are notations for constructive ordinals such that $u\, < _o \,v$ , then there are classes of c.e. languages that can be TxtEx-learned by conjecturing v-correction grammars but not by conjecturing u-correction grammars. Surprisingly, we show that— above "ω-many" corrections—it is not possible to strengthen the hierarchy: TxtEx-learning u-correction grammars of classes of c.e. languages, where u is a notation in O for any ordinal, can be simulated by TxtBe-learning ω-correction grammars, where ω is any notation for the smallest infinite ordinal ω. (shrink)

In this paper we present a new hierarchy of analytical tableaux systems TNDC n, 1≤nhierarchy of propositional paraconsistent logics Cn, 1≤n (...) n, 1≤nhierarchy Cn, 1≤nshrink)

In this paper we present a new hierarchy of analytical tableaux systems TNDC n, 1≤n<ω, for da Costa's hierarchy of propositional paraconsistent logics Cn, 1≤n<ω. In our tableaux formulation, we introduce da Costa's “ball” operator “o”, the generalized operators “k” and “(k)”, for 1≤k, and the negations “~k”, for k≥1, as primitive operators, differently to what has been done in the literature, where these operators are usually defined operators. We prove a version of Cut Rule for the TNDC (...) n, 1≤n<ω, and also prove that these systems are logically equivalent to the corresponding systems Cn, 1≤n<ω. The systems TNDC n constitute completely automated theorem proving systems for the systems of da Costa's hierarchy Cn, 1≤n<ω. (shrink)

It is well known that Frege was an extensionalist, in the following sense: he held that the truth-value of a sentence is always a function only of the references of its parts. One consequence of this view is that expressions occurring in certain linguistic contexts – for example, the that-clauses of propositional attitude ascriptions – do not have their usual references, but refer instead to what are usually their senses. But although a number of philosophers have objected to this result, (...) no one has yet attempted to see what happens to Frege's views – and, in particular, to his theory of sense and reference – if his extensionalism is abandoned while his other views are maintained. This paper thus does two things. First, it clears the way for such an attempt, by arguing that recent defences of Frege's extensionalism – by Tyler Burge, Saul Kripke, Terence Parsons and Christopher Peacocke – fall short. Second, it sketches a positive proposal for a non-extensionalist application of Frege's theory of sense and reference to sentences of indirect discourse and ascriptions of propositional attitude. (shrink)

Hay and, then, Johnson extended the classic Rice and Rice-Shapiro Theorems for computably enumerable sets, to analogs for all the higher levels in the finite Ershov Hierarchy. The present paper extends their work to analogs in the transfinite Ershov Hierarchy. Some of the transfinite cases are done for all transfinite notations in Kleene's important system of notations, equation image. Other cases are done for all transfinite notations in a very natural, proper subsystem equation image of equation image, where (...) equation image has at least one notation for each constructive ordinal. In these latter cases it is open as to what happens for the entire set of transfinite notations in equation image. (shrink)

The Turing degrees of infinite levels of the Ershov hierarchy were studied by Liu and Peng [8]. In this paper, we continue the study of Turing degrees of infinite levels and lift the study of density property to the levels beyond ω2. In doing so, we rely on notations with some nice properties. We introduce the concept of normalizing notations and generate normalizing notations for higher levels. The generalizations of the weak density theorem and the nondensity theorem are proved (...) for higher levels in the Ershov hierarchy. Furthermore, we also investigate the minimal degrees in the infinite levels of the Ershov hierarchy. (shrink)

We classify the asymptotic densities of the sets according to their level in the Ershov hierarchy. In particular, it is shown that for, a real is the density of an n‐c.e. set if and only if it is a difference of left‐ reals. Further, we show that the densities of the ω‐c.e. sets coincide with the densities of the sets, and there are ω‐c.e. sets whose density is not the density of an n‐c.e. set for any.