We explore the complexity of Sacks’ Splitting Theorem in terms of the mind change functions associated with the members of the splits. We prove that, for any c.e. set A, there are low computably enumerable sets $A_0\sqcup A_1=A$ splitting A with $A_0$ and $A_1$ both totally $\omega ^2$ -c.a. in terms of the Downey–Greenberg hierarchy, and this result cannot be improved to totally $\omega $ -c.a. as shown in [9]. We also show that if cone avoidance (...) is added then there is no level below $\varepsilon _0$ which can be used to characterize the complexity of $A_1$ and $A_2$. (shrink)

A set of natural numbers is called d.r.e. if it may be obtained from some recursively enumerable set by deleting the numbers belonging to another recursively enumerable set. Sacks showed that for each non-recursive recursively enumerable set A there are disjoint recursively enumerable sets B, C which cover A such that A is recursive in neither A ∩ B nor A ∩ C. In this paper, we construct a counterexample which shows that Sacks's theorem is not in (...) general true when A is d.r.e. rather than r.e. (shrink)

We formulate an abstract version of the finite injury method in the form of the Baire category theorem. The theorem has the following corollaries: The Friedberg-Muchnik pair of recursively enumerable degrees, the Sacks splitting theorem, the existence of a minimal degree below 0′ and the Shoenfield jump theorem.

A recursively enumerable splitting of an r.e. setAis a pair of r.e. setsBandCsuch thatA=B∪CandB∩C= ⊘. Since for such a splitting degA= degB∪ degC, r.e. splittings proved to be a quite useful notion for investigations into the structure of the r.e. degrees. Important splitting theorems, like Sacks splitting [S1], Robinson splitting [R1] and Lachlan splitting [L3], use r.e. splittings.Since each r.e. splitting of a set induces a splitting of its degree, it is (...) natural to study the relation between the degrees of r.e. splittings and the degree splittings of a set. We say a setAhas thestrong universal splitting property if each splitting of its degree is represented by an r.e. splitting of itself, i.e., if for degA=b∪cthere is an r.e. splittingB, CofAsuch that degB=band degC=c. The goal of this paper is the study of this splitting property.In the literature some weaker splitting properties have been studied as well as splitting properties which imply failure of the SUSP. (shrink)

The foundation scheme in set theory asserts that every nonempty class has an ∈\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\in $$\end{document}-minimal element. In this paper, we investigate the logical strength of the foundation principle in basic set theory and α\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\alpha $$\end{document}-recursion theory. We take KP set theory without foundation as the base theory. We show that KP-\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$^-$$\end{document} + Π1\documentclass[12pt]{minimal} \usepackage{amsmath} (...) \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\Pi _1$$\end{document}-Foundation + V=L\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$V=L$$\end{document} is enough to carry out finite injury arguments in α\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\alpha $$\end{document}-recursion theory, proving both the Friedberg-Muchnik theorem and the Sacks splitting theorem in this theory. In addition, we compare the strengths of some fragments of KP. (shrink)

A splitting of an r.e. set A is a pair A1, A2 of disjoint r.e. sets such that A1 A2 = A. Theorems about splittings have played an important role in recursion theory. One of the main reasons for this is that a splitting of A is a decomposition of A in both the lattice, , of recursively enumerable sets and in the uppersemilattice, R, of recursively enumerable degrees . Thus splitting theor ems have been used to (...) obtain results about the structure of , the structure of R, and the relationship between the two structures. Furthermore it is fair to say that questions about splittings have often generated important new technical developments in recursion theory. In this article we survey most of the results and techniques associated with splitting properties of r.e. sets in ordinary recursion theory. (shrink)

This is a contribution to the study of the Muchnik and Medvedev lattices of non-empty Π01 subsets of 2ω. In both these lattices, any non-minimum element can be split, i. e. it is the non-trivial join of two other elements. In fact, in the Medvedev case, ifP > MQ, then P can be split above Q. Both of these facts are then generalised to the embedding of arbitrary finite distributive lattices. A consequence of this is that both lattices have decidible (...) ∃-theories. (shrink)

The Sacks Density Theorem [7] states that the Turing degrees of the recursively enumerable sets are dense. We show that the Density Theorem holds in every model of P - + BΣ 2 . The proof has two components: a lemma that in any model of P - + BΣ 2 , if B is recursively enumerable and incomplete then IΣ 1 holds relative to B and an adaptation of Shore's [9] blocking technique in α-recursion theory to (...) models of arithmetic. (shrink)

It is known from work of P. Young that there are recursively enumerable sets which have optimal orders for enumeration, and also that there are sets which fail to have such orders in a strong sense. It is shown that both these properties are widespread in the class of recursively enumerable sets. In fact, any infinite recursively enumerable set can be split into two sets each of which has the property under consideration. A corollary to this result is that there (...) are recursive sets with no optimal order of enumeration. (shrink)

We investigate the relationship of the degrees of splittings of a computably enumerable set and the degree of the set. We prove that there is a high computably enumerable set whose only proper splittings are low 2.

The notion of a weakly scattered theory T is defined. T need not be scattered. For each a model of T, let sr() be the Scott rank of . Assume sr() ≤ ω\sp A \sb 1 for all a model of T. Let σ\sp T \sb 2 be the least Σ₂ admissible ordinal relative to T. If T admits effective k-splitting as defined in this paper, then θσ\cal Aθ\cal A$ a model of T.

We complete a study of the splitting/non-splitting properties of the enumeration degrees below by proving an analog of Harrington’s non-splitting theorem for the enumeration degrees. We show how non-splitting techniques known from the study of the c.e. Turing degrees can be adapted to the enumeration degrees.

Given a normal (multi-)modal logic a characterization is given of the finitely presentable algebras A whose logics L A split the lattice of normal extensions of . This is a substantial generalization of Rautenberg [10] and [11] in which is assumed to be weakly transitive and A to be finite. We also obtain as a direct consequence a result by Blok [2] that for all cycle-free and finite A L A splits the lattice of normal extensions of K. Although we (...) firmly believe it to be true, we have not been able to prove that if a logic splits the lattice of extensions of then is the logic of an algebra finitely presentable over ; in this respect our result remains partial. (shrink)

This paper provides a sound and complete proof system for a language that adds to Dynamic Epistemic Logic a discrete previous-time operator as well as single symbol formulas that partially reveal the most recent event that occurred. The completeness theorem is by filtration followed by model unraveling and other model transformations. Decidability follows from the completeness proof. The degree to which it is important to include the additional single symbol formulas is addressed in a discussion about the difficulties of (...) the completeness for a language that only adds the previous-time operator to DEL. Discussion is also given regarding the completeness for a language obtained by removing common knowledge operators from. (shrink)

We show that the top of any diamond with bottom 0 in the r.e. degrees is also the top of a stack of n diamonds with bottom 0.

Applications of quantum mechanics in the computational and information processing tasks is a recent research interest among the researchers. Certain operations which are impossible to achieve in the description of quantum mechanics are known as no-go theorems. One such theorem is no-splitting theorem of quantum states. The no-splitting theorem states that the information in an unknown quantum bit is an inseparable entity and cannot be split into two complementary qubits. In this work, we try to (...) find out the class of operators for which the splitting is possible in a probabilistic way. The work also aims to find the connection between the unitary operators and probabilistic splitting. (shrink)

, a notion of forcing over E, the E-closure of L, is said to be effective if every sideways -generic extension preserves E-closure. There are set notions of forcing in E that do not preserve E-closure. The main theorem below asserts that is effective if and only if it is locally proper, a weak variant of Shelah's notion of proper.

Contents: Recursive Enumerability and the Jump Operator; On the Degrees Less Than 0'; A Simple Set Which Is Not Effectively Simple; The Recursively Enumerable Degrees Are Dense; Metarecursive Sets (with G Kreisel); Post's Problem, Admissible Ordinals and Regularity; On a Theorem of Lachlan and Marlin; A Minimal Hyperdegree (with R O Gandy); Measure-Theoretic Uniformity in Recursion Theory and Set Theory; Forcing with Perfect Closed Sets; Recursion in Objects of Finite Type; The a-Finite Injury Method (with S G Simpson); Remarks (...) Against Foundational Activity; Countable Admissible Ordinals and Hyperdegrees; The 1-Section of a Type n Object; The k-Section of a Type n Object; Post's Problem, Absoluteness and Recursion in Finite Types; Effective Bounds on Morley Rank; On the Number of Countable Models; Post's Problem in E-Recursion; The Limits of E-Recursive Enumerability; Effective Versus Proper Forcing. (shrink)

The splitting theorem says that any set of formulae has a finest representation as a family of letter-disjoint sets. Parikh formulated this for classical propositional logic, proved it in the finite case, used it to formulate a criterion for relevance in belief change, and showed that AGMpartial meet revision can fail the criterion. In this paper we make three further contributions. We begin by establishing a new version of the well-known interpolation theorem, which we call parallel interpolation, (...) use it to prove the splitting theorem in the infinite case, and show how AGM belief change operations may be modified, if desired, so as to ensure satisfaction of Parikh’s relevance criterion. (shrink)

Reverse mathematics is a program in the foundations of mathematics founded by Friedman and developed extensively by Simpson and others. The aim of RM is to find the minimal axioms needed to prove a theorem of ordinary, that is, non-set-theoretic, mathematics. As suggested by the title, this paper deals with two RM-phenomena, namely, splittings and disjunctions. As to splittings, there are some examples in RM of theorems A, B, C such that A↔, that is, A can be split into (...) two independent parts B and C. As to disjunctions, there are examples in RM of theorems D, E, F such that D↔, that is, D can be written as the disjunction of two independent parts E and F. By contrast, we show in this paper that there is a plethora of splittings and disjunctions in Kohlenbach’s higher-order RM. (shrink)

In [2], Jockusch and Shore have introduced a new hierarchy of sets and operators called the REA hierarchy. In this note we prove analogues of the Friedberg Jump Theorem and the Sacks Jump Theorem for many REA operators. MSC: 03D25, 03D55.

Recent experiments have shown that certain fluid-mechanical systems, namely oil droplets bouncing on oil films, can mimic a wide range of quantum phenomena, including double-slit interference, quantization of angular momentum and Zeeman splitting. Here I investigate what can be learned from these systems concerning no-go theorems as those of Bell and Kochen-Specker. In particular, a model for the Bell experiment is proposed that includes variables describing a ‘background’ field or medium. This field mimics the surface wave that accompanies the (...) droplets in the fluid-mechanical experiments. It appears that quite generally such a model can violate the Bell inequality and reproduce the quantum statistics, even if it is based on local dynamics only. The reason is that measurement independence is not valid in such models. This opens the door for local ‘background-based’ theories, describing the interaction of particles and analyzers with a background field, to complete quantum mechanics. Experiments to test these ideas are also proposed. (shrink)

Split preorders are preordering relations on a domain whose composition is defined in a particular way by splitting the domain into two disjoint subsets. These relations and the associated composition arise in categorial proof theory in connection with coherence theorems. Here split preorders are represented isomorphically in the category whose arrows are binary relations and whose composition is defined in the usual way. This representation is related to a classical result of representation theory due to Richard Brauer.

According to [M.S. Kurilić, Cohen-stable families of subsets of the integers, J. Symbolic Logic 66 257–270], adding a Cohen real destroys a splitting family on ω if and only if is isomorphic to a splitting family on the set of rationals, , whose elements have nowhere dense boundaries. Consequently, implies the Cohen-indestructibility of . Using the methods developed in [J. Brendle, S. Yatabe, Forcing indestructibility of MAD families, Ann. Pure Appl. Logic 132 271–312] the stability of splitting (...) families in several forcing extensions is characterized in a similar way . Also, it is proved that a splitting family is preserved by the Sacks forcing if and only if it is preserved by some forcing which adds a new real. The corresponding hierarchy of splitting families is investigated. (shrink)

In this paper we study elementary submodels of a stable homogeneous structure. We improve the independence relation defined in Hyttinen 167–182). We apply this to prove a structure theorem. We also show that dop and sdop are essentially equivalent, where the negation of dop is the property we use in our structure theorem and sdop implies nonstructure, see Hyttinen.

Let κ denote a regular uncountable cardinal and NS the normal ideal of nonstationary subsets of κ. Our results concern the well-known open question whether NS fails to be κ + -saturated, i.e., are there κ + stationary subsets of κ with pairwise intersections nonstationary? Our first observation is: Theorem. NS is κ + -saturated iff for every normal ideal J on κ there is a stationary set $A \subseteq \kappa$ such that $J = NS \mid A = \{X (...) \subseteq \kappa:X \cap A \in NS\}$ . Turning our attention to large cardinals, we extend the usual (weak) Mahlo hierarchy to define "greatly Mahlo" cardinals and obtain the following: Theorem. If κ is greatly Mahlo then NS is not κ + -saturated. Theorem. If κ is ordinal Π 1 1 -indescribable (e.g., weakly compact), ethereal (e.g., subtle), or carries a κ-saturated ideal, then κ is greatly Mahlo. Moreover, there is a stationary set of greatly Mahlo cardinals below any ordinal Π 1 1 -indescribable cardinal. These methods apply to other normal ideals as well; e.g., the subtle ideal on an ineffable cardinal κ is not κ + -saturated. (shrink)

We give an example of a variety of Heyting algebras and of a splitting algebra in this variety that is not finitely presentable. Moreover, we show that the corresponding splitting pair cannot be defined by any finitely presentable algebra. Also, using the Gödel-McKinsey-Tarski translation and the Blok-Esakia theorem, we construct a variety of Grzegorczyk algebras with similar properties.

Separates the purely combinatorial component of Arrow's impossibility theorem in the theory of collective preference from its decision-theoretic part, and likewise for the closely related Blair/Bordes/Kelly/Suzumura theorem. Such a separation provides a particularly elegant proof of Arrow's result, via a new 'splitting theorem'.

A set S of degrees is said to be an initial segment if c ≤ d ∈ S→-c∈S. Shoenfield has shown that if P is the lattice of all subsets of a finite set then there is an initial segment of degrees isomorphic to P. Rosenstein [2] (independently) proved the same to hold of the lattice of all finite subsets of a countable set. We shall show that “countable set” may be replaced by “set of cardinality at most that of (...) the continuum.” This result is also an extension of [3, Corollary 2 to Theorem 15], which states that there is a sublattice of degrees isomorphic to the lattice of all finite subsets of 2N. (A sublattice of degrees is a subset closed under ∪ and ∩; an initial segment closed under ∪ is necessarily a sublattice, but not conversely.)It seems worth noting that the proof of the present result was preceded in time by our proof [4] of the analogous theorem for hyperdegrees, and is in fact an adaptation of that proof. Thus the present work has been influenced much more directly by the Gandy-Sacks forcing construction of a minimal hyperdegree [1] than by previous work on initial segments of degrees. (shrink)

The classical Feferman–Vaught Theorem for First Order Logic explains how to compute the truth value of a first order sentence in a generalized product of first order structures by reducing this computation to the computation of truth values of other first order sentences in the factors and evaluation of a monadic second order sentence in the index structure. This technique was later extended by Läuchli, Shelah and Gurevich to monadic second order logic. The technique has wide applications in decidability (...) and definability theory. Here we give a unified presentation, including some new results, of how to use the Feferman–Vaught Theorem, and some new variations thereof, algorithmically in the case of Monadic Second Order Logic MSOL . We then extend the technique to graph polynomials where the range of the summation of the monomials is definable in MSOL . Here the Feferman–Vaught Theorem for these polynomials generalizes well known splitting theorems for graph polynomials. Again, these can be used algorithmically. Finally, we discuss extensions of MSOL for which the Feferman–Vaught Theorem holds as well. (shrink)

Let G be a simple group of finite Morley rank with a definable BN-pair of rank 2 where B=UT for T=B ∩ N and U a normal subgroup of B with Z≠1. By [9] 853) the Weyl group W=N/T has cardinality 2n with n=3,4,6,8 or 12. We prove here:Theorem 1. If n=3, then G is interpretably isomorphic to PSL3 for some algebraically closed field K.Theorem 2. Suppose Z contains some B-minimal subgroup AZ with RMRM for both parabolic subgroups (...) P1 and P2. Then n=3,4 or 6 and G is interpretably isomorphic to PSL3, PSp4 or G2 for some algebraically closed field K.Theorem 3. If U is nilpotent and n≠8, then G is interpretably isomorphic to either PSL3, PSp4 or G2 for some algebraically closed field K. (shrink)

Both the Beth definability theorem and Craig's lemma (interpolation theorem from now on) deal with the issue of the entanglement of one language L1 with another language L2, that is to say, information transfer—or the lack of such transfer—between the two languages. The notion of splitting we study below looks into this issue. We briefly relate our own results in this area as well as the results of other researchers like Kourousias and Makinson, and Peppas, Chopra and (...) Foo.Section 3 does contain one apparently new theorem. (shrink)

Reverse mathematics is a program in the foundations of mathematics founded by Friedman and developed extensively by Simpson and others. The aim of RM is to find the minimal axioms needed to prove a theorem of ordinary, that is, non-set-theoretic, mathematics. As suggested by the title, this paper deals with the study of the topological notions of dimension and paracompactness, inside Kohlenbach’s higher-order RM. As to splittings, there are some examples in RM of theorems A, B, C such that (...) A ↔, that is, A can be split into two independent parts B and C, and the aforementioned topological notions give rise to a number of splittings involving highly natural A, B, C. Nonetheless, the higher-order picture is markedly different from the second-one: in terms of comprehension axioms, the proof in higher-order RM of, for example, the paracompactness of the unit interval requires full second-order arithmetic, while the second-order/countable version of paracompactness of the unit interval is provable in the base theory RCA 0. We obtain similarly “exceptional” results for the Urysohn identity, the Lindelöf lemma, and partitions of unity. We show that our results exhibit a certain robustness, in that they do not depend on the exact definition of cover, even in the absence of the axiom of choice. (shrink)

We study cardinal invariants of systems of meager hereditary families of subsets of ω connected with the collapse of the continuum by Sacks forcing S and we obtain a cardinal invariant yω such that S collapses the continuum to yω and y ≤ yω ≤ b. Applying the Baumgartner-Dordal theorem on preservation of eventually narrow sequences we obtain the consistency of y = yω < b. We define two relations $\leq _{0}^{\ast}$ and $\leq _{1}^{\ast}$ on the set $(^{\omega}\omega)_{{\rm (...) Fin}}$ of finite-to-one functions which are Tukey equivalent to the eventual dominance relation of functions such that if $\germ{F}\subseteq (^{\omega}\omega)_{Fin}$ is $\leq _{1}^{\ast}$ -unbounded, well-ordered by $\leq _{1}^{\ast}$ , and not $\leq _{0}^{\ast}$ -dominating, then there is a nonmeager p-ideal. The existence of such a system F follows from Martin's axiom. This is an analogue of the results of [3], [9, 10] for increasing functions. (shrink)

We use a fundamental theorem of Vaught, called the covering theorem in [V] (cf. theorem 0.1 below) as well as a generalization of it (cf. Theorem $0.1^\ast$ below) to derive several known and a few new results related to the logic $L_{\omega_1\omega}$. Among others, we prove that if every countable model in a $PC_{\omega_1\omega}$ class has only countably many automorphisms, then the class has either $\leq\aleph_0$ or exactly $2^{\aleph_0}$ nonisomorphic countable members (cf. Theorem $4.3^\ast$) and (...) that the class of countable saturated structures of a sufficiently large countable similarity type is not $PC_{\omega_1\omega}$ among countable structures (cf. Theorem 5.2). We also give a simple proof of the Lachlan-Sacks theorem on bounds of Morley ranks ($\s 7$). (shrink)

I prove several natural preservation theorems for the countable support iteration. This solves a question of Rosłanowski regarding the preservation of localization properties and greatly simplifies the proofs in the area.

We investigate the complexity of various combinatorial theorems about linear and partial orders, from the points of view of computability theory and reverse mathematics. We focus in particular on the principles ADS (Ascending or Descending Sequence), which states that every infinite linear order has either an infinite descending sequence or an infinite ascending sequence, and CAC (Chain-AntiChain), which states that every infinite partial order has either an infinite chain or an infinite antichain. It is well-known that Ramsey's Theorem for (...) pairs (RT₂²) splits into a stable version (SRT₂²) and a cohesive principle (COH). We show that the same is true of ADS and CAC, and that in their cases the stable versions are strictly weaker than the full ones (which is not known to be the case for RT₂² and SRT₂²). We also analyze the relationships between these principles and other systems and principles previously studied by reverse mathematics, such as WKL₀, DNR, and BΣ₂. We show, for instance, that WKL₀ is incomparable with all of the systems we study. We also prove computability-theoretic and conservation results for them. Among these results are a strengthening of the fact, proved by Cholak, Jockusch, and Slaman, that COH is Π₁¹-conservative over the base system RCA₀. We also prove that CAC does not imply DNR which, combined with a recent result of Hirschfeldt, Jockusch, Kjos-Hanssen, Lempp, and Slaman, shows that CAC does not imply SRT₂² (and so does not imply RT₂²). This answers a question of Cholak, Jockusch, and Slaman. Our proofs suggest that the essential distinction between ADS and CAC on the one hand and RT₂² on the other is that the colorings needed for our analysis are in some way transitive. We formalize this intuition as the notions of transitive and semitransitive colorings and show that the existence of homogeneous sets for such colorings is equivalent to ADS and CAC, respectively. We finish with several open questions. (shrink)

We prove that any speedable computably enumerable set may be split into a disjoint pair of speedable computably enumerable sets. This solves a longstanding question of J.B. Remmel concerning the behavior of computably enumerable sets in Blum's machine independent complexity theory. We specify dynamic requirements and implement a novel way of detecting speedability-by embedding the relevant measurements into the substage structure of the tree construction. Technical difficulties in satisfying the dynamic requirements lead us to implement "local" strategies that only look (...) down the tree. The (obvious) problems with locality are then resolved by placing an isomorphic copy of the entire priority tree below each strategy (yielding a self-similar tree). This part of the construction could be replaced by an application of the Recursion Theorem, but shows how to achieve the same effect with a more direct construction. (shrink)

A definable pair of disjoint non-OD sets of reals exists in the Sacks and ????0-large generic extensions of the constructible universe L. More specifically, if a∈2ω is eith...