We introduce a very weak language on p-adic fields K, which is just rich enough to have exactly the same definable subsets of the line K that one has using the ring language. (In our context, definable always means definable with parameters.) We prove that the only definable functions in the language are trivial functions. We also give a definitional expansion of in which K has quantifier elimination, and we obtain a cell decomposition result for -definable sets.

Our language can serve as a p-adic analogue of the very weak language (<) on the real numbers, to define a notion of minimality on the field of p-adic numbers and on related valued fields. These fields are not necessarily Henselian and may have positive characteristic.

Algorithmic randomness was originally defined for Cantor space with the fair-coin measure. Recent work has examined algorithmic randomness in new contexts, in particular closed subsets of 2ɷ ([2] and [8]). In this paper we use the probability theory of closed set-valued random variables (RACS) to extend the definition of Martin-Löf randomness to spaces of closed subsets of locally compact, Hausdorff, second countable topological spaces. This allows for the study of Martin-Löf randomness in many new spaces, but also gives a new perspective on Martin-Löf randomness for 2ɷ and on the algorithmically random closed sets of [2] and [8]. The first half of this paper is devoted to developing the machinery of Martin-Löf randomness for general spaces of closed sets. We then prove some general results and move on to show how the algorithmically random closed sets of [2] and [8] fit into this new framework.

In this paper we show that there is a pair of superhigh r.e. degree that forms a minimal pair. An analysis of the proof shows that a critical ingredient is the growth rates of certain order functions. This leads us to investigate certain high r.e. degrees, which resemble ∅′ very closely in terms of ∅′-jump traceability. In particular, we will construct an ultrahigh degree which is cappable.

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.

In his paper [3] Hindley shows that strong reduction in combinatory logic (see [1] for the basic discussion of this notion) cannot be axiomatized with a finite number of axiom schemes, and then he presents an infinite system of axiom schemes for strong reduction. Hindley lists one axiom and six axiom schemes, together with a method (clause (viii) below) for generating further axiom schemes from these. The results of this note are that different applications of clause (viii) yield different axiom schemes, and that the property of being an axiom is decidable.

The first-order theory of a string automatic structure is known to be decidable, but there are examples of string automatic structures with nonelementary first-order theories. We prove that the first-order theory of a string automatic structure of bounded degree is decidable in doubly exponential space (for injective automatic presentations, this holds even uniformly). This result is shown to be optimal since we also present a string automatic structure of bounded degree whose first-order theory is hard for 2EXPSPACE. We prove similar results also for tree automatic structures. These findings close the gaps left open in [28] by improving both the lower and the upper bounds.

We prove that RCA0 + RRT ⊬ ACA0 where RRT is the Rainbow Ramsey Theorem for 2-bounded colorings of triples. This reverse mathematical result is based on a cone avoidance theorem, that every 2-bounded coloring of pairs admits a cone-avoiding infinite rainbow, regardless of the complexity of the given coloring. We also apply the proof of the cone avoidance theorem to the question whether RCA0 + RRT ⊦ ACA0 and obtain some partial answer.

We define a class of productiveσ-ideals of subsets of the Cantor space 2ω and observe that both σ-ideals of meagre sets and of null sets are in this class. From every productive σ-ideal we produce a σ-ideal of subsets of the generalized Cantor space 2κ. In particular, starting from meagre sets and null sets in 2ω we obtain meagre sets and null sets in 2ω, respectively. Then we investigate additivity, covering number, uniformity and cofinality of . For example, we show that

Our results generalizes those from [5].

Extending Gödel's Dialectica interpretation, we provide a functional interpretation of classical theories of positive arithmetic inductive definitions, reducing them to theories of finite-type functionals defined using transfinite recursion on well-founded trees.

In contrast with the notion of complexity, a set A is called anti-complex if the Kolmogorov complexity of the initial segments of A chosen by a recursive function is always bounded by the identity function. We show that, as for complexity, the natural arena for examining anti-complexity is the weak-truth table degrees. In this context, we show the equivalence of anti-complexity and other lowness notions such as r.e. traceability or being weak truth-table reducible to a Schnorr trivial set. A set A is anti-complex if and only if it is reducible to another set B with tiny use, whereby we mean that the use function for reducing A to B can be made to grow arbitrarily slowly, as gauged by unbounded nondecreasing recursive functions. This notion of reducibility is then studied in its own right, and we also investigate its range and the range of its uniform counterpart.

In this note we shall assume acquaintance with [T4] and the parts of [T1] which deal with intuitionistic arithmetic in all finite types. The bibliography just continues the bibliography of [T4].

The principal purpose of this note is the discussion of two models for intuitionistic finite type arithmetic with fan functional (HAω + MUC). The first model is needed to correct an oversight in the proof of Theorem 6 [T4, §5]: the model ECF+ as defined there cannot be shown to have the required properties in EL + QF-AC, the reason being that a change in the definition of W12 alone does not suffice—if one wishes to establish closure under the operations of HAω the definitions of W1σ for other σ have to be adopted as well. It is difficult to see how to do this directly in a uniform way — but we succeed via a detour, which is described in §2.

For a proper understanding, we should perhaps note already here that on the assumption of the fan theorem, ECF+ as defined in [T4] and the new model of this note coincide (since then the definition of W12 [T4, p. 594] is equivalent to the definition for W12 in the case of ECF); but in EL it is impossible to prove this (and under assumption of Church's thesis the two models differ).

We answer in the affirmative the following question of Jörg Brendle: If there is a Σ21 mad family, is there then a Π11 mad family?

We show that Blackwell determinacy in L(ℝ) implies determinacy in L(ℝ).

We introduce a natural generalization of Borel's Conjecture. For each infinite cardinal number κ, let BCκ denote this generalization. Then BCℕ0 is equivalent to the classical Borel conjecture. Assuming the classical Borel conjecture, ¬BCℕ1 is equivalent to the existence of a Kurepa tree of height ℕ1. Using the connection of BCκ with a generalization of Kurepa's Hypothesis, we obtain the following consistency results:

(1) If it is consistent that there is a 1-inaccessible cardinal then it is consistent that BCℕ1.

(2) If it is consistent that BCℕ1, then it is consistent that there is an inaccessible cardinal.

(3) If it is consistent that there is a 1-inaccessible cardinal with ω inaccessible cardinals above it, then ¬BCℕω + (∀n < ω)BCℕn is consistent.

(4) If it is consistent that there is a 2-huge cardinal, then it is consistent that BCℕω

(5) If it is consistent that there is a 3-huge cardinal, then it is consistent that BCκ for a proper class of cardinals κ of countable cofinality.

Adjoin, to a countable standard model M of Zermelo-Fraenkel set theory (ZF), a countable set A of independent Cohen generic reals. If one attempts to construct the model generated over M by these reals (not necessarily containing A as an element) as the intersection of all standard models that include M ∪ A, the resulting model fails to satisfy the power set axiom, although it does satisfy all the other ZF axioms. Thus, there is no smallest ZF model including M ∪ A, but there are minimal such models. These are classified by their sets of reals, and there is one minimal model whose set of reals is the smallest possible. We give several characterizations of this model, we determine which weak axioms of choice it satisfies, and we show that some better known models are forcing extensions of it.

J. D. Monk has shown that for first order languages with finitely many variables there is no finite set of schema which axiomatizes the universally valid formulas. There are such finite sets of schema which axiomatize the formulas valid in all structures of some fixed finite size.

The first minimal degree construction is due to Spector [7]. To this Sacks [5] has added the priority method of Friedberg [1] and Muchnik [4] to obtain a minimal degree less than 0′. Sacks' methods have been modified in several directions to obtain minimal degrees satisfying various incomparability conditions.

In this paper we investigate the relationship between the number of countable and decidable models of a complete theory. The number of decidable models will be determined in two ways, in §1 with respect to abstract isomorphism type, and in §2 with respect to recursive isomorphism type.

Definition 1. A complete theory is (α, β) if the number of countable models of T, up to abstract isomorphism, is β, and similarly the number of decidable models of T is α.

Definition 2. A model is ω-decidable if ∣∣= ω and for an effective listing {θn∣n < ω} of all sentences in the language of Th() augmented by new constant symbols i*, i < ω, {n ∣〈, i〉i<ω ⊨ θn} is recursive, where i interprets i* (in these terms, is decidable if is abstractly isomorphic to an ω-decidable model).

Definition 3. A complete theory is (α, β)r if it is (γ, β) for some γ and it has exactly αω-decidable models up to recursive isomorphism.

Specifically we will show in §1 that there is a (2, ω) theory, and in §2 that although there is a (2, 2ω) theory, there is no (2, β)r theory for any β, β < 2ω.

Ellerman, Comer, and Macintyre have all observed that sheaves are an interesting generalization of models and are deserving of model theoretic attention. Scott has pointed out that sheaves are Heyting algebra valued models. The reverse does not hold however since almost no genuine Boolean valued model is a sheaf.

In §1 we shall review the definition of a sheaf and prove a theorem about Boolean valued models using the sheaf construction. In §2 we shall be concerned with the set of sentences preserved by global sections. Our principal result is that global section sentences are also normal submodel sentences. (We define as a normal submodel of if is a submodel of and every point of B − A can be moved by an automorphism of which fixes each point of A.) In §3 we prove that every normal submodel sentence is the negation of a disjunction of Horn sentences and that the set of normal submodel sentences is r.e. but not recursive. §3 involves only traditional model theory and can be read independently of the first two sections.