An infinite binary sequence is complex if the Kolmogorov complexity of its initial segments is bounded below by a computable function. We prove that a class P contains a complex element if and only if it contains a wtt-cover for the Cantor set. That is, if and only if for every Y ⊆ ω there is an X in P such that X ≥wttY. We show that this is also equivalent to the class's being large in some sense. We give an example of how this result can be used in the study of scattered linear orders.

We define the notion of a weakly pointed tree, and characterize the amount of genericity necessary to prevent a uniformly branching tree being weakly pointed. We use these ideas to show there is no topological analogue of a measure-theoretic selection theorem of Graf and Mauldin.

§1. Introduction. Sacks [16] showed that every computably enumerable (c.e.) degree > 0 has a c.e. splitting. Hence, relativising, every c.e. degree has a Δ2 splitting above each proper predecessor (by ‘splitting’ we understand ‘nontrivial splitting’). Arslanov [1] showed that 0′ has a d.c.e. splitting above each c.e. a < 0′. On the other hand, Lachlan [11] proved the existence of a c.e. a < 0 which has no c.e. splitting above some proper c.e. predecessor, and Harrington [10] showed that one could take a = 0′. Splitting and nonsplitting techniques have had a number of consequences for definability and elementary equivalence in the degrees below 0′.

Heterogeneous splittings are best considered in the context of cupping and non-cupping. Posner and Robinson [15] showed that every nonzero Δ2 degree can be nontrivially cupped to 0′, and Arslanov [1] showed that every c.e. degree > 0 can be d.c.e. cupped to 0′ (and hence since every d.c.e., or even n-c.e., degree has a nonzero c.e. predecessor, every n-c.e. degree > 0 is d.c.e. cuppable). Cooper [4] and Yates (see Miller [13]) showed the existence of degrees noncuppable in the c.e. degrees. Moreover, the search for relative cupping results was drastically limited by Cooper [5], and Slaman and Steel [17] (see also Downey [9]), who showed that there is a nonzero c.e. degree a below which even Δ2 cupping of c.e. degrees fails.

We prove below what appears to be the strongest possible of such nonsplitting and noncupping results.

We will study some aspects of the local structure of models of certain C-minimal theories. We will prove (theorem 19) that, in a sufficiently saturated C-minimal structure in which the algebraic closure has the exchange property and which is locally modular, we can construct an infinite type-definable group around any non trivial point (a term to be defined later).

In this paper a method for the replacement, in formulas, of strong quantifiers by functions is introduced that can be considered as an alternative to Skolemization in the setting of constructive theories. A constructive extension of intuitionistic predicate logic that captures the notions of preorder and existence is introduced and the method, orderization, is shown to be sound and complete with respect to this logic. This implies an analogue of Herbrand's theorem for intuitionistic logic. The orderization method is applied to the constructive theories of equality and groups.

In this paper we study generic complexity of undecidable problems. It turns out that some classical undecidable problems are, in fact, strongly undecidable, i.e., they are undecidable on every strongly generic subset of inputs. For instance, the classical Halting Problem is strongly undecidable. Moreover, we prove an analog of the Rice theorem for strongly undecidable problems, which provides plenty of examples of strongly undecidable problems. Then we show that there are natural super-undecidable problems, i.e., problem which are undecidable on every generic (not only strongly generic) subset of inputs. In particular, there are finitely presented semigroups with super-undecidable word problem. To construct strongly- and super-undecidable problems we introduce a method of generic amplification (an analog of the amplification in complexity theory). Finally, we construct absolutely undecidable problems, which stay undecidable on every non-negligible set of inputs. Their construction rests on generic immune sets.

We deal with a restricted form WC-N′ of the weak continuity principle, a version BT′ of Baire's theorem, and a boundedness principle BD-N. We show, in the spirit of constructive reverse mathematics, that WC-N′, BT′ + ¬LPO and BD-N + ¬LPO are equivalent in a constructive system, where LPO is the limited principle of omniscience.

Given a supercompact cardinal κ and a regular cardinal λ < κ, we describe a type of forcing such that in the generic extension the cofinality of κ is λ, there is a very good scale at κ, a bad scale at κ, and SCH at κ fails. When creating our model we have great freedom in assigning the value of 2κ, and so we can make SCH hold or fail arbitrarily badly.

We prove that a combinatorial consequence of the negation of the PCF conjecture for intervais, involving free subsets relative to set mappings, is not implied by even the strongest known large cardinal axiom.

We investigate the relationship between lowness for Schnorr randomness and Schnorr triviality. We show that a real is low for Schnorr randomness if and only if it is Schnorr trivial and hyperimmune free.

Much previous study has been done on the degree spectra of prime models of a complete atomic decidable theory. Here we study the analogous questions for homogeneous models. We say a countable model has a d-basis if the types realized in are all computable and the Turing degree d can list -indices for all types realized in . We say has a d-decidable copy if there exists a model ≅ such that the elementary diagram of is d-computable. Goncharov, Millar, and Peretyat'kin independently showed there exists a homogeneous with a 0-basis but no decidable copy.

We prove that any homogeneous with a 0′-basis has a low decidable copy. This implies Csima's analogous result for prime models. In the case where all types of the theory T are computable and is a homogeneous model with a 0-basis, we show has copies decidable in every nonzero degree. A degree d is 0-homogeneous bounding if any automorphically nontrivial homogeneous with a 0-basis has a d-decidable copy. We show that the nonlow2 degrees are 0-homogeneous bounding.

We examine the computably enumerable (c.e.) degrees of prime models of complete atomic decidable (CAD) theories. A structure has degree d if d is the degree of its elementary diagram. We show that if a CAD theory T has a prime model of c.e. degree c, then T has a prime model of strictly lower c.e. degree b, where, in addition, b is low (b′ = 0′), This extends Csima's result that every CAD theory has a low prime model. We also prove a density result for c.e. degrees of prime models. In particular, if c and d are c.e. degrees with d < c and c not low2 (c″ > 0″), then for any CAD theory T, there exists a c.e. degree b with d < b < c such that T has a prime model of degree b, where b can be chosen so that b′ is any degree c.e. in c with d′ ≤ b′. As a corollary, we show that for any degree c with 0 < c < 0′, every CAD theory has a prime model of low c.e. degree incomparable with c. We show also that every CAD theory has prime models of low c.e. degree that form a minimal pair, extending another result of Csima. We then discuss how these results apply to homogeneous models.

Elementary Recursive Nonstandard Analysis, in short ERNA, is a constructive system of nonstandard analysis proposed around 1995 by Patrick Suppes and Richard Sommer, who also proved its consistency inside PRA. It is based on an earlier system developed by Rolando Chuaqui and Patrick Suppes, of which Michal Rössler and Emil Jeřábek have recently proposed a weakened version. We add a Πı-transfer principle to ERNA and prove the consistency of the extended theory inside PRA. In this extension of ERNA a Σı-supremum principle ‘up-to-infinitesimals’, and some well-known calculus results for sequences are deduced. Finally, we prove that transfer is ‘too strong’ for finitism by reconsidering Rössler and Jeřábek's conclusions.

We consider the problem whether the theorems of the fragments form a strictly increasing hierarchy. We shall show a link to some results about the lengths of proofs in predicate logic that supports the conjecture that the hierarchy is strictly increasing.

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

The purpose of this note is to demonstrate that a weak form of club guessing on ω1 implies the existence of an Aronszajn line with no Countryman suborders. An immediate consequence is that the existence of a five element basis for the uncountable linear orders does not follow from the forcing axiom for ω-proper forcings.

Denef and Loeser denned a map from the Grothendieck ring of sets definable in pseudo-finite fields to the Grothendieck ring of Chow motives, thus enabling to apply any cohomological invariant to these sets. We generalize this to perfect, pseudo algebraically closed fields with pro-cyclic Galois group.

In addition, we define some maps between different Grothendieck rings of definable sets which provide additional information, not contained in the associated motive. In particular we infer that the map of Denef-Loeser is not injective.