Elementary differences between the degrees of unsolvability and degrees of compressibility

Given two infinite binary sequences A,B we say that B can compress at least as well as A if the prefix-free Kolmogorov complexity relative to B of any binary string is at most as much as the prefix-free Kolmogorov complexity relative to A, modulo a constant. This relation, introduced in Nies (2005) [14] and denoted by A≤_LKB, is a measure of relative compressing power of oracles, in the same way that Turing reducibility is a measure of relative information. The equivalence classes induced by ≤_LK are called LK degrees (or degrees of compressibility) and there is a least degree containing the oracles which can only compress as much as a computable oracle, also called the ‘low for K’ sets. A well-known result from Nies (2005) [14] states that these coincide with the K-trivial sets, which are the ones whose initial segments have minimal prefix-free Kolmogorov complexity.We show that with respect to ≤_LK, given any non-trivial sets X,Y there is a computably enumerable set A which is not K-trivial and it is below X,Y. This shows that the local structures of and Turing degrees are not elementarily equivalent to the corresponding local structures in the LK degrees. It also shows that there is no pair of sets computable from the halting problem which forms a minimal pair in the LK degrees; this is sharp in terms of the jump, as it is known that there are sets computable from which form a minimal pair in the LK degrees. We also show that the structure of LK degrees below the LK degree of the halting problem is not elementarily equivalent to the or structures of LK degrees. The proofs introduce a new technique of permitting below a set that is not K-trivial, which is likely to have wider applications.     

A minimal classical sequent calculus free of structural rules

Gentzen’s classical sequent calculus has explicit structural rules for contraction and weakening. They can be absorbed (in a right-sided formulation) by replacing the axiom P,¬P by Γ,P,¬P for any context Γ, and replacing the original disjunction rule with Γ,A,B implies Γ,A∨B.This paper presents a classical sequent calculus which is also free of contraction and weakening, but more symmetrically: both contraction and weakening are absorbed into conjunction, leaving the axiom rule intact. It uses a blended conjunction rule, combining the standard context-sharing and context-splitting rules: Γ,Δ,A and Γ,Σ,B implies Γ,Δ,Σ,A∧B. We refer to this system as minimal sequent calculus.We prove a minimality theorem for the propositional fragment : any propositional sequent calculus S (within a standard class of right-sided calculi) is complete if and only ifS contains (that is, each rule of is derivable in S). Thus one can view as a minimal complete core of Gentzen’s .     

Finite depth and Jacobson-Bourbaki correspondence

We introduce a notion of depth three tower C⊆B⊆A with depth two ring extension A|B being the case B=C. If and B|C is a Frobenius extension with A|B|C depth three, then A|C is depth two. If A, B and C correspond to a tower G>H>K via group algebras over a base ring F, the depth three condition is the condition that K has normal closure K^G contained in H. For a depth three tower of rings, a pre-Galois theory for the ring and coring (A⊗_BA)^C involving Morita context bimodules and left coideal subrings is applied to specialize a Jacobson-Bourbaki correspondence theorem for augmented rings to depth two extensions with depth three intermediate division rings.     

Open selections on smooth fans

Given a dendroid X, an open selection is an open map such that s(A)∈A for every A∈C(X). We show that a smooth fan X admits an open selection if and only if X is locally connected.     

Projective mad families

Using almost disjoint coding we prove the consistency of the existence of a definable ω-mad family of infinite subsets of ω (resp. functions from ω to ω) together with b=2^ω=ω₂.     

Fonction asymptotique de Samuel des sections hyperplanes et multiplicité

Let (A,m_A,k) be a local noetherian ring and I an m_A-primary ideal. The asymptotic Samuel function (with respect to I) : A?R∪{+∞} is defined by , ∀x∈A. Similarly, one defines, for another ideal J, as the minimum of as x varies in J. Of special interest is the rational number . We study the behavior of the asymptotic Samuel function (with respect to I) when passing to hyperplane sections of A as one does for the theory of mixed multiplicities.     

Coactions on Hochschild homology of Hopf-Galois extensions and their coinvariants

Let B⊆A be an H-Galois extension, where H is a Hopf algebra over a field K. If M is a Hopf bimodule then , the Hochschild homology of A with coefficients in M, is a right comodule over the coalgebra C_H=H/[H,H]. Given an injective left C_H-comodule V, our aim is to understand the relationship between and . The roots of this problem can be found in Lorenz (1994) [15], where and are shown to be isomorphic for any centrally G-Galois extension. To approach the above mentioned problem, in the case when A is a faithfully flat B-module and H satisfies some technical conditions, we construct a spectral sequence

     

Properties of two-dimensional sets with small sumset

We give tight lower bounds on the cardinality of the sumset of two finite, nonempty subsets A,B⊆R² in terms of the minimum number h₁(A,B) of parallel lines covering each of A and B. We show that, if h₁(A,B)?s and |A|?|B|?2s²−3s+2, then

     

The double negation of the intermediate value theorem

In the context of intuitionistic analysis, we consider the set F consisting of all continuous functions ? from [0,1] to R such that ?(0)=0 and ?(1)=1, and the set I₀ consisting of ?’s in F where there exists x∈[0,1] such that . It is well-known that there are weak counterexamples to the intermediate value theorem, and with Brouwer’s continuity principle we have I₀≠F. However, there exists no satisfying answer to . We try to answer to this question by reducing it to a schema (which we call ) about intuitionistic decidability that asserts “there exists an intuitionistically enumerable set that is not intuitionistically decidable”. We also introduce the notion of strong Specker double sequence, and prove that the existence of such a double sequence is equivalent to the existence of a function ?∈F_mon where .     

Rigid continua and transfinite inductive dimension

We introduce a general method of resolving first countable, compact spaces that allows accurate estimate of inductive dimensions. We apply this method to construct, inter alia, for each ordinal number α>1 of cardinality ?c, a rigid, first countable, non-metrizable continuum Sα with . Sα is the increment in some compactification of [0,1) and admits a fully closed, ring-like map onto a metric continuum. Moreover, every subcontinuum of Sα is separable. Additionally, Sα can be constructed so as to be: (1) a hereditarily indecomposable Anderson-Choquet continuum with covering dimension a given natural number n, provided α>n, (2) a hereditarily decomposable and chainable weak Cook continuum, (3) a hereditarily decomposable and chainable Cook continuum, provided α is countable, (4) a hereditarily indecomposable Cook continuum with covering dimension one, or (5) a Cook continuum with covering dimension two, provided α>2.We also produce a chainable and hereditarily decomposable space Sω(c⁺) with , , trind₀Sω(c⁺) and trInd₀Sω(c⁺) all equal to ω(c⁺), the first ordinal of cardinality c⁺.     

A localization inequality for set functions

We prove the following theorem, which is an analog for discrete set functions of a geometric result of Lovász and Simonovits. Given two real-valued set functions f₁,f₂ defined on the subsets of a finite set S, satisfying for i∈{1,2}, there exists a positive multiplicative set function μ over S and two subsets A,B⊆S such that for i∈{1,2}μ(A)f_i(A)+μ(B)f_i(B)+μ(A∪B)f_i(A∪B)+μ(A∩B)f_i(A∩B)?0. The Ahlswede-Daykin four function theorem can be deduced easily from this.