Assuming that 0# exists, we prove that there is a structure that can effectively interpret its own jump. In particular, we get a structure such that

where is the set of Turing degrees which compute a copy of

More interesting than the result itself is its unexpected complexity. We prove that higher-order arithmetic, which is the union of full “nth-order arithmetic for all n, cannot prove the existence of such a structure.

Restricted to first-order formulas, the rules of inference in the Curry-Howard type theory are equivalent to those of first-order predicate logic as formalized by Heyting, with one exception: ∃-elimination in the Curry-Howard theory, where ∃x: A,F(x) is understood as disjoint union, are the projections, and these do not preserve first-orderedness. This note shows, however, that the Curry-Howard theory is conservative over Heyting's system.

The following problem is studied: How large and how small can the Löwenheim and Hanf numbers of unbounded logics be in relation to the most common large cardinals? The main result is that the Löwenheim number of the logic with the Härtig-quantifier can be consistently put in between any two of the first weakly inaccessible, the first weakly Mahlo, the first weakly compact, the first Ramsey, the first measurable and the first supercompact cardinals.

We show that Mitchell order on downward closed extenders below rank-to-rank type is wellfounded.

Natural deduction systems with indefinite and definite descriptions (ε-terms and ι-terms) are presented, and interpreted in Martin-LÖf's intensional type theory. The interpretations are formalizations of ideas which are implicit in the literature of constructive mathematics: if we have proved that an element with a certain property exists, we speak of ‘the element such that the property holds’ and refer by that phrase to the element constructed in the existence proof. In particular, we deviate from the practice of interpreting descriptions by contextual definitions.

We show that the class of ${\cal L}$-constructible functions is closed under integration for any P-minimal expansion of a p-adic field $\left( {K,{\cal L}} \right)$. This generalizes results previously known for semi-algebraic and subanalytic structures. As part of the proof, we obtain a weak version of cell decomposition and function preparation for P-minimal structures, a result which is independent of the existence of Skolem functions. A direct corollary is that Denef’s results on the rationality of Poincaré series hold in any P-minimal expansion of a p-adic field $\left( {K,{\cal L}} \right)$.

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.

The Gödel Class is the class of prenex formulas of pure quantification theory whose prefixes have the form ∀y1∀y2∃x1 … ∃xn. The Gödel Class with Identity, or GCI, is the corresponding class of formulas of quantification theory extended by inclusion of the identity-sign “ = ”. Although the Gödel Class has long been kndwn to be solvable, the decision problem for the Gödel Class with Identity is open. In this paper we prove that there is no primitive recursive decision procedure for the GCI, or, indeed, for the subclass of the GCI containing just those formulas with prefixes ∀y1∀y2∃x.

Throughout this paper we take quantification theory to include, aside from logical signs, infinitely many k-place predicate letters for each k > 0, but no function signs or constants. Moreover, by “prenex formula” we include only those without free variables. A decision procedure for a class of formulas is a recursive function that carries a formula in the class to 0 if the formula is satisfiable and to 1 if not. A class is solvable iff there exists a decision procedure for it. A class is finitely controllable iff every satisfiable formula in the class has a finite model. Since we speak only of effectively specified classes, finite controllability implies solvability (but not conversely).

The GCI has a curious history. Gödel showed the Gödel Class (without identity) solvable in 1932 [4] and finitely controllable in 1933 [5].

We study inversions of the jump operator on classes, combined with certain basis theorems. These jump inversions have implications for the study of the jump operator on the random degrees—for various notions of randomness. For example, we characterize the jumps of the weakly 2-random sets which are not 2-random, and the jumps of the weakly 1-random relative to 0′ sets which are not 2-random. Both of the classes coincide with the degrees above 0′ which are not 0′-dominated. A further application is the complete solution of [24, Problem 3.6.9]: one direction of van Lambalgen's theorem holds for weak 2-randomness, while the other fails.

Finally we discuss various techniques for coding information into incomplete randoms. Using these techniques we give a negative answer to [24, Problem 8.2.14]: not all weakly 2-random sets are array computable. In fact, given any oracle X, there is a weakly 2-random which is not array computable relative to X. This contrasts with the fact that all 2-random sets are array computable.

In this paper we discuss cylindric algebras with terms. The setting is two—sorted algebras—one sort for terms and one for Boolean elements. As with cylindric algebras, a cylindric algebra with terms has its roots in first order predicate logic [HMT1].

Let Σ be a set of sentences in a first order language with terms, equality and variables u0,u1,u2, …, Define a relation ≡Σ on Fm, the set of formulas, by φ ≡Σθ if and only if Σ ⊢ φ ↔ θ, and on Tm, the set of terms, by τ ≡Σσ if and only if Σ ⊢ τ ≈ σ. The operations +, ·, cκ, 0, 1 are defined as usual on equivalence classes. Define , where is σ with τ substituted for all occurrences of uκ. That the operation *κ, for κ < α, is well defined follows from the first order axioms of equality. Let vκ = [uκ]. To establish the link between terms and Booleans, define operations oκ as follows: , where φ' is a variant of φ such that uκ is free for τ in φ′ and is φ′ with τ substituted for all free occurrences of uκ in φ′. From the first order axioms it follows that oκ, for κ < α, is well defined. Finally, instead of diagonal elements, we define a Boolean-valued operation on terms as follows: [τ] e [σ] = [τ ≈ σ].

The incompleteness of ZF set theory leads one to look for natural extensions of ZF in which one can prove statements independent of ZF which appear to be “true”. One approach has been to add large cardinal axioms. Or, one can investigate second-order expansions like Kelley-Morse class theory, KM. In this paper we look at a set theory ZF(aa), with an added quantifier aa which ranges over ordinals. The “aa” stands for “almost all”, and although we will consider interpretations in terms of the closed unbounded filter on a regular cardinal κ, we will consider other interpretations also.

We start in §1 by giving the axioms for the theory ZF(aa) and presenting a completeness theorem which gives a model-theoretic definition of ZF(aa). In §2 we investigate set theory with a satisfaction predicate and interpret it in a fragment of ZF(aa). In §3 we generalize the methods of §2 to obtain a hierarchy of satisfaction predicates. We use these predicates to prove reflection theorems, as well as to prove the consistency of certain fragments of ZF(aa). Next, in §4 we discuss expandability of models of ZF to models of fragments of ZF(aa) and of Kelley-Morse. We conclude in §5 with a discussion of an extension ZF(aa) + DET of ZF(aa) in which the quantifier aa is self-dual.

It is a well-known fact that the notion of an archimedean order cannot be formalized in the first-order calculus. In [12] and [18], A. Robinson and E. Zakon characterized the elementary class generated by all the archimedean, totally-ordered abelian groups (o-groups) in the language 〈+,<〉, calling it the class of regularly ordered or generalized archimedean abelian groups. Since difference (−) and 0 are definable in that language, it is immediate that in the expanded language 〈 +, −, 0, < 〉 the definable expansion of the class of regular groups is also the elementary class generated by the archimedean ones. In the more general context of lattice-ordered groups (l-groups), the notion of being archimedean splits into two different notions: a strong one (being hyperarchimedean) and a weak one (being archimedean). Using the representation theorem of K. Keimel for hyperarchimedean l-groups, we extend in this paper the Robinson and Zakon characterization to the elementary class generated by the prime-projectable, hyperarchimedean l-groups. This characterization is also extended here to the elementary class generated by the prime-projectable and projectable archimedean l-groups (including all complete l-groups). Finally, transferring a result of A. Touraille on the model theory of Boolean algebras with distinguished ideals, we give the classification up to elementary equivalence of the characterized class.

We recall that a lattice-ordered group, l-group for short, is a structure

In [1] the notions of strongly minimal formula and algebraic closure were applied to the study of ℵ1-categorical theories. In this paper we study a particularly simple class of ℵ1-categorical theories. We characterize this class in terms of the analysis of the Stone space of models of T given by Morley [3].

We assume familiarity with [1] and [3], but for convenience we list the principal results and definitions from those papers which are used here. Our notation is the same as in [1] with the following exceptions.

We deal with a countable first order language L. We may extend the language L in several ways. If is an L-structure, there is a natural extension of L obtained by adjoining to L a constant a for each (the universe of ). For each sentence A(a1, …, an) ∈ L(A) we say satisfies A(a1, …, an) and write if in Shoenfield's notation If is an L-structure and X is a subset of , then L(X) is the language obtained by adjoining to L a name x for each is the natural expansion of to an L(X)-structure. A structure is an inessential expansion [4, p. 141] of an L-structure if for some .

We calculate the Cantor-Bendixson rank of the Ziegler spectrum over a commutative valuation domain R proving that it is equal to the double Krull dimension of R.

We deal with ontological problems concerning basic systems of explicit mathematics, as formalized in Jäger's language of types and names. We prove a generalized inseparability lemma, which implies a form of Rice's theorem for types and a refutation of the strong power type axiom POW+. Next, we show that POW+ can already be refuted on the basis of a weak uniform comprehension without complementation, and we present suitable optimal refinements of the remaining results within the weaker theory.

We prove that a stable solvable group G which satisfies xn = 1 generically is of finite exponent dividing some power of n. Furthermore, G is nilpotent-by-finile.

A second result is that in a stable group of finite exponent, involutions either have big centralisers, or invert a subgroup of finite index (which hence has to be abelian).

This paper belongs to cylindric-algebraic model theory understood in the sense of algebraic logic. We show the existence of isomorphic but not lower base-isomorphic cylindric set algebras. These algebras are regular and locally finite. This solves a problem raised in [N 83] which was implicitly present also in [HMTAN 81]. This result implies that a theorem of Vaught for prime models of countable languages does not continue to hold for languages of any greater power.