A short proof of the preservation of the ωω‐bounding property

There are two versions of the Proper Iteration Lemma. The stronger (but less well‐known) version can be used to give simpler proofs of iteration theorems (e.g., [7, Lemma 24] versus [9, Theorem IX.4.7]). In this paper we give another demonstration of the fecundity of the stronger version by giving a short proof of Shelah's theorem on the preservation of the ω^ω‐bounding property. (© 2003 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

The Computational Power of ℳ︁ω

We prove that the Kleene schemes for primitive recursion relative to the μ‐operator, relativized to some nondeterministic objects, have the same power to express total functionals when interpreted over the partial continuous functionals and over the Kleene‐Kreisel continuous functionals. Relating the former interpretation to Niggl's ℳ︁^ω we prove Nigg's conjecture that ℳ︁^ω is strictly weaker than Plotkin's PCF + PA.     

On some sets of dictionaries whose ω ‐powers have a given

A dictionary is a set of finite words over some finite alphabet X. The ω ‐power of a dictionary V is the set of infinite words obtained by infinite concatenation of words in V. Lecomte studied in [10] the complexity of the set of dictionaries whose associated ω ‐powers have a given complexity. In particular, he considered the sets ??( Σ ⁰k) (respectively, ??( Π ⁰_k), ??( Δ ¹₁)) of dictionaries V ? 2* whose ω ‐powers are Σ ⁰_k‐sets (respectively, Π ⁰_k‐sets, Borel sets). In this paper we first establish a new relation between the sets ??( Σ ⁰₂) and ??( Δ ¹₁), showing that the set ??( Δ ¹₁) is “more complex” than the set ??( Σ ⁰₂). As an application we improve the lower bound on the complexity of ??( Δ ¹₁) given by Lecomte, showing that ??( Δ ¹₁) is in Σ ¹ ₂(2^2*)\ Π ⁰₂. Then we prove that, for every integer k ≥ 2 (respectively, k ≥ 3), the set of dictionaries ??( Π ⁰_k+1) (respectively, ??( Σ ⁰_{k +1})) is “more complex” than the set of dictionaries ??( Π ⁰_k) (respectively, ??( Σ ⁰_k)) (© 2010 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

ω‐categorical weakly o‐minimal expansions of Boolean lattices

We study ω‐categorical weakly o‐minimal expansions of Boolean lattices. We show that a structure ?? = (A,≤, ?) expanding a Boolean lattice (A,≤) by a finite sequence I of ideals of A closed under the usual Heyting algebra operations is weakly o‐minimal if and only if it is ω‐categorical, and hence if and only if A/I has only finitely many atoms for every I ∈ ?. We propose other related examples of weakly o‐minimal ω‐categorical models in this framework, and we examine the internal structure of these models.     

The strong partition relation on ω1 revisited

We give a new proof of the strong partition relation on ω₁, assuming the axiom of determinacy, which uses only a general argument not involving the complete analysis of a measure on ω₁. (© 2003 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

σ‐short Boolean algebras

We introduce properties of Boolean algebras which are closely related to the existence of winning strategies in the Banach‐Mazur Boolean game. A σ‐short Boolean algebra is a Boolean algebra that has a dense subset in which every strictly descending sequence of length ω does not have a nonzero lower bound. We give a characterization of σ‐short Boolean algebras and study properties of σ‐short Boolean algebras. (© 2003 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Hierarchies in φ‐spaces and applications

We establish some results on the Borel and difference hierarchies in φ‐spaces. Such spaces are the topological counterpart of the algebraic directed‐complete partial orderings. E.g., we prove analogs of the Hausdorff Theorem relating the difference and Borel hierarchies and of the Lavrentyev Theorem on the non‐collapse of the difference hierarchy. Some of our results generalize results of A. Tang for the space Pω. We also sketch some older applications of these hierarchies and present a new application to the question of characterizing the ω‐ary Boolean operations generating a given level of the Wadge hierarchy from the open sets. (© 2004 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Index sets for ω‐languages

An ω‐language is a set of infinite sequences (words) on a countable language, and corresponds to a set of real numbers in a natural way. Languages may be described by logical formulas in the arithmetical hierarchy and also may be described as the set of words accepted by some type of automata or Turing machine. Certain families of languages, such as the languages, may enumerated as P₀, P₁, … and then an index set associated to a given property R (such as finiteness) of languages is just the set of e such that P_e has the property. The complexity of index sets for 7 types of languages is determined for various properties related to the size of the language.     

S‐asymptotically ω‐periodic solutions for semilinear Volterra equations

We study S‐asymptotically ω‐periodic mild solutions of the semilinear Volterra equation u′(t)=(a* Au)(t)+f(t, u(t)), considered in a Banach space X, where A is the generator of an (exponentially) stable resolvent family. In particular, we extend the recent results for semilinear fractional integro‐differential equations considered in (Appl. Math. Lett. 2009; 22:865–870) and for semilinear Cauchy problems of first order given in (J. Math. Anal. Appl. 2008; 343(2): 1119–1130). Applications to integral equations arising in viscoelasticity theory are shown. Copyright © 2010 John Wiley & Sons, Ltd.     

Radius two trees specify χ-bounded classes

A class of graphs χ is said to be χ-bounded, with χ-binding function f, if for all G ? Γ, χ (G) ≦ f (ω(G)), where χ(G) is the chromatic number of G and ω(G) is the clique number of G. It has been conjectured that for every tree T, the class of graphs that do not induce T is χ-bounded. We show that this is true in the case where T is a tree of radius two.     

ON THE ITERATED ω-RULE

Let Γ_n(φ) be a formula of L_PA (PA = Peano Arithmetic) meaning “there is a proof of φ from PA-axioms, in which ω-rule is iterated no more than n times”. We examine relations over pairs of natural numbers of the kind. (n, k) ≦_H (n', k') iff PA + RFN_n' (H_k') ? RFN_n (H_k). Where H denotes one of the hierarchies ∑ or Π and RFN_n(C) is the scheme of the reflection principle for Γ_n restricted to formulas from the class C(Γ_n(φ) implies “φ is true”, for every φ ∈ C). Our main result is that. (n, k) ≦H (n', k') if n ≦ n' and k ≦ max (k', 2n' + 1).     

Canonical forms of Borel-measurable mappings Δ: [ω] →

We show that for every Borel-measurable mapping Δ: [ω]^ω → there exists A [ω]^ω and there exists a continuous mapping Γ: [A]^ω → [A]^ω with Γ(X) X such that for all X, Y [A]^ω it follows that Δ(X) = Δ(Y) if Γ(X) = Γ(Y). In a sense, this is generalization of the Erdös-Rado canonization theorem     

α-Stable characterization of Banach spaces (1 < α < 2)

This work characterizes some subclasses of α-stable (0 < α < 1) Banach spaces in terms of the extendibility to Radon laws of certain α-stable cylinder measures. These result extend the work of S. Chobanian and V. Tarieladze (J. Multivar. Anal.7, 183–203 (1977)). For these spaces it is shown that every Radon stable measure is the continuous image of a stable measure on a suitable L_β space with β = α(1 − α)⁻¹. The latter result extends some work of Garling (Ann. Probab.4, 600–611 (1976)) and Jain (Proceedings, Symposia in Pure Math. XXXI, p. 55–65, Amer. Math. Soc., Providence, R.I.).     

Ω‐estimates related to irreducible algebraic integers

We study large values of the remainder term E_K (x) in the asymptotic formula for the number of irreducible integers in an algebraic number field K. We show that E_K (x) = Ω_± (√(x)(log x)) for certain positive constant B_K, improving in that way the previously best known estimate E_K (x) = Ω_± (x^(1/2)‐ε) for every ε > 0, due to A. Perelli and the present author. Assuming that no entire L‐function from the Selberg class vanishes on the vertical line σ = 1, we show that E_K (x) = Ω_± (√(x)(log log x)^{D (K)‐1}(log x)^‐1), supporting a conjecture raised recently by the author. In particular, it follows that the last omega estimate is a consequence of the Selberg Orthonormality Conjecture (© 2010 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

The existence of free ultrafilters on ω does not imply the extension of filters on ω to ultrafilters

Let X be an infinite set and let and denote the propositions “every filter on X can be extended to an ultrafilter” and “X has a free ultrafilter”, respectively. We denote by the Stone space of the Boolean algebra of all subsets of X. We show:

相似文献   

Maximal σ‐polynomials of connected 3‐chromatic graphs

In the set of graphs of order n and chromatic number k the following partial order relation is defined. One says that a graph G is less than a graph H if c_i(G) ≤ c_i(H) holds for every i, k ≤ i ≤ n and at least one inequality is strict, where c_i(G) denotes the number of i‐color partitions of G. In this paper the first ? n/2 ? levels of the diagram of the partially ordered set of connected 3‐chromatic graphs of order n are described. © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 210–222, 2003     

On κ‐hereditary Sets and Consequences of the Axiom of Choice

We will prove that some so‐called union theorems (see [2]) are equivalent in ZF⁰ to statements about the transitive closure of relations. The special case of “bounded” union theorems dealing with κ‐hereditary sets yields equivalents to statements about the transitive closure of κ‐narrow relations. The instance κ = ω₁ (i. e., hereditarily countable sets) yields an equivalent to Howard‐Rubin's Form 172 (the transitive closure Tc(x) of every hereditarily countable set x is countable). In particular, the countable union theorem (Howard‐Rubin's Form 31) and, a fortiori, the axiom of countable choice imply Form 172.     

Perfect coloring and linearly χ‐bound P6‐free graphs

We derive decomposition theorems for P₆, K₁ + P₄‐free graphs, P₅, K₁ + P₄‐free graphs and P₅, K₁ + C₄‐free graphs, and deduce linear χ‐binding functions for these classes of graphs (here, P_n (C_n) denotes the path (cycle) on n vertices and K₁ + G denotes the graph obtained from G by adding a new vertex and joining it with every vertex of G). Using the same techniques, we also obtain an optimal χ‐binding function for P₅, C₄‐free graphs which is an improvement over that given in [J. L. Fouquet, V. Giakoumakis, F. Maire, and H. Thuillier, 11 , Discrete Math, 146, 33–44.]. © 2006 Wiley Periodicals, Inc. J Graph Theory 54: 293–306, 2007     

Embedding vector‐valued Besov spaces into spaces of γ ‐radonifying operators

It is shown that a Banach space E has type p if and only for some (all) d ≥ 1 the Besov space B^{(1/p – 1/2)d} _p,p (?^d ; E) embeds into the space γ (L²(?^d ), E) of γ ‐radonifying operators L²(?^d ) → E. A similar result characterizing cotype q is obtained. These results may be viewed as E ‐valued extensions of the classical Sobolev embedding theorems. (© 2008 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)