Limiting identification of r.e. indexes for r.e. languages (from a presentation of elements of the language) and limiting identification of programs for computable functions (from a graph of the function) have served as models for investigating the boundaries of learnability. Recently, a new approach to the study of “intrinsic” complexity of identification in the limit has been proposed. This approach, instead of dealing with the resource requirements of the learning algorithm, uses the notion of reducibility from recursion theory to compare and to capture the intuitive difficulty of learning various classes of concepts. Freivalds, Kinber, and Smith have studied this approach for function identification and Jain and Sharma have studied it for language identification.

The present paper explores the structure of these reducibilities in the context of language identification. It is shown that there is an infinite hierarchy of language classes that represent learning problems of increasing difficulty. It is also shown that the language classes in this hierarchy are incomparable, under the reductions introduced, to the collection of pattern languages.

Richness of the structure of intrinsic complexity is demonstrated by proving that any finite, acyclic, directed graph can be embedded in the reducibility structure. However, it is also established that this structure is not dense. The question of embedding any infinite, acyclic, directed graph is open.

We here examine the expressive power of first order logic with generalized quantifiers over finite ordered structures. In particular, we address the following problem: Given a family Q of generalized quantifiers expressing a complexity class C, what is the expressive power of first order logic FO(Q) extended by the quantifiers in Q? From previously studied examples, one would expect that FO(Q) captures LC, i.e., logarithmic space relativized to an oracle in C. We show that this is not always true. However, after studying the problem from a general point of view, we derive sufficient conditions on C such that FO(Q) captures LC. These conditions are fulfilled by a large number of relevant complexity classes, in particular, for example, by NP. As an application of this result, it follows that first order logic extended by Henkin quantifiers captures LNP. This answers a question raised by Blass and Gurevich [Ann. Pure Appl. Logic, vol. 32, 1986]. Furthermore we show that for many families Q of generalized quantifiers (including the family of Henkin quantifiers), each FO(Q)-formula can be replaced by an equivalent FO(Q)-formula with only two occurrences of generalized quantifiers. This generalizes and extends an earlier normal-form result by I. A. Stewart [Fundamenta Inform, vol. 18, 1993].

Model-theoretic concepts of saturation and categoricity are studied in the context of accessible categories. Accessible categories which are categorical in a strong sense are related to categories of M-sets (M is a monoid). Typical examples of such categories are categories of λ-saturated objects.

In this paper we explicate a very weak version of the principle □ discovered by Jensen who proved it holds in the constructible universe L. This principle is strong enough to include many of the known applications of □, but weak enough that it is consistent with the existence of very large cardinals. In this section we show that this principle is equivalent to a common combinatorial device, which we call a Jensen matrix. In the second section we show that our principle is consistent with a supercompact cardinal. In the third section of this paper we show that this principle is exactly equivalent to the statement that every torsion free Abelian group has a filtration into σ-balanced subgroups. In the fourth section of this paper we show that this principle fails if you assume the Chang's Conjecture:

In the fifth section of the paper we review the proofs that the various weak squares we consider are strictly decreasing in strength. Section 6 was added in an ad hoc manner after the rest of the paper was written, because the subject matter of Theorem 6.1 fit well with the rest of the paper. It deals with a principle dubbed “Not So Very Weak Square”, which appears close to Very Weak Square but turns out not to be equivalent.

To show that a formula A is not provable in propositional classical logic, it suffices to exhibit a finite boolean model which does not satisfy A. A similar property holds in the intuitionistic case, with Kripke models instead of boolean models (see for instance [11]). One says that the propositional classical logic and the propositional intuitionistic logic satisfy a finite model property. In particular, they are decidable: there is a semi-algorithm for provability (proof search) and a semi-algorithm for non provability (model search). For that reason, a logic which is undecidable, such as first order logic, cannot satisfy a finite model property.

The case of linear logic is more complicated. The full propositional fragment LL has a complete semantics in terms of phase spaces [2, 3], but it is undecidable [9]. The multiplicative additive fragment MALL is decidable, in fact PSPACE-complete [9], but the decidability of the multiplicative exponential fragment MELL is still an open problem. For affine logic, that is, linear logic with weakening, the situation is somewhat better: the full propositional fragment LLW is decidable [5].

Here, we show that the finite phase semantics is complete for MALL and for LLW, but not for MELL. In particular, this gives a new proof of the decidability of LLW. The noncommutative case is mentioned, but not handled in detail.

The complexity of priority proofs in recursion theory has been growing since the first priority proofs in [1] and [11]. Refined versions of classic priority proofs can be found in [18]. To this date, this part of recursion theory is at about the same stage of development as real analysis was in the early days, when the notions of topology, continuity, compactness, vector space, inner product space, etc., were not invented. There were no general theorems involving these concepts to prove results about the real numbers and the proofs were repetitive and lengthy.

The priority method contains an unprecedent wealth of combinatorics which is used to answer questions in recursion theory and is bound to have applications in many other fields as well. Unfortunately, very little progress has been made in finding theorems to formulate the combinatorial part of the priority method so as to answer questions without having to reprove the combinatorics in each case.

Lempp and Lerman in [10] provide an overview of the subject. The entire edifice of definitions and theorems which formulate the combinatorics of the priority method has acquired the name Priority Theory. From a different vein, Groszek and Slaman in [2] have initiated a program to classify priority constructions in terms of how much induction or collection is needed to carry them out. This program studies the complexity of priority proofs and can be called Complexity Theory of Priority Proofs or simply Complexity.

In this paper we study (self-)applicative theories of operations and binary words in the context of polynomial time computability. We propose a first order theory PTO which allows full self-application and whose provably total functions on = {0, 1}* are exactly the polynomial time computable functions. Our treatment of PTO is proof-theoretic and very much in the spirit of reductive proof theory.

Let S be the group of all permutations of the set of natural numbers. The cofinality spectrum CF(S) of S is the set of all regular cardinals λ such that S can be expressed as the union of a chain of λ proper subgroups. This paper investigates which sets C of regular uncountable cardinals can be the cofinality spectrum of S. The following theorem.is the main result of this paper.

Theorem. Suppose that V ⊨ GCH. Let C be a set of regular uncountable cardinals which satisfies the following conditions.

(a) C contains a maximum element.

(b) If μ is an inaccessible cardinal such thatμ = sup(C ∩ μ), thenμ ∈ C.

(c) if μ is a singular cardinal such thatμ = sup(C ∩ μ), thenμ+ ∈ C.

Then there exists a c.c.c. notion of forcing ℙ such that Vℙ ⊨ CF(S) = C.

We shall also investigate the connections between the cofinality spectrum and pcf theory; and show that CF(S) cannot be an arbitrarily prescribed set of regular uncountable cardinals.

We give positive answers to two open questions from [15]. (1) For every set C countably determined over , if C is then it must be over , and (2) every Borel subset of the product of two internal sets X and Y all of whose vertical sections are can be represented as an intersection (union) of Borel sets with vertical sections of lower Borel rank. We in fact show that (2) is a consequence of the analogous result in the case when X is a measurable space and Y a complete separable metric space (Polish space) which was proved by A. Louveau and that (1) is equivalent to the property shared by the inverse standard part map in Polish spaces of preserving almost all levels of the Borel hierarchy.

We consider the problem of finding and classifying representations in algebraic logic. This is approached by letting two players build a representation using a game. Homogeneous and universal representations are characterized according to the outcome of certain games. The Lyndon conditions defining representable relation algebras (for the finite case) and a similar schema for cylindric algebras are derived. Finte relation algebras with homogeneous representations are characterized by first order formulas. Equivalence games are defined, and are used to establish whether an algebra is ω-categorical. We have a simple proof that the perfect extension of a representable relation algebra is completely representable.

An important open problem from algebraic logic is addressed by devising another two-player game, and using it to derive equational axiomatisations for the classes of all representable relation algebras and representable cylindric algebras.

Other instances of this approach are looked at, and include the step by step method.

Let L = 〈<, +, hq, 1〉q∈ℚ where ℚ is the set of rational numbers and hq is a one-place function symbol corresponding to multiplication by q. Then the L-theory of Scott's model for intuitionistic analysis is decidable.

A Partial Combinatory Algebra is completable if it can be extended to a total one. In [1] it is asked (question 11, posed by D. Scott, H. Barendregt, and G. Mitschke) if every PCA can be completed. A negative answer to this question was given by Klop in [12, 11]; moreover he provided a sufficient condition for completability of a PCA (M, •, K,S) in the form of ten axioms (inequalities) on terms of M. We prove that just one of these axiom (the so called Barendregt's axiom) is sufficient to guarantee (a slightly weaker notion of) completability.

We prove that a (recursively) enumerable degree is contiguous iff it is locally distributive. This settles a twenty-year old question going back to Ladner and Sasso. We also prove that strong contiguity and contiguity coincide, settling a question of the first author, and prove that no m-topped degree is contiguous, settling a question of the first author and Carl Jockusch [11]. Finally, we prove some results concerning local distributivity and relativized weak truth table reducibility.

We show that all posets of uniform density ℵ1 may have to add a Cohen real and develop some forcing machinery for obtaining this sort of result.

Let φ be a monadic second order sentence about a finite structure from a class which is closed under disjoint unions and has components. Compton has conjectured that if the number of n element structures has appropriate asymptotics, then unlabelled (labelled) asymptotic probabilities ν(φ) (μ(φ) respectively) for φ always exist. By applying generating series methods to count finite models, and a tailor made Tauberian lemma, this conjecture is proved under a mild additional condition on the asymptotics of the number of single component -structures. Prominent among examples covered, are structures consisting of a single unary function (or partial function) and a fixed number of unary predicates.

The p-adic semianalytic sets are defined, locally, as boolean combinations of sets of the form over the p-adic fields ℚp, where f is an analytic function. A well-know example due to Osgood showed the projection of a semianalytic set need not be a semianalytic set. We call those sets that are, locally, the projections of p-adic semianalytic sets p-adic subanalytic sets. The theory of p-adic subanalytic sets was presented by Denef and Van den Dries in [5]. The basic tools are the quantifier elimination techniques together with the ultrametric Weierstrass Preparation Theorem. Simultaneously with their developments of the p-adic subanalytic sets, they established some basic properties of p-adic semianalytic sets.

In this paper, we prove that the closure of any p-adic semianalytic set is also a semianalytic set. The analogous property for real semianalytic sets was proved in [12] and that for rigid semianalytic sets, informed by the referee, has been proved recently by a quite different method in [14] (cf. [9]). The keys to the proof are a separation lemma (Lemma 2) and an analytic cell decomposition theorem (Theorem 2) which is an analytic version of Denef's cell decomposition theorem (see [3, 4]; A total different form of anayltic cells appeared in [13]). The analytic cell decomposition theorem allows us to partition certain kinds of basic subsets into analytic cells that possess the closure property (see §1 for the definition).

Type two cuts, bad cuts and very bad cuts are introduced in [10] for studying the relationship between Loeb measure and U-topology of a hyperfinite time line in an ω1-saturated nonstandard universe. The questions concerning the existence of those cuts are asked there. In this paper we answer, fully or partially, some of those questions by showing that: (1) type two cuts exist, (2) the ℵ1-isomorphism property implies that bad cuts exist, but no bad cuts are very bad.

This paper, a continuation of the series [22, 24], presents two methods for establishing the finite model property (FMP, for short) of normal modal logics containing K4. The methods are oriented mainly to logics represented by their canonical axioms and yield for such axiomatizations several sufficient conditions of FMP. We use them to obtain solutions to two well known open FMP problems. Namely, we prove that

• every normal extension of K4 with modal reduction principles has FMP and

• every normal extension of S4 with a formula of one variable has FMP.

These results are interesting not only from the technical point of view. Actually, they reveal important properties of a quite natural family of modal logics—formulas of one variable and, in particular, modal reduction principles are typical axioms in modal logic. Unfortunately, the technical apparatus developed in this paper is applicable only to logics with transitive frames, and the situation with FMP of extensions of K by modal reduction principles, even by axioms of the form □np → □mp still remains unclear. I think at present this is one of the major challenges in completeness theory.

The language of the canonical formulas, introduced in [22] (I'll refer to that paper as Part I), is a way of describing the “geometry and topology” of formulas' refutation (general) frames by means of some finite refutation patterns.

Let be the infinitary language obtained from the first-order language of graphs by closure under conjunctions and disjunctions of arbitrary sets of formulas, provided only finitely many distinct variables occur among the formulas. Let p(n) be the edge probability of the random graph on n vertices. It is shown that if p(n) ≪ n−1 satisfies certain simple conditions on its growth rate, then for every , the probability that σ holds for the random graph on n vertices converges. In fact, if p(n) = n−α, α > 1, then the probability is either smaller than for some d > 0, or it is asymptotic to cn−d for some c > 0, d ≥ 0. Results on the difficulty of computing the asymptotic probability are given.