Fitting, in [1] and [2], investigated two families of many-valued modal logics. The first, which is somewhat familiar in the literature, is that of the logics characterized using a many-valued version of the Kripke model (binary modal model in his terminology) with a two-valued accessibility relation. On the other hand, those logics which are characterized using another many-valued version of the Kripke model (implicational modal model), with a many-valued accessibility relation, form the second family. Although he gave a sequent calculus for each of these logics, it is far from having the cut-elimination property (CEP) or the subformula property. So we will give a substitute for his system enjoying the subformula property, though it is not of ordinary sequent calculus but of the many-valued version of sequent calculus initiated by Takahashi [7] and Rousseau [3].

The author, unaware of the deduction systems with CEP, had given in [8] and [9], after Rousseau [4], the deduction systems for the intuitionistic many-valued logics which enjoy CEP only for a certain restricted class of proofs. Then in [10], he gave for three-valued modal logics the ones with CEP, but these systems have a rule of inference which is unnecessary if the Cut rule is present. Why are we particular about CEP? The author's answer is that a cut-free proof is easy to examine since it is composed solely of subformulas of the formulas which form its conclusion. In this direction, the author has given, for modal logics with the Brouwerian axiom [11], the ones without CEP which nevertheless enjoy the subformula property. This paper is a sequel to the study in [11].

This paper deals with a fundamental problem in the theory of recursion on initial segments of the ordinal numbers which was originated by Kripke [4] and Platek [8]. Following Kreisel-Sacks [3], we define a notion of relative recursiveness for this abstract recursion theory which allows us to speak of a function ƒ being weakly recursive in a set A via a partial recursive function g; this makes it reasonable to speak of partial recursive functions as ‘reduction procedures’. We say that a reduction procedure g is intrinsically consistent if for any set A there is a partial function ƒ which is weakly recursive in A via g. It is an elementary result of ordinary recursion theory that an arbitrary reduction procedure can be replaced in a uniform manner by an intrinsically consistent reduction procedure without the loss of any function f being reducible to any set A. In §3 we show that for recursion theory on the ordinals less than any infinite cardinal the analogous result is consistent with the axioms of set theory. In §5 we show that for all other cases of abstract recursion theory the analogous result fails in a very strong way to be true.

In [1], Sacks points out that there is one fundamental question: which true statements of ordinary recursion theory remain true when appropriately extended to metarecursion theory?

A particular interest is taken in the question [1]:

Q6. How does one define the jump operator for metarecursion theory? (A satisfactory definition should have the property that if A is metarecursive in B, then the jump of A is metarecursive in the jump of B.)

In [2], Kreisel and Sacks give some definitions of predicates and functions analogous to those of Kleene as follows:

The T-predicate of [2] is analogous to that of Kleene [3]. Its definition is

where e is the Gödel number of a finite system of equations E and t(e, s) is a special metarecursive function which indexes “deductions” from E.

U(e, s) is a metarecursive function such that if t(e, s) = 〈e, M, N, x, y〉, then U(e,s) = y.

Two partial functions {e} s and {e} are

Then e is intrinsically consistent if for all x, s 1 and s 2, if t(e, S 1) = 〈e, M 1 N 1, x, y 1〉, t(e, s 2) = 〈e, M 2, N 2, x, y 2〉 and (M 1 ∪ M 2) ∩ (N 1 ∪ N 2) = ∅, then y 1 = y 2.

We use the notions of effective dimension and Kolmogorov complexity to describe a geometry on the set of infinite binary sequences. Geometric concepts that we define and use include angle, projections and scalar multiplication. A question related to compressibility is addressed using these ideas.

The present note offers a short argument for the descent theorems of Zawadowski [10] (originally [9]) and Makkai [6], which were conjectured by Pitts after the descent theorem of Joyal and Tierney [3] for open geometric morphisms of (Grothendieck) toposes. The original proofs, which involve variants of Makkai's [5] duality for first order logic, are rather involved and there has been considerable interest in locating simpler proofs. Viewed categorically, the descent theorems establish a bicategorical exactness property (conservative morphisms are effective descent) for pretop (the 2-category of small pretoposes, pretopos functors, and natural transformations), for exact (exact categories, exact functors, and natural transformations), and for bpretop* (Boolean pretoposes, pretopos functors, and natural isomorphisms). Viewed logically, they fragment into a familiar Beth/Tarski-type definability theorem and a covering theorem for certain functors on PCΔ-categories (groupoids, in the Boolean case); the latter (as the former) is a arithmetical statement about the syntax of first order logic ([6, §3])).

The argument here involves special models and, independently, a continuity lemma of Makkai. The use of special models is axiomatic in that only a few properties (listed below) are needed. The continuity lemma, 9.1 of [6], is established via forcing and can be read independently of the rest of that paper. Because of its interest to both the model theorist and the category theorist, the argument is first given as straight model theory and afterwards it is briefly indicated how the descent theorems follow.

Peano's five axioms for the sequence of natural numbers run as follows: (1) 1 is a number, (2) Any number α has a unique sequent a′ (3) Different numbers have different sequents, (4) 1 is not a sequent, and (5) The principle of mathematical induction.

Now, in a system of axioms, it seems desirable, in the first place, to avoid symbols for particular individuals and symbols for functions, and, secondly, to secure the property of complete independence. In fact, Peano's system can be replaced by an equivalent one which fulfills both requirements. In such a system, the symbol “1” and the function “sequent” will not appear, although they may be introduced afresh through definitions. Besides, the principle of mathematical induction will no more play the rôle of an axiom, because, under the second requirement, it can hardly be stated in a simple and elegant form.

We show there are intermediate P-minimal structures between the semialgebraic and subanalytic languages which do not have definable Skolem functions. As a consequence, by a result of Mourgues, this shows there are P-minimal structures which do not admit classical cell decomposition.

We present a much-shortened proof of a major result (originally due to Vorob’ev) about intuitionistic propositional logic: in essence, a correction of our 1992 article, avoiding several unnecessary definitions.

A recent result of J.P. Burgess [1] states:

Theorem 0. Let F be a multifunction from an analytic subset T of a Polish space to a Polish space X. If F is Borel measurable, Graph(F) is coanalytic in T × X and F(t) is nonmeager in its closure for each t Є T, then F admits a Borel measurable selector.

The above result unifies and significantly extends earlier results of H. Sarbadhikari [8], S.M. Srivastava [9] and G. Debs (unpublished). The reader is referred to [1] for details.

The aim of this article is to give an effective version of Theorem 0. We do this by proving a basis theorem for Π11 sets which are nonmeager in their closure and satisfy a local version of the measurability condition in Theorem 0. Our basis theorem generalizes a well-known result of P.G. Hinman [4] and S.K. Thomason [10] (see also [5] and [7, 4F.20]). Our methods are similar to those used by A. Louveau to prove that a , σ-compact set is contained in a , σ-compact set (see [7, 4F.18]).

The paper is organized as follows. §2 is devoted to preliminaries. In §3, we prove the basis theorem and deduce as a consequence an effective version of Theorem 0. We show in §4 how our methods can be used to give alternative proofs of some known results.

Discussions with R. Barua, B.V. Rao and V.V. Srivatsa are gratefully acknowledged. I am indebted to J.P. Burgess for drawing my attention to an error in an earlier draft of this paper.

We show that the set of natural numbers has an exponential diophantine definition in the rationals. It follows that the corresponding decision problem is undecidable.

We show that there is a structure of countably infinite signature with P = N2P and a structure of finite signature with P = N1P and N1P ≠ N2P. We give a further example of a structure of finite signature with P ≠ N1P and N1P ≠ N1P. Together with a result from [10] this implies that for each possibility of P versus NP over structures there is an example of countably infinite signature. Then we show that for some finite the class of -structures with P = N1P is not closed under ultraproducts and obtain as corollaries that this class is not ∆-elementary and that the class of -structures with P ≠ N1P is not elementary. Finally we prove that for all ƒ dominating all polynomials there is a structure of finite signature with the following properties: P ≠ N1P, N1P ≠ N2P, the levels N2TIME(ni) of N2P and the levels N1TIME(ni) of N1P are different for different i, indeed DTIME(ni′) ⊈ N2TIME(ni) if i ′ > i; DTIME(ƒ) ⊈ N2P, and N2P ⊈ DEC. DEC is the class of recognizable sets with recognizable complements. So this is an example where the internal structure of N2P is analyzed in a more detailed way. In our proofs we use methods in the style of classical computability theory to construct structures except for one use of ultraproducts.

The notion of quasi-minimal structures was denned by B. Zil'ber as a natural generalization of minimal structures. Inspired by his work, we study here basic model theoretic properties of quasi-minimal structures. Main result is the construction of ω-saturated quasi-minimal models under ω-stability assumption.

We investigate some versions of amoeba for tree-forcings in the generalized Cantor and Baire spaces. This answers [10, Question 3.20] and generalizes a line of research that in the standard case has been studied in [11], [13], and [7]. Moreover, we also answer questions posed in [3] by Friedman, Khomskii, and Kulikov, about the relationships between regularity properties at uncountable cardinals. We show ${\bf{\Sigma }}_1^1$-counterexamples to some regularity properties related to trees without club splitting. In particular we prove a strong relationship between the Ramsey and the Baire properties, in slight contrast with the standard case.

There is a distinction within the natural language between those singular terms which designate and those which do not. On the basis of this distinction there arise irregularities both in the assignment to expressions of semantical properties and relations and in the presumed attribution of existence to individuals. Although such irregularities are characteristic of the employment of singular terms, they are not reproduced either for or within the usual formalized languages. Accordingly, we construct a formalized language for which the mentioned irregularities are reproduced — hence, a language which in this respect mirrors more faithfully than is customary the structure of the natural language.

Professor Prior (Formal logic (1955), pp. 305–307) gives alternative postulate sets for Lewis's S5, one substantially Lewis's own set (p. 305, 6.1) and another, considerably simpler, due to Prior himself (pp. 306–307, 6.5). This note aims at showing that the systems based on these two postulate sets are in fact equivalent. We label the system based on Lewis's postulates ‘S5’, as usual, and that on Prior's postulates ‘P’.

The form of the postulate set for P considered here is as follows. We add to the full propositional calculus one definition:

Df. M: M = NLN;

and two special rules:

L1: ⊦Cαβ → ⊦CLαβ;

L2: ⊦Cαβ → ⊦CαLβ, if α is fully modalized (a propositional formula is fully modalized, if and only if all occurrences of propositional variables in it lie within the scope of a modal operator).

Prior's text (pp. 201–205) indicates sufficiently how it could be shown that any thesis of S5 is a thesis of P and that the rules and definitions of S5 are obtainable as derived rules of P. We turn, therefore, to the problem of showing that any thesis of P is a thesis of S5 and that the rules and definition of P are obtainable as derived rules of S5.