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.     

Friedberg Numberings of Families of n-Computably Enumerable Sets

We establish a number of results on numberings, in particular, on Friedberg numberings, of families of d.c.e. sets. First, it is proved that there exists a Friedberg numbering of the family of all d.c.e. sets. We also show that this result, patterned on Friedberg's famous theorem for the family of all c.e. sets, holds for the family of all n-c.e. sets for any n>2. Second, it is stated that there exists an infinite family of d.c.e. sets without a Friedberg numbering. Third, it is shown that there exists an infinite family of c.e. sets (treated as a family of d.c.e. sets) with a numbering which is unique up to equivalence. Fourth, it is proved that there exists a family of d.c.e. sets with a least numbering (under reducibility) which is Friedberg but is not the only numbering (modulo reducibility).     

Equivalence of bar induction and bar recursion for continuous functions with continuous moduli

We compare Brouwer's bar theorem and Spector's bar recursion for the lowest type in the context of constructive reverse mathematics. To this end, we reformulate bar recursion as a logical principle stating the existence of a bar recursor for every function which serves as the stopping condition of bar recursion. We then show that the decidable bar induction is equivalent to the existence of a bar recursor for every continuous function from ${\mathbb{N}}^{\mathbb{N}}$ to $\mathbb{N}$ with a continuous modulus. We also introduce fan recursion, the bar recursion for binary trees, and show that the decidable fan theorem is equivalent to the existence of a fan recursor for every continuous function from ${\{0,1\}}^{\mathbb{N}}$ to $\mathbb{N}$ with a continuous modulus. The equivalence for bar induction holds over the extensional version of intuitionistic arithmetic in all finite types augmented with the characteristic principles of Gödel's Dialectica interpretation. On the other hand, we show the equivalence for fan theorem without using such extra principles.     

On constructivity and the Rosser property: a closer look at some Gödelean proofs

The proofs of Kleene, Chaitin and Boolos for Gödel's First Incompleteness Theorem are studied from the perspectives of constructivity and the Rosser property. A proof of the incompleteness theorem has the Rosser property when the independence of the true but unprovable sentence can be shown by assuming only the (simple) consistency of the theory. It is known that Gödel's own proof for his incompleteness theorem does not have the Rosser property, and we show that neither do Kleene's or Boolos' proofs. However, we show that a variant of Chaitin's proof can have the Rosser property. The proofs of Gödel, Rosser and Kleene are constructive in the sense that they explicitly construct, by algorithmic ways, the independent sentence(s) from the theory. We show that the proofs of Chaitin and Boolos are not constructive, and they prove only the mere existence of the independent sentences.     

Stability of representations of effective partial algebras

An algebra is effective if its operations are computable under some numbering. When are two numberings of an effective partial algebra equivalent? For example, the computable real numbers form an effective field and two effective numberings of the field of computable reals are equivalent if the limit operator is assumed to be computable in the numberings (theorems of Moschovakis and Hertling). To answer the question for effective algebras in general, we give a general method based on an algebraic analysis of approximations by elements of a finitely generated subalgebra. Commonly, the computable elements of a topological partial algebra are derived from such a finitely generated algebra and form a countable effective partial algebra. We apply the general results about partial algebras to the recursive reals, ultrametric algebras constructed by inverse limits, and to metric algebras in general. © 2011 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim     

Burkholder-Gundy-Davis inequality in martingale Hardy spaces with variable exponent

In this article, by extending classical Dellacherie's theorem on stochastic sequences to variable exponent spaces, we prove that the famous Burkholder-Gundy-Davis inequality holds for martingales in variable exponent Hardy spaces. We also obtain the variable exponent analogues of several martingale inequalities in classical theory, including convexity lemma, Chevalier's inequality and the equivalence of two kinds of martingale spaces with predictable control. Moreover, under the regular condition on σ-algebra sequence we prove the equivalence between five kinds of variable exponent martingale Hardy spaces.     

Reductions between types of numberings

This paper considers reductions between types of numberings; these reductions preserve the Rogers Semilattice of the numberings reduced and also preserve the number of minimal and positive degrees in their semilattice. It is shown how to use these reductions to simplify some constructions of specific semilattices. Furthermore, it is shown that for the basic types of numberings, one can reduce the left-r.e. numberings to the r.e. numberings and the k-r.e. numberings to the $(k+1)$-r.e. numberings; all further reductions are obtained by concatenating these reductions.     

Computable Solutions of Equations over Endomorphisms of Negative Numberings

We prove that a broad class of systems of equations have endomorphisms of negative numberings as solutions. Moreover, we prove that if the endomorphisms of a numbering uniformly solve this class of systems of equations and have the separability property then the numbering is negative.     

A note on partial numberings

The different behaviour of total and partial numberings with respect to the reducibility preorder is investigated. Partial numberings appear quite naturally in computability studies for topological spaces. The degrees of partial numberings form a distributive lattice which in the case of an infinite numbered set is neither complete nor contains a least element. Friedberg numberings are no longer minimal in this situation. Indeed, there is an infinite descending chain of non‐equivalent Friedberg numberings below every given numbering, as well as an uncountable antichain. (© 2005 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Products of Menger spaces: A combinatorial approach

We construct Menger subsets of the real line whose product is not Menger in the plane. In contrast to earlier constructions, our approach is purely combinatorial. The set theoretic hypothesis used in our construction is far milder than earlier ones, and holds in almost all canonical models of set theory of the real line. On the other hand, we establish productive properties for versions of Menger's property parameterized by filters and semifilters. In particular, the Continuum Hypothesis implies that every productively Menger set of real numbers is productively Hurewicz, and each ultrafilter version of Menger's property is strictly between Menger's and Hurewicz's classic properties. We include a number of open problems emerging from this study.     

Ramsey's theorem with sums or unions

Using Hindman's theorem as a strong pigeonhole principle, we prove strengthened versions of Ramsey's theorem and of various generalizations of Ramsey's theorem due to Nash-Williams, Galvin and Prikry, and Silver.     

Dynamic Picone's identity and its applications

We prove some Picone-type identities and inequalities for a class of first-order nonlinear dynamic systems and derive various weighted inequalities of Wirtinger type and Hardy type on time scales. As applications we study oscillatory and related properties of these systems including Reid's roundabout theorem on disconjugacy, Sturm's separation and comparison theorems, as well as a variational method in the oscillation theory.     

The equational theory of a nontrivial discriminator variety is co-NP-hard

Discriminator varieties play a central role in the classification of decidable varieties; and they arise naturally in the study of algebraic logics. There are also important connections with the reduction of theorem proving to equational logic. In this paper we show, for any nontrivial discriminator variety, that the problem of determining if an equation holds in the variety is co-NP-hard.Received August 24, 2002; accepted in final form August 5, 2004.     

Strong reducibility of partial numberings

A strong reducibility relation between partial numberings is introduced which is such that the reduction function transfers exactly the numbers which are indices under the numbering to be reduced into corresponding indices of the other numbering. The degrees of partial numberings of a given set with respect to this relation form an upper semilattice.In addition, Ershovs completion construction for total numberings is extended to the partial case: every partially numbered set can be embedded in a set which results from the given set by adding one point and which is enumerated by a total and complete numbering. As is shown, the degrees of complete numberings of the extended set also form an upper semilattice. Moreover, both semilattices are isomorphic.This is not so in the case of the usual, weaker reducibility relation for partial numberings which allows the reduction function to transfer arbitrary numbers into indices.This research has partially been supported by INTAS under grant 00-499 Computability in Hierarchies and Topological Spaces.Mathematics Subject Classification (2000): 03D45     

Weak convergence of empirical and quantile processes in sup-norm metrics via kmt-constructions

There has been much interest recently in the specially constructed empirical processes of Komlós, Major and Tusnády [2]; as one would guess, much of the application has come from the Hungarian school.In this note we contribute to the unifying effect this profound work has had by showing how the major theorem of O'Reilly [4] follows in rather elementary fashion from this powerful construction. We also take this opportunity to restate O'Reilly's criterion in an elementary form that is far more intelligible.     

Coalitional power structure without the pareto principle

In this paper we have extended Arrow's analysis to a framework where for any given profile of individual preference orderings the decision procedure specifies a non-trivial probability distribution over possible social orderings. We have demonstrated that if the social decision procedure satisfies certain probabilistic versions of weak independence of irrelevant alternatives, then it is characterized by a ‘power’ structure for all possible coalitions of individuals without assuming either the Pareto Principle or its antecedents. A generalised version of Arrow's impossibility theorem follows as a special case of our result. We have weakened Arrow's independence condition, and have shown the existence of a hierarchy of dictators without imposing the Pareto criterion.     

The axiomatic power of Kolmogorov complexity

The famous Gödel incompleteness theorem states that for every consistent, recursive, and sufficiently rich formal theory T there exist true statements that are unprovable in T. Such statements would be natural candidates for being added as axioms, but how can we obtain them? One classical (and well studied) approach is to add to some theory T an axiom that claims the consistency of T  . In this paper we discuss another approach motivated by Chaitin's version of Gödel's theorem where axioms claiming the randomness (or incompressibility) of some strings are probabilistically added, and show that it is not really useful, in the sense that this does not help us prove new interesting theorems. This result answers a question recently asked by Lipton. The situation changes if we take into account the size of the proofs: randomly chosen axioms may help making proofs much shorter (unless NP=PSPACE$\mathrm{NP}=\mathrm{PSPACE}$).     

Low upper bounds in the LR degrees

We say that A≤_LRB if every B-random real is A-random—in other words, if B has at least as much derandomization power as A. The LR reducibility is a natural weak reducibility in the context of randomness, and generalizes lowness for randomness. We study the existence and properties of upper bounds in the context of the LR degrees. In particular, we show that given two (or even finitely many) low sets, there is a low c.e. set which lies LR above both. This is very different from the situation in the Turing degrees, where Sacks’ splitting theorem shows that two low sets can join to 0^′.     

Planarity and duality of finite and infinite graphs

We present a short proof of the following theorems simultaneously: Kuratowski's theorem, Fary's theorem, and the theorem of Tutte that every 3-connected planar graph has a convex representation. We stress the importance of Kuratowski's theorem by showing how it implies a result of Tutte on planar representations with prescribed vertices on the same facial cycle as well as the planarity criteria of Whitney, MacLane, Tutte, and Fournier (in the case of Whitney's theorem and MacLane's theorem this has already been done by Tutte). In connection with Tutte's planarity criterion in terms of non-separating cycles we give a short proof of the result of Tutte that the induced non-separating cycles in a 3-connected graph generate the cycle space. We consider each of the above-mentioned planarity criteria for infinite graphs. Specifically, we prove that Tutte's condition in terms of overlap graphs is equivalent to Kuratowski's condition, we characterize completely the infinite graphs satisfying MacLane's condition and we prove that the 3-connected locally finite ones have convex representations. We investigate when an infinite graph has a dual graph and we settle this problem completely in the locally finite case. We show by examples that Tutte's criterion involving non-separating cycles has no immediate extension to infinite graphs, but we present some analogues of that criterion for special classes of infinite graphs.     

解析余亚正规算子的α-Weyl定理

若T有单值延伸性且T为reguloid算子,则Weyl定理对f(T)成立,其中f∈H(σ(T)),而当T~*有单值延伸性且T是reguloid算子,α-Weyl定理对f(T)成立,其中,f∈H(σ(T)),作为定理应用,我们证明了Weyl定理对解析M-亚正规算子成立,α-Weyl定理对解析余亚正规算子成立。