On the Relation of Σ-Reducibility Between Admissible Sets

Reducibility on admissible sets is studied which is a stronger version of the usual -presentability of models. One of its informal prototypes is the interpretability of one computational device in the other. We obtain criteria of reducibility for recursively listed and pure sets, introduce the notion of jump, and prove exact boundaries for the ordinals of jumps. We also show that this reducibility is lifted to -superstructures. Several results are proven on the relations of this reducibility to some known reducibilities.     

A construction of interpolating wavelets on invariant sets

We introduce the concept of a refinable set relative to a family of contractive mappings on a metric space, and demonstrate how such sets are useful to recursively construct interpolants which have a multiscale structure. The notion of a refinable set parallels that of a refinable function, which is the basis of wavelet construction. The interpolation points we recursively generate from a refinable set by a set-theoretic multiresolution are analogous to multiresolution for functions used in wavelet construction. We then use this recursive structure for the points to construct multiscale interpolants. Several concrete examples of refinable sets which can be used for generating interpolatory wavelets are included.

     

Reducibility on families

A reducibility on families of subsets of natural numbers is introduced which allows the family per se to be treated without its representation by natural numbers being fixed. This reducibility is used to study a series of problems both in classical computability and on admissible sets: for example, describing index sets of families belonging to , generalizing Friedberg’s completeness theorem for a suitable reducibility on admissible sets, etc. *Supported by RFBR (project No. 05-01-00605) and by the Council for Grants (under RF President) and State Aid of Young Candidates of Science (grant MK-4314.2008.1). **Supported by RFBR (projects No. 08-01-00442 and 06-04002-DFGa), by the Council for Grants (under RF President) of Leading Scientific Schools (grant NSh-335.2008.1), and by the Russian Foundation for Support of Domestic Science. Translated from Algebra i Logika, Vol. 48, No. 1, pp. 31-53, January-February, 2009.     

Pseudo definably connected definable sets

In o‐minimal structures, every cell is definably connected and every definable set is a finite union of its definably connected components. In this note, we introduce pseudo definably connected definable sets in weakly o‐minimal structures having strong cell decomposition, and prove that every strong cell in those structures is pseudo definably connected. It follows that every definable set can be written as a finite union of its pseudo definably connected components. We also show that the projections of pseudo definably connected definable sets are pseudo definably connected. Finally, we compare pseudo definable connectedness with (recently introduced) weak definable connectedness of definable sets in weakly o‐minimal structures.     

Models with second order properties IV. A general method and eliminating diamonds

We show how to build various models of first-order theories, which also have properties like: tree with only definable branches, atomic Boolean algebras or ordered fields with only definable automorphisms.For this we use a set-theoretic assertion, which may be interesting by itself on the existence of quite generic subsets of suitable partial orders of power λ⁺, which follows from ?_λ and even weaker hypotheses (e.g., λ=?₀, or λ strongly inaccessible). For a related assertion, which is equivalent to the morass see Shelah and Stanley [16].The various specific constructions serve also as examples of how to use this set-theoretic lemma. We apply the method to construct rigid ordered fields, rigid atomic Boolean algebras, trees with only definable branches; all in successors of regular cardinals under appropriate set- theoretic assumptions. So we are able to answer (under suitable set-theoretic assumptions) the following algebraic question.Saltzman's Question. Is there a rigid real closed field, which is not a subfield of the reals?     

Σ-Bounded algebraic systems and universal functions. I

We introduce the concept of a Σ-bounded algebraic system and prove that if a system is Σ- bounded with respect to a subset A then in a hereditarily finite admissible set over this system there exists a universal Σ-function for the family of functions definable by Σ-formulas with parameters in A. We obtain a necessary and sufficient condition for the existence of a universal Σ-function in a hereditarily finite admissible set over a Σ-bounded algebraic system. We prove that every linear order is a Σ-bounded system and in a hereditarily finite admissible set over it there exists a universal Σ-function.     

近似空间的拓扑性质及其应用

近似空间(U,R)的全体可定义集构成X上的一个拓扑.本文在不要求论域U是有限的前提下探讨近似空间上这个拓扑的局部性质和可数性质,以及拓扑空间可近似化的充要条件及公理化体系,并寻找它们在粗糙集理论中的应用.     

First-order definability and algebraicity of the sets of annihilating and generating collections of elements for some relatively free solvable groups

We study the first-order definable, Diophantine, and algebraic subsets in the set of all ordered sets generating a group or generating a group as a normal subgroup for some relatively free solvable groups.     

Realisability for infinitary intuitionistic set theory

We introduce a realisability semantics for infinitary intuitionistic set theory that is based on Ordinal Turing Machines (OTMs). We show that our notion of OTM-realisability is sound with respect to certain systems of infinitary intuitionistic logic, and that all axioms of infinitary Kripke-Platek set theory are realised. Finally, we use a variant of our notion of realisability to show that the propositional admissible rules of (finitary) intuitionistic Kripke-Platek set theory are exactly the admissible rules of intuitionistic propositional logic.     

About the Admissible Predicates on Admissible Sets

We study the admissible predicates, i.e., the predicates having the property that their addition to the signature of an admissible set preserves the property “to be an admissible set.” We show that the family of these predicates is much wider than the family of Δ-predicates. We also construct a family of admissible predicates of cardinality 2^ω such that the addition of an arbitrary pair of predicates of this family to the signature of an admissible set violates the admissibility of the latter as well as other examples of families of admissible predicates.Original Russian Text Copyright © 2005 Morozov A. S.The author was supported by the International Russian-German Program (Grant RFRB-DFG 01-01-04003), the Russian Science Support Foundation, and the State Maintenance Program for the Leading Scientific Schools of the Russian Federation (Grant 2112.2003.1).__________Translated from Sibirskii Matematicheskii Zhurnal, Vol. 46, No. 4, pp. 841–850, July–August, 2005.     

Virtually stable maps and their fixed point sets

We introduce the concept of virtually stable selfmaps of Hausdorff spaces, which generalizes virtually nonexpansive selfmaps of metric spaces introduced in the previous work by the first author, and explore various properties of their convergence sets and fixed point sets. We also prove that the fixed point set of a virtually stable selfmap satisfying a certain kind of homogeneity is always star-convex.     

Effective Borel measurability and reducibility of functions

The investigation of computational properties of discontinuous functions is an important concern in computable analysis. One method to deal with this subject is to consider effective variants of Borel measurable functions. We introduce such a notion of Borel computability for single‐valued as well as for multi‐valued functions by a direct effectivization of the classical definition. On Baire space the finite levels of the resulting hierarchy of functions can be characterized using a notion of reducibility for functions and corresponding complete functions. We use this classification and an effective version of a Selection Theorem of Bhattacharya‐Srivastava in order to prove a generalization of the Representation Theorem of Kreitz‐Weihrauch for Borel measurable functions on computable metric spaces: such functions are Borel measurable on a certain finite level, if and only if they admit a realizer on Baire space of the same quality. This Representation Theorem enables us to introduce a realizer reducibility for functions on metric spaces and we can extend the completeness result to this reducibility. Besides being very useful by itself, this reducibility leads to a new and effective proof of the Banach‐Hausdorff‐Lebesgue Theorem which connects Borel measurable functions with the Baire functions. Hence, for certain metric spaces the class of Borel computable functions on a certain level is exactly the class of functions which can be expressed as a limit of a pointwise convergent and computable sequence of functions of the next lower level. (© 2004 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Degrees of presentability of structures. I

Presentations of structures in admissible sets, as well as different relations of effective reducibility between the structures, are treated. Semilattices of degrees of Σ-definability are the main object of investigation. It is shown that the semilattice of degrees of Σ-definability of countable structures agrees well with semilattices of T-and e-degrees of subsets of natural numbers. Also an attempt is made to study properties of the structures that are inherited under various effective reducibilities and explore how degrees of presentability depend on choices of different admissible sets as domains for presentations. Supported by RFBR grant Nos. 05-0100481 and 06-0104002, by the Council for Grants (under RF President) for State Support of Young Candidates of Science and Their Supervisors via project MK-1239.2005.1, and via INTAS project YSF 04-83-3310. __________ Translated from Algebra i Logika, Vol. 46, No. 6, pp. 763–788, November–December, 2007.     

Truncations of principal geometries

We investigate the class of principal pregeometries (free simplicial geometries with spanning simplex) which form an important subclass of the class of transversal pregeometries (free simplicial geometries). We give a coordinate-free method for imbedding a transversal pregeometry on a simplex as a free simplicial pregeometry which makes use only of the set-theoretic properties of a presentation of the transversal pregeometry. We introduce the notion of an (r, k)-principal set as a generalization of principal basis and prove the collection of (r, k)-principal sets of a rank k pregeometry, if non-empty, are the bases of another pregeometry whose structure is determined. An algorithm for constructing principal sets is given. We then characterize truncations of principal geometries in terms of the existence of a principal set. We do this by erecting a given pregeometry to a free simplicial pregeometry with spanning simplex. The erection is the freest of all erections of the given pregeometry.     

Reflection of Long Game Formulas

We study game formulas the truth of which is determined by a semantical game of uncountable length. The main theme is the study of principles stating reflection of these formulas in various admissible sets. This investigation leads to two weak forms of strict-II¹₁ reflection (or ∑₁-compactness). We show that admissible sets such as H(ω₂) and L_ω2 which fail to have strict-II¹₁ reflection, may or may not, depending on set-theoretic hypotheses satisfy one or both of these weaker forms. Mathematics Subject Classification : 03C70, 03C75.     

Definable Sets in Generic Structures and their Cardinalities

Analyzing diagrams forming generative classes, we describe definable sets and their links in generic structures as well as cardinality bounds for these definable sets, finite or infinite. Introducing basic characteristics for definable sets in generic structures, we compare them each others and with cardinalities of these sets.We introduce calculi for (type-)definable sets allowing to compare their cardinalities. In terms of these calculi, Trichotomy Theorem for possibilities comparing cardinalities of definable sets is proved. Using these calculi, we characterize the possibility to construct a generic structure of a given generative class.     

Fundamental group in o-minimal structures with definable Skolem functions

In this paper we work in an arbitrary o-minimal structure with definable Skolem functions and prove that definably connected, locally definable manifolds are uniformly definably path connected, have an admissible cover by definably simply connected, open definable subsets and, definable paths and definable homotopies on such locally definable manifolds can be lifted to locally definable covering maps. These properties allow us to obtain the main properties of the general o-minimal fundamental group, including: invariance and comparison results; existence of universal locally definable covering maps; monodromy equivalence for locally constant o-minimal sheaves – from which one obtains, as in algebraic topology, classification results for locally definable covering maps, o-minimal Hurewicz and Seifert–van Kampen theorems.