A computably enumerable vector space with the strong antibasis property

Downey and Remmel have completely characterized the degrees of c.e. bases for c.e. vector spaces (and c.e. fields) in terms of weak truth table degrees. In this paper we obtain a structural result concerning the interaction between the c.e. Turing degrees and the c.e. weak truth table degrees, which by Downey and Remmel's classification, establishes the existence of c.e. vector spaces (and fields) with the strong antibasis property (a question which they raised). Namely, we construct c.e. sets such that the c.e. W-degrees below that of A are disjoint from the nonzero c.e. T-degrees below that of A and comparable to that of B. Received: 2 December 1998     

On the filter of computably enumerable supersets of an r-maximal set

We study the filter ℒ^*(A) of computably enumerable supersets (modulo finite sets) of an r-maximal set A and show that, for some such set A, the property of being cofinite in ℒ^*(A) is still Σ⁰ ₃-complete. This implies that for this A, there is no uniformly computably enumerable “tower” of sets exhausting exactly the coinfinite sets in ℒ^*(A). Received: 6 November 1999 / Revised version: 10 March 2000 /?Published online: 18 May 2001     

Density results in the Δ20 e-degrees

We show that the Δ⁰ ₂ enumeration degrees are dense. We also show that for every nonzero n-c. e. e-degree a, with n≥ 3, one can always find a nonzero 3-c. e. e-degree b such that b < a on the other hand there is a nonzero ωc. e. e-degree which bounds no nonzero n-c. e. e-degree. Received: 13 June 2000 / Published online: 3 October 2001     

The computable Lipschitz degrees of computably enumerable sets are not dense

The computable Lipschitz reducibility was introduced by Downey, Hirschfeldt and LaForte under the name of strong weak truth-table reducibility (Downey et al. (2004) [6]). This reducibility measures both the relative randomness and the relative computational power of real numbers. This paper proves that the computable Lipschitz degrees of computably enumerable sets are not dense. An immediate corollary is that the Solovay degrees of strongly c.e. reals are not dense. There are similarities to Barmpalias and Lewis’ proof that the identity bounded Turing degrees of c.e. sets are not dense (George Barmpalias, Andrew E.M. Lewis (2006) [2]), however the problem for the computable Lipschitz degrees is more complex.     

Kolmogorov complexity and computably enumerable sets

We study the computably enumerable sets in terms of the:     

Jumps of computably enumerable equivalence relations

We study computably enumerable equivalence relations (or, ceers), under computable reducibility ≤, and the halting jump operation on ceers. We show that every jump is uniform join-irreducible, and thus join-irreducible. Therefore, the uniform join of two incomparable ceers is not equivalent to any jump. On the other hand there exist ceers that are not equivalent to jumps, but are uniform join-irreducible: in fact above any non-universal ceer there is a ceer which is not equivalent to a jump, and is uniform join-irreducible. We also study transfinite iterations of the jump operation. If a is an ordinal notation, and E is a ceer, then let $E^{(a)}$ denote the ceer obtained by transfinitely iterating the jump on E along the path of ordinal notations up to a. In contrast with what happens for the Turing jump and Turing reducibility, where if a set X is an upper bound for the A-arithmetical sets then $X^{(2)}$ computes $A^{(\omega )}$, we show that there is a ceer R such that $R\ge {\mathrm{Id}}^{(n)}$, for every finite ordinal n, but, for all k, $R^{(k)}?{\mathrm{Id}}^{(\omega )}$ (here Id is the identity equivalence relation). We show that if $a,b$ are notations of the same ordinal less than ${\omega }^2$, then $E^{(a)}\equiv E^{(b)}$, but there are notations $a,b$ of ${\omega }^2$ such that ${\mathrm{Id}}^{(a)}$ and ${\mathrm{Id}}^{(b)}$ are incomparable. Moreover, there is no non-universal ceer which is an upper bound for all the ceers of the form ${\mathrm{Id}}^{(a)}$ where a is a notation for ${\omega }^2$.     

On one-sided versus two-sided classification

One-sided classifiers are computable devices which read the characteristic function of a set and output a sequence of guesses which converges to 1 iff the set on the input belongs to the gven class. Such a classifier istwo-sided if the sequence of its output in addition converges to 0 on setsnot belonging to the class. The present work obtains the below mentionedresults for one-sided classes (= Σ⁰ ₂ classes) with respect to four areas: Turing complexity, 1-reductions, index sets and measure. There are one-sided classes which are not two-sided. This can have two reasons: (1) the class has only high Turing complexity. Then there are some oracles which allow to construct noncomputale two-sided classifiers. (2) The class is difficult because of some topological constraints and then there are also no nonrecursive two-sided classifiers. For case (1), several results are obtainedto localize the Turing complexity of certain types of one-sided classes. The concepts of 1-reduction, 1-completeness and simple sets is transferred to one-sided classes: There are 1-complete classes and simple classes, but no class is at the same time 1-complete nd simple. The one-sided classes have a natural numbering. Most of the common index sets relative to this numbering have the high complexity Π¹ ₁: the index set of the class {0,1}^∞, the index set of the equality problem and the index set of all two-sided classes. On the other side the index set of the empty class has complexity Π⁰ ₂; Π⁰ ₂ and Σ⁰ ₂ are the least complexities any nontrivial index set can have. Lusin showed that any one-sided class is measurable. Concerning the effectiveness of this measure, it is shown that a one-sided class has recursive measure 0 if it has measure 0, but that thre are one-sided classes having measure 1 without having measure 1 effectively. The measure of a two-sided class can be computed in the limit. Received: 2 December 1999 / Revised version: 28 February 2000 / Published online: 15 June 2001     

Index sets and parametric reductions

We investigate the index sets associated with the degree structures of computable sets under the parameterized reducibilities introduced by the authors. We solve a question of Peter Cholakand the first author by proving the fundamental index sets associated with a computable set A, {e : W _e ≤ _q ^u A} for q∈ {m, T} are Σ₄ ⁰ complete. We also show hat FPT(≤ _q ⁿ ), that is {e : W _e computable and ≡ _q ⁿ ?}, is Σ₄ ⁰ complete. We also look at computable presentability of these classes. Received: 13 July 1996 / Revised version: 14 April 2000 / Published online: 18 May 2001     

The similarity degree of an operator algebra, II

For every integer , there is a unital closed subalgebra with similarity degree equal precisely to d, in the sense of our previous paper. This means that for any unital homomorphism we have with independent of u, and the exponent d in this estimate cannot be improved. The proof that the degree is larger than crucially uses an upper bound for the norms of certain Gaussian random matrices due to Haagerup and Thorbj?rnsen. We also include several complements to our previous publications on the same subject. Received: 25 April, 1999; Accepted: 23 June, 1999     

The Karp complexity of unstable classes

A class K of structures is controlled if, for all cardinals λ, the relation of L _∞,λ-equivalence partitions K into a set of equivalence classes (as opposed to a proper class). We prove that the class of doubly transitive linear orders is controlled, while any pseudo-elementary class with the ω-independence property is not controlled. Received: 23 September 1998 / Revised version: 6 July 1999 / Published online: 21 December 2000     

Recursive events in random sequences

Let ω be a Kolmogorov–Chaitin random sequence with ω_{1: n} denoting the first n digits of ω. Let P be a recursive predicate defined on all finite binary strings such that the Lebesgue measure of the set {ω|∃nP(ω_{1: n} )} is a computable real α. Roughly, P holds with computable probability for a random infinite sequence. Then there is an algorithm which on input indices for any such P and α finds an n such that P holds within the first n digits of ω or not in ω at all. We apply the result to the halting probability Ω and show that various generalizations of the result fail. Received: 1 December 1998 / Published online: 3 October 2001     

The theory of {\vec Z}C(2)^2-lattices is decidable

For arbitrary finite group and countable Dedekind domain such that the residue field is finite for every maximal -ideal , we show that the localizations at every maximal ideal of two -lattices are isomorphic if and only if the two lattices satisfy the same first order sentences. Then we investigate generalizations of the above results to arbitrary -torsion-free -modules and we apply the previous results to show the decidability of the theory of -lattices. Eventually, we show that -lattices have undecidable theory. Received November 28, 1995     

Computability in structures representing a Scott set

Continuing work begun in [10], we utilize a notion of forcing for which the generic objects are structures and which allows us to determine whether these “generic” structures compute certain sets and enumerations. The forcing conditions are bounded complexity types which are consistent with a given theory and are elements of a given Scott set. These generic structures will “represent” this given Scott set, in the sense that the structure has a certain weak saturation property with respect to bounded complexity types in the Scott set. For example, if ? is a nonstandard model of PA, then ? represents the Scott set ? = n∈ω | ?⊧“the nth prime divides a” | a∈?. The notion of forcing yields two main results. The first characterizes the sets of natural numbers computable in all models of a given theory representing a given Scott set. We show that the characteristic function of such a set must be enumeration reducible to a complete existential type which is consistent with the given theory and is an element of the given Scott set. The second provides a sufficient condition for the existence of a structure ? such that ? represents a countable jump ideal and ? does not compute an enumeration of a given family of sets ?. This second result is of particular interest when the family of sets which cannot be enumerated is ? = Rep[Th(?)]. Under this additional assumption, the second result generalizes a result on TA [6] and on certain other completions of PA [10]. For example, we show that there also exist models of completions of ZF from which one cannot enumerate the family of sets represented by the theory. Received: 8 October 1997 / Published online: 25 January 2001     

An elementary proof of strong normalization for intersection types

We provide a new and elementary proof of strong normalization for the lambda calculus of intersection types. It uses no strong method, like for instance Tait-Girard reducibility predicates, but just simple induction on type complexity and derivation length and thus it is obviously formalizable within first order arithmetic. To obtain this result, we introduce a new system for intersection types whose rules are directly inspired by the reduction relation. Finally, we show that not only the set of strongly normalizing terms of pure lambda calculus can be characterized in this system, but also that a straightforward modification of its rules allows to characterize the set of weakly normalizing terms. Received: 15 June 1998 / Revised version: 15 November 1999 / Published online: 15 June 2001     

Natural deduction with general elimination rules

The structure of derivations in natural deduction is analyzed through isomorphism with a suitable sequent calculus, with twelve hidden convertibilities revealed in usual natural deduction. A general formulation of conjunction and implication elimination rules is given, analogous to disjunction elimination. Normalization through permutative conversions now applies in all cases. Derivations in normal form have all major premisses of elimination rules as assumptions. Conversion in any order terminates. Through the condition that in a cut-free derivation of the sequent Γ⇒C, no inactive weakening or contraction formulas remain in Γ, a correspondence with the formal derivability relation of natural deduction is obtained: All formulas of Γ become open assumptions in natural deduction, through an inductively defined translation. Weakenings are interpreted as vacuous discharges, and contractions as multiple discharges. In the other direction, non-normal derivations translate into derivations with cuts having the cut formula principal either in both premisses or in the right premiss only. Received: 1 December 1998 / Revised version: 30 June 2000 / Published online: 18 July 2001     

Near coherence and filter games

We investigate a two-player game involving pairs of filters on ω. Our results generalize a result of Shelah ([7] Chapter VI) dealing with applications of game theory in the study of ultrafilters. Received: 28 September 1998 / Published online: 25 January 2001     

Groupwise dense families

We show that the Filter Dichotomy Principle implies that there are exactly four classes of ideals in the set of increasing functions from the natural numbers. We thus answer two open questions on consequences of ? < ?. We show that ? < ? implies that ? = ?, and that Filter Dichotomy together with ? < ? implies ? < ?. The technical means is the investigation of groupwise dense sets, ideals, filters and ultrafilters. With related techniques we prove the new inequality ?≤ cf(?). Received: 9 October 1998 / Revised version: 18 August 1999 / Published online: 21 December 2000     

The shrinking principle and the axiom of choice

The axiom of choice is equivalent to the shrinking principle: every indexed cover of a set has a refinement with the same index set which is a partition. A simple and direct proof of this equivalence is given within an elementary fragment of constructive Zermelo–Fraenkel set theory. Variants of the shrinking principle are discussed, and it is related to a similar but different principle formulated by Vaught.     

An explicit bound for uniform perfectness of the Julia sets of rational maps

A compact set C in the Riemann sphere is called uniformly perfect if there is a uniform upper bound on the moduli of annuli which separate C. Julia sets of rational maps of degree at least two are uniformly perfect. Proofs have been given independently by Ma né and da Rocha and by Hinkkanen, but no explicit bounds are given. In this note, we shall provide such an explicit bound and, as a result, give another proof of uniform perfectness of Julia sets of rational maps of degree at least two. As an application, we provide a lower estimate of the Hausdorff dimension of the Julia sets. We also give a concrete bound for the family of quadratic polynomials in terms of the parameter c. Received: 7 June 1999; in final form: 9 November 1999 / Published online: 17 May 2001     

Disasters in topology without the axiom of choice

We show that some well known theorems in topology may not be true without the axiom of choice. Received: 29 August 1995 / Revised version: 23 June 2000 / Published online: 3 October 2001