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.

In the present paper we prove that the poset of all extensions of the logic defined by a class of matrices whose sets of distinguished values are equationally definable by their algebra reducts is the retract, under a Galois connection, of the poset of all subprevarieties of the prevariety generated by the class of the algebra reducts of the matrices involved. We apply this general result to the problem of finding and studying all extensions of the logic of paradox (viz., the implication-free fragment of any non-classical normal extension of the relevance-mingle logic). In order to solve this problem, we first study the structure of prevarieties of Kleene lattices. Then, we show that the poset of extensions of the logic of paradox forms a four-element chain, all the extensions being finitely many-valued and finitely-axiomatizable logics. There are just two proper consistent extensions of the logic of paradox. The first is the classical logic that is relatively axiomatized by the Modus ponens rule for the material implication. The second extension, being intermediate between the logic of paradox and the classical logic, is the one relatively axiomatized by the Ex Contradictione Quodlibet rule.

A combinatorial criterium is given when a monadic quantifier is expressible by means of universe-independent monadic quantifiers of width n. It is proved that the corresponding hierarchy does not collapse. As an application, it is shown that the second resumption (or vectorization) of the Härtig quantifier is not definable by monadic quantifiers. The techniques rely on Ramsey theory.

In this paper we discuss several generalization of theorems from stability theory to simple theories. Cherlin and Hrushovski, in [2] develop a substitute for canonical bases in finite rank, ω-categorical supersimple theories. Motivated by methods there, we prove the existence of canonical bases (in a suitable sense) for types in any simple theory. This is done in Section 2. In general these canonical bases will (as far as we know) exist only as “hyperimaginaries”, namely objects of the form a/E where a is a possibly infinite tuple and E a type-definable equivalence relation. (In the supersimple, ω-categorical case, these reduce to ordinary imaginaries.) So in Section 1 we develop the general theory of hyperimaginaries and show how first order model theory (including the theory of forking) generalises to hyperimaginaries. We go on, in Section 3 to show the existence and ubiquity of regular types in supersimple theories, ω-categorical simple structures and modularity is discussed in Section 4. It is also shown here how the general machinery of simplicity simplifies some of the general theory of smoothly approximable (or Lie-coordinatizable) structures from [2].

Throughout this paper we will work in a large, saturated model M of a complete theory T. All types, sets and sequences will have size smaller than the size of M. We will assume that the reader is familiar with the basics of forking in simple theories as laid out in [4] and [6]. For basic stability-theoretic results concerning regular types, orthogonality etc., see [1] or [9].

An ω-categorical supersimple group is finite-by-abelian-by-finite, and has finite SU-rank. Every definable subgroup is commensurable with an acl(ø)-definable subgroup. Every finitely based regular type in a CM-trivial ω-categorical simple theory is non-orthogonal to a type of SU-rank 1. In particular, a supersimple ω-categorical CM-trivial theory has finite SU-rank.

The choice construct (choose x: φ(x)) is useful in software specifications. We study extensions of first-order logic with the choice construct. We prove some results about Hilbert's ε operator, but in the main part of the paper we consider the case when all choices are independent.

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.

The (modal) μ-calculus ([14]) is a very powerful extension of modal logic with least and greatest fixed point operators. It is of great interest to computer science for expressing properties of processes such as termination (every run is finite) and fairness (on every infinite run, no action is repeated infinitely often to the exclusion of all others).

The power of the μ-calculus is also evident from a more theoretical perspective. The μ-calculus is a fragment of monadic second-order logic (MSO) containing only formulae that are invariant for bisimulation, in the sense that they cannot distinguish between bisimilar states. Janin and Walukiewicz prove the converse: any property which is invariant for bisimulation and MSO-expressible is already expressible in the μ-calculus ([13]). Yet the μ-calculus enjoys many desirable properties which MSO lacks, like a complete sequent-calculus ([29]), an exponential-time decision procedure, and the finite model property ([25]). Switching from MSO to its bisimulation-invariant fragment gives us these desirable properties.

In this paper we take a classical logician's view of the μ-calculus. As far as we are concerned a new logic should not be allowed into the community of logics without at least considering the standard questions that any logic is bothered with. In this paper we perform this rite of passage for the μ-calculus. The questions we will be concerned with are the following.

One of the fundamental results of descriptive complexity theory, due to Immerman [13] and Vardi [18], says that a class of ordered finite structures is definable in fixed-point logic if, and only if, it is computable in polynomial time. Much effort has been spent on the problem of capturing polynomial time, that is, describing all polynomial time computable classes of not necessarily ordered finite structures by a logic in a similar way.

The most obvious shortcoming of fixed-point logic itself on unordered structures is that it cannot count. Immerman [14] responded to this by adding counting constructs to fixed-point logic. Although it has been proved by Cai, Fürer, and Immerman [1] that the resulting fixed-point logic with counting, denoted by IFP+C, still does not capture all of polynomial time, it does capture polynomial time on several important classes of structures (on trees, planar graphs, structures of bounded tree-width [15, 9, 10]).

The main motivation for such capturing results is that they may give a better understanding of polynomial time. But of course this requires that the logical side is well understood. We hope that our analysis of IFP+C-formulas will help to clarify the expressive power of IFP+C; in particular, we derive a normal form. Moreover, we obtain a problem complete for IFP+C under first-order reductions.

It is consistent that there is a set mapping from the four-tuples of ωn into the finite subsets with no free subsets of size tn for some natural number tn. For any n < ω it is consistent that there is a set mapping from the pairs of ωn into the finite subsets with no infinite free sets. For any n < ω it is consistent that there is a set mapping from the pairs of ωn into ωn with no uncountable free sets.

Let be the class of structures 〈λ, <, A〉, where A ⊆ λ is disjoint from a club, and let be the class of structures 〈λ, <, A), where A ⊆ λ contains a club. We prove that if λ = λ<κ is regular, then no sentence of Lλ + κ separates and On the other hand, we prove that if λ = μ+ , μ = μ<μ, and a forcing axiom holds (and if μ = ℵ0), then there is a sentence of Lλλ which separates and .

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.

Can one extend crisp Peano arithmetic PA by a possibly many-valued predicate Tr(x) saying “x is true” and satisfying the “dequotation schema” for all sentences φ? This problem is investigated in the frame of Łukasiewicz infinitely valued logic.

One of the main tools in the study of nonmonotonic consequence relations is the representation of such relations in terms of preferential models. In this paper we give an unified and simpler framework to obtain such representation theorems.

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.

We describe a method for obtaining classical logic from intuitionistic logic which does not depend on any proof system, and show that by applying it to the most important implicational relevance logics we get relevance logics with nice semantical and proof-theoretical properties. Semantically all these logics are sound and strongly complete relative to classes of structures in which all elements except one are designated. Proof-theoretically they correspond to cut-free hypersequential Gentzen-type calculi. Another major property of all these logics is that the classical implication can faithfully be translated into them.

Using the Lascar inequalities, we show that any finite rank δ-closed subset of a quasiprojective variety is definably isomorphic to an affine δ-closed set. Moreover, we show that if X is a finite rank subset of the projective space ℙn and a is a generic point of ℙn, then the projection from a is injective on X. Finally we prove that if RM = RC in DCF0, then RM = RU.

In [1], S. Buss introduced the systems of Bounded Arithmetic for (i = 0,1,2,…) which has a close relationship to classes in polynomial hierarchy.

In [4], we defined a very special kind of proof-predicate Prfi for which gives detailed information on bounds of free variables used in the proof. There we also introduced infinitely many Gödel sentences for Prfi (k = 0, 1, 2, …) and showed that the properties of Prfi and are closely related to the P ≠ NP problem. Then we presented many conjectures on Prfi and which imply P ≠ NP.

Now in [2], Feferman emphasized that the arithmetization of metamathematics must be carried out intensionally. Bounded Arithmetic is a very interesting case in this sense.

In this paper, we also introduce the usual proof-predicate PRFi for and infinitely many Gödel sentences for PRFi(k= 0, 1, 2, …). Then we show that (Prfi, )and (PRFi, ) form a good contrast, this contrast is also closely related to the P ≠ NP problem, and present more conjectures which imply P ≠ NP.

As in [4] we define to be the following extension of Buss' original .

(1) We add finitely many function symbols which express polynomial time computable functions to Buss' original language of .

(2) All basic axioms on function symbols and ≤ can be expressed by initial sequents without logical symbols.

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

We address ZFC inequalities between some cardinal invariants of the continuum, which turned out to be true in spite of strong expectations given by [11].