One of the main results of Gödel [4] and [5] is that, if M is a transitive set such that 〈M, Є 〉 is a model of ZF (Zermelo-Fraenkel set theory) and α is the least ordinal not in M, then 〈Lα, Є 〉 is also a model of ZF.

In this note we shall use the Jensen uniformisation theorem to show that results analogous to the above hold for certain subsystems of ZF. The subsystems we have in mind are those that are formed by restricting the formulas in the separation and replacement axioms to various levels of the Levy hierarchy.

This is all done in §1. In §2 we proceed to establish the exact order relationships which hold among the ordinals of the minimal models of some of the systems discussed in §1. Although the proofs of these latter results will not require any use of the uniformisation theorem, we will find it convenient to use some of the more elementary results and techniques from Jensen's fine-structural theory of L. We thus provide a brief review of the pertinent parts of Jensen's works in §0, where a list of general preliminaries is also furnished.

We remark that some of the techniques which we use in the present paper have been used by us previously in [6] to prove various results about β-models of analysis. Since β-models for analysis are analogous to transitive models for set theory, this is not surprising.

We give resource bounded versions of the Completeness Theorem for propositional and predicate logic. For example, it is well known that every computable consistent propositional theory has a computable complete consistent extension. We show that, when length is measured relative to the binary representation of natural numbers and formulas, every polynomial time decidable propositional theory has an exponential time (EXPTIME) complete consistent extension whereas there is a nondeterministic polynomial time (NP) decidable theory which has no polynomial time complete consistent extension when length is measured relative to the binary representation of natural numbers and formulas. It is well known that a propositional theory is axiomatizable (respectively decidable) if and only if it may be represented as the set of infinite paths through a computable tree (respectively a computable tree with no dead ends). We show that any polynomial time decidable theory may be represented as the set of paths through a polynomial time decidable tree. On the other hand, the statement that every polynomial time decidable tree represents the set of complete consistent extensions of some theory which is polynomial time decidable, relative to the tally representation of natural numbers and formulas, is equivalent to P = NP. For predicate logic, we develop a complexity theoretic version of the Henkin construction to prove a complexity theoretic version of the Completeness Theorem. Our results imply that that any polynomial space decidable theory Δ possesses a polynomial space computable model which is exponential space decidable and thus Δ has an exponential space complete consistent extension. Similar results are obtained for other notions of complexity.

This paper concerns automorphisms of the computably enumerable sets. We prove two results relating semilow sets and prompt degrees via automorphisms, one of which is complementary to a recent result of Downey and Harrington. We also show that the property of effective simplicity is not invariant under automorphism, and that in fact every promptly simple set is automorphic to an effectively simple set. A major technique used in these proofs is a modification of the Harrington-Soare version of the method of Harrington-Soare and Cholak for constructing Δ30 automorphisms; this modification takes advantage of a recent result of Soare on the extension of “restricted” automorphisms to full automorphisms.

In [3] a definition of negation was presented for the system K′ of extended basic logic [1], but it has since been shown by Peter Päppinghaus (personal communication) that this definition fails to give rise to the law of double negation as I claimed it did. The purpose of this note is to revise this defective definition in such a way that it clearly does give rise to the law of double negation, as well as to the other negation rules of K′.

Although Päppinghaus's original letter to me was dated September 19, 1972, the matter has remained unresolved all this time. Only recently have I seen that there is a simple way to correct the definition. I am of course very grateful to Päppinghaus for pointing out my error in claiming to be able to derive the rule of double negation from the original form of the definition.

The corrected definition will, as before, use fixed-point operators to give the effect of the required kind of transfinite induction, but this time a double transfinite induction will be used, somewhat like the double transfinite induction used in [5] to define simultaneously the theorems and antitheorems of system CΓ.

Define to be the smallest cardinality of a function f: X→Y with I, X, Y, ⊆ 2ω such that there is no Borel function g ⊇ f. In this paper we prove that it is relatively consistent with ZFC to have b < where b is, as usual, smallest cardinality of an unbounded family in Ωω. This answers a question raised by Zapletal.

We also show that it is relatively consistent with ZFC that there exists X ⊆ 2ω such that the Borei order of X is bounded but there exists a relatively analytic subset of X which is not relatively coanalytic. This answers a question of Mauldin.

In this note I construct a proper o-minimal expansion of the ordered additive group of rationals.

Let T be an infinite pseudo-tree. In [2], we showed that the cellularity of the pseudo-tree algebra Treealg(T) was the maximum of four cardinals cT, lT, ϕT, and μT: roughly, cT is the “tallness” of T: lT is the “width” of T, ϕ is the number of “points of finite branching” in T: and μ is the number of “sections of no branching” in T. Here we ask: which inequalities among these four cardinals may be satisfied, in some sense, by a pseudo-tree? We show that the possible inequalities among cT, lT, ϕT, and μT attained by pseudo-trees T are closely related to the existence of generalized Suslin trees.