Polish group actions,nice topologies,and admissible sets

Let G be a closed subgroup of S_∞ and X be a Polish G ‐space. To every x ∈ X we associate an admissible set A _x and show how questions about X which involve Baire category can be formalized in A _x . (© 2008 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

On Σ-subsets of naturals over abelian groups

We obtain conditions for the Σ-definability of a subset of the set of naturals in the hereditarily finite admissible set over a model and for the computability of a family of such subsets. We prove that: for each e-ideal I there exists a torsion-free abelian group A such that the family of e-degrees of Σ-subsets of ω in $\mathbb{H}\mathbb{F}(A)$ coincides with I; there exists a completely reducible torsion-free abelian group in the hereditarily finite admissible set over which there exists no universal Σ-function; for each principal e-ideal I there exists a periodic abelian group A such that the family of e-degrees of Σ-subsets of ω in $\mathbb{H}\mathbb{F}(A)$ coincides with I.     

Degrees of presentability of structures. II

We show that the property of being locally constructivizable is inherited under Muchnik reducibility, which is weakest among the effective reducibilities considered over countable structures. It is stated that local constructivizability of level higher than 1 is inherited under Σ-reducibility but is not inherited under Medvedev reducibility. An example of a structure and a relation P ⊆ M is constructed for which but ≢_∑ . Also, we point out a class of structures which are effectively defined by a family of their local theories. 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 (project MK-1239.2005.1), and by INTAS (project YSF 04-83-3310). __________ Translated from Algebra i Logika, Vol. 47, No. 1, pp. 108–126, January–February, 2008.     

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.     

Note on generalized open sets

Characterizations of γ-open sets and locally γ-regular sets are given. We generalize some already established results and answer an open question by giving a characterization to γ-quasi-open sets.      

On the Ershov Upper Semilattice

We find some links between -reducibility and T-reducibility. We prove that (1) if a quasirigid model is strongly -definable in a hereditarily finite admissible set over a locally constructivizable B-system, then it is constructivizable; (2) every abelian p-group and every Ershov algebra is locally constructivizable; (3) if an antisymmetric connected model is -definable in a hereditarily finite admissible set over a countable Ershov algebra then it is constructivizable.     

Σ-Subsets of Natural Numbers

It is shown that the class of all possible families of -subsets of finite ordinals in admissible sets coincides with a class of all non-empty families closed under e-reducibility and . The construction presented has the property of being minimal under effective definability. Also, we describe the smallest (w.r.t. inclusion) classes of families of subsets of natural numbers, computable in hereditarily finite superstructures. A new series of examples is constructed in which admissible sets lack in universal -function. Furthermore, we show that some principles of classical computability theory (such as the existence of an infinite non-trivial enumerable subset, existence of an infinite computable subset, reduction principle, uniformization principle) are always satisfied for the classes of all -subsets of finite ordinals in admissible sets.