2025-12-04 | | Total: 5
A Turing degree is d.c.e. if it contains a set that is the difference of two c.e. sets. A d.c.e. degree $\mathbf{d}$ is isolated if there exists a c.e. degree $\mathbf{a}<\mathbf{d}$ such that every c.e. degree below $\mathbf{d}$ is also below $\mathbf{a}$; $\mathbf{d}$ is upper isolated if there exists a c.e. degree $\mathbf{a}>\mathbf{d}$ such that every c.e. degree above $\mathbf{d}$ is also above $\mathbf{a}$; $\mathbf{d}$ is bi-isolated if it is both isolated and upper isolated. In this paper, we prove the existence of bi-isolated d.c.e. degrees in models of $\mathsf{I}Σ_1$.
We investigate the semigroup of invariant types through the lens of Ellis theory; primarily focusing on definably amenable NIP groups. In this context, we observe that the collection of strong right $f$-generic types forms the unique minimal left ideal and thus, the Ellis subgroups are isomorphic to $G/G^{00}$ via the canonical quotient map. As consequence of the Newelski-Pillay conjecture, the Ellis subgroups of the semigroup of invariant types are abstractly isomorphic to the Ellis subgroups of the semigroup of finitely satisfiable types in the definable amenable NIP setting. We are interested in the existence of natural isomorphisms from invariant Ellis subgroups to finitely satisfiable Ellis subgroups and we determine when these isomorphisms can be witnessed by variants of the canonical NIP retraction map. Several limiting examples are provided. Outside of the NIP context, we provide an abelian group (and thus definably amenable) with an $\emptyset$-definable (dfg) type in which the invariant Ellis subgroups and finitely satisfiable Ellis subgroups not isomorphic.
We prove that the perfect set dichotomy theorem holds in the Solovay model $V ((ω^ω)^{V[G]})$. Namely, for every equivalence relation $E$ on $\mathbb{R}$, either $\mathbb{R}/E$ is well-orderable or there exists a perfect set consisting of $E$-inequivalent reals. Furthermore we consider a generalization of the Solovay model for an uncountable regular cardinal $μ$ and show the perfect set dichotomy theorem for $μ^μ$ also holds in that model. We establish the three element basis theorem for uncountable linear orders in the Solovay model for a weakly compact cardinal, in a general form covering the uncountable case.
In a 1985 commentary to his collected works, Kolmogorov informed the reader that his 1932 paper 'On the interpretation of intuitionistic logic' "was written in hope that with time, the logic of solution of problems [i.e., intuitionistic logic] will become a permanent part of a [standard] course of logic. A unified logical apparatus was intended to be created, which would deal with objects of two types - propositions and problems." We construct such a formal system as well as its predicate version, QHC, which is a conservative extension of both the intuitionistic predicate calculus QH and the classical predicate calculus QC. The axioms of QHC are obtained as a result of a simultaneous formalization of two well-known alternative explanations of intiuitionistic logic: 1) Kolmogorov's problem interpretation (with familiar refinements by Heyting and Kreisel) and 2) the proof interpretation by Orlov and Heyting, as clarified and extended by Gödel.
We address the problem of identifying a proof-theoretic framework that enables a compositional analysis of finite-trace properties in concurrent systems, with a particular focus on those specified via prefix-closure. To this end, we investigate the interaction of a prefix-closure operator and its residual (with respect to set-theoretic inclusion) with language intersection, union, and concatenation, and introduce the variety of closure $\ell$-monoids as a minimal algebraic abstraction of finite-trace properties to be conveniently described within an analytic proof system. Closure $\ell$-monoids are division-free reducts of distributive residuated lattices equipped with a forward diamond/backward box residuated pair of unary modal operators, where the diamond is a topological closure operator satisfying $\Diamond(x \cdot y) \leq \Diamond x \cdot \Diamond y$. As a logical counterpart to these structures, we present $\mathsf{LMC}$, a Gentzen-style system based on the division-free fragment of the Distributive Full Lambek Calculus. In $\mathsf{LMC}$, structural terms are built from formulas using Belnap-style structural operators for monoid multiplication, meet, and diamond. The rules for the modalities and the structural diamond are taken from Moortgat's system $\mathsf{NL}(\Diamond)$. We show that the calculus is sound and complete with respect to the variety of closure $\ell$-monoids and that it admits cut elimination.