Minimal degrees which are but not

We give a short proof of the existence of minimal Turing degrees which are but not .

     

A splitting theorem for degrees

We prove that, for any , and with _{T}A\oplus U$"> and r.e., in , there are pairs and such that ; ; and, for any and from and any set , if and , then . We then deduce that for any degrees , , and such that and are recursive in , , and is into , can be split over avoiding . This shows that the Main Theorem of Cooper (Bull. Amer. Math. Soc. 23 (1990), 151-158) is false.

     

There is no degree invariant half-jump

We prove that there is no degree invariant solution to Post's problem that always gives an intermediate degree. In fact, assuming definable determinacy, if is any definable operator on degrees such that on a cone then is low or high on a cone of degrees, i.e., there is a degree such that for every or for every .

     

Recursively enumerable sets of polynomials over a finite field

We prove that a relation over is recursively enumerable if and only if it is Diophantine over . We do this by first constructing a model of in , where n is represented by Zⁿ. In a second step, we show that it suffices to eliminate a bounded universal quantifier. Then finally, the hardest part of the proof is to show that we can eliminate this quantifier.     

Extensions and extremality of recursively generated weighted shifts

Given an -step extension of a recursively generated weight sequence , and if denotes the associated unilateral weighted shift, we prove that

1).\end{cases}\end{displaymath}">

In particular, the subnormality of an extension of a recursively generated weighted shift is independent of its length if the length is bigger than 1. As a consequence we see that if is a canonical rank-one perturbation of the recursive weight sequence , then subnormality and -hyponormality for eventually coincide. We then examine a converse--an ``extremality" problem: Let be a canonical rank-one perturbation of a weight sequence and assume that -hyponormality and -hyponormality for coincide. We show that is recursively generated, i.e., is recursive subnormal.

     

On the unique representation of families of sets

Let and be uncountable Polish spaces. represents a family of sets provided each set in occurs as an -section of . We say that uniquely represents provided each set in occurs exactly once as an -section of . is universal for if every -section of is in . is uniquely universal for if it is universal and uniquely represents . We show that there is a Borel set in which uniquely represents the translates of if and only if there is a Vitali set. Assuming there is a Borel set with all sections sets and all non-empty sets are uniquely represented by . Assuming there is a Borel set with all sections which uniquely represents the countable subsets of . There is an analytic set in with all sections which represents all the subsets of , but no Borel set can uniquely represent the sets. This last theorem is generalized to higher Borel classes.

     

Games and general distributive laws in Boolean algebras

The games and are played by two players in -complete and max -complete Boolean algebras, respectively. For cardinals such that or , the -distributive law holds in a Boolean algebra iff Player 1 does not have a winning strategy in . Furthermore, for all cardinals , the -distributive law holds in iff Player 1 does not have a winning strategy in . More generally, for cardinals such that , the -distributive law holds in iff Player 1 does not have a winning strategy in . For regular and , implies the existence of a Suslin algebra in which is undetermined.

     

Isomorphism of lattices of recursively enumerable sets

Let , and for , let be the lattice of subsets of which are recursively enumerable relative to the ``oracle' . Let be , where is the ideal of finite subsets of . It is established that for any , is effectively isomorphic to if and only if , where is the Turing jump of . A consequence is that if , then . A second consequence is that can be effectively embedded into preserving least and greatest elements if and only if .

     

A join theorem for the computably enumerable degrees

It is shown that for any computably enumerable (c.e.) degree , if , then there is a c.e. degree such that (so is lowand is high). It follows from this and previous work of P. Cholak, M. Groszek and T. Slaman that the low and low c.e. degrees are not elementarily equivalent as partial orderings.

     

On some random thin sets of integers

We show how different random thin sets of integers may have different behaviour. First, using a recent deviation inequality of Boucheron, Lugosi and Massart, we give a simpler proof of one of our results in Some new thin sets of integers in harmonic analysis, Journal d'Analyse Mathématique 86 (2002), 105-138, namely that there exist -Rider sets which are sets of uniform convergence and -sets for all but which are not Rosenthal sets. In a second part, we show, using an older result of Kashin and Tzafriri, that, for , the -Rider sets which we had constructed in that paper are almost surely not of uniform convergence.

     

How often are two permutations comparable?

Two permutations of are comparable in the Bruhat order if one is closer, in a natural way, to the identity permutation, , than the other. We show that the number of comparable pairs is of order at most, and at least. For the related weak order, the corresponding bounds are and , where . In light of numerical experiments, we conjecture that for each order the upper bound is qualitatively close to the actual number of comparable pairs.

     

The removal of from some undecidable problems involving elementary functions

We show that in the ring generated by the integers and the functions and defined on it is undecidable whether or not a function has a positive value or has a root. We also prove that the existential theory of the exponential field is undecidable.

     

The -theory of the computably enumerable Turing degrees is undecidable

We show the undecidability of the -theory of the partial order of computably enumerable Turing degrees.

     

Some remarks on totally imperfect sets

We prove the following two theorems.

Theorem 1. Let be a strongly meager subset of . Then it is dual Ramsey null.

We will say that a -ideal of subsets of satisfies the condition iff for every , if

then .

Theorem 2. The -ideals of perfectly meager sets, universally meager sets and perfectly meager sets in the transitive sense satisfy the condition .

     

The Hausdorff dimension of visible sets of planar continua

For a compact set and a point , we define the visible part of from to be the set

(Here denotes the closed line segment joining to .)

In this paper, we use energies to show that if is a compact connected set of Hausdorff dimension greater than one, then for (Lebesgue) almost every point , the Hausdorff dimension of is strictly less than the Hausdorff dimension of . In fact, for almost every ,

We also give an estimate of the Hausdorff dimension of those points where the visible set has dimension greater than for some .

     

Schreier sets in Ramsey theory

We show that Ramsey theory, a domain presently conceived to guarantee the existence of large homogeneous sets for partitions on -tuples of words (for every natural number ) over a finite alphabet, can be extended to one for partitions on Schreier-type sets of words (of every countable ordinal). Indeed, we establish an extension of the partition theorem of Carlson about words and of the (more general) partition theorem of Furstenberg-Katznelson about combinatorial subspaces of the set of words (generated from -tuples of words for any fixed natural number ) into a partition theorem about combinatorial subspaces (generated from Schreier-type sets of words of order any fixed countable ordinal). Furthermore, as a result we obtain a strengthening of Carlson's infinitary Nash-Williams type (and Ellentuck type) partition theorem about infinite sequences of variable words into a theorem, in which an infinite sequence of variable words and a binary partition of all the finite sequences of words, one of whose components is, in addition, a tree, are assumed, concluding that all the Schreier-type finite reductions of an infinite reduction of the given sequence have a behavior determined by the Cantor-Bendixson ordinal index of the tree-component of the partition, falling in the tree-component above that index and in its complement below it.

     

Removable sets for continuous solutions of quasilinear elliptic equations

We show that sets of Hausdorff measure zero are removable for -Hölder continuous solutions to quasilinear elliptic equations similar to the -Laplacian. The result is optimal. We also treat larger sets in terms of a growth condition. In particular, our results apply to quasiregular mappings.

     

Some new results in multiplicative and additive Ramsey theory

There are several notions of largeness that make sense in any semigroup, and others such as the various kinds of density that make sense in sufficiently well-behaved semigroups including and . It was recently shown that sets in which are multiplicatively large must contain arbitrarily large geoarithmetic progressions, that is, sets of the form , as well as sets of the form . Consequently, given a finite partition of , one cell must contain such configurations. In the partition case we show that we can get substantially stronger conclusions. We establish some combined additive and multiplicative Ramsey theoretic consequences of known algebraic results in the semigroups and , derive some new algebraic results, and derive consequences of them involving geoarithmetic progressions. For example, we show that given any finite partition of there must be, for each , sets of the form together with , the arithmetic progression , and the geometric progression in one cell of the partition. More generally, we show that, if is a commutative semigroup and a partition regular family of finite subsets of , then for any finite partition of and any , there exist and such that is contained in a cell of the partition. Also, we show that for certain partition regular families and of subsets of , given any finite partition of some cell contains structures of the form for some .