The resurrection axioms are forms of forcing axioms that were introduced recently by Hamkins and Johnstone, who developed on earlier ideas of Chalons and Veličković. In this note, we introduce a stronger form of resurrection (which we call unbounded resurrection) and show that it gives rise to families of axioms which are consistent relative to extendible cardinals, and which imply the strongest known instances of forcing axioms, such as Martin’s Maximum++. In addition, we study the unbounded resurrection postulates in terms of consistency lower bounds, obtaining, for example, failures of the weak square principle.

We show that MRP + MA implies that ITP(λ,ω2) holds for all cardinal λ ≥ ω2. This generalizes a result by Weiβ who showed that PFA implies that ITP(λ, ω2) holds for all cardinal λ ≥ ω2. Consequently any of the known methods to prove MRP + MA consistent relative to some large cardinal hypothesis requires the existence of a strongly compact cardinal. Moreover if one wants to force MRP + MA with a proper forcing, it requires at least a supercompact cardinal. We also study the relationship between MRP and some weak versions of square. We show that MRP implies the failure of □(λ, ω) for all λ ≥ ω2 and we give a direct proof that MRP + MA implies the failure of □(λ, ω1) for all λ ≥ ω2.

We investigate the set (ω) of partitions of the natural numbers ordered by ≤* where A ≤* B if by gluing finitely many blocks of A we can get a partition coarser than B. In particular, we determine the values of a number of cardinals which are naturally associated with the structure ((ω), ≥*), in terms of classical cardinal invariants of the continuum.

We settle a question in the literature about degrees of models of true arithmetic and upper bounds for the arithmetic sets. We prove that there is a model of true arithmetic whose degree is not a uniform upper bound for the arithmetic sets. The proof involves two forcing constructions.

We show that the quasi-order of continuous embeddability between finitely branching dendrites (a natural class of fairly simple compacta) is -complete. We also show that embeddability between countable linear orders with infinitely many colors is -complete.

We consider the monadic second-order theory of linear order. For the sake of brevity, linearly ordered sets will be called chains.

Let = ⟨A <⟩ be a chain. A formula ø(t) with one free individual variable t defines a point-set on A which contains the points of A that satisfy ø(t). As usually we identify a subset of A with its characteristic predicate and we will say that such a formula defines a predicate on A.

A formula (X) one free monadic predicate variable defines the set of predicates (or family of point-sets) on A that satisfy (X). This family is said to be definable by (X) in A. Suppose that is a subchain of = ⟨B, <⟩. With a formula (X, A) we associate the following family of point-sets (or set of predicates) {P : P ⊆ A and (P, A) holds in } on A. This family is said to be definable by in with at the background.

Note that in such a definition bound individual (respectively predicate) variables of range over B (respectively over subsets of B). Hence, it is reasonable to expect that the presence of a background chain allows one to define point sets (or families of point-sets) on A which are not definable inside .

Let [NB]1 denote the ideal generated by nonbounding c.e. degrees and NCup the ideal of noncuppable c.e. degrees. We show that both [NB]1 ∩ NCup and the ideal generated by nonbounding and noncuppable degrees are new, in the sense that they are different from M, [NB]1 and NCup—the only three known definable ideals so far.

Exploring further the properties of ITRM-recognizable reals started in [1], we provide a detailed analysis of recognizable reals and their distribution in Gödels constructible universe L. In particular, we show that new unrecognizable reals are generated at every index $\gamma \, \ge \,\omega _\omega ^{CK}$. We give a machine-independent characterization of recognizability by proving that a real r is recognizable if and only if it is ${\Sigma _1}$-definable over ${L_{\omega _\omega ^{CK,\,r}}}$ and that $r\, \in \,{L_{\omega _\omega ^{CK,\,r}}}$ for every recognizable real r and show that either every or no r with $r\, \in \,{L_{\omega _\omega ^{CK,\,r}}}$ generated over an index stage ${L_\gamma }$ is recognizable. Finally, the techniques developed along the way allow us to prove that the halting number for ITRMs is recognizable and that the set of ITRM-computable reals is not ITRM-decidable.

We show that there is a strong connection between Weihrauch reducibility on one hand, and provability in EL0, the intuitionistic version of RCA0, on the other hand. More precisely, we show that Weihrauch reducibility to the composition of finitely many instances of a theorem is captured by provability in EL0 together with Markov’s principle, and that Weihrauch reducibility is captured by an affine subsystem of EL0 plus Markov’s principle.

The class of stable posets is defined and investigated. We give a forcing construction of a universe of set theory which satisfies a weak form of Martin's Axiom and 2ℵ0 > ℵ1 and yet some propositions which follow from CH hold in this universe.

Let A be an infinite set and let K be creative: we show that K ≤QA if and only if KA. (Here ≤Q denotes Q-reducibility, and is the subreducibility of ≤Q obtained by requesting that Q-reducibility be provided by a computable function f such that Wf(x) ∩ Wf(y) = ∅. if x ≠ y.) Using this result we prove that A is hyperhyperimmune if and only if no subset B of A is s-complete, i.e., there is no subset B of A such that ≤sB, where ≤s denotes s-reducibility, and denotes the complement of K.

The theories considered here are countable and complete, and the types are all complete too. Let T be an L-theory. A sequence σ = (σn(ν))n∈ω of L-formulas is said to be independent (with respect to T) if for each α ∈ 2<ω, the sentence

is in T. As an example, let T = Th(Z, +), and let σ be the sequence of formulas saying (in the language of groups) ν is divisible by the nth prime, for n ∈ ω.

A theory T has an independent sequence of formulas just in case it has types. If T has one independent sequence σ, then it has other independent sequences of arbitrarily high degree. (These can be obtained by taking conjunctions of the formulas from σ. If T has an independent sequence that is recursive, or one that is recursive in some type, then T will have types of arbitrarily high degree. (This follows from the fact that the independent sequence can be used to encode any set in a type.)

Nadel and the author had wondered whether a theory with types must have an independent sequence of formulas that is recursive in one of the types. The main result of the present paper is an example of a recursive theory for which this is not the case.

The context for this paper is Feferman's theory of explicit mathematics, a formal framework serving many purposes. It is suitable for representing Bishop-style constructive mathematics as well as generalized recursion, including direct expression of structural concepts which admit self-application. The object of investigation here is the theory of explicit mathematics augmented by the monotone fixed point principle, which asserts that any monotone operation on classifications (Feferman's notion of set) possesses a least fixed point. To be more precise, the new axiom not merely postulates the existence of a least solution, but, by adjoining a new functional constant to the language, it is ensured that a fixed point is uniformly presentable as a function of the monotone operation.

The upshot of the paper is that the latter extension of explicit mathematics (when based on classical logic) embodies considerable proof-theoretic strength. It is shown that it has at least the strength of the subsystem of second order arithmetic based on comprehension.

This is a continuation of two previous papers by the same title [2] and examines mainly the interpolation property for the logic CD with constant domains, i.e., the extension of the intuitionistic predicate logic with the schema

It is known [3], [4] that this logic is complete for the class of all Kripke structures with constant domains.

Theorem 47. The strong Robinson consistency theorem is not true for CD.

Proof. Consider the following Kripke structure with constant domains. The set S of possible worlds is ω0, the set of positive integers. R is the natural ordering ≤. Let ω0 0 = , Bn, is a sequence of pairwise disjoint infinite sets. Let L0 be a language with the unary predicates P, P1 and consider the following extensions for P,P1 at the world m.

(a) P is true on ⋃i≤2nBi, and P1 is true on ⋃i≤2n+1Bi for m = 2n.

(b) P is true on ⋃i≤2nBi, and P1 for ⋃i≤2n+1Bi for m = 2n.

Let (Δ,Θ) be the complete theory of this structure. Consider another unary predicate Q. Let L be the language with P, Q and let M be the language with P1, Q.

Let ($\rm L$;C) be the (up to isomorphism unique) countable homogeneous structure carrying a binary branching C-relation. We study the reducts of ($\rm L$;C), i.e., the structures with domain $\rm L$ that are first-order definable in ($\rm L$;C). We show that up to existential interdefinability, there are finitely many such reducts. This implies that there are finitely many reducts up to first-order interdefinability, thus confirming a conjecture of Simon Thomas for the special case of ($\rm L$;C). We also study the endomorphism monoids of such reducts and show that they fall into four categories.

We say that a system S of sentential calculus is an extension of a system R, if R and S have the same class of (meaningful) sentences, and every provable sentence of R is also provable in S. If the two classes of provable sentences do not coincide, we call S a proper extension of R.

By a complete system of sentential calculus is meant one which is itself consistent, but has no consistent proper extensions. Thus one cannot add a new independent primitive sentence to a complete system without obtaining an inconsistent system. The usual two-valued sentential calculus is complete in the sense defined.

It has been shown by Lindenbaum that every incomplete system of sentential calculus possesses at least one complete extension. In this paper we shall examine how many complete extensions there are of some of the Lewis systems of sentential calculus. We shall show that there is only one complete extension of S4 (and hence also of S5, which is an extension of S4), and that there are infinitely many complete extensions of S2 (and hence also of S1, since S2 is an extension of S1). We leave open the question how many complete extensions there are of S3.

One general program of α-recursion theory is to determine as much as possible of the lattice structure of (α), the lattice of α-r.e. sets under inclusion. It is hoped that structure results will shed some light on whether or not the theory of (α) is decidable with respect to a suitable language for lattice theory. Fix such a language ℒ.

Many of the basic results about the lattice structure involve various sorts of simple α-r.e. sets (we use definitions which are definable in ℒ over (α)). It is easy to see that simple sets exist for all admissible α. Chong and Lerman [1] have found some necessary and some sufficient conditions for the existence of hhsimple α-r.e. sets, although a complete determination of these conditions has not yet been made. Lerman and Simpson [9] have obtained some partial results concerning r-maximal α-r.e. sets. Lerman [6] has shown that maximal α-r.e. sets exist iff a is a certain sort of constructibly countable ordinal. Lerman [5] has also investigated the congruence relations, filters, and ideals of (α). Here various sorts of simple sets have also proved to be vital tools. The importance of simple α-r.e. sets to the study of the lattice structure of (α) is hence obvious.

Lerman [6, Q22] has posed the following problem: Find an admissible α for which all simple α-r.e. sets have the same 1-type with respect to the language ℒ. The structure of (α) for such an α would be much less complicated than that of (ω). Lerman [7] showed that such an α could not be a regular cardinal of L. We show that there is no such admissible α.

We show that if d ∈ GH1 then (≤ d) has the complementation property, i.e., for all a < d there is some b < d such that a ∧ b = 0 and a ∨ b = d.

If Σ is the class of all fields and Σ* is the class of all algebraically closed fields, then it is well known that Σ* is characterized by the following properties:

(i) Σ* is the class of models of some first order theory K*.

(ii) If m1m2 are in Σ* and m1 ⊆ m2 then m1 ≺ m2 (m1 is an elementary substructure of m2, i.e. any first order sentence true in m1 is true in m2).

(iii) If m1 is in Σ then there is a structure m2 in Σ* such that m1 ⊆ m2.

If Σ is some other class of models of a first order theory K and a subclass Σ* of Σ exists satisfying (i)–(iii) then Σ* is uniquely determined and K* (which is unique up to logical equivalence) is called the model-companion of K. This notion is a generalization of the fundamental notion of model-completion introduced and extensively studied by A. Robinson [6], When the model-companion exists it provides the basis for a satisfactory treatment of the notion of an algebraically closed model of K.

Recently A. Robinson has developed a more general formulation of the notion of “algebraically closed” structures in Σ, which is applicable to any inductive elementary class Σ of structures (by elementary we always mean ECΔ). Condition (i) must be weakened to

(i′) Σ* is closed under elementary substructure (i.e. if m1 is in Σ* and m2 ≺ m1 then m2 is in Σ*).

Let ω be the nonnegative integers. G. E. Sacks once asked whether there exists an infinite X ⊆ ω such that, for all Y ⊆ X, ω1Yω1 where ω1 is the first nonrecursive ordinal. In this note we negatively answer this question by giving a simple proof that for every infinite set X ⊆ ω there exists Y ⊆ X such that the first recursively inaccessible ordinal. This is accomplished by proving that Hα is hyper-arithmetic in Y whereHα is the αth hyperjump of the empty set ∅, defined in a suitable sense for all ordinals

Background information and undefined notation can be found in Rogers [11]. In particular, we write A ≤hB(A ≤T B) if A is hyperarithmetical (recursive) in B, and A ≡hB if A ≤hB and B ≤hA. We will say that a set A is hyperarithmetically (recursively) encodable if, for every infinite set X ⊆ ω, there exists Y ⊆ X such that A ≤hY (A ≤TY). For any set A (hyperdegree a) let A′ (a′) denote the hyperjump of A (a). Let 0 denote the hyperdegree of ∅. A function f majorizes a function g if f(n) ≥ g(n) for every n. E1 is the representing (type-2) functional of

introduced by Tugué [13] (also Kleene [6]). Let be the smallest ordinal which is not the order type of any well-ordering recursive in E1. Information on can be found in Richter [9] and [10].