Estimation of the algorithmic complexity of classes of computable models

We estimate the algorithmic complexity of the index set of some natural classes of computable models: finite computable models (Σ ₂ ⁰ -complete), computable models with ω-categorical theories (Δ _ω ⁰ -complex Π _ω+2 ⁰ -set), prime models (Δ _ω ⁰ -complex Π _ω+2 ⁰ -set), models with ω ₁-categorical theories (Δ _ω ⁰ -complex Σ _ω+1 ⁰ -set. We obtain a universal lower bound for the model-theoretic properties preserved by Marker’s extensions (Δ _ω ⁰ .     

Index sets of decidable models

We study the index sets of the class of d-decidable structures and of the class of d-decidable countably categorical structures, where d is an arbitrary arithmetical Turing degree. It is proved that the first of them is m-complete ∑ ₃ ^{0, d} , and the second is m-complete ∑ ₃ ^{0, d} \∑ ₃ ^{0, d} in the universal computable numbering of computable structures for the language with one binary predicate.     

Isomorphisms,definable relations,and Scott families for integral domains and commutative semigroups

In the present article, we prove the following four assertions: (1) For every computable successor ordinal α, there exists a Δ _α ⁰ -categorical integral domain (commutative semigroup) which is not relatively Δ _α ⁰ -categorical (i.e., no formally Σ _α ⁰ Scott family exists for such a structure). (2) For every computable successor ordinal α, there exists an intrinsically Σ _α ⁰ -relation on the universe of a computable integral domain (commutative semigroup) which is not a relatively intrinsically Σ _α ⁰ -relation. (3) For every computable successor ordinal α and finite n, there exists an integral domain (commutative semigroup) whose Δ _α ⁰ -dimension is equal to n. (4) For every computable successor ordinal α, there exists an integral domain (commutative semigroup) with presentations only in the degrees of sets X such that Δ _α ⁰ (X) is not Δ _α ⁰ . In particular, for every finite n, there exists an integral domain (commutative semigroup) with presentations only in the degrees that are not n-low.     

A note on Δ 2 0 -Spectra of linear orderings and degree spectra of the successor relation

In this paper we construct linear orderings whoseΔ ₂ ⁰ -spectra coincide with classes of all high₀ and high₁ degrees, respectively. We also prove that there exists a computable linear ordering such that its degree spectrum of the successor relation coincides with a fixed nonempty class of degrees which represents a Σ ₁ ⁰ -spectrum of some Ø′-computable linear ordering.     

An example related to Gregory’s Theorem

In this paper, we give an example of a complete computable infinitary theory T with countable models ${\mathcal{M}}$ and ${\mathcal{N}}$ , where ${\mathcal{N}}$ is a proper computable infinitary extension of ${\mathcal{M}}$ and T has no uncountable model. In fact, ${\mathcal{M}}$ and ${\mathcal{N}}$ are (up to isomorphism) the only models of T. Moreover, for all computable ordinals α, the computable ${\Sigma_\alpha}$ part of T is hyperarithmetical. It follows from a theorem of Gregory (JSL 38:460–470, 1972; Not Am Math Soc 17:967–968, 1970) that if T is a Π ₁ ¹ set of computable infinitary sentences and T has a pair of models ${\mathcal{M}}$ and ${\mathcal{N}}$ , where ${\mathcal{N}}$ is a proper computable infinitary extension of ${\mathcal{M}}$ , then T would have an uncountable model.     

Spectral asymptotics and trace formulas for differential operators with unbounded coefficients

In the space L ²[0, π], we consider the operators $$ L = L_0 + V, L_0 = - y'' + (\nu ^2 - 1/4)r^{ - 2} y (\nu \geqslant 1/2) $$ with the Dirichlet boundary conditions. The potential V is the operator of multiplication by a function (in general, complex-valued) in L ²[0, π] satisfying the condition $$ \int\limits_0^\pi {r^\varepsilon } (\pi - r)^\varepsilon |V(r)|dr < \infty , \varepsilon \in [0,1] $$ . We prove the trace formula Σ _n=1 ^∞ [µ _n ? λ _n ? Σ _k=1 ^m α _k ⁽ⁿ⁾ ] = 0.     

Power Majorization and Majorization of Sequences

Let \(\bar x\) , \(\bar y\ \in\ R_n\) be vectors which satisfy x₁ ≥ x₂ ≥ … ≥ x_n and y₁ ≥ y₂ >- … ≥ y_n and Σx_i = Σy_i. We say that \(\bar x\) is power majorized by \(\bar y\) if Σx_i ^p ≤ Σy_i ^p for all real p ? [0, 1] and Σx_i ^p ≥ Σy_i ^p for p ∈ [0, 1]. In this paper we give a classification of functions ? (which includes all possible positive polynomials) for which \(\bar\phi(\bar x) \leq \bar\phi(\bar y)\) (see definition below) when \(\bar x\) is power majorized \(\bar y\) . We also answer a question posed by Clausing by showing that there are vectors \(\bar x\) , \(\bar y\ \in\ R^n\) of any dimension n ≥ 4 for which there is a convex function ? such that \(\bar x\) is power majorized by \(\bar y\) and \(\bar\phi(\bar x)\ >\ \bar\phi(\bar y)\) .     

The limits of determinacy in second order arithmetic: consistency and complexity strength

We prove that determinacy for all Boolean combinations of \({F_{\sigma \delta }}\) (Π ₃ ⁰ ) sets implies the consistency of second-order arithmetic and more. Indeed, it is equivalent to the statement saying that for every set X and every number n, there exists a β-model of Π _n ¹ -comprehension containing X. We prove this result by providing a careful level-by-level analysis of determinacy at the finite level of the difference hierarchy on \({F_{\sigma \delta }}\) (Π ₃ ⁰ ) sets in terms of both reverse mathematics, complexity and consistency strength. We show that, for n ≥ 1, determinacy for sets at the nth level in this difference hierarchy lies strictly between (in the reverse mathematical sense of logical implication) the existence of β-models of Π _n+2 ¹ -comprehension containing any given set X, and the existence of β-models of Δ _n+2 ¹ -comprehension containing any given set X. Thus the nth of these determinacy axioms lies strictly between Π _n+2 ¹ -comprehension and Δ _n+2 ¹ -comprehension in terms of consistency strength. The major new technical result on which these proof theoretic ones are based is a complexity theoretic one. The nth determinacy axiom implies closure under the operation taking a set X to the least Σ _n+1 admissible containing X (for n = 1; this is due to Welch [9]).     

A property of algebraic univoque numbers

Consider the set $ {\mathcal{U}} $ of real numbers q ≧ 1 for which only one sequence (c _i ) of integers 0 ≦ c _i ≦ q satisfies the equality Σ _i=1 ^∞ c _i q ^?i = 1. We show that the set of algebraic numbers in $ {\mathcal{U}} $ is dense in the closure $ \overline {\mathcal{U}} $ of $ {\mathcal{U}} $ .     

Wavelet characterization of growth spaces of harmonic functions

We consider the space h _ν ^∞ of harmonic functions in R ₊ ⁿ⁺¹ with finite norm ‖u‖ _ν = sup |u(x, t)|/v(t), where the weight ν satisfies the doubling condition. Boundary values of functions in h _ν ^∞ are characterized in terms of their smooth multiresolution approximations. The characterization yields the isomorphism of Banach spaces h _ν ^∞ ～ l ^∞. The results are also applied to obtain the law of the iterated logarithm for the oscillation of functions in h _ν ^∞ along vertical lines.     

Metrische Räume mit Dreiseitverbindbaren

This paper presents a system of axioms for n-dimensional metric geometry. For every group satisfying the axioms there exist a group-space and an embedding of into a projective-metric space Ω. We construct an isomorphism of onto a subgroup of a special orthogonal group O _n+1 ^* (K,f). This group belongs to a metric vector space (V,f) over a field K of characteristic ≠ 2 where dim rad V≦1. The (full) groups o _n+1 ^* (K,f) are models of the system of axioms.     

A Short Note on Essentially Σ1 Sentences

Guaspari (J Symb Logic 48:777–789, 1983) conjectured that a modal formula is it essentially Σ₁ (i.e., it is Σ₁ under any arithmetical interpretation), if and only if it is provably equivalent to a disjunction of formulas of the form ${\square{B}}$ . This conjecture was proved first by A. Visser. Then, in (de Jongh and Pianigiani, Logic at Work: In Memory of Helena Rasiowa, Springer-Physica Verlag, Heidelberg-New York, pp. 246–255, 1999), the authors characterized essentially Σ₁ formulas of languages including witness comparisons using the interpretability logic ILM. In this note we give a similar characterization for formulas with a binary operator interpreted as interpretability in a finitely axiomatizable extension of IΔ ₀  + Supexp and we address a similar problem for IΔ ₀  + Exp.     

Some results on the local cohomology of minimax modules

Let R be a commutative Noetherian ring with identity and I an ideal of R. It is shown that, if M is a non-zero minimax R-module such that dim Supp H _I ⁱ (M) ? 1 for all i, then the R-module H _I ⁱ (M) is I-cominimax for all i. In fact, H _I ⁱ (M) is I-cofinite for all i ? 1. Also, we prove that for a weakly Laskerian R-module M, if R is local and t is a non-negative integer such that dim Supp H _I ⁱ (M) ? 2 for all i < t, then Ext _R ^j (R/I,H _I ⁱ (M)) and Hom _R (R/I,H _I ^t (M)) are weakly Laskerian for all i < t and all j ? 0. As a consequence, the set of associated primes of H _I ⁱ (M) is finite for all i ? 0, whenever dim R/I ? 2 and M is weakly Laskerian.     

Sparsity and non-Euclidean embeddings

We present a relation between sparsity and non-Euclidean isomorphic embeddings. We introduce a general restricted isomorphism property and show how it enables one to construct embeddings of ? _p ⁿ , p > 0, into various types of Banach or quasi-Banach spaces. In particular, for 0 < r < p < 2 with r ≤ 1, we construct a family of operators that embed ? _p ⁿ into $\ell _r^{(1 + \eta )n}$ , with sharp polynomial bounds in η > 0.     

Comparison Inequalities for One Sided Normal Probabilities

Several sharp upper and lower bounds for the ratio of two normal probabilities $\mathbb{P}\Biggl(\,\bigcap_{i=1}^{n}\bigl\{\xi^{(1)}_i\leq \mu_i\bigr\}\Biggr)\Big/\mathbb{P}\Biggl(\,\bigcap_{i=1}^{n}\bigl\{\xi^{(0)}_i\leq \mu_i\bigr\}\Biggr)$ are given in this paper for various cases, where (ξ ₁ ⁽⁰⁾ ,ξ ₂ ⁽⁰⁾ ,…,ξ _n ⁽⁰⁾ ) and (ξ ₁ ⁽¹⁾ ,ξ ₂ ⁽¹⁾ , …,ξ _n ⁽¹⁾ ) are standard normal random variables with covariance matrices R ⁰=(r _ij ⁰ ) and R ¹=(r _ij ¹ ), respectively.     

Domatic partitions of computable graphs

Given a graph G, we say that a subset D of the vertex set V is a dominating set if it is near all the vertices, in that every vertex outside of D is adjacent to a vertex in D. A domatic k-partition of G is a partition of V into k dominating sets. In this paper, we will consider issues of computability related to domatic partitions of computable graphs. Our investigation will center on answering two types of questions for the case when k = 3. First, if domatic 3-partitions exist in a computable graph, how complicated can they be? Second, a decision problem: given a graph, how difficult is it to decide whether it has a domatic 3-partition? We will completely classify this decision problem for highly computable graphs, locally finite computable graphs, and computable graphs in general. Specifically, we show the decision problems for these kinds of graphs to be ${\Pi^{0}_{1}}$ -, ${\Pi^{0}_{2}}$ -, and ${\Sigma^{1}_{1}}$ -complete, respectively.     

Positive solutions for multi-point boundary value problems for nonlinear fractional differential equations

The paper studies the problem of existence of positive solution to the following boundary value problem: $D_{0^ + }^\sigma u''(t) - g(t)f(u(t)) = 0$ , t ∈ (0, 1), u″(0) = u″(1) = 0, au(0) ? bu′(0) = Σ _i=1 ^m?2 a _i u(ξ _i ), cu(1) + du′(1) = Σ _i=1 ^m?2 b _i u(ξ _i ), where $D_{0^ + }^\sigma$ is the Riemann-Liouville fractional derivative of order 1 < σ ≤ 2 and f is a lower semi-continuous function. Using Krasnoselskii’s fixed point theorems in a cone, the existence of one positive solution and multiple positive solutions for nonlinear singular boundary value problems is established.     

Universality is a Σ 1 1 -complete property

Our purpose in this article is to prove that if ? ∞ < a < b < ∞, then the set of all sequences with terms in C([a, b], ?) which posses a universal element is Σ ₁ ¹ -complete in C([a, b], ?)^?.