In this note we shall prove

Theorem 0.1. Letbe a countably ω-iterable-mouse which satisfies AD, and [α, β] a weak gap of. Supposeis captured by mice with iteration strategies in ∣α. Let n be least such that ; then we have that believes that has the Scale Property.

This complements the work of [5] on the construction of scales of minimal complexity on sets of reals in K(ℝ). Theorem 0.1 was proved there under the stronger hypothesis that all sets definable over are determined, although without the capturing hypothesis. (See [5, Theorem 4.14].) Unfortunately, this is more determinacy than would be available as an induction hypothesis in a core model induction. The capturing hypothesis, on the other hand, is available in such a situation. Since core model inductions are one of the principal applications of the construction of optimal scales, it is important to prove 0.1 as stated.

Our proof will incorporate a number of ideas due to Woodin which figure prominently in the weak gap case of the core model induction. It relies also on the connection between scales and iteration strategies with the Dodd-Jensen property first discovered in [3]. Let be the pointclass at the beginning of the weak gap referred to in 0.1. In section 1, we use Woodin's ideas to construct a Γ-full a mouse having ω Woodin cardinals cofinal in its ordinals, together with an iteration strategy Σ which condenses well in the sense of [4, Def. 1.13]. In section 2, we construct the desired scale from and Σ.

The Inner Model Hypothesis (IMH) and the Strong Inner Model Hypothesis (SIMH) were introduced in [4]. In this article we establish some upper and lower bounds for their consistency strength.

We repeat the statement of the IMH, as presented in [4]. A sentence in the language of set theory is internally consistent iff it holds in some (not necessarily proper) inner model. The meaning of internal consistency depends on what inner models exist: If we enlarge the universe, it is possible that more statements become internally consistent. The Inner Model Hypothesis asserts that the universe has been maximised with respect to internal consistency:

The Inner Model Hypothesis (IMH): If a statement φ without parameters holds in an inner model of some outer model of V (i.e., in some model compatible with V), then it already holds in some inner model of V.

Equivalently: If φ is internally consistent in some outer model of V then it is already internally consistent in V. This is formalised as follows. Regard V as a countable model of Gödel-Bernays class theory, endowed with countably many sets and classes. Suppose that V* is another such model, with the same ordinals as V. Then V* is an outer model of V (V is an inner model of V*) iff the sets of V* include the sets of V and the classes of V* include the classes of V. V* is compatible with V iff V and V* have a common outer model.

We say that a real X is n-generic relative to a perfect tree T if X is a path through T and for all sets S, there exists a number k such that either X∣k ϵ S or for all a σ ϵ T extending X∣k we have a σ ∉ S. A real X is n-generic relative to some perfect tree if there exists such a T. We first show that for every number n all but countably many reals are n-generic relative to some perfect tree. Second, we show that proving this statement requires ZFC− + “∃ infinitely many iterates of the power set of ω”. Third, we prove that every finite iterate of the hyperjump, , is not 2-generic relative to any perfect tree and for every ordinal α below the least λ such that supβ<λ (βth admissible) = λ, the iterated hyperjump is not 5-generic relative to any perfect tree. Finally, we demonstrate some necessary conditions for reals to be 1-generic relative to some perfect tree.

We define a class of finite state automata acting on transfinite sequences, and use these automata to prove that no singular cardinal can be defined by a monadic second order formula over the ordinals.

In this paper we study the metric spaces that are definable in a polynomially bounded o-minimal structure. We prove that the family of metric spaces definable in a given polynomially bounded o-minimal structure is characterized by the valuation field Λ of the structure. In the last section we prove that the cardinality of this family is that of Λ. In particular these two results answer a conjecture given in [SS] about the countability of the metric types of analytic germs. The proof is a mixture of geometry and model theory.

ℵ0-stable ℵ0-categorical linked quaternionic mappings are studied and are shown to correspond (in some sense) to special groups which are ℵ0-stable, ℵ0-categorical, satisfy AP(3) and have finite 2-symbol length. They are also related to special groups whose isometry relation is a finite union of cosets, which are then considered on their own, as well as their links with pseudofinite, profinite and weakly normal special groups.

In this paper, I will give a new characterisation of the spaces of complete theories of pseudofinite fields and of algebraically closed fields with a generic automorphism (ACFA) in terms of the Vietoris topology on absolute Galois groups of prime fields.

We construct a model with an indecisive precipitous ideal and a model with a precipitous ideal with a non precipitous normal ideal below it. Such kind of examples were previously given by M. Foreman [2] and R. Laver [4] respectively. The present examples differ in two ways: first- they use only a measurable cardinal and second- the ideals are over a cardinal. Also a precipitous ideal without a normal ideal below it is constructed. It is shown in addition that if there is a precipitous ideal over a cardinal κ such that

• after the forcing with its positive sets the cardinality of κ remains above ℵ1

• there is no a normal precipitous ideal then there is 0†.

Global co-stationarity of the ground model from an ℵ2-c.c. forcing which adds a new subset of ℵ1 is internally consistent relative to an ω1-Erdős hyperstrong cardinal and a sufficiently large measurable above.

A truth for λ is a pair 〈Q, ψ〉 so that Q ⊆ Hλ, ψ is a first order formula with one free variable, and there exists B ⊆ Hλ+ such that (Hλ+; ∈, B) ⊨ ψ[Q]. A cardinal λ is , indescribable just in case that for every truth 〈Q, ψ〈 for λ, there exists < λ so that is a cardinal and 〈Q ∩ , ψ) is a truth for . More generally, an interval of cardinals [κ, λ] with κ ≤ λ is indescribable if for every truth 〈Q, ψ〈 for λ, there exists , and π: → Hλ so that is a cardinal, is a truth for , and π is elementary from () into (H; ∈, κ, Q) with id.

We prove that the restriction of the proper forcing axiom to ϲ-linked posets requires a indescribable cardinal in L, and that the restriction of the proper forcing axiom to ϲ+-linked posets, in a proper forcing extension of a fine structural model, requires a indescribable 1-gap [κ, κ+]. These results show that the respective forward directions obtained in Hierarchies of Forcing Axioms I by Neeman and Schimmerling are optimal.

We investigate the structure of the Medvedev lattice as a partial order. We prove that every interval in the lattice is either finite, in which case it is isomorphic to a finite Boolean algebra, or contains an antichain of size . the size of the lattice itself. We also prove that it is consistent with ZFC that the lattice has chains of size . and in fact that these big chains occur in every infinite interval. We also study embeddings of lattices and algebras. We show that large Boolean algebras can be embedded into the Medvedev lattice as upper semilattices, but that a Boolean algebra can be embedded as a lattice only if it is countable. Finally we discuss which of these results hold for the closely related Muchnik lattice.

We say that A ≤LRB if every B-random number is A-random. Intuitively this means that if oracle A can identify some patterns on some real γ, oracle B can also find patterns on γ. In other words, B is at least as good as A for this purpose. We study the structure of the LR degrees globally and locally (i.e., restricted to the computably enumerable degrees) and their relationship with the Turing degrees. Among other results we show that whenever ∝ is not GL2 the LR degree of ∝ bounds degrees (so that, in particular, there exist LR degrees with uncountably many predecessors) and we give sample results which demonstrate how various techniques from the theory of the c.e. degrees can be used to prove results about the c.e. LR degrees.

We show, under the assumption that factoring is hard, that a model of PV exists in which the polynomial hierarchy does not collapse to the linear hierarchy; that a model of exists in which NP is not in the second level of the linear hierarchy; and that a model of exists in which the polynomial hierarchy collapses to the linear hierarchy.

Our methods are model-theoretic. We use the assumption about factoring to get a model in which the weak pigeonhole principle fails in a certain way, and then work with this failure to obtain our results.

As a corollary of one of the proofs, we also show that in the failure of WPHP (for definable relations) implies that the strict version of PH does not collapse to a finite level.

We study the minimal complexity of tilings of a plane with a given tile set. We note that every tile set admits either no tiling or some tiling with Kolmogorov complexity of its (n × n)-squares. We construct tile sets for which this bound is tight: all (n × n)-squares in all tilings have complexity Ω(n). This adds a quantitative angle to classical results on non-recursivity of tilings—that we also develop in terms of Turing degrees of unsolvability.

We prove that there are groups in the constructible universe whose automorphism towers are highly malleable by forcing. This is a consequence of the fact that, under a suitable diamond hypothesis, there are sufficiently many highly rigid non-isomorphic Souslin trees whose isomorphism relation can be precisely controlled by forcing.

§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.

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 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.

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 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.