A high noncuppable {\Sigma^0_2} e-degree

We construct a e-degree which is both high and noncuppable. Thus demonstrating the existence of a high e-degree whose predecessors are all properly .     

Embedding FD(ω) into {\mathcal{P}_s} densely

Let be the lattice of degrees of non-empty subsets of 2 ^ω under Medvedev reducibility. Binns and Simpson proved that FD(ω), the free distributive lattice on countably many generators, is lattice-embeddable below any non-zero element in . Cenzer and Hinman proved that is dense, by adapting the Sacks Preservation and Sacks Coding Strategies used in the proof of the density of the c.e. Turing degrees. With a construction that is a modification of the one by Cenzer and Hinman, we improve on the result of Binns and Simpson by showing that for any , we can lattice embed FD(ω) into strictly between and . We also note that, in contrast to the infinite injury in the proof of the Sacks Density Theorem, in our proof all injury is finite, and that this is also true for the proof of Cenzer and Hinman, if a straightforward simplification is made. Thanks to my adviser Peter Cholak for his guidance in my research. I also wish to thank the anonymous referee for helpful comments and suggestions. My research was partially supported by NSF grants DMS-0245167 and RTG-0353748 and a Schmitt Fellowship at the University of Notre Dame.     

Partitions of large Rado graphs

Let κ be a cardinal which is measurable after generically adding many Cohen subsets to κ and let be the κ-Rado graph. We prove, for 2 ≤ m < ω, that there is a finite value such that the set [κ] ^m can be partitioned into classes such that for any coloring of any of the classes C _i in fewer than κ colors, there is a copy of in such that is monochromatic. It follows that , that is, for any coloring of with fewer than κ colors there is a copy of such that has at most colors. On the other hand, we show that there are colorings of such that if is any copy of then for all , and hence . We characterize as the cardinality of a certain finite set of types and obtain an upper and a lower bound on its value. In particular, and for m > 2 we have where r _m is the corresponding number of types for the countable Rado graph. Research of M. Džamonja and J. A. Larson were partially supported by Engineering and Physical Sciences Research Council and research of W. J. Mitchell was partly supported by grant number DMS 0400954 from the United States National Science Foundation.     

Potential continuity of colorings

We say that a coloring is continuous if it is continuous with respect to some second countable topology on κ. A coloring c is potentially continuous if it is continuous in some -preserving extension of the set-theoretic universe. Given an arbitrary coloring , we define a forcing notion that forces c to be continuous. However, this forcing might collapse cardinals. It turns out that is c.c.c. if and only if c is potentially continuous. This gives a combinatorial characterization of potential continuity. On the other hand, we show that adding Cohen reals to any model of set theory introduces a coloring which is potentially continuous but not continuous. has no uncountable c-homogeneous subset in the Cohen extension, but such a set can be introduced by forcing. The potential continuity of c can be destroyed by some c.c.c. forcing. The research for this paper was supported by G.I.F. Research Grant No. I-802-195.6/2003. The author would like to thank Uri Abraham for very fruitful discussions on the subject of this article.     

Weights of twisted exponential sums

Let k be a finite field of characteristic p, l a prime number different from p, a nontrivial additive character, and a character on . Then ψ defines an Artin-Schreier sheaf on the affine line , and χ defines a Kummer sheaf on the n-dimensional torus . Let be a Laurent polynomial. It defines a k-morphism . In this paper, we calculate the weights of under some non-degeneracy conditions on f. Our results can be used to estimate sums of the form

Degrees of difficulty of generalized r.e. separating classes

Important examples of classes of functions are the classes of sets (elements of ^ω 2) which separate a given pair of disjoint r.e. sets: . A wider class consists of the classes of functions f ∈ ^ω k which in a generalized sense separate a k-tuple of r.e. sets (not necessarily pairwise disjoint) for each k ∈ ω: . We study the structure of the Medvedev degrees of such classes and show that the set of degrees realized depends strongly on both k and the extent to which the r.e. sets intersect. Let denote the Medvedev degrees of those such that no m + 1 sets among A ₀,...,A _k-1 have a nonempty intersection. It is shown that each is an upper semi-lattice but not a lattice. The degree of the set of k-ary diagonally nonrecursive functions is the greatest element of . If 2 ≤ l < k, then 0 _M is the only degree in which is below a member of . Each is densely ordered and has the splitting property and the same holds for the lattice it generates. The elements of are exactly the joins of elements of for . Supported by National Science Foundation grants DMS 0554841, 0532644 and 0652732.     

Chains and antichains in partial orderings

We study the complexity of infinite chains and antichains in computable partial orderings. We show that there is a computable partial ordering which has an infinite chain but none that is or , and also obtain the analogous result for antichains. On the other hand, we show that every computable partial ordering which has an infinite chain must have an infinite chain that is the difference of two sets. Our main result is that there is a computably axiomatizable theory K of partial orderings such that K has a computable model with arbitrarily long finite chains but no computable model with an infinite chain. We also prove the corresponding result for antichains. Finally, we prove that if a computable partial ordering has the feature that for every , there is an infinite chain or antichain that is relative to , then we have uniform dichotomy: either for all copies of , there is an infinite chain that is relative to , or for all copies of , there is an infinite antichain that is relative to .     

Branching in the {\Sigma^0_2} -enumeration degrees: a new perspective

We give an alternative and more informative proof that every incomplete -enumeration degree is the meet of two incomparable -degrees, which allows us to show the stronger result that for every incomplete -enumeration degree a, there exist enumeration degrees x ₁ and x ₂ such that a, x ₁, x ₂ are incomparable, and for all b  ≤  a, b  =  (b ∨ x ₁ ) ∧ (b ∨ x ₂ ). The first author would like to thank her advisor, Andrea Sorbi, whose guidance made this paper possible. The second author has been supported by a Marie Curie Incoming International Fellowship of the European Community FP6 Program under contract number MIFI-CT-2006-021702.     

Effectively closed sets and enumerations

An effectively closed set, or class, may viewed as the set of infinite paths through a computable tree. A numbering, or enumeration, is a map from ω onto a countable collection of objects. One numbering is reducible to another if equality holds after the second is composed with a computable function. Many commonly used numberings of classes are shown to be mutually reducible via a computable permutation. Computable injective numberings are given for the family of classes and for the subclasses of decidable and of homogeneous classes. However no computable numberings exist for small or thin classes. No computable numbering of trees exists that includes all computable trees without dead ends. Research partially supported by National Science Foundation grants DMS 0554841, 0532644 and 0652732.     

Convex sets with semidefinite representation

We provide a sufficient condition on a class of compact basic semialgebraic sets for their convex hull co(K) to have a semidefinite representation (SDr). This SDr is explicitly expressed in terms of the polynomials g _j that define K. Examples are provided. We also provide an approximate SDr; that is, for every fixed , there is a convex set such that (where B is the unit ball of ), and has an explicit SDr in terms of the g _j ’s. For convex and compact basic semi-algebraic sets K defined by concave polynomials, we provide a simpler explicit SDr when the nonnegative Lagrangian L _f associated with K and any linear is a sum of squares. We also provide an approximate SDr specific to the convex case.      

Syzygies of grids of projective lines

In this paper we study the syzygy modules of a grid or a fat grid of . We compute the minimal free resolution for the ideal of a complete grid in , and we conjecture this resolution in . Moreover we compute the minimal free resolution for the ideal of an incomplete grid of . We also conjecture the minimal free resolution for the ideal of a fat complete grid in .      

Wadge Degrees of Infinitary Rational Relations

We show that, from the topological point of view, 2-tape Büchi automata have the same accepting power as Turing machines equipped with a Büchi acceptance condition. The Borel and the Wadge hierarchies of the class RAT _ω of infinitary rational relations accepted by 2-tape Büchi automata are equal to the Borel and the Wadge hierarchies of ω-languages accepted by real-time Büchi 1-counter automata or by Büchi Turing machines. In particular, for every non-null recursive ordinal α, there exist some -complete and some -complete infinitary rational relations. And the supremum of the set of Borel ranks of infinitary rational relations is an ordinal which is strictly greater than the first non-recursive ordinal . This very surprising result gives answers to questions of Simonnet [39] and of Lescow and Thomas [30,43]. This paper is an extended version of a conference paper which appeared in the Proceedings of the 23rd International Symposium on Theoretical Aspects of Computer Science, STACS 2006, [19].     

A speciality theorem for curves in P<Superscript>5</Superscript>

Let be an integral projective curve. One defines the speciality index e(C) of C as the maximal integer t such that , where ω _C denotes the dualizing sheaf of . Extending a classical result of Halphen concerning the speciality of a space curve, in the present paper we prove that if is an integral degree d curve not contained in any surface of degree  < s, in any threefold of degree  < t, and in any fourfold of degree  < u, and if , then Moreover equality holds if and only if C is a complete intersection of hypersurfaces of degrees u, , and . We give also some partial results in the general case , .      

Generalised twists,stationary loops,and the Dirichlet energy over a space of measure preserving maps

Let be a bounded Lipschitz domain and consider the Dirichlet energy functional

Skew Boolean algebras derived from generalized Boolean algebras

Every skew Boolean algebra S has a maximal generalized Boolean algebra image given by S/ where is the Green’s relation defined initially on semigroups. In this paper we study skew Boolean algebras constructed from generalized Boolean algebras B by a twisted product construction for which . In particular we study the congruence lattice of with an eye to viewing as a minimal skew Boolean cover of B. This construction is the object part of a functor from the category GB of generalized Boolean algebras to the category LSB of left-handed skew Boolean algebras. Thus we also look at its left adjoint functor . This paper was written while the second author was a Visiting Professor in the Department of Education at the University of Cagliari. The facilities and assistance provided by the University and by the Department are gratefully acknowledged.     

Existence theory of abstract approximate deconvolution models of turbulence

This report studies an abstract approach to modeling the motion of large eddies in a turbulent flow. If the Navier-Stokes equations (NSE) are averaged with a local, spatial convolution type filter, , the resulting system is not closed due to the filtered nonlinear term . An approximate deconvolution operator D is a bounded linear operator which is an approximate filter inverse

Parameterized partition relations on the real numbers

We consider several kinds of partition relations on the set of real numbers and its powers, as well as their parameterizations with the set of all infinite sets of natural numbers, and show that they hold in some models of set theory. The proofs use generic absoluteness, that is, absoluteness under the required forcing extensions. We show that Solovay models are absolute under those forcing extensions, which yields, for instance, that in these models for every well ordered partition of there is a sequence of perfect sets whose product lies in one piece of the partition. Moreover, for every finite partition of there is and a sequence of perfect sets such that the product lies in one piece of the partition, where is the set of all infinite subsets of X. The proofs yield the same results for Borel partitions in ZFC, and for more complex partitions in any model satisfying a certain degree of generic absoluteness. This work was supported by the research projects MTM 2005-01025 of the Spanish Ministry of Science and Education and 2005SGR-00738 of the Generalitat de Catalunya. A substantial part of the work was carried out while the second-named author was ICREA Visiting Professor at the Centre de Recerca Matemàtica in Bellaterra (Barcelona), and also during the first-named author’s stays at the Instituto Venezolano de Investigaciones Científicas and the California Institute of Technology. The authors gratefully acknowledge the support provided by these institutions.     

The Jordan curve theorem and the Schönflies theorem in weak second-order arithmetic

In this paper, we show within ${\mathsf{RCA}_0}In this paper, we show within that both the Jordan curve theorem and the Sch?nflies theorem are equivalent to weak K?nig’s lemma. Within , we prove the Jordan curve theorem using an argument of non-standard analysis based on the fact that every countable non-standard model of has a proper initial part that is isomorphic to itself (Tanaka in Math Logic Q 43:396–400, 1997).      

The elementary computable functions over the real numbers: applying two new techniques

The basic motivation behind this work is to tie together various computational complexity classes, whether over different domains such as the naturals or the reals, or whether defined in different manners, via function algebras (Real Recursive Functions) or via Turing Machines (Computable Analysis). We provide general tools for investigating these issues, using two techniques we call approximation and lifting. We use these methods to obtain two main theorems. First, we provide an alternative proof of the result from Campagnolo et al. (J Complex 18:977–1000, 2002), which precisely relates the Kalmar elementary computable functions to a function algebra over the reals. Second, we build on that result to extend a result of Bournez and Hainry (Theor Comput Sci 348(2–3):130–147, 2005), which provided a function algebra for the real elementary computable functions; our result does not require the restriction to functions. In addition to the extension, we provide an alternative approach to the proof. Their proof involves simulating the operation of a Turing Machine using a function algebra. We avoid this simulation, using a technique we call lifting, which allows us to lift the classic result regarding the elementary computable functions to a result on the reals. The two new techniques bring a different perspective to these problems, and furthermore appear more easily applicable to other problems of this sort.