We show that in the lattice E Π of Π 0 1 classes there are initial segments [ $\emptyset$ , P] = L(P) which are not Boolean algebras, but which have a decidable theory. In fact, we will construct for any finite distributive lattice L which satisfies the dual of the usual reduction property a Π 0 1 class P such that L is isomorphic to the lattice L(P)*, which is L(P), modulo finite differences. For the 2-element lattice, we (...) obtain a minimal class, first constructed by Cenzer, Downey, Jockusch and Shore in 1993. For the simplest new Π 0 1 class P constructed, P has a single, non-computable limit point and L(P)* has three elements, corresponding to $\emptyset$ , P and a minimal class P $_0 \subset$ P. The element corresponding to P 0 has no complement in the lattice. On the other hand, the theory of L(P) is shown to be decidable. A Π 0 1 class P is said to be decidable if it is the set of paths through a computable tree with no dead ends. We show that if P is decidable and has only finitely many limit points, then L(P)* is always a Boolean algebra. We show that if P is a decidable Π 0 1 class and L(P) is not a Boolean algebra, then the theory of L(P)interprets the theory of arithmetic and is therefore undecidable. (shrink)

Using properties of${\cal K}$-pairs of sets, we show that every nonzero enumeration degreeabounds a nontrivial initial segment of enumeration degrees whose nonzero elements have all the same jump asa. Some consequences of this fact are derived, that hold in the local structure of the enumeration degrees, including: There is an initial segment of enumeration degrees, whose nonzero elements are all high; there is a nonsplitting high enumeration degree; every noncappable enumeration degree is high; every nonzero low (...) enumeration degree can be capped by degrees of any possible local jump ; every enumeration degree that bounds a nonzero element of strictly smaller jump, is bounding; every low enumeration degree below a non low enumeration degreeacan be capped belowa. (shrink)

MOTIVATION The constructivization of ; => D(_£^') poses several problems. For some of these the tools of MD can be modified; for others new methods will need to be established. What must we do to make a full approximation to ; * D? We ...

Given a model \ of set theory, and a nontrivial automorphism j of \, let \\) be the submodel of \ whose universe consists of elements m of \ such that \=x\) for every x in the transitive closure of m ). Here we study the class \ of structures of the form \\), where the ambient model \ satisfies a frugal yet robust fragment of \ known as \, and \=m\) whenever m is a finite ordinal in the sense (...) of \ Our main achievement is the calculation of the theory of \ as precisely \-\. The following theorems encapsulate our principal results:Theorem A. Every structure in \ satisfies \-\.Theorem B. Each of the following three conditions is sufficient for a countable structure \ to be in \: \ is a transitive model of \-\. \ is a recursively saturated model of \-\. \ is a model of \.Theorem C. Suppose \ is a countable recursively saturated model of \ and I is a proper initial segment of \ that is closed under exponentiation and contains \. There is a group embedding \ from \\) into \\) such that I is the longest initial segment of \ that is pointwise fixed by \ for every nontrivial \.\)In Theorem C, \\) is the group of automorphisms of the structure X, and \ is the ordered set of rationals. (shrink)

It is known that every non-universal self-full degree in the structure of the degrees of computably enumerable equivalence relations (ceers) under computable reducibility has exactly one strong minimal cover. This leaves little room for embedding wide partial orders as initial segments using self-full degrees. We show that considerably more can be done by staying entirely inside the collection of non-self-full degrees. We show that the poset can be embedded as an initial segment of the degrees of ceers (...) with infinitely many classes. A further refinement of the proof shows that one can also embed the free distributive lattice generated by the lower semilattice as an initial segment of the degrees of ceers with infinitely many classes. (shrink)

A standard result about hyperdegrees is proved (under PD) for all $\triangle^1_{2n + 1}$-degrees.

A standard result about hyperdegrees is proved for allΔ2n+11-degrees.

Recent results on initial segments of the Turing degrees are presented, and some conjectures about initial segments that have implications for the existence of nontrivial automorphisms of the Turing degrees are indicated.

A 2-affable ultrafilter has only finitely many predecessors in the Rudin-Keisler ordering of isomorphism classes of ultrafilters over the natural numbers. If the continuum hypothesis is true, then there is an ℵ 1 -sequence of ultrafilters D α such that the strict Rudin-Keisler predecessors of D α are precisely the isomorphs of the D β 's for $\beta.

We affirm a conjecture of Sacks [1972] by showing that every countable distributive lattice is isomorphic to an initial segment of the hyperdegrees, $\scr{D}_{h}$ . In fact, we prove that every sublattice of any hyperarithmetic lattice (and so, in particular, every countable, locally finite lattice) is isomorphic to an initial segment of $\scr{D}_{h}$ . Corollaries include the decidability of the two quantifier theory of $\scr{D}_{h}$ and the undecidability of its three quantifier theory. The key tool in (...) the proof is a new lattice representation theorem that provides a notion of forcing for which we can prove a version of the fusion lemma in the hyperarithmetic setting and so the preservation of $\omega _{1}^{CK}$ . Somewhat surprisingly, the set theoretic analog of this forcing does not preserve ω₁. On the other hand, we construct countable lattices that are not isomorphic to any initial segment of $\scr{D}_{h}$. (shrink)

A standard result about hyperdegrees is proved (under PD) for all ▵ 1 2n + 1 -degrees.

By an "inverse iteration" of Sacks forcing over a model of V = L, we produce a model in which the degrees of constructibility of nonconstructible reals have order type ω 1 *.

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)

We combine two techniques of set theory relating to minimal degrees of constructibility. Jensen constructed a minimal real which is additionally a Π 1 2 singleton. Groszek built an initial segment of order type 1 + α * , for any ordinal α. This paper shows how to force a Π 1 2 singleton such that the c-degrees beneath it, all represented by reals, are of type 1 + α * , for many ordinals α. We also examine (...) the definability α needs to be so represented by a real. (shrink)

Suppose that 〈xk〉k∈ℕ is a countable sequence of real numbers. Working in the usual subsystems for reverse mathematics, RCA0 suffices to prove the existence of a sequence of reals 〈uk〉k∈ℕ such that for each k, uk is the minimum of {x0, x1, …, xk}. However, if we wish to prove the existence of a sequence of integer indices of minima of initial segments of 〈xk〉k∈ℕ, the stronger subsystem WKL0 is required. Following the presentation of these reverse mathematics results, we (...) will derive computability theoretic corollaries and use them to illustrate a distinction between computable analysis and constructive analysis. (shrink)

If $M \models PA (= Peano Arithmetic)$ , we set $A^M = \{N \subset_e M: N \models PA\}$ and study this family.

In this paper we describe the well-founded initial segment of the free Heyting algebra ������α on finitely many, α, generators. We give a complete classification of initial sublattices of ������₂ isomorphic to ������₁ (called 'low ladders'), and prove that for 2 < α < ω, the height of the well-founded initial segment of ������α.

For any countable nonstandard modelM of a sufficiently strong fragment of arithmeticT, and any nonstandard numbersa, c εM, M⊨c≦a, there is a modelK ofT which agrees withM up toa and such that inK there is a proof of contradiction inT with Gödel number $ \leqq 2^{a^c } $.

In any nonstandard model of Peano arithmetic, the standard part is not first-order definable. But we show that in some model the standard part is definable as the unique solution of a formula , where P is a unary predicate variable.

The WEAVER ++ model discussed by Levelt et al. assumes incremental encoding and articulation following complete encoding. However, many of the response latency results can also be accounted for by assuming incremental articulation. Another temporal variable, initial segment duration, can distinguish WEAVER ++'s incremental encoding account from the incremental articulation account.

A generalization is given of McAloon's result on initial segments ofmodels of GlΔ0, the fragment of Peano Arithmetic where the induction scheme is restricted to formulas with bounded quantifiers.

A generalization is given of McAloon's result on initial segments ofmodels of GlΔ0, the fragment of Peano Arithmetic where the induction scheme is restricted to formulas with bounded quantifiers.

By an "inverse iteration" of Sacks forcing over a model of $V = L$, we produce a model in which the degrees of constructibility of nonconstructible reals have order type $\omega_1^\ast$.

Where AR is the set of arithmetic Turing degrees, 0 (ω ) is the least member of { $\mathbf{\alpha}^{(2)}|\mathbf{a}$ is an upper bound on AR}. This situation is quite different if we examine HYP, the set of hyperarithmetic degrees. We shall prove (Corollary 1) that there is an a, an upper bound on HYP, whose hyperjump is the degree of Kleene's O. This paper generalizes this example, using an iteration of the jump operation into the transfinite which is based on (...) results of Jensen and is detailed in [3] and [4]. In $\S1$ we review the basic definitions from [3] which are needed to state the general results. (shrink)

The formation of segments in the Drosophila early embryo is understood in greater detail than any other complex developmental process. Now, by studying other types of insect embryo, we can hope to deduce something of the ancestral mechanism of segmentation and the ways in which it has been modified in evolution. The parasitic wasp, Copidosoma floridanum, is spectacularly atypical of insects in that the small egg cell divides extensively, with no initial syncytial phase, and forms eventually some 2000 embryos(1). (...) This process raises intriguing questions about the control of embryonic polarity and segmentation. (shrink)

chical reinforcement learning that does not rely on a pri ori hierarchical structures Thus the approach deals with a more di cult problem compared with existing work It in volves learning to segment sequences to create hierarchical structures based on reinforcement received during task ex ecution with di erent levels of control communicating with each other through sharing reinforcement estimates obtained by each others The algorithm segments sequences to re duce non Markovian temporal dependencies to facilitate the learning of (...) the overall task Initial experiments demon strated the basic promise of the approach.. (shrink)

The relatively simple central nervous system (CNS) of the Drosophila embryo provides a useful model system for investigating the mechanisms that generate and pattern complex nervous systems. Central to the generation of different types of neurons by precursor neuroblasts is the initial specification of neuroblast identity and the Drosophila segment polarity genes, genes that specify regions within a segment or repeating unit of the Drosophila embryo, have emerged recently as significant players in this process. During neurogenesis the (...) segment polarity genes are expressed in the neuroectodermal cells from which neuroblasts delaminate and they continue to be expressed in neuroblasts and their progeny. Loss-of-function mutations in these genes lead to a failure in the formation of neuroblasts and/or specification of neuroblast identity. Results from several recent studies suggest that regulatory interactions between segment polarity genes during neurogenesis lead to an increase in the number of neuroblasts and specification of different identities to neuroblasts within a population of cells. BioEssays 21:472–485, 1999. © 1999 John Wiley & Sons, Inc. (shrink)