We develop the concepts of recursively nowhere dense sets and sets that are recursively of first category and study closed sets of points in light of Baire's Category Theorem. Our theorems are primarily concerned with exdomains of recursive quantum functions and hence with avoidable points . An avoidance function is a recursive function which can be used to expel avoidable points from domains of recursive quantum functions. We define an avoidable set of points to be an arbitrary (...) subset of the avoidable points of a single avoidance function, and we study an effective union of such sets which we call a piecemeal avoidable set. We note that each of ‘the set of recursive points’ and ‘the set of avoidable points’ is of first category but not recursively of first category. We show an exdomain exists which is recursively nowhere dense, as well as one that is nowhere dense but not recursively nowhere dense. After establishing that every exdomain is recursively of first category, we prove that given any fixed exdomain, there is another exdomain, which while dense in the underlying space, is disjoint from the fixed exdomain. Finally, we show how to build a recursive sequence of recursive quantum functions that have mutually disjoint, dense exdomains. (shrink)

We study topological constructions in the recursion theoretic framework of the lattice of recursively enumerable open subsets of a topological space X. Various constructions produce complemented recursively enumerable open sets with additional recursion theoretic properties, as well as noncomplemented open sets. In contrast to techniques in classical topology, we construct a disjoint recursively enumerable collection of basic open sets which cannot be extended to a recursively enumerable disjoint collection of basic open sets whose union is dense in X.

We prove a recursion theoretic characterization of the Topological Vaught Conjecture in the Zermelo‐Fraenkel set theory by using tools from effective descriptive set theory and by revisiting the result of Miller that orbits in Polish G‐spaces are Borel sets.

In this paper we develop a point-free approach to the study of topological spaces and functions on them, establish platforms for both and present some findings on recursive points. In the first sections of the paper, we obtain conditions under which our approach leads to the generation of ideal objects with which mathematicians work. Next, we apply the effective version of our approach to the real numbers, and make exact connections to the classical approach to recursive reals. In (...) the succeeding sections of the paper, we introduce machinery to produce functions on topological spaces and find succinct conditions which will be effectivized in our sequel. (shrink)

In [5], Metakides and Nerode introduced the study of recursively enumerable substructures of a recursively presented structure. The main line of study presented in [5] is to examine the effective content of certain algebraic structures. In [6], Metakides and Nerode studied the lattice of r.e. subspaces of a recursively presented vector space. This lattice was later studied by Kalantari, Remmel, Retzlaff and Shore. Similar studies have been done by Metakides and Nerode [7] for algebraically closed fields, by Remmel [10] for (...) Boolean algebras and by Metakides and Remmel [8] and [9] for orderings. Kalantari and Retzlaff [4] introduced and studied the lattice of r.e. subsets of a recursively presented topological space. Kalantari and Retzlaff consideredX, a topological space with ⊿, a countable basis. This basis is coded into integers and with the help of this coding, r.e. subsets ofωgive rise to r.e. subsets ofX. The notion of “recursiveness” of a topological space is the natural next step which gives rise to the question of what should be the “degree” of an r.e. open subset ofX? It turns out that any r.e. open set partitions ⊿; into four sets whose Turing degrees become central in answering the question raised above.In this paper we show that the degrees of the elements of the partition of ⊿ imposed by an r.e. open set can be “controlled independently” in a sense to be made precise in the body of the paper. In [4], Kalantari and Retzlaff showed that givenAany r.e. set andany r.e. open subset ofX, there exists an r.e. open set ℋ which is a subset ofand is dense in and in whichAis coded. This shows that modulo a nowhere dense set, an r.e. open set can become as complicated as desired. After giving the general technical and notational machinery in §1, and giving the particulars of our needs in §2, in §3 we prove that the set ℋ described above could be made to be precisely of degree ofA. We then go on and establish various results on the mentioned partitioning of ⊿. One of the surprising results is that there are r.e. open sets such that every element of partitioning of ⊿ is of a different degree. Since the exact wording of the results uses the technical definitions of these partitioning elements, we do not summarize the results here and ask the reader to examine §3 after browsing through §§1 and 2. (shrink)

This paper is a culmination of our new foundations for recursive analysis through recursive topology as reported in Kalantari and Welch 125; 98 87). While in those papers we developed groundwork for an approach to point free analysis and applied recursion theory, in this paper we blend techniques of recursion theory with those of topology to establish new findings. We present several new techniques different from existing ones which yield interesting results. Incidental to our work is (...) a unifying explanation of various schools of study for recursive analysis. (shrink)

This paper is a sequel to our [7]. In that paper we constructed a Π1 0 tree of avoidable points. Here we construct a Π1 0 tree of shadow points. This tree is a tree of sharp filters, where a sharp filter is a nested sequence of basic open sets converging to a point. In the construction we assign to each basic open set on the tree an address in 2<ω. One interesting fact is that while our Π1 0 tree (...) of sharp filters (a subtree of Δ<ω) is isomorphic to the tree of addresses (a subtree of 2<ω), the tree of addresses is recursively enumerable but not recursive. To achieve this end we use a finite injury priority argument. (shrink)

Dynamic Topological Logic ( ) is a modal logic which combines spatial and temporal modalities for reasoning about dynamic topological systems , which are pairs consisting of a topological space X and a continuous function f : X → X . The function f is seen as a change in one unit of time; within one can model the long-term behavior of such systems as f is iterated. One class of dynamic topological systems where the long-term behavior of f is (...) particularly interesting is that of minimal systems ; these are dynamic topological systems which admit no proper, closed, f -invariant subsystems. In such systems the orbit of every point is dense, which within translates into a non-trivial interaction between spatial and temporal modalities. This interaction, however, turns out to make the logic simpler, and while s in general tend to be undecidable, interpreted over minimal systems we obtain decidability, although not in primitive recursive time; this is the main result that we prove in this paper. We also show that interpreted over minimal systems is incomplete for interpretations on relational Kripke frames and hence does not have the finite model property; however it does have a finite non-deterministic quasimodel property. Finally, we give a set of formulas of which characterizes the class of minimal systems within the class of dynamic topological systems, although we do not offer a full axiomatization for the logic. (shrink)

In this paper we continue our work of Kalantari and Welch . There we introduced machinery to produce a point-free approach to points and functions on topological spaces and found conditions for both which lend themselves to effectivization. While we studied recursive points in that paper, here, we present two useful classes of recursive functions on topological spaces, apply them to the reals, and find precise accounting for the nature of the properties of some examples that exist in (...) the literature. We end with a construction of a recursive function on a small subset of the unit interval which is strongly nonextendible. (shrink)

This paper is an investigation of definability hierarchies on effective topological spaces. An open subset U of an effective space X is definable iff there is a parameter free definition φ of U so that the atomic predicate symbols of φ are recursively open relations on X . The complexity of a definable open set may be identified with the quantifier complexity of its definition. For example, a set U is an ∃∃∀∃-set if it has an ∃∃∀∃ parameter free definition (...) using only recursively open predicate symbols. Since X is not equipped with a natural pairing apparatus such a U need not be an ∃∀∃-set. Let Σ denote the class of all ∃-sets, ∃∃-sets, ∃∃∃-sets etc. We show that an open set is in Σ iff it is equivalent modulo a nowhere dense set to a recursively enumerable open set . Thus Σ = e.r.e. Indeed we show the existence of a universal Σ -set as well as the existence of universal sets for higher levels of the definability hierarchy. (shrink)

We give an examination of the automorphism group Aut of a countable recursively saturated model M of PA. The main result is a characterisation of strong elementary initial segments of M as the initial segments consisting of fixed points of automorphisms of M. As a corollary we prove that, for any consistent completion T of PA, there are recursively saturated countable models M1, M2 of T, such that Aut[ncong]Aut, as topological groups with a natural topology. Other results include a (...) classification of the normal subgroups of Aut of the form [lcub]g: g [uharr] A = idA[rcub], for sets A M, and a highly homogeneous representation of Aut as a subgroup of Aut. (shrink)

We investigate connections between the syntactic and semantic distance of programs on an abstract, recursion theoretic level. For a certain rather restrictive notion of interdependency of the two kinds of distances, there remain only few and “unnatural” numberings allowing such close relationship. Weakening the requirements leads to the discovery of universal metrics such that for an arbitrary recursively enumerable family of functions a numbering compatible with such a metric can uniformly be constructed. We conclude our considerations with some implications on (...) learning theory. (shrink)

The recursion-theoretic study of mathematical structures other thanωis now a field of much activity. Analysis and algebra are two such structures which have been studied for their effective contents. Studies in analysis began with the work of Specker on nonconstructive proofs in analysis [16] and in Lacombe's inspiring notes on relevant notions of recursive analysis [8]. Studies in algebra originated in the work of Frolich and Shepherdson on effective extensions of explicit fields [1] and in Rabin's study of computable (...) fields [15]. Equipped with the richness of modern techniques in recursion theory, Metakides and Nerode [11]–[13] began investigating the effective content of vector spaces and fields; these studies have been extended by Kalantari, Remmel, Retzlaff, Shore and others.Kalantari and Retzlaff [5] began a foundational inquiry into effectiveness in topological spaces. They consider a topological spaceXwith a countable basis ⊿ for the topology. The space isfully effective, that is, the basis elements are coded intoωand the operation of intersection of basis elements and the relation of inclusion among them are both computable. Similar to, the lattice of recursively enumerable subsets ofω, the collection of r.e. open subsets ofXforms a latticeℒunder the usual operations of union and intersection. (shrink)

We formulate an abstract version of the finite injury method in the form of the Baire category theorem. The theorem has the following corollaries: The Friedberg-Muchnik pair of recursively enumerable degrees, the Sacks splitting theorem, the existence of a minimal degree below 0′ and the Shoenfield jump theorem.

Starting with D. Scott's work on the mathematical foundations of programming language semantics, interest in topology has grown up in theoretical computer science, under the slogan `open sets are semidecidable properties'. But whereas on effectively given Scott domains all such properties are also open, this is no longer true in general. In this paper a characterization of effectively given topological spaces is presented that says which semidecidable sets are open. This result has important consequences. Not only follows the classical (...) Rice-Shapiro Theorem and its generalization to effectively given Scott domains, but also a recursion theoretic characterization of the canonical topology of effectively given metric spaces. Moreover, it implies some well known theorems on the effective continuity of effective operators such as P. Young and the author's general result which in its turn entails the theorems by Myhill-Shepherdson, Kreisel-Lacombe-Shoenfield and Ceĭtin-Moschovakis, and a result by Eršov and Berger which says that the hereditarily effective operations coincide with the hereditarily effective total continuous functionals on the natural numbers. (shrink)

The n-th PowerSet is used in defining the SuperHyperOperation, SuperHyperAxiom, and their corresponding Neutrosophic SuperHyperOperation, Neutrosophic SuperHyperAxiom in order to build the SuperHyperAlgebra and Neutrosophic SuperHyperAlgebra. In general, in any field of knowledge, one in fact encounters SuperHyperStructures. Also, six new types of topologies have been introduced in the last years (2019-2022), such as: Refined Neutrosophic Topology, Refined Neutrosophic Crisp Topology, NeutroTopology, AntiTopology, SuperHyperTopology, and Neutrosophic SuperHyperTopology. Neutrosophic set has been derived from a new branch of philosophy, namely (...) Neutrosophy. Neutrosophic set is capable of dealing with uncertainty, indeterminacy and inconsistent information. Neutrosophic set approaches are suitable to modeling problems with uncertainty, indeterminacy and inconsistent information in which human knowledge is necessary, and human evaluation is needed. Neutrosophic set theory firstly proposed in 1998 by Florentin Smarandache, who also developed the concept of single valued neutrosophic set, oriented towards real world scientific and engineering applications. Since then, the single valued neutrosophic set theory has been extensively studied in books and monographs introducing neutrosophic sets and its applications, by many authors around the world. Also, an international journal - Neutrosophic Sets and Systems started its journey in 2013. This first volume collects original research and applications from different perspectives covering different areas of neutrosophic studies, such as decision-making, neutroalgebra, neutro metric, and some theoretical papers. (shrink)

We show that—unlike products of ‘transitive’ modal logics which are usually undecidable—their ‘expanding domain’ relativisations can be decidable, though not in primitive recursive time. In particular, we prove the decidability and the finite expanding product model property of bimodal logics interpreted in two-dimensional structures where one component—call it the ‘flow of time’—is • a finite linear order or a finite transitive tree and the other is composed of structures like • transitive trees/partial orders/quasi-orders/linear orders or only finite such structures (...) expanding over time. The decidability proof is based on Kruskal’s tree theorem, and the proof of non-primitive recursiveness is by reduction of the reachability problem for lossy channel systems. The result is used to show that the dynamic topological logic interpreted in topological spaces with continuous functions is decidable if the number of function iterations is assumed to be finite. (shrink)

Recursion or self-reference is a key feature of contemporary research and writing in semiotics. The paper begins by focusing on the role of recursion in poststructuralism. It is suggested that much of what passes for recursion in this field is in fact not recursive all the way down. After the paradoxical meaning of radical recursion is adumbrated, topology is employed to provide some examples. The properties of the Moebius strip prove helpful in bringing out the dialectical nature of (...) radical recursion. The Moebius is employed to explore the recursive interplay of terms that are classically regarded as binary opposites: identity and difference, object and subject, continuity and discontinuity, etc. To realize radical recursion in an even more concrete manner, a higher-dimensional counterpart of the Moebius strip is utilized, namely, the Klein bottle. The presentation concludes by enlisting phenomenological philosopher Maurice Merleau-Ponty’s concept of depth to interpret the Klein bottle’s extra dimension. (shrink)

Effective inseparability of pairs of sets is an important notion in logic and computer science. We study the effective inseparability of sets which appear as index sets of subsets of an effectively given topological T0-space and discuss its consequences. It is shown that for two disjoint subsets X and Y of the space one can effectively find a witness that the index set of X cannot be separated from the index set of Y by a recursively enumerable set, if X (...) intersects the topological closure of an effectively enumerable subset of Y. As a consequence of a more general parametric inseparability result a theorem of Rice-Shapiro type is obtained. Moreover, under some additional requirements it follows that nonopen subsets have productive index sets. This implies a generalized Rice theorem: Connected spaces have only trivial completely recursive subsets. As application some decision problems in computable analysis and domain theory are studied. It follows that the complement of the halting problem can be reduced to the problem to decide of a number whether it is a computable irrational. The same is true for the problems to decide whether two numbers are equal, whether one is not greater than the other, and whether a number is equal to a given number. In the case of an effectively given continuous complete partial order the complexity of the last problem depends on whether the given element is the smallest element, in which case the complement of the halting problem is reducible to it, whether it is a base element and maximal, then the decision problem is recursively isomorphic to the halting problem, or whether it is none of these. In this case, both the halting problem and its complement are reducible to the problem. The same is true in nontrivial cases for the problems whether an element belongs to the basis, whether two elements of the partial order are equal, or whether one approximates the other. In general, for any nonempty proper subset of the partial order either the halting problem or its complement can be reduced to the membership problem of the subset. (shrink)

Fine and Kripke extended S5, S4, S4.2 and such to produce propositionally quantified systems , , : given a Kripke frame, the quantifiers range over all the sets of possible worlds. is decidable and, as Fine and Kripke showed, many of the other systems are recursively isomorphic to second-order logic. In the present paper I consider the propositionally quantified system that arises from the topological semantics for S4, rather than from the Kripke semantics. The topological system, which I dub , (...) is strictly weaker than its Kripkean counterpart. I prove here that second-order arithmetic can be recursively embedded in . In the course of the investigation, I also sketch a proof of Fine's and Kripke's results that the Kripkean system is recursively isomorphic to second-order logic. (shrink)

We investigate computational properties of propositional logics for dynamical systems. First, we consider logics for dynamic topological systems (W.f), fi, where W is a topological space and f a homeomorphism on W. The logics come with ‘modal’ operators interpreted by the topological closure and interior, and temporal operators interpreted along the orbits {w, f(w), f2 (w), ˙˙˙} of points w ε W. We show that for various classes of topological spaces the resulting logics are not recursively enumerable (and so not (...) recursively axiomatisable). This gives a ‘negative’ solution to a conjecture of Kremer and Mints. Second, we consider logics for dynamical systems (W, f), where W is a metric space and f and isometric function. The operators for topological interior/closure are replaced by distance operators of the form ‘everywhere/somewhere in the ball of radius a, ‘for a ε Q +. In contrast to the topological case, the resulting logic turns out to be decidable, but not in time bounded by any elementary function. (shrink)

Drawing on contemporary pragmatic philosophy and grounded in a reading of techniques associated with digital media as sophist practices of influence and manipulation, this paper proposes an ‘experimental’ reading of key aspects of the topological qualities of the infrastructure of the knowledge economy, with its obsessive attempts at measuring, recording and monitoring, or ‘qualculation’. Taking seriously, albeit with humour, early criticisms of actor-network for its ostensibly Machiavellian proclivities, it offers a series of playful stratagems for the exploration and analysis of (...) power as an emergent property of socio-technical relations. Topology, in this account, becomes relevant to cultural analysis because of the way that it allows us to think together processes constructive of the intensive continua of ‘desiring production’ with the sociotechnical operations of digital media infrastructures. Different elements operative within digital media (the super-hub, the power of small numbers, recursion and relational databases) are read stratagematically – as figures of a praxis (the material practice of immaterial labour), that reveals different facets of the operations of power, while also allowing for counter-tactics to be deployed. Rather than proposing a theoretical account or an empirical analysis, the paper develops what Stengers (2011) calls ‘operative constructs’, which become ingredients for further active exploration of and thinking about the topological qualities of mediatic infrastructure. The paper addresses four different and overlapping areas of digital media from a point of view that considers the plural, compositional quality of media/power relations. (shrink)

In this paper we first give a variant of a theorem of Jockusch–Lewis– Remmel on existence of a computable, degree-preserving homeomorphism between a bounded strong ${\Pi^0_2}$ class and a bounded ${\Pi^0_1}$ class in 2 ω . Namely, we show that for mathematically common and interesting topological spaces, such as computably presented ${\mathbb{R}^n}$ , we can obtain a similar result where the homeomorphism is in fact the identity mapping. Second, we apply this finding to give a new, priority-free proof of existence (...) of a tree of shadow points computable in 0′. (shrink)

Dynamic Topological Logic () is a combination of , under its topological interpretation, and the temporal logic interpreted over the natural numbers. is used to reason about properties of dynamical systems based on topological spaces. Semantics are given by dynamic topological models, which are tuples , where is a topological space, f a function on X and V a truth valuation assigning subsets of X to propositional variables. Our main result is that the set of valid formulas of over spaces (...) with continuous functions is recursively enumerable. We show this by defining alternative semantics for . Under standard semantics, is not complete for Kripke frames. However, we introduce the notion of a non-deterministic quasimodel, where the function f is replaced by a binary relation g assigning to each world multiple temporal successors. We place restrictions on the successors so that the logic remains unchanged; under these alternative semantics, becomes Kripke-complete. We then apply model-search techniques to enumerate the set of all valid formulas. (shrink)

We propose and investigate a uniform modal logic framework for reasoning about topology and relative distance in metric and more general distance spaces, thus enabling the comparison and combination of logics from distinct research traditions such as Tarski’s for topological closure and interior, conditional logics, and logics of comparative similarity. This framework is obtained by decomposing the underlying modal-like operators into first-order quantifier patterns. We then show that quite a powerful and natural fragment of the resulting first-order logic can (...) be captured by one binary operator comparing distances between sets and one unary operator distinguishing between realised and limit distances . Due to its greater expressive power, this logic turns out to behave quite differently from both and conditional logics. We provide finite axiomatisations and ExpTime-completeness proofs for the logics of various classes of distance spaces, in particular metric spaces. But we also show that the logic of the real line is not recursively enumerable. This result is proved by an encoding of Diophantine equations. (shrink)

In this paper we investigate the properties of automorphism groups of countable short recursively saturated models of arithmetic. In particular, we show that Kaye's Theorem concerning the closed normal subgroups of automorphism groups of countable recursively saturated models of arithmetic applies to automorphism groups of countable short recursively saturated models as well. That is, the closed normal subgroups of the automorphism group of a countable short recursively saturated model of PA are exactly the stabilizers of the invariant cuts of the (...) model which are closed under exponentiation. This Galois correspondence is used to show that there are countable short recursively saturated models of arithmetic whose automorphism groups are not isomorphic as topological groups. Moreover, we show that the automorphism groups of countable short arithmetically saturated models of PA are not topologically isomorphic to the automorphism groups of countable short recursively saturated models of PA which are not short arithmetically saturated. (shrink)

The first-order theory of the lattice of recursively enumerable closed subsets of an effective topological space is proved undecidable using the undecidability of the first-order theory of the lattice of recursively enumerable sets. In particular, the first-order theory of the lattice of recursively enumerable closed subsets of Euclidean n -space, for all n , is undecidable. A more direct proof of the undecidability of the lattice of recursively enumerable closed subsets of Euclidean n -space, n ⩾ 2, is provided using (...) the method of reduction and the recursive inseparability of the set of all formulae satisfiable in every model of the theory of SIBs and the set of all formulae refutable in some finite model of the theory of SIBs. (shrink)

Sierpinski networks are networks of fractal nature having several applications in computer science, music, chemistry, and mathematics. These networks are commonly used in chaos, fractals, recursive sequences, and complex systems. In this article, we compute various connectivity polynomials such as M -polynomial, Zagreb polynomials, and forgotten polynomial of generalized Sierpinski networks S k n and recover some well-known degree-based topological indices from these. We also compute the most general Zagreb index known as α, β -Zagreb index and several other (...) general indices of similar nature for this network. Our results are the natural generalizations of already available results for particular classes of such type of networks. (shrink)

Local sentences and the formal languages they define were introduced by Ressayre in. We prove that locally finite ω‐languages and effective analytic sets have the same topological complexity: the Borel and Wadge hierarchies of the class of locally finite ω‐languages are equal to the Borel and Wadge hierarchies of the class of effective analytic sets. In particular, for each non‐null recursive ordinal there exist some ‐complete and some ‐complete locally finite ω‐languages, and the supremum of the set of Borel (...) ranks of locally finite ω‐languages is the ordinal, which is strictly greater than the first non‐recursive ordinal. This gives an answer to the question of the topological complexity of locally finite ω‐languages, which was asked by Simonnet and also by Duparc, Finkel, and Ressayre in. Moreover we show that the topological complexity of a locally finite ω‐language defined by a local sentence φ may depend on the models of the Zermelo‐Fraenkel axiomatic system. Using similar constructions as in the proof of the above results we also show that the equivalence, the inclusion, and the universality problems for locally finite ω‐languages are ‐complete, hence highly undecidable. (shrink)

The main result of this paper partially answers a question raised in about the existence of countable just recursively saturated models of Peano Arithmetic with non‐isomorphic automorphism groups. We show the existence of infinitely many countable just recursively saturated models of Peano Arithmetic such that their automorphism groups are not topologically isomorphic. We also discuss maximal open subgroups of the automorphism group of a countable arithmetically saturated model of in a very good interstice.

The paper examines the sudden disappearance in the United States of millions of honeybees in managed bee colonies. The major research undertaken in the U.S. concentrates on finding the pathogens responsible. This paper suggests an alternative avenue of research a) that as a result of global warming there is a disjunction between bees pollinating cycles and the life cycle of plants b) that understanding changes in “timing cycles” as a result of global warming is the key to understanding the disappearance (...) of the bees. It notes that Gregory Bateson argued that any condition of ecosystem collapse would be characterized first by a collapse in its communicative order rather, than from changed physical states. The collapse of bee colonies and demise of other pollinators is a seeming confirmation of Gregory Bateson argument. Honeybees are ‘go betweens’ in ecosystemic order. It also argues that an appropriate topology of timing cycles and their recursions would enable better visual comprehension of the heterarchical ‘pattern which connects’, in Bateson’s phrase, and prompt awareness of possible catastrophe in human food supplies. (shrink)

Let ℳ be a countable, recursively saturated model of Peano Arithmetic, and let Aut be its automorphism group considered as a topological group with the pointwise stabilizers of finite sets being the basic open subgroups. Kaye proved that the closed normal subgroups are precisely the obvious ones, namely the stabilizers of invariant cuts. A proof of Kaye's theorem is given here which, although based on his proof, is different enough to yield consequences not obtainable from Kaye's proof.

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)

One of the earliest applications of transfinite numbers is in the construction of derived sequences by Cantor [2]. In [6], the existence of derived sequences for countable closed sets is proved in ATR0. This existence theorem is an intermediate step in a proof that a statement concerning topological comparability is equivalent to ATR0. In actuality, the full strength of ATR0 is used in proving the existence theorem. To show this, we will derive a statement known to be equivalent to ATR0, (...) using only RCA0 and the assertion that every countable closed set has a derived sequence. We will use three of the subsystems of second order arithmetic defined by H. Friedman , which can be roughly characterized by the strength of their set comprehension axioms. RCA0 includes comprehension for Δmath image definable sets, ACA0 includes comprehension for arithmetical sets, and ATR0 appends to ACA0 a comprehension scheme for sets defined by transfinite recursion on arithmetical formulas. MSC: 03F35, 54B99. (shrink)

An algebra is effective if its operations are computable under some numbering. When are two numberings of an effective partial algebra equivalent? For example, the computable real numbers form an effective field and two effective numberings of the field of computable reals are equivalent if the limit operator is assumed to be computable in the numberings . To answer the question for effective algebras in general, we give a general method based on an algebraic analysis of approximations by elements of (...) a finitely generated subalgebra. Commonly, the computable elements of a topological partial algebra are derived from such a finitely generated algebra and form a countable effective partial algebra. We apply the general results about partial algebras to the recursive reals, ultrametric algebras constructed by inverse limits, and to metric algebras in general. © 2011 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim. (shrink)

We study concepts of decidability for subsets of Euclidean spaces ℝk within the framework of approximate computability . A new notion of approximate decidability is proposed and discussed in some detail. It is an effective variant of F. Hausdorff's concept of resolvable sets, and it modifies and generalizes notions of recursivity known from computable analysis, formerly used for open or closed sets only, to more general types of sets. Approximate decidability of sets can equivalently be expressed by computability of the (...) characteristic functions by means of appropriately working oracle Turing machines. The notion fulfills some natural requirements and is hereditary under canonical embeddings of sets into spaces of higher dimensions. However, it is not closed under binary union or intersection of sets. We also show how the framework of resolvability and approximate decidability can be applied to investigate concepts of reducibility for subsets of Euclidean spaces. (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)

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)

Given two (positive) equivalence relations ∼ 1 , ∼ 2 on the set ω of natural numbers, we say that ∼ 1 is m-reducible to ∼ 2 if there exists a total recursive function h such that for every x, y ∈ ω, we have $x \sim_1 y \operatorname{iff} hx \sim_2 hy$ . We prove that the equivalence relation induced in ω by a positive precomplete numeration is complete with respect to this reducibility (and, moreover, a "uniformity property" holds). (...) This result allows us to state a classification theorem for positive equivalence relations (Theorem 2). We show that there exist nonisomorphic positive equivalence relations which are complete with respect to the above reducibility; in particular, we discuss the provable equivalence of a strong enough theory: this relation is complete with respect to reducibility but it does not correspond to a precomplete numeration. From this fact we deduce that an equivalence relation on ω can be strongly represented by a formula (see Definition 8) iff it is positive. At last, we interpret the situation from a topological point of view. Among other things, we generalize a result of Visser by showing that the topological space corresponding to a partition in e.i. sets is irreducible and we prove that the set of equivalence classes of true sentences is dense in the Lindenbaum algebra of the theory. (shrink)

We explore a non-classical, universal set theory, based on a purely 'structural' conception of sets. A set is a transfinite process of unfolding of an arbitrary binary structure, with identity of sets given by the observational equivalence between such processes. We formalize these notions using infinitary modal logic, which provides partial descriptions for set structures up to observational equivalence. We describe the comprehension and topological properties of the resulting set-theory, and we use it to give non-classical solutions to classical paradoxes, (...) to prove fixed-point theorems that relate recursion and corecursion, to formalize 'super-large', reflexive categories and 'super-large' circular modes, and to provide 'natural' solutions for domain equations. (shrink)

We discuss the foundations of constructive mathematics, including recursive mathematics and intuitionism, in relation to classical mathematics. There are connections with the foundations of physics, due to the way in which the different branches of mathematics reflect reality. Many different axioms and their interrelationship are discussed. We show that there is a fundamental problem in BISH (Bishop’s school of constructive mathematics) with regard to its current definition of ‘continuous function’. This problem is closely related to the definition in BISH (...) of ‘locally compact’. Possible approaches to this problem are discussed. Topology seems to be a key to understanding many issues. We offer several new simplifying axioms, which can form bridges between the various branches of constructive mathematics and classical mathematics (‘reuniting the antipodes’). We give a simplification of basic intuitionistic theory, especially with regard to so-called ‘bar induction’. We then plead for a limited number of axiomatic systems, which differentiate between the various branches of mathematics. Finally, in the appendix we offer BISH an elegant topological definition of ‘locally compact’, which unlike the current definition is equivalent to the usual classical and/or intuitionistic definition in classical and intuitionistic mathematics, respectively. (shrink)

By an unfounded chain for a function f:X→X we mean a sequence nω of elements of X s.t. fxn+1=xn for every n. Unfounded chains can be regarded as a generalization of fixed points, but on the other hand are linked with concepts concerning non-well-founded situations, as ungrounded sentences and the hypergame. In this paper, among other things, we prove a lemma in general topology, we exhibit an extensional recursive function from the set of sentences of PA into itself (...) without an unfounded chain, and we prove that every term in a Magari algebra has an unfounded chain. (shrink)

We prove that, for each countable ordinal ξ≥1, there exist some -complete ω-powers, and some -complete ω-powers, extending previous works on the topological complexity of ω-powers [O. Finkel, Topological properties of omega context free languages, Theoretical Computer Science 262 669–697; O. Finkel, Borel hierarchy and omega context free languages, Theoretical Computer Science 290 1385–1405; O. Finkel, An omega-power of a finitary language which is a borel set of infinite rank, Fundamenta informaticae 62 333–342; D. Lecomte, Sur les ensembles de phrases (...) infinies constructibles a partir d’un dictionnaire sur un alphabet fini, Séminaire d’Initiation a l’Analyse, 1, année 2001–2002; D. Lecomte, Omega-powers and descriptive set theory, Journal of Symbolic Logic 70 1210–1232; J. Duparc, O. Finkel, An ω-Power of a Context-Free Language Which Is Borel Above , in: S. Bold, B. Löwe, T. Räsch, J. van Benthem , in the Proceedings of the international conference foundations of the formal sciences V : Infinite Games, November 26th to 29th, 2004, Bonn, Germany, in: Studies in Logic, vol. 11, College Publications at King’s College, 2007, pp. 109–122]. We prove effective versions of these results; in particular, for each recursive ordinal there exist some recursive sets A2<ω such that , where and denote classes of the hyperarithmetical hierarchy. To do this, we prove effective versions of a result by Kuratowski, describing a set as the range of a closed subset of the Baire space ωω by a continuous bijection. This leads us to prove closure properties for the pointclasses in arbitrary recursively presented Polish spaces. We apply our existence results to get better computations of the topological complexity of some sets of dictionaries considered in [D. Lecomte, Omega-powers and descriptive set theory, Journal of Symbolic Logic 70 1210–1232]. (shrink)

Let M be a countable recursively saturated model of Th(), and let GAut(M), considered as a topological group. We examine connections between initial segments of M and subgroups of G. In particular, for each of the following classes of subgroups HG, we give characterizations of the class of terms of the topological group structure of H as a subgroup of G. (a) for some (b) for some (c) for some (d) for some (Here, M(a) denotes the smallest M containing a, (...) , , and .). (shrink)

Cantor’s proof that the reals are uncountable forms a central pillar in the edifices of higher order recursion theory and set theory. It also has important applications in model theory, and in the foundations of topology and analysis. Due partly to these factors, and to the simplicity and elegance of the proof, it has come to be accepted as part of the ABC’s of mathematics. But even if as an Archimedean point it supports tomes of mathematical theory, there is (...) a question that demands clarification: What, exactly, does Cantor’s proof show? One of few places where this question is addressed is Appendix II of Wittgenstein’s Remarks on the Foundations of Mathematics. This essay is devoted to clarifying Wittgenstein’s remarks in that section. (shrink)