In 1978 Shelah introduced a new class of theories, called simple (see [Shi]) which properly contained the class of stable theories. Shelah generalized part of the theory of forking to the simple context. After approximately 15 years of neglecting the general theory (although there were works by Hrushovski on finite rank with a definability assumption, as well as deep results on specific simple theories by Cherlin, Hrushovski, Chazidakis, Macintyre and Van den dries, see [CH], [CMV], [HP1], [HP2], [ChH]) there was a breakthrough, initiated with the work of Kim ([K1]). Kim proved that almost all the technical machinery of forking developed in the stable context could be generalized to simple case. However, the theory of multiplicity (i.e., the description of the (bounded) set of non forking extensions of a given complete type) no longer holds in the context of simple theories. Indeed, by contrast to simple theories, stable theories share a strong amalgamation property of types, namely if p and q are two “free” complete extensions over a superset of A, and there is no finite equivalence relation over A which separates them, then the conjunction of p and q is consistent (and even free over A.) In [KP] Kim and Pillay proved a weak version of this property for any simple theory, namely “the Independence Theorem for Lascar strong types”. This was a weaker version both because of the requirement that the sets of parameters of the types be mutually independent, as well as the use of Lascar strong types instead of the usual strong types. A very fundamental and interesting problem is whether the independence theorem can be proved for any simple theory, using only the usual strong types. In 1997 Buechler proved ([Bu]) the strong-type version of the independence theorem for an important subclass of simple theories, namely the class of low theories (which includes the class of stable theories and the class of supersimple theories of finite D-rank.)

Working in ZFC, we show that for any infinite cardinal k and ordinal y < (2<k)+ the polarized partition relation

holds. Our proof of this relation involves the use of elementary substructures of set models of large fragments of ZFC.

We give a direct proof of admissibility of cut and contraction for the contraction-free sequent calculus G4ip for intuitionistic propositional logic and for a corresponding multi-succedent calculus: this proof extends easily in the presence of quantifiers, in contrast to other, indirect, proofs, i.e., those which use induction on sequent weight or appeal to admissibility of rules in other calculi.

The paper establishes the general structure of the inconsistent models of arithmetic of [7]. It is shown that such models are constituted by a sequence of nuclei. The nuclei fall into three segments: the first contains improper nuclei: the second contains proper nuclei with linear chromosomes: the third contains proper nuclei with cyclical chromosomes. The nuclei have periods which are inherited up the ordering. It is also shown that the improper nuclei can have the order type of any ordinal, of the rationals, or of any other order type that can be embedded in the rationals in a certain way.

We investigate topological properties of subsets S of the real plane, expressed by first-order logic sentences in the language of the reals augmented with a binary relation symbol for S. Two sets are called topologically elementary equivalent if they have the same such first-order topological properties. The contribution of this paper is a natural and effective characterization of topological elementary equivalence of closed semi-algebraic sets.

Ever since [4]. systems of spheres have been considered to give an intuitive and elegant way to give a semantics for logics of theory- or belief- change. Several authors [5, 11] have considered giving up the rather strong assumption that systems of spheres be linearly ordered by inclusion. These more general structures are called hypertheories after [8]. It is shown that none of the proposed logics induced by these weaker structures are compact and thus cannot be given a strongly complete axiomatization in a finitary logic. Complete infinitary axiomatizations are given for several intuitive logics based on hypertheories that are not linearly ordered by inclusion.

In [8] it is proved that all the intermediate logics axiomatizable by formulas in one variable, except four of them, are not strongly complete. We considerably improve this result by showing that all the intermediate logics axiomatizable by formulas in one variable, except eight of them, are not strongly ω-complete. Thus, a definitive classification of such logics with respect to the notions of canonicity, strong completeness, ω-canonicity and strong ω-completeness is given.

Feiner [F] showed that a Boolean algebra need not have a computable copy (see also [T2]). Downey and Jockusch [D-J] showed that every low Boolean algebra does have a computable copy. Thurber [T3], showed that every low2 Boolean algebra has a computable copy. Here we show that every Boolean algebra which is low3, or even low4, has a computable copy.

The results of [D-J] and [T3] were obtained by passing to linear orderings. In [D-J], there is an embedding theorem saying that any linear ordering which is with the successor relation as an added predicate can be embedded in a slightly larger linear ordering which is computable. An isomorphism theorem of Remmel [R] is used to show that the interval algebras of the two linear orderings are isomorphic (except in a trivial case). In [T3], there is an embedding theorem saying that any linear ordering which is with certain added predicates can be embedded in one which is with successor. Again the isomorphism theorem of Remmel is used to show that the interval algebras are isomorphic (except in a trivial case).

Here, instead of passing to linear orderings, we work directly with Boolean algebras. We begin with a review of the known results. We re-formulate the embedding theorems of Downey-Jockusch and Thurber in terms of Boolean algebras. We extract from Remmel's isomorphism theorem some information on complexity. In this way, we show that a low Boolean algebra is isomorphic to a computable one by an isomorphism which is , at worst, and the same is true for a low2 Boolean algebra.

We deal with several pcf problems: we characterize another version of exponentiation: maximal number of k-branches in a tree with λ nodes, deal with existence of independent sets in stable theories, possible cardinalities of ultraproducts and the depth of ultraproducts of Boolean Algebras. Also we give cardinal invariants for each λ with a pcf restriction and investigate further TD{f). The sections can be read independently, although there are some minor dependencies.

Soit f une fonction de N dans N qui ne soit pas calculable en temps polynomial, et a un élément d'un corps differentiel K de caractéristique nulle. Nous appelons probleme des grandes puissances l'ensembledes uples = (x1…..xn) de K telsque x1 = af(n) et problème des grandes racines l'ensemble des uples de K tels que . Ce sont deux exemples de problèmes que l'utilisation de la dérivée ne permet pas de résoudre plus rapidement. Nous montrons que le problème des grandes racines n'est pas polynomial au sens des corps differentiels, même si nous autorisons un nombre polynomial de paramètres. et que le problème des grandes puissances n'est pas polynomial au sens des corps differentiels. même au niveau non uniforme. Les démonstrations utilisent la stabilité polynomial de la théorie des corps de caractéristique nulle. montrée par L. Blum, F. dicker. M. Shub et S. Smale, ainsi que le lemme de réduction qui permet de ramener un polynôme differentiel des variables a un polynôme des variables et de leurs dérivées.

We introduce a new framework for asymptotic probabilities of sentences, in which we have a σ-additive measure on the sample space of all sequences A = {} of finite models, where the universe of is {1,2, …, n}. and use this framework to strengthen 0-1 laws for logics.

Several attempts have been done to distinguish “positive” information in an arbitrary first order theory, i.e., to find a well behaved class of closed sets among the definable sets. In many cases, a definable set is said to be closed if its conjugates are sufficiently distinct from each other. Each such definition yields a class of theories, namely those where all definable sets are constructible, i.e., boolean combinations of closed sets. Here are some examples, ordered by strength:

Weak normality describes a rather small class of theories which are well understood by now (see, for example, [P]). On the other hand, normalization is so weak that all theories, in a suitable context, are normalizable (see [HH]). Thus equational theories form an interesting intermediate class of theories. Little work has been done so far. The original work of Srour [S1, S2, S3] adopts a point of view that is closer to universal algebra than to stability theory. The fundamental definitions and model theoretic properties can be found in [PS], though some easy observations are missing there. Hrushovski's example of a stable non-equational theory, the first and only one so far, is described in the unfortunately unpublished manuscript [HS]. In fact, it is an expansion of the free pseudospace constructed independently by Baudisch and Pillay in [BP] as an example of a strictly 2-ample theory. Strong equationality, defined in [Hr], is also investigated in [HS].

Some cardinal invariants from Cichoń's diagram can be characterized using the notion of cut-and-choose games on cardinals. In this paper we give another way to characterize those cardinals in terms of infinite games. We also show that some properties for forcing, such as the Sacks Property, the Laver Property and ωω-boundingness, are characterized by cut-and-choose games on complete Boolean algebras.

We study the following classes:

● Q* (r1A1…..rkAk) which is defined to be the collection of all sets that can be computed by a Turing machine that on any input makes a total of ri, queries to Ai, for all i ∈ {1..… k}.

● Q(r1A1…..rkAk) which is defined like Q* (r1A1….. rkAk) except that queries to Ai, must be made before queries to Ai+1 for all i ∈ {1….. k – 1}.

● QC(r1A1….. rkAk) which is defined like Q{r1A1….. rkAk) except that the Turing machine must halt even if given incorrect answers to some of its queries.

We show that if A1 ….. Ak are jumps that are not too close together, then all three of these classes are identical and are not changed if we permute (r1…..rkAk). This extends a result of Beigel's [1]. Since the second class is not affected by permutations, we say that these sets commute with each other. We also show that jumps that are too close together may not commute. We also characterize the commutative sequences of sets obtained by iterating the jump operation through an ordinal notation.

There are properties of finite structures that are expressible with the use of Hilbert's ∈-operator in a manner that does not depend on the actual interpretation for ∈-terms. but not expressible in plain first-order. This observation strengthens a corresponding result of Gurevich, concerning the invariant use of an auxiliary ordering in first-order logic over finite structures. The present result also implies that certain non-deterministic choice constructs, which have been considered in database theory, properly enhance the expressive power of first-order logic even as far as deterministic queries are concerned, thereby answering a question raised by Abiteboul and Vianu.

The notion of a D-ring, generalizing that of a differential or a differenee ring, is introduced, Quantifier elimination and a version of the Ax—Kochen—Eršov principle is proven for a theory of valued D-fields of residual characteristic zero.

A number of classical theories are interpreted in analogous theories that are based on intuitionistic logic. The classical theories considered include subsystems of first- and second-order arithmetic, bounded arithmetic, and admissible set theory.

Given a Mahlo cardinal k and a regular ε such that ω1 < ε < k we show that ◇k(cf = ε) holds in V provided that there are only non-stationarily many β < k with o(β) ≥ ε in K.

This paper grew as a continuation of [Sh462] but in the present form it can serve as a motivation for it as well. We deal with the same notions, all defined in 1.1, and use just one simple lemma from there whose statement and proof we repeat as 2.1. Originally entangledness was introduced, in [BoSh210] for example, in order to get narrow boolean algebras and examples of the nonmultiplicativity of c.c-ness. These applications became marginal when other methods were found and successfully applied (especially Todorčevic walks) but after the pcf constructions which made their début in [Sh-g] and were continued in [Sh462] it seems that this notion gained independence.

Generally we aim at characterizing the existence of strong and weak entangled orders in cardinal arithmetic terms. In [Sh462, §6] necessary conditions were shown for strong entangledness which in a previous version was erroneously proved to be equivalent to plain entangledness. In §1 we give a forcing counterexample to this equivalence and in §2 we get those results for entangledness (certainly the most interesting case). A new construction of an entangled order ends this section. In §3 we get weaker results for positively entangledness, especially when supplemented with the existence of a separating point (Definition 2.2). An antipodal case is defined in 3.10 and completely characterized in 3.11. Lastly we outline in 3.12 a forcing example showing that these two subcases of positive entangledness comprise no dichotomy. The work was done during the fall of 1994 and the winter of 1995. The second author proved Theorems 1.2, 2.14, the result that is mentioned in Remark 2.11 and what appears in this version as Theorem 2.10(a) with the further assumption den (I)θ < μ. The first author is responsible for waving off this assumption (actually by showing that it holds in the general case), for Theorems 2.12 and 2.13 in Section 2 and for the work which is presented in Section 3.

A minimal field of non-zero characteristic is algebraically closed.