We prove a strengthened version of Shavrukov’s result on the non-isomorphism of diagonalizable algebras of two $\Sigma _1$ -sound theories, based on the improvements previously found by Adamsson. We then obtain several corollaries to the strengthened result by applying it to various pairs of theories and obtain new non-isomorphism examples. In particular, we show that there are no surjective homomorphisms from the algebra $(\mathfrak {L}_T, \Box _T\Box _T)$ onto the algebra $(\mathfrak {L}_T, \Box _T)$. The case of bimodal diagonalizable algebras (...) is also considered. We give several examples of pairs of theories with isomorphic diagonalizable algebras but non-isomorphic bimodal diagonalizable algebras. (shrink)

We prove a number of structural theorems about the honest polynomial m-degrees contingent on the assumption P = NP . In particular, we show that if P = NP , then the topped finite initial segments of Hm are exactly the topped finite distributive lattices, the topped initial segments of Hm are exactly the direct limits of ascending sequences of finite distributive lattices, and all recursively presentable distributive lattices are initial segments of Hm ∩ RE. Additionally, assuming ¦∑¦ = 1, (...) we show that the theory of the hpm-degrees is undecidable. We also show that index sets cannot be minimal. Lastly, we examine an alternative definition of honest m-reduction under which recursive minimal sets can be constructed. (shrink)

By a result of L.D. Beklemishev, the hierarchy of nested applications of the $$\Sigma _1$$ -collection rule over any $$\Pi _2$$ -axiomatizable base theory extending Elementary Arithmetic collapses to its first level. We prove that this result cannot in general be extended to base theories of arbitrary quantifier complexity. In fact, given any recursively enumerable set of true $$\Pi _2$$ -sentences, S, we construct a sound $$(\Sigma _2 \! \vee \! \Pi _2)$$ -axiomatized theory T extending S such that the (...) hierarchy of nested applications of the $$\Sigma _1$$ -collection rule over T is proper. Our construction uses some results on subrecursive degree theory obtained by L. Kristiansen. (shrink)