We obtain a large class of significant examples of n-random reals (i.e., Martin-Löf random in oracle ∅(n−1)) à la Chaitin. Any such real is defined as the probability that a universal monotone Turing machine performing possibly infinite computations on infinite (resp. finite large enough, resp. finite self-delimited) inputs produces an output in a given set . In particular, we develop methods to transfer many-one completeness results of index sets to n-randomness of associated probabilities.

The paper is aimed at studying the topological dimension for sets definable in weakly o-minimal structures in order to prepare background for further investigation of groups, group actions and fields definable in the weakly o-minimal context. We prove that the topological dimension of a set definable in a weakly o-minimal structure is invariant under definable injective maps, strengthening an analogous result from [2] for sets and functions definable in models of weakly o-minimal theories. We pay special attention to large subsets of Cartesian products of definable sets, showing that if X, Y and S are non-empty definable sets and S is a large subset of X × Y. then for a large set of tuples , where k = dim(Y), the union of fibers is large in Y. Finally, given a weakly o-minimal structure , we find various conditions equivalent to the fact that the topological dimension in enjoys the addition property.

We investigate the theory IΔ0+Ω1 and strengthen [Bu86, Theorem 8.6] to the following: if NP ≠ co-NP, then Σ-completeness for witness comparison foumulas is not provable in bounded arithmetic. i.e.,

Next we study a “small reflection principle” in bounded arithmetic. We prove that for all sentences φ

The proof hinges on the use of definable cuts and partial satisfaction predicates akin to those introduced by Pudlák in [Pu86].

Finally, we give some applications of the small reflection principle, showing that the principle can sometimes be invoked in order to circumvent the use of provable Σ-completeness for witness comparison formulas.

If κ is a measurable cardinal, then it is a well-known fact that there is at least one normal ultrafilter over κ. In [K-1], Kunen showed that one cannot say more without further assumptions, for if U is a normal ultrafilter over κ, then L[U] is an inner model of ZFC in which κ has exactly one normal measure. On the other hand, Kunen and Paris showed [K-P] that if κ is measurable in the ground model, then there is a forcing extension in which κ has normal ultrafilters, so it is consistent that κ has the maximum possible number of normal ultrafilters. Starting with assumptions stronger than measurability, Mitchell [Mi-1] filled in the gap by constructing models of ZFC + GCH satisfying “there are exactly λ normal ultrafilters over κ”, where λ could be κ+ or κ++ (measured in the model), or anything ≤ κ. Whether or not Mitchell's results can be obtained by starting only with a measurable cardinal in the ground model and defining a forcing extension is unknown.

There are substantial differences between the Mitchell models and the Kunen-Paris models. In the Kunen-Paris models κ can be the only measurable cardinal. However, in the Mitchell model in which κ has exactly 2 normal ultrafilters, one of them contains the set {α < κ: α is measurable} while the other does not. Thus it is natural to ask if it is possible to get a model M of ZFC in which κ is the only measurable cardinal and κ has exactly 2 normal ultrafilters. In this paper we will show that, using appropriate large cardinal assumptions, the answer is yes.

Let Ω be an infinite cardinal larger than ω. By Lω we mean a language with infinitely long expressions having no individual constants, and such that the only predicates are < and =, and the length of ν or ∃ in a formula in Lω is smaller than Ω (cf. §2).

A commutative ring A is said to be algebraically closed if every finite system of polynomial equations and inequations in one or more variables with coefficients in A which has a solution in some (commutative) extension of A already has a solution in A. Abraham Robinson's study of model-theoretic forcing has provided powerful new tools for the study of algebraically closed structures in general, and will be applied here to the study of algebraically closed commutative rings. Familiarity with the model-theoretic notions connected with the study of algebraically closed structures is assumed; for background consult [1], [2], and [3].

Our main results are the following:

1. The theory of commutative rings with identity has no model companion in the sense of Robinson.

2. The Hilbert Nullstellensatz, suitably formulated for the class of algebraically closed commutative rings, holds for finitely generated polynomial ideals but fails for certain infinitely generated polynomial ideals.

3. If A is algebraically closed, then A/rad A need not be algebraically closed as a semiprime ring: If A is finitely generic then A/rad A is algebraically closed as a semiprime ring, but if A is infinitely generic then A/rad A is not algebraically closed as a semiprime ring.

We propose a model-theoretic framework for investigating profinite groups. Within this framework we define and investigate small profinite groups. We consider the question if any small profinite group has an open abelian subgroup.

Let ω be the set of natural numbers, i.e. {0,1,2,…}. A set A (≤ω) is called n-generic if it is Cohen-generic for n-quantifier arithmetic. As characterized by Jockusch [4], this is equivalent to saying that for every set of strings S, there is a σ < A such that σ ∈ S or ∀ν ≥ σ(ν ∉ S). When we say degree, we mean Turing degree (of unsolvability). We call a degree n-generic if it has an n-generic representative. A nonrecursive degree a is called minimal if there is no nonrecursive degree b with b < a. Jockusch [4] exhibited various properties of generic degrees, and he showed that any 2-generic degree bounds no minimal degree. Chong and Jockusch [1] showed that any 1-generic degree below 0′ bounds no minimal degree. Haught [3] refuted one of the conjectures in [1] and showed that if a is a 1-generic degree and 0 < b < a < 0′ then b is also 1-generic. We show here that there is a 1-generic degree which bounds a minimal degree. This gives an affirmative answer to questions in [1] and [4], As any 1-generic degree below 0′ bounds no minimal degree, we see that our 1-generic degree which bounds a minimal degree is not below 0′, but can be constructed recursively in 0″. Furthermore we see that the initial segments below 1-generic degrees are not order isomorphic.

We prove for any μ = μ<μ < θ < λ. λ large enough (just strongly inaccessible Mahlo) the consistency of and even for σ < μ. The new point is that possibly 0 > μ+.

We introduce and study the notions of a PAC-substructure of a stable structure, and a bounded substructure of an arbitrary substructure, generalizing [10]. We give precise definitions and equivalences, saying what it means for properties such as PAC to be first order, study some examples (such as differentially closed fields) in detail, relate the material to generic automorphisms, and generalize a “descent theorem” for pseudo-algebraically closed fields to the stable context. We also point out that the elementary invariants of pseudo-algebraically closed fields from [6] are also valid for pseudo-differentially closed fields.

Our concern is the completeness problem for spi-logics, that is, sets of implications between strictly positive formulas built from propositional variables, conjunction and modal diamond operators. Originated in logic, algebra and computer science, spi-logics have two natural semantics: meet-semilattices with monotone operators providing Birkhoff-style calculi and first-order relational structures (aka Kripke frames) often used as the intended structures in applications. Here we lay foundations for a completeness theory that aims to answer the question whether the two semantics define the same consequence relations for a given spi-logic.

We study universal minimal flows of the homeomorphism groups of generalized Ważewski dendrites WP, $P \subseteq \left\{ {3,4, \ldots ,\omega } \right\}$. If P is finite, we prove that the universal minimal flow of the homeomorphism group H (WP) is metrizable and we compute it explicitly. This answers a question of Duchesne. If P is infinite, we show that the universal minimal flow of H (WP) is not metrizable. This provides examples of topological groups which are Roelcke precompact and have a nonmetrizable universal minimal flow with a comeager orbit.

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.

A stable theory is finitely based if every set of indiscernibles is based on a finite subset. This is a common generalization of superstability and 1-basedness. We show that if such theories have more than one model they must have infinitely many, and prove some other conjectures.

We extend the notion of limitwise monotonic functions to include arbitrary computable domains. We then study which sets and degrees are support increasing (support strictly increasing) limitwise monotonic on various computable domains. As applications, we provide a characterization of the sets S with computable increasing η-representations using support increasing limitwise monotonic sets on ℚ and note relationships between the class of order-computable sets and the class of support increasing (support strictly increasing) limitwise monotonic sets on certain domains.

The notion of CM-triviality was introduced by Hrushovski, who showed that his new strongly minimal sets have this property. Recently Baudisch has shown that his new ω1-categorical group has this property. Here we show that any group of finite Morley rank definable in a CM-trivial theory is nilpotent-by-finite, or equivalently no simple group of finite Morley rank can be definable in a CM-trivial theory.

We study o-minimal expansions of Archimedean totally ordered groups. We first prove that any such expansion must be elementarily embeddable via a unique (provided some nonzero element is 0-definable) elementary embedding into a unique o-minimal expansion of the additive ordered group of real numbers . We then show that a definable function in an o-minimal expansion of enjoys good differentiability properties and use this to prove that an Archimedean real closed field is definable in any nonsemilinear expansion of . Combining these results, we obtain several restrictions on possible o-minimal expansions of arbitrary Archimedean ordered groups and in particular of the rational ordered group.

This paper contributes to the question of under which conditions recursively enumerable sets with isomorphic lattices of recursively enumerable-supersets are automorphic in the lattice of all recursively enumerable sets. We show that hyperhypersimple sets (i.e. sets where the recursively enumerable supersets form a Boolean algebra) are automorphic if there is a -definable isomorphism between their lattices of supersets. Lerman, Shore and Soare have shown that this is not true if one replaces by .

We show that the theory of the local structure of the enumeration degrees is computably isomorphic to the theory of first order arithmetic. We introduce a novel coding method, using the notion of a -pair, to code a large class of countable relations.

In this paper we will present an application of generalized recursion theory to (noncombinatorial) set theory. More precisely we will combine a priority argument in α-recursion theory with a forcing construction to prove a theorem about the interdefinability of certain subsets of admissible ordinals.

Our investigation was prompted by G. Sacks and S. Simpson asking [6] if it is obvious that there are, for each Σn-admissible α, Σn (over L α ) subsets of α which are Δn -incomparable. If one understands “B is Δn in C” to mean that there are Σn /L α reduction procedures which put out B and when one feeds in C, then the answer is an unqualified “yes.” In this sense “Δn in” is a direct generalization of “α-recursive in” (replace Σ1 by Σn in the definition) and so amenable to the methods of [7, §§3, 5]. Indeed one simply chooses a complete Σn−1 set A and mimics the construction of [6] as modified in [7, §5] to produce two α-A-r.e. sets B and C neither of which is α-A-recursive in the other. By the remarks on translation [7, §3] this will immediately give the desired result for this definition of “Δn in.”

There is, however, the more obvious and natural notion of “Δn in” to be considered: B is Δn in C iff there are Σn and Πn formulas of ⟨L α , C⟩ which define B.