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)

While every endpointed interval I in a linear order J is, considered as a linear order in its own right, trivially Muchnik‐reducible to J itself, this fails for Medvedev‐reductions. We construct an extreme example of this: a linear order in which no endpointed interval is Medvedev‐reducible to any other, even allowing parameters, except when the two intervals have finite difference. We also construct a scattered linear order which has many endpointed intervals Medvedev‐incomparable to itself; the only other (...) known construction of such a linear order yields an ordinal of extremely high complexity, whereas this construction produces a low‐level‐arithmetic example. Additionally, the constructions here are “coarse” in the sense that they lift to other uniform reducibility notions in place of Medvedev reducibility itself. (shrink)

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)

The partial ordering of Medvedev reducibility restricted to the family of Π0 1 classes is shown to be dense. For two disjoint computably enumerable sets, the class of separating sets is an important example of a Π0 1 class, which we call a ``c.e. separating class''. We show that there are no non-trivial meets for c.e. separating classes, but that the density theorem holds in the sublattice generated by the c.e. separating classes.

Let w and M be the countable distributive lattices of Muchnik and Medvedev degrees of non-empty Π1 0 subsets of 2ω, under Muchnik and Medvedev reducibility, respectively. We show that all countable distributive lattices are lattice-embeddable below any non-zero element of w . We show that many countable distributive lattices are lattice-embeddable below any non-zero element of M.

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.

A $\Pi^0_1$ class can be defined as the set of infinite paths through a computable tree. For classes $P$ and $Q$, say that $P$ is Medvedev reducible to $Q$, $P \leq_M Q$, if there is a computably continuous functional mapping $Q$ into $P$. Let $\mathcal{L}_M$ be the lattice of degrees formed by $\Pi^0_1$ subclasses of $2^\omega$ under the Medvedev reducibility. In "Non-branching degrees in the Medvedev lattice of $\Pi \sp{0}\sb{1} classes," I provided a characterization of nonbranching/branching (...) and a classification of the nonbranching degrees. In this paper, I present a similar classification of the branching degrees. In particular, $P$ is separable if there is a clopen set $C$ such that $P \cap C \neq \emptyset \neq P \cap C^c$ and $P \cap C \perp_M P \cap C^c$. By the results in the first paper, separability is an invariant of a Medvedev degree and a degree is branching if and only if it contains a separable member. Further define $P$ to be hyperseparable if, for all such $C$, $P \cap C \perp_M P \cap C^c$ and totally separable if, for all $X,Y \in P$, $X \perp_T Y$. I will show that totally separable implies hyperseparable implies separable and that the reverse implications do not hold, that is, that these are three distinct types of branching degrees. Along the way I will show some related results and present a combinatorial framework for constructing $\Pi^0_1$ classes with priority arguments. (shrink)

A $\Pi _{1}^{0}$ class is the set of paths through a computable tree. Given classes P and Q, P is Medvedev reducible to Q, P ≤M Q, if there is a computably continuous functional mapping Q into P. We look at the lattice formed by $\Pi _{1}^{0}$ subclasses of 2ω under this reduction. It is known that the degree of a splitting class of c.e. sets is non-branching. We further characterize non-branching degrees, providing two additional properties which guarantee non-branching: (...) inseparable and hyperinseparable. Our main result is to show that non-branching iff inseparable if hyperinseparable if homogeneous and that all unstated implications do not hold. We also show that inseparable and not hyperinseparable degrees are downward dense. (shrink)

The tower number ${\mathfrak t}$ and the ultrafilter number $\mathfrak {u}$ are cardinal characteristics from set theory. They are based on combinatorial properties of classes of subsets of $\omega $ and the almost inclusion relation $\subseteq ^*$ between such subsets. We consider analogs of these cardinal characteristics in computability theory.We say that a sequence $(G_n)_{n \in {\mathbb N}}$ of computable sets is a tower if $G_0 = {\mathbb N}$, $G_{n+1} \subseteq ^* G_n$, and $G_n\smallsetminus G_{n+1}$ is infinite for each n. (...) A tower is maximal if there is no infinite computable set contained in all $G_n$. A tower ${\left \langle {G_n}\right \rangle }_{n\in \omega }$ is an ultrafilter base if for each computable R, there is n such that $G_n \subseteq ^* R$ or $G_n \subseteq ^* \overline R$ ; this property implies maximality of the tower. A sequence $(G_n)_{n \in {\mathbb N}}$ of sets can be encoded as the “columns” of a set $G\subseteq \mathbb N$. Our analogs of ${\mathfrak t}$ and ${\mathfrak u}$ are the mass problems of sets encoding maximal towers, and of sets encoding towers that are ultrafilter bases, respectively. The relative position of a cardinal characteristic broadly corresponds to the relative computational complexity of the mass problem. We use Medvedev reducibility to formalize relative computational complexity, and thus to compare such mass problems to known ones.We show that the mass problem of ultrafilter bases is equivalent to the mass problem of computing a function that dominates all computable functions, and hence, by Martin’s characterization, it captures highness. On the other hand, the mass problem for maximal towers is below the mass problem of computing a non-low set. We also show that some, but not all, noncomputable low sets compute maximal towers: Every noncomputable (low) c.e. set computes a maximal tower but no 1-generic $\Delta ^0_2$ -set does so.We finally consider the mass problems of maximal almost disjoint, and of maximal independent families. We show that they are Medvedev equivalent to maximal towers, and to ultrafilter bases, respectively. (shrink)

Important examples of $\Pi^0_1$ classes of functions $f \in {}^\omega\omega$ are the classes of sets (elements of ω 2) which separate a given pair of disjoint r.e. sets: ${\mathsf S}_2(A_0, A_1) := \{f \in{}^\omega2 : (\forall i < 2)(\forall x \in A_i)f(x) \neq i\}$ . A wider class consists of the classes of functions f ∈ ω k which in a generalized sense separate a k-tuple of r.e. sets (not necessarily pairwise disjoint) for each k ∈ ω: ${\mathsf S}_k(A_0,\ldots,A_k-1) := (...) \{f \in {}^\omega k : (\forall i < k) (\forall x \in A_i) f(x) \neq i\}$ . We study the structure of the Medvedev degrees of such classes and show that the set of degrees realized depends strongly on both k and the extent to which the r.e. sets intersect. Let ${\mathcal S}^m_k$ denote the Medvedev degrees of those ${\mathsf S}_k(A_0,\ldots,A_{k-1})$ such that no m + 1 sets among A 0,...,A k-1 have a nonempty intersection. It is shown that each ${\mathcal S}^m_k$ is an upper semi-lattice but not a lattice. The degree of the set of k-ary diagonally nonrecursive functions $\mathsf{DNR}_k$ is the greatest element of ${\mathcal S}^1_k$ . If 2 ≤ l < k, then 0 M is the only degree in ${\mathcal S}^1_l$ which is below a member of ${\mathcal S}^1_k$ . Each ${\mathcal S}^m_k$ is densely ordered and has the splitting property and the same holds for the lattice ${\mathcal L}^m_k$ it generates. The elements of ${\mathcal S}^m_k$ are exactly the joins of elements of ${\mathcal S}^1_i$ for $\lceil{k \over m}\rceil \leq i \leq k$. (shrink)

A mass problem is a set of functions$\omega \to \omega $. For mass problems${\mathcal {C}}, {\mathcal {D}}$, one says that${\mathcal {C}}$is Muchnik reducible to${\mathcal {D}}$if each function in${\mathcal {C}}$is computed by a function in${\mathcal {D}}$. In this paper we study some highness properties of Turing oracles, which we view as mass problems. We compare them with respect to Muchnik reducibility and its uniform strengthening, Medvedev reducibility.For$p \in [0,1]$let${\mathcal {D}}(p)$be the mass problem of infinite bit sequencesy(i.e.,$\{0,1\}$-valued functions) such (...) that for each computable bit sequencex, the bit sequence$ x {\,\leftrightarrow\,} y$has asymptotic lower density at mostp(where$x {\,\leftrightarrow\,} y$has a$1$in positionniff$x(n) = y(n)$). We show that all members of this family of mass problems parameterized by a realpwith$0 p$for each computable setx. We prove that the Medvedev (and hence Muchnik) complexity of the mass problems${\mathcal {B}}(p)$is the same for all$p \in (0, 1/2)$, by showing that they are Medvedev equivalent to the mass problem of functions bounded by${2^{2}}^{n}$that are almost everywhere different from each computable function.Next, together with Joseph Miller, we obtain a proper hierarchy of the mass problems of type$\text {IOE}$: we show that for any order functiongthere exists a faster growing order function$h $such that$\text {IOE}(h)$is strictly above$\text {IOE}(g)$in the sense of Muchnik reducibility.We study cardinal characteristics in the sense of set theory that are analogous to the highness properties above. For instance,${\mathfrak {d}} (p)$is the least size of a setGof bit sequences such that for each bit sequencexthere is a bit sequenceyinGso that$\underline \rho (x {\,\leftrightarrow\,} y)>p$. We prove within ZFC all the coincidences of cardinal characteristics that are the analogs of the results above. (shrink)

There is a Turing computable embedding $\Phi $ of directed graphs $\mathcal {A}$ in undirected graphs. Moreover, there is a fixed tuple of formulas that give a uniform effective interpretation; i.e., for all directed graphs $\mathcal {A}$, these formulas interpret $\mathcal {A}$ in $\Phi $. It follows that $\mathcal {A}$ is Medvedev reducible to $\Phi $ uniformly; i.e., $\mathcal {A}\leq _s\Phi $ with a fixed Turing operator that serves for all $\mathcal {A}$. We observe that there is a graph (...) G that is not Medvedev reducible to any linear ordering. Hence, G is not effectively interpreted in any linear ordering. Similarly, there is a graph that is not interpreted in any linear ordering using computable $\Sigma _2$ formulas. Any graph can be interpreted in a linear ordering using computable $\Sigma _3$ formulas. Friedman and Stanley [4] gave a Turing computable embedding L of directed graphs in linear orderings. We show that there is no fixed tuple of $L_{\omega _1\omega }$ -formulas that, for all G, interpret the input graph G in the output linear ordering $L$. Harrison-Trainor and Montalbán [7] have also shown this, by a quite different proof. (shrink)

We study the Lindenbaum algebra ${\fancyscript{A}}$ (WKL o, RCA o) of sentences in the language of second-order arithmetic that imply RCA o and are provable from WKL o. We explore the relationship between ${\Sigma^1_1}$ sentences in ${\fancyscript{A}}$ (WKL o, RCA o) and ${\Pi^0_1}$ classes of subsets of ω. By applying a result of Binns and Simpson (Arch. Math. Logic 43(3), 399–414, 2004) about ${\Pi^0_1}$ classes, we give a specific embedding of the free distributive lattice with countably many generators into ${\fancyscript{A}}$ (...) (WKL o, RCA o). (shrink)

Let ${\mathcal{P}_s}$ be the lattice of degrees of non-empty ${\Pi_1^0}$ subsets of 2 ω under Medvedev reducibility. Binns and Simpson proved that FD(ω), the free distributive lattice on countably many generators, is lattice-embeddable below any non-zero element in ${\mathcal{P}_s}$ . Cenzer and Hinman proved that ${\mathcal{P}_s}$ is dense, by adapting the Sacks Preservation and Sacks Coding Strategies used in the proof of the density of the c.e. Turing degrees. With a construction that is a modification of the one (...) by Cenzer and Hinman, we improve on the result of Binns and Simpson by showing that for any ${\mathcal{U} < _s \mathcal{V}}$ , we can lattice embed FD(ω) into ${\mathcal{P}_s}$ strictly between ${deg_s(\mathcal{U})}$ and ${deg_s({\mathcal V})}$ . We also note that, in contrast to the infinite injury in the proof of the Sacks Density Theorem, in our proof all injury is finite, and that this is also true for the proof of Cenzer and Hinman, if a straightforward simplification is made. (shrink)

In this paper we study a reducibility that has been introduced by Klaus Weihrauch or, more precisely, a natural extension for multi-valued functions on represented spaces. We call the corresponding equivalence classes Weihrauch degrees and we show that the corresponding partial order induces a lower semi-lattice. It turns out that parallelization is a closure operator for this semi-lattice and that the parallelized Weihrauch degrees even form a lattice into which the Medvedev lattice and the Turing degrees can be (...) embedded. The importance of Weihrauch degrees is based on the fact that multi-valued functions on represented spaces can be considered as realizers of mathematical theorems in a very natural way and studying the Weihrauch reductions between theorems in this sense means to ask which theorems can be transformed continuously or computably into each other. As crucial corner points of this classification scheme the limited principle of omniscience LPO, the lesser limited principle of omniscience LLPO and their parallelizations are studied. It is proved that parallelized LLPO is equivalent to Weak Kőnig's Lemma and hence to the Hahn—Banach Theorem in this new and very strong sense. We call a multi-valued function weakly computable if it is reducible to the Weihrauch degree of parallelized LLPO and we present a new proof, based on a computational version of Kleene's ternary logic, that the class of weakly computable operations is closed under composition. Moreover, weakly computable operations on computable metric spaces are characterized as operations that admit upper semi-computable compact-valued selectors and it is proved that any single-valued weakly computable operation is already computable in the ordinary sense. (shrink)

We prove that the Weihrauch lattice can be transformed into a Brouwer algebra by the consecutive application of two closure operators in the appropriate order: first completion and then parallelization. The closure operator of completion is a new closure operator that we introduce. It transforms any problem into a total problem on the completion of the respective types, where we allow any value outside of the original domain of the problem. This closure operator is of interest by itself, as it (...) generates a total version of Weihrauch reducibility that is defined like the usual version of Weihrauch reducibility, but in terms of total realizers. From a logical perspective completion can be seen as a way to make problems independent of their premises. Alongside with the completion operator and total Weihrauch reducibility we need to study precomplete representations that are required to describe these concepts. In order to show that the parallelized total Weihrauch lattice forms a Brouwer algebra, we introduce a new multiplicative version of an implication. While the parallelized total Weihrauch lattice forms a Brouwer algebra with this implication, the total Weihrauch lattice fails to be a model of intuitionistic linear logic in two different ways. In order to pinpoint the algebraic reasons for this failure, we introduce the concept of a Weihrauch algebra that allows us to formulate the failure in precise and neat terms. Finally, we show that the Medvedev Brouwer algebra can be embedded into our Brouwer algebra, which also implies that the theory of our Brouwer algebra is Jankov logic. (shrink)

We carry out some of Galois' work in the setting of an arbitrary first-order theory T. We replace the ambient algebraically closed field by a large model M of T, replace fields by definably closed subsets of M, assume that T codes finite sets, and obtain the fundamental duality of Galois theory matching subgroups of the Galois group of L over F with intermediate extensions F ≤ K ≤ L. This exposition of a special case of [10] has the advantage (...) of requiring almost no background beyond familiarity with fields, polynomials, first-order formulae, and automorphisms. (shrink)

This paper began as a generalization of a part of the author's PhD thesis about ACFA and ended up with a characterization of groups definable in T A . The thesis concerns minimal formulae of the form x ∈ A ∧ σ(x) = f(x) for an algebraic curve A and a dominant rational function f: A → σ(A). These are shown to be uniform in the Zilber trichotomy, and the pairs (A, f) that fall into each of the three cases (...) are characterized. These characterizations are definable in families. This paper covers approximately half of the thesis, namely those parts of it which can be made purely model-theoretic by moving from ACFA, the model companion of the class of algebraically closed fields with an endomorphism, to T A , the model companion of the class of models of an arbitrary totally-transcendental theory T with an injective endomorphism, if this model-companion exists. A T A analog of the characterization of groups definable in ACFA is obtained in the process. The full characterization of the cases of the Zilber trichotomy in the thesis is obtained from these intermediate results with heavy use of algebraic geometry. (shrink)

Using the Feferman-Vaught Theorem, we prove that a definable subset of a product structure must be a Boolean combination of open sets, in the product topology induced by giving each factor structure the discrete topology. We prove that for families of structures with certain properties, including families of integral domains, the pure Boolean generalized product is definable in the direct product structure. We use these results to obtain characterizations of the definable subsets of $$\prod _p \mathbb {F}_p$$ —in particular, every (...) formula is equivalent to a Boolean combination of $$\exists \forall \exists $$ formulae. (shrink)

Name der Zeitschrift: Byzantinische Zeitschrift Jahrgang: 109 Heft: 2 Seiten: 821-836.

We consider the computably enumerable sets under the relation of Q-reducibility. We first give several results comparing the upper semilattice of c.e. Q-degrees, RQ, Q, under this reducibility with the more familiar structure of the c.e. Turing degrees. In our final section, we use coding methods to show that the elementary theory of RQ, Q is undecidable.

We give several characterizations of Schnorr trivial sets, including a new lowness notion for Schnorr triviality based on truth-table reducibility. These characterizations allow us to see not only that some natural classes of sets, including maximal sets, are composed entirely of Schnorr trivials, but also that the Schnorr trivial sets form an ideal in the truth-table degrees but not the weak truth-table degrees. This answers a question of Downey, Griffiths and LaForte.

This paper uses an atomistic ontology of universals, individuals, and facts to provide a semantics for ramified type theory. It is shown that with some natural constraints on the sort of universals and facts admitted into a model, the axiom of reducibility is made valid.

We show that the c.e. Q1,N\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${Q_{1,N}}$$\end{document}-degrees are not an upper semilattice. We prove that if M is an r-maximal set, A is an arbitrary set and M≡Q1,NA\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${M \equiv{}_ {Q_{1,N}}A}$$\end{document}, then M≤mA\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${M\leq{}_{m} A}$$\end{document}. Also, if M1 and M2 are r-maximal sets, A and B are major subsets of M1 and M2, respectively, and M1\A≡Q1,NM2\B\documentclass[12pt]{minimal} \usepackage{amsmath} (...) \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${M_{1}{\setminus} A\equiv{}_{Q_{1,N}}M_{2}{\setminus} B}$$\end{document}, then M1\A≡mM2\B\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${M_{1}{\setminus}A\equiv{}_{m}M_{2}{\setminus} B}$$\end{document}. If M1 and M2 are r-maximal sets and M10,M11\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${M_{1}^{0},\,M_{1}^{1}}$$\end{document} and M20,M21\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${M_{2}^{0},\,M_{2}^{1}}$$\end{document} are nontrivial splittings of M1 and M2, respectively, then M10≡Q1,NM20\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${M_{1}^{0} \equiv{}_{Q_{1,N}}M_{2}^{0}}$$\end{document} if and only if M10≡1M20\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${M_{1}^{0} \equiv{}_{1}M_{2}^{0}}$$\end{document}. From this result follows that if A and B are Friedberg splitting of an r-maximal set, then the Q1,N\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${Q_{1,N}}$$\end{document}-degree of A contains only one c.e. 1-degree. (shrink)

A two-stage sequential choice model is studied, the first stage being defined by q-Pareto multicriterial choice rule, and the second stage being defined by scalar extremization model. In this model, at the first stage the q-Pareto rule choses alternatives which are not only undominated in terms of Pareto comparison, but also includes into choice the alternatives which are dominated by no more than q alternatives. Since the choice set of the first-stage usually contains too many elements, obtained set is used (...) as a presentation for the second stage constructed by a scalar extremization model. The properties of the model are studied as well as its representability to one-stage scalar extremization model. (shrink)

The present paper is part of a larger project of investigating how far puzzling questions about Carnap’s philosophical deflationism – as expressed most prominently in “Empricism, Semantics and Ontology”1 – can be answered by reference to his own preferred position in areas upon which this meta-philosophical position can be expected to have a bearing. For that project the explorations below provide a starting point; on the present occasion they will, I hope, be found to be of independent interest. At issue (...) is the question of what makes Carnap’s The Logical Structure of the World a pre-physicalist work. (shrink)

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. (shrink)