Search

We examine whether some well-known properties of partial recursive functions are valid for ITBM-computable functions, i.e., functions which can be computed with infinite time Blum–Shub–Smale machines. It is shown that properties of graphs of ITBM-computable functions differ from the usual properties of graphs of partial recursive functions. All possible ranges of ITBM-computable functions are described, and we consider the existence problem for ITBM-computable bijections between ITBM-computable sets of the same cardinality.

We consider two kinds of reducibilities on finite families of predicates on a countable set: the definability of predicates and their complements of one family via another by means of existential formulas with parameters and the same definability on isomorphism types of families. Ordered structures of degrees generated by families of unary predicates are described. It is proved that for both reducibilities, there exist continuum many minimal nonzero degrees.

The study of automorphisms of computable and other structures connects computability theory with classical group theory. Among the noncomputable countable structures, computably enumerable structures are one of the most important objects of investigation in computable model theory. Here we focus on the lattice structure of computably enumerable substructures of a given canonical computable structure. In particular, for a Turing degree d, we investigate the groups of d-computable automorphisms of the lattice of d-computably enumerable vector spaces, of the interval Boolean algebra Bη of the ordered set of rationals, and of the lattice of d-computably enumerable subalgebras of Bη. For these groups, we show that Turing reducibility can be used to substitute the group-theoretic embedding. We also prove that the Turing degree of the isomorphism types for these groups is the second Turing jump d′′ of d.

We study the possibilities of defining some operations on fields via the remaining operations. In particular, we prove that multiplication on an arbitrary field can be defined via addition if and only if the field is a finite extension of its prime subfield. We give a sufficient condition for the nondefinability of addition via multiplication and demonstrate that multiplication and addition on the reals and complexes cannot be mutually defined by means of the relations with parameters which are preserved under automorphisms. We also describe the mutual definability of addition, multiplication, and exponentiation via the remaining two operations.

It is proved that the ordinal ω1cannot be embedded into a preordering Σ-definable with parameters in the hereditarily finite superstructure over the real numbers. As a corollary, we obtain the descriptions of ordinals Σ-presentable over$$ \mathbb{H}\mathbbm{F} $$(ℝ) and of Godel constructive sets of the form Lα. It is also shown that there are no Σ-presentations of structures of T-, m-, 1- and tt-degrees.

We introduce and study the class of holographic models which can be defined by copying of some of its finite parts by means of automorphisms. We prove this class to differ from the class of countably categorical models. Characterizations of the classes of holographic Boolean algebras, abelian groups, linear orderings, fields, and equivalences are given.

We construct a computably enumerable partial ordering having neither computably enumerable maximal chains nor computably enumerable maximal antichains.

It is proved that any countable consistent theory with infinite models has a Σ-presentable model of cardinality 2ω over ℍ𝔽(ℝ). It is shown that some structures studied in analysis (in particular, a semigroup of continuous functions, certain structures of nonstandard analysis, and infinite-dimensional separable Hilbert spaces) have no simple Σ-presentations in hereditarily finite superstructures over existentially Steinitz structures. The results are proved by a unified method on the basis of a new general sufficient condition.

Functions that are computable on infinite time Blum–Shub–Smale machines (ITBM) are characterized via iterated Turing jumps, and we propose a normal form for these functions. It is also proved that the set of ITBM computable reals coincides with ℝ∩L ωω.

We prove the embeddability of the structure of Turing degrees into the structure of degrees of existential interpretability. The notion of weakly bounded Turing reducibility (wbT-reducibility) arises in the proof naturally. We demonstrate that this reducibility is situated strictly between the bounded truth-table reducibility and Turing reducibility and differs from the truth-table reducibility.

We introduce a class of existentially Steinitz structures containing, in particular, the fields of real and complex numbers. A general result is proved which implies that if $$ \mathfrak{M} $$ is an existentially Steinitz structure then the following structures cannot be embedded in any structure Σ-presentable with trivial equivalence over ℍ $$ \mathbb{F} $$ ( $$ \mathfrak{M} $$ ): the Boolean algebra of all subsets of ω, its factor modulo the ideal consisting of finite sets, the group of all permutations on ω, its factor modulo the subgroup of all finitary permutations, the semigroup of all mappings from ω to ω, the lattice of all open sets of real numbers, the lattice of all closed sets of real numbers, the group of all permutations of ℝ Σ-definable with parameters over ℍ $$ \mathbb{F} $$ (ℝ), and the semigroup of such mappings from ℝ to ℝ.

We study linear orders definable over negative and positive equivalences and their computable automorphisms. Special attention is paid to equivalences like η(α) = α 2∪id ω , α ⊆ ω. In particular, we describe orders that have negative presentations over such equivalences for co-enumerable sets α. Presentable and nonpresentable order types are exemplified for equivalences with various extra properties. We also give examples of negative orders with computable automorphisms whose inverses are not computable.

We prove the nonexistence of universal Σ-presentable linear orderings as well as the effective infinity of the class of Σ-presentations of the natural order on ℝ over an admissible set ℍ $$ \mathbb{F} $$ (ℝ).

For arbitrary tuples of real parameters \(\bar p\), we prove the existence and effective infiniteness of the class of the linear orders on ℝ of type 〈ℝ

We prove that the semigroup of all functions from the set of natural numbers to natural numbers by composition has no one-valued Σ-presentations with parameters over the hereditarily finite superstructure over the real numbers.

This paper is a survey of results together with a list of open questions on \(\Sigma \)–definability of structures over \(\mathbb {HF}(\mathbb {R})\), the hereditarily finite superstructure over the ordered field of the real numbers.

We consider countable free groups of different ranks. For these groups, we investigate computability theoretic complexity of index sets within the class of free groups and within the class of all groups. For a computable free group of infinite rank, we consider the difficulty of finding a basis.

It is proved that every two Σ-presentations of an ordered field $ \mathbb{R} $ of reals over $ \mathbb{H}\mathbb{F}\,\left( \mathbb{R} \right) $ , whose universes are subsets of $ \mathbb{R} $ , are mutually Σ-isomorphic. As a consequence, for a series of functions $ f:\mathbb{R} \to \mathbb{R} $ (e.g., exp, sin, cos, ln), it is stated that the structure $ \mathbb{R} $ = 〈R, +, ×

In utility maximization problems the best investment strategy allows an investor to get an expected utility $u(x)$ given an initial capital x. So the value function u can be viewed as a utility function. A traditional assumption on the utility function is differentiability, so we come naturally to the question of whether a value function u is differentiable. In the standard utility maximization problem the value function is usually differentiable. In this paper we show that it is not the case for robust utility maximization problems unless a utility function U is of power, exponential, or logarithmic form.

We define the automorphism spectrum of a computable structure $$ \mathcal{M} $$ , a complexity measure of the symmetries of $$ \mathcal{M} $$ , and prove that certain sets of Turing degrees can be realized as automorphism spectra, while certain others cannot.

Under study are the automorphism groups of computable formal contexts. We give a general method to transform results on the automorphisms of computable structures into results on the automorphisms of formal contexts. Using this method, we prove that the computable formal contexts and computable structures actually have the same automorphism groups and groups of computable automorphisms. We construct some examples of formal contexts and concept lattices that have nontrivial automorphisms but none of them could be hyperarithmetical in any hyperarithmetical presentation of these structures. We also show that it could be happen that two formal concepts are automorphic but they are not hyperarithmetically automorphic in any hyperarithmetical presentation.

We prove in a uniform way that the following lattices have no computable presentations: the lattice of all computable order theoretic automorphisms of the rational numbers; the lattice of the computable functions from the rational numbers to the rational numbers having continuous extensions to functions on the real numbers; and the lattice of the monotonic functions on the natural numbers. Nevertheless, we prove that the lattice of all computable mappings from the rational numbers to the rational numbers has a computable presentation.

We investigate effective categoricity of computable Abelian p -groups A . We prove that all computably categorical Abelian p -groups are relatively computably categorical, that is, have computably enumerable Scott families of existential formulas. We investigate which computable Abelian p -groups are Δ 2 0 categorical and relatively Δ 2 0 categorical.

We study the isomorphism types of ordered structures of concepts for computable formal contexts from the point of view of computable model theory. We show that, although these structures could have the cardinality of the continuum or—if they are countable—could have an arbitrary high hyperarithmetical complexity, they are in some sense very close to computable orderings. We give some sufficient conditions for these orderings to have computable presentations. A full description is given of the isomorphism types of discrete concept lattices. We also give some counterexamples.

We study the relationship between algebraic structures and their inverse semigroups of partial automorphisms. We consider a variety of classes of natural structures including equivalence structures, orderings, Boolean algebras, and relatively complemented distributive lattices. For certain subsemigroups of these inverse semigroups, isomorphism (elementary equivalence) of the subsemigroups yields isomorphism (elementary equivalence) of the underlying structures. We also prove that for some classes of computable structures, we can reconstruct a computable structure, up to computable isomorphism, from the isomorphism type of its inverse semigroup of computable partial automorphisms.

We compute the levels of complexity in analytical and arithmetical hierarchies for the sets of the Σ-formulas defining in the hereditarily finite superstructure over the ordered field of the reals the classes of open, closed, clopen, nowhere dense, dense subsets of ℝn, first category subsets in ℝn as well as the sets of pairs of Σ-formulas corresponding to the relations of set equality and inclusion which are defined by them. It is also shown that the complexity of the set of the Σ-formulas defining connected sets is at least Π11.

We study Σ-definability of countable models over hereditarily finite {ie193-01} superstructures over the field ℝ of reals, the field ℂ of complex numbers, and over the skew field ℍ of quaternions. In particular, it is shown that each at most countable structure of a finite signature, which is Σ-definable over {ie193-02} with at most countable equivalence classes and without parameters, has a computable isomorphic copy. Moreover, if we lift the requirement on the cardinalities of the classes in a definition then such a model can have an arbitrary hyperarithmetical complexity, but it will be hyperarithmetical in any case. Also it is proved that any countable structure Σ-definable over {ie193-03}, possibly with parameters, has a computable isomorphic copy and that being Σ-definable over {ie193-04} is equivalent to being Σ-definable over {ie193-05}.

The main result of the paper is describing all definable subsets in the group Aut 〈ℚ; ⩽〉 of all automorphisms of the natural ordering on the rational numbers, and also in groups of the form Aut I 〈ℚ; ⩽〉, where I is a Turing ideal consisting of elements of Aut 〈ℚ; ⩽〉 whose Turing degree is contained in I. This description is properly a uniform method for proving definability of all basic properties appearing in works on the theory of groups Aut I 〈ℚ; ⩽〉, as well as definability of a number of new sets. Also, we describe automorphism groups for such groups Aut I 〈ℚ; ⩽〉 and state a number of structure properties for elementary subgroups in Aut 〈ℚ; ⩽〉.

We introduce and study the notions of computable formal context and computable formal concept. We give some examples of computable formal contexts in which the computable formal concepts fail to form a lattice and study the complexity aspects of formal concepts in computable contexts. In particular, we give some sufficient conditions under which the computability or noncomputability of a formal concept could be recognized from its lattice-theoretic properties. We prove the density theorem showing that in a Cantor-like topology every formal concept can be approximated by computable ones. We also show that not all formal concepts have lattice-theoretic approximations as suprema or infima of families of computable formal concepts.

We prove that there is a first-order sentence ϕ such that the group of all computable automorphisms of the ordering of the rational numbers is its only model among the groups that are embeddable in the group of all computable permutations.

We introduce the notion of F-parametrizable model and prove some general results on elementary submodels of F-parametrizable models. Using this notion, we can uniformly characterize all elementary submodels for the field of real numbers and for the group of all permutations on natural numbers in the first order language as well as in the language of hereditarily finite superstructures. Assuming the constructibility axiom, we obtain a simpler characterization of elementary submodels of F-parametrizable models and prove some additional properties of the structure of their elementary submodels.

We describe up to finite coverings causal flat affine complete Lorentzian manifolds such that the past and the future of any point are closed near this point. We say that these manifolds are strictly causal. In particular, we prove that their fundamental groups are virtually abelian. In dimension 4, there is only one, up to a scaling factor, strictly causal manifold which is not globally hyperbolic. For a generic point of this manifold, either the past or the future is not closed and contains a lightlike straight line., To appear in Geometriae Dedicata

A criterion is obtained for existence of two isomorphic but not hyperarithmetically isomorphic tuples in a hyperarithmetical model. This criterion is used to show that such a situation occurs in the models of well-known classes.

We construct a computable vector space with the trivial computable automorphism group, but with the dependence relations as complicated as possible, measured by their Turing degrees. As a corollary, we answer a question asked by A.S. Morozov in [Rigid constructive modules, Algebra and Logic, 28 (5) (1989) 570–583 (in Russian); (1990) 379–387 (English transl.)].

We study effective presentations and homeomorphisms of effective topological spaces. By constructing a functor from the category of computable models into the category of effective topological spaces, we show in particular that there exist homeomorphic effective topological spaces admitting no hyperarithmetical homeomorphism between them and there exist effective topological spaces whose autohomeomorphism group has the cardinality of the continuum but whose only hyperarithmetical autohomeomorphism is trivial. It is also shown that if the group of autohomeomorphisms of a hyperarithmetical topological space has cardinality less than 2ω then this group is hyperarithmetical. We introduce the notion of strong computable homeomorphism and solve the problem of the number of effective presentations of T0-spaces with effective bases of clopen sets with respect to strong homeomorphisms.

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.

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 \(\mathbb{H}\mathbb{Y}\mathbb{P}\)-superstructures. Several results are proven on the relations of this reducibility to some known reducibilities.

We show that not each model can be replaced by a model of finite signature so that its automorphism group remains the same.

Basics and results on groups of computable automorphisms are collected in [1].We recall the main definitions. A computable model $$\mathfrak{M} = \langle A,f_0^{n_0 } ,...;P_0^{m_0 } ,...\rangle $$ is a model in which A is a computable subset of the set ! of natural numbers, the mappings i 7! ni(the number of arguments of fi) and i ↦ mi (the number of arguments of Pi) are computable, andall operations fi and predicates Pi are computable uniformly in i. A computable automorphism ofa computable model M is an automorphism of \(\mathfrak{M}\) which is a computable function on its universe. Allsuch automorphisms form a group denoted by Autc \(\mathfrak{M}\).

We construct a two-generated group with the co-recursively enumerable word problem that has no presentation by recursive permutations. This answers Higman’s question and exemplifies a group with the minimal possible number of generators. The previous article [1], in which that question was claimed settled, contains an incorrigible error.

We describe all endomorphisms of the group AutT ɛ of all recursive permutations. It is proved that the family of these endomorphisms is countable, and that they all are continuous and may be defined by some natural recursive operators. Orbits relative to the image of AutTω prove to be recursive, and there exists a recursive model M such that this image is exactly its recursive automorphism group. There exists a universal endomorphism which contains, in a sense, all endomorphisms of that group. The universal endomorphism is unique with respect to some natural recursive equivalence.

The aim of the chapter is to extend the application of convex duality methods to the problem of maximizing expected utility from terminal wealth. More precisely, we restrict attention to a dual characterization of the value function of this problem and to a static setting. A general scheme to solve this problem is proposed. In the case where the utility function is finite on \(\mathbb{R}\), we use the approach, suggested by Biagini and Frittelli, based on using an Orlicz space constructed from an investor’s utility function. We reduce the original problem to an optimization problem in this space in a nontrivial way, which allows us to weaken essentially assumptions on the model. We also study the problem of utility maximization with random endowment considered by Cvitanic, Schachermayer, and Wang. Using the space ψ L ∞ with a weight function ψ constructed from a random endowment permits us to consider unbounded random endowments. Another important contribution is that in both problems under consideration, we provide versions of the dual problem that are free of singular functionals.

It is proved that there exists no relationship between isomorphism types of the ordinary and recursive automorphism groups of recursive models and the property of being decidable for these models. Moreover, we show that all isomorphism types of recursive automorphism groups can be realized in a single (up to isomorphism) decidable countably categorical model. Taking account of the action of a group on the universe of the model makes it possible to distinguish between the classes of groups for decidable and all the recursive models.