We study a class of formulas generalizing the weak law of the excluded middle and provide a characterization of these formulas in terms of Kripke frames and Brouwer algebras. We use these formulas to separate logics corresponding to factors of the Medvedev lattice.

We prove that the first-order theory of the Medvedev degrees, the first-order theory of the Muchnik degrees, and the third-order theory of true arithmetic are pairwise recursively isomorphic (obtained independently by Lewis, Nies, and Sorbi [7]). We then restrict our attention to the degrees of closed sets and prove that the following theories are pairwise recursively isomorphic: the first-order theory of the closed Medvedev degrees, the first-order theory of the compact Medvedev degrees, the first-order theory of the closed Muchnik degrees, (...) the first-order theory of the compact Muchnik degrees, and the second-order theory of true arithmetic. Our coding methods also prove that neither the closed Medvedev degrees nor the compact Medvedev degrees are elementarily equivalent to either the closed Muchnik degrees or the compact Muchnik degrees. (shrink)

We survey the theory of Mucnik and Medvedev degrees of subsets of $^{\omega}{\omega}$with particular attention to the degrees of $\Pi_{1}^{0}$ subsets of $^{\omega}2$. Sections 1-6 present the major definitions and results in a uniform notation. Sections 7-6 present proofs, some more complete than others, of the major results of the subject together with much of the required background material.

We study the Medvedev degrees of mass problems with distinguished topological properties, such as denseness, closedness, or discreteness. We investigate the sublattices generated by these degrees; the prime ideal generated by the dense degrees and its complement, a prime filter; the filter generated by the nonzero closed degrees and the filter generated by the nonzero discrete degrees. We give a complete picture of the relationships of inclusion holding between these sublattices, these filters, and this ideal. We show that the sublattice (...) of the closed Medvedev degrees is not a Brouwer algebra. We investigate the dense degrees of mass problems that are closed under Turing equivalence, and we prove that the dense degrees form an automorphism base for the Medvedev lattice. The results hold for both the Medvedev lattice on the Baire space and the Medvedev lattice on the Cantor space. (shrink)

Simpson introduced the lattice of Π0 1 classes under Medvedev reducibility. Questions regarding completeness in are related to questions about measure and randomness. We present a solution to a question of Simpson about Medvedev degrees of Π0 1 classes of positive measure that was independently solved by Simpson and Slaman. We then proceed to discuss connections to constructive logic. In particular we show that the dual of does not allow an implication operator (i.e. that is not a Heyting algebra). We (...) also discuss properties of the class of PA-complete sets that are relevant in this context. (shrink)

We study the connection between factors of the Medvedev lattice and constructive logic. The algebraic properties of these factors determine logics lying in between intuitionistic propositional logic and the logic of the weak law of the excluded middle (also known as De Morgan, or Jankov, logic). We discuss the relation between the weak law of the excluded middle and the algebraic notion of join-reducibility. Finally we discuss autoreducible degrees.

We characterize the join-irreducible Medvedev degrees as the degrees of complements of Turing ideals, thereby solving a problem posed by Sorbi. We use this characterization to prove that there are Medvedev degrees above the second-least degree that do not bound any join-irreducible degrees above this second-least degree. This solves a problem posed by Sorbi and Terwijn. Finally, we prove that the filter generated by the degrees of closed sets is not prime. This solves a problem posed by Bianchini and Sorbi.