The Analytic Polynomial-Time Hierarchy

Motivated by results on interactive proof systems we investigate an ?-?hierarchy over P using word quantifiers as well as two types of set quantifiers. This hierarchy, which extends the (arithmetic) polynomial-time hierarchy, is called the analytic polynomial-time hierarchy. It is shown that every class of this hierarchy coincides with one of the following Classes: ∑, Π (k?0), PSPACE, ∑ or Π (k?1). This improves previous results by Orponen [6] and allows interesting comparisons with the above mentioned results on inter-active proof systems.     

ITERATIONS OF SATISFACTION CLASSES AND MODELS OF PEANO ARITHMETIC

We consider iterations of satisfaction classes and apply them to construct expansions of models of Peano arithmetic to models of A|Δ+∑-AC. 1991 MSC: 03F35, 03C62.     

ANALYTIC COMPLETENESS THEOREM FOR ABSOLUTELY CONTINUOUS BIPROBABILITY MODELS

Hoover [2] proved a completeness theorem for the logic L(∫)??. The aim of this paper is to prove a similar completeness theorem with respect to product measurable biprobability models for a logic L(∫₁, ∫₂) with two integral operators. We prove: If T is a ∑₁ definable theory on ?? (a countable admissible set and ω ∈) and consistent with the axioms of L(∫₁, ∫₂), then there is an analytic absolutely continuous biprobability model in which every sentence in T is satified.     

Recursive Structures and Ershov's Hierarchy

Ash and Nerode [2] gave natural definability conditions under which a relation is intrinsically r. e. Here we generalize this to arbitrary levels in Ershov's hierarchy of Δ sets, giving conditions under which a relation is intrinsically α-r. e. Mathematics Subject Classification: 03C57, 03D55.     

On Σ1-definable Functions Provably Total in I ∏

We prove the following theorem: Let φ(x) be a formula in the language of the theory PA^? of discretely ordered commutative rings with unit of the form ?yφ′(x,y) with φ′ and let ∈ Δ₀ and let fφ: ? → ? such that f_φ(x) = y iff φ′(x,y) & (?z < y) φ′(x,z). If I ∏ ∈(?x ≥ 0), φ then there exists a natural number K such that I ∏ ? ?y?x(x > y ? ?φ(x) < x^K). Here I ∏₁^? denotes the theory PA^? plus the scheme of induction for formulas φ(x) of the form ?yφ′(x,y) (with φ′) with φ′ ∈ Δ₀.     

Subgraphs smaller than the girth

For graphs A, B, let () denote the number of subsets of nodes of A for which the induced subgraph is B. If G and H both have girth > k, and if () = () for every k-node tree T, then for every k-node forest F, () = (). Say the spread of a tree is the number of nodes in a longest path. If G is regular of degree d, on n nodes, with girth > k, and if F is a forest of total spread ≤k, then the value of () depends only on n and d.     

Extracting Algorithms from Intuitionistic Proofs

This paper presents a new method - which does not rely on the cut-elimination theorem - for characterizing the provably total functions of certain intuitionistic subsystems of arithmetic. The new method hinges on a realizability argument within an infinitary language. We illustrate the method for the intuitionistic counterpart of Buss's theory S, and we briefly sketch it for the other levels of bounded arithmetic and for the theory IΣ₁.     

On invariant measures of extensions of Markov transition functions

By using the LITTLEWOOD matrices A_2n we generalize CLARKSON' S inequalities, or equivalently, we determine the norms ‖A_2n: l(L_P) → l(L_P)‖ completely. The result is compared with the norms ‖A_2n: l → l‖, which are calculated implicitly in PIETSCH [6].     

Function Spaces with Exponential Weights II

This paper is a continuation of [8]. We study weighted function spaces of type B and F on the Euclidean space Rⁿ, where u is a weight function of at most exponential growth. In particular, u(χ (±|χ|) is an admissible weight. We deal with atomic decompositions of these spaces. Furthermore, we prove that the spaces B and F are isomorphic to the corresponding unweighted spaces B and F.     

Ulm Classification of Analytic Equivalence Relations in Generic Universes

We prove that if every real belongs to a set generic extension of L, then every Σ equivalence relation E on reals either admits a Δ₁ reduction to the equality on the set 2^{< ω1} of all countable binary sequences, or the Vitali equivalence E₀ continuously embeds in E. The proofs are based on a topology generated by OD sets.     

An Infinitary Graded Modal Logic (Graded Modalities VI)

We prove a completeness theorem for K, the infinitary extension of the graded version K⁰ of the minimal normal logic K, allowing conjunctions and disjunctions of countable sets of formulas. This goal is achieved using both the usual tools of the normal logics with graded modalities and the machinery of the predicate infinitary logics in a version adapted to modal logic.     

On the Lorentz-Marcinkiewicz Operator Ideal

This article deals with the LORENTZ-MARCINKIEWICZ operator ideal ?? generated by an additive s-function and the LORENTZ-MARCINKIEWICZ sequence space λ^q(φ). We give eigenvalue distributions for operators belonging to ?? (E, E) and we show the interpolation properties of ??-ideals. Furthermore, we study certain SCHAUDER bases in ?? (H, K), H and K Hilbert spaces.     

How many normal measures can ℵ carry?

Relative to the existence of a supercompact cardinal with a measurable cardinal above it, we show that it is consistent for ?₁ to be regular and for ? to be measurable and to carry precisely τ normal measures, where τ ≥ ? is any regular cardinal. This extends the work of [2], in which the analogous result was obtained for ?_{ω +1} using the same hypotheses (© 2010 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Resonance phenomena for a class of partial differential equations of higher order in cylindrical waveguides

We consider a domain Ω in ?ⁿ of the form Ω = ?^l × Ω′ with bounded Ω′ ? ?^n?l. In Ω we study the Dirichlet initial and boundary value problem for the equation ? u + [(? ? ?… ? ?)^m + (? ? ?… ? ?)^m]u = fe^?iωt. We show that resonances can occur if 2m ≥ l. In particular, the amplitude of u may increase like t^α (α rational, 0<α<1) or like in t as t∞∞. Furthermore, we prove that the limiting amplitude principle holds in the remaining cases.     

Über die Radon-Transformation kreissymmetrischer Funktionen und ihre Beziehung zur Sommerfeldschen Theorie der Hankelfunktionen

For the Radon transform of functions with circular symmetry an inversion formula is proved in a new and elementary way. The inversion formula combined with Fourier theory is applied to Sommer-feld's integral for H, yielding a representation of products which generalizes Nicholson's integral for |H| ².     

Countable Direct Sums of Banach Spaces

Let (X_n) be a sequence of infinite-dimensional BANACH spaces. We prove that has a non-locally complete quotient if X₁ is not quasi-reflexive.     

Cylinder Homomorphisms and Chow Groups

Let X be a projective algebraic manifold of dimension n (over C), CH¹(X) the Chow group of algebraic cycles of codimension l on X, modulo rational equivalence, and A¹(X) ? CH¹(X) the subgroup of cycles algebraically equivalent to zero. We say that A¹(X) is finite dimensional if there exists a (possibly reducible) smooth curve T and a cycle z∈CH¹(Γ × X) such that z_*:A¹(Γ)-A¹(X) is surjective. There is the well known Abel-Jacobi map λ₁:A¹(X)-J(X), where J(X) is the lth Lieberman Jacobian. It is easy to show that A¹(X)→J(X) A¹(X) finite dimensional. Now set with corresponding map A^*(X)→J(X). Also define Level . In a recent book by the author, there was stated the following conjecture: where it was also shown that (?) in (**) is a consequence of the General Hodge Conjecture (GHC). In this present paper, we prove A^*(X) finite dimensional ?? Level (H^*(X)) ≤ 1 for a special (albeit significant) class of smooth hypersurfaces. We make use of the family of k-planes on X, where ([…] = greatest integer function) and d = deg X; moreover the essential technical ingredients are the Lefschetz theorems for cohomology and an analogue for Chow groups of hypersurfaces. These ingredients in turn imply very special cases of the GHC for our choice of hypersurfaces X. Some applications to the Griffiths group, vanishing results, and (universal) algebraic representatives for certain Chow groups are given.     

Sharp Sobolev Embeddings and Related Hardy Inequalities: The Sub -- Critical Case

The paper deals with sharp embeddings of the spaces B and F into rearrangement-variant spaces and related Hardy inequalities. Here (1/_p, s) belongs to the interior of the shaded invariant spaces region in the Figure     

Selbstadjungierte Relations-Erweiterungen für eine Klasse von symmetrischen Differential-Funktional-Operatoren

Symmetry- and selfadjointness-conditions are derived for ordinary differential-integral-interface operators under integral-interface conditions. Criteria for the existence of selfadjoint extensions in L×L are given. These extensions are characterized in a constructive way. The main tools are some extension-theorems for linear relations (subspaces), wich are developed in section 2.     

The circular chromatic number of the Mycielskian of G

In a search for triangle-free graphs with arbitrarily large chromatic numbers, Mycielski developed a graph transformation that transforms a graph G into a new graph μ(G), we now call the Mycielskian of G, which has the same clique number as G and whose chromatic number equals χ(G) + 1. Chang, Huang, and Zhu [G. J. Chang, L. Huang, & X. Zhu, Discrete Math, to appear] have investigated circular chromatic numbers of Mycielskians for several classes of graphs. In this article, we study circular chromatic numbers of Mycielskians for another class of graphs G. The main result is that χ_c(μ(G)) = χ(μ(G)), which settles a problem raised in [G. J. Chang, L. Huang, & X. Zhu, Discrete Math, to appear, and X. Zhu, to appear]. As χ_c(G) = and χ(G) = , consequently, there exist graphs G such that χ_c(G) is as close to χ(G) − 1 as you want, but χ_c(μ(G)) = χ(μ(G)). © 1999 John Wiley & Sons, Inc. J Graph Theory 32: 63–71, 1999