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.

Nous définissons une classe de suites de polynômes, calculés par des circuits de complexité polynomiale comprenant des additions, des soustractions. des multiplications et des sommations de Valiant. Nous montrons que cette classe est close pour la prise de la fonction-coefficient. définie au paragraphe 3 de cet article; nous en déduisons l'existence d'un circuit de complexité 72.n2, calculant le coefficient binomial de deux nombres de n chiffres, donnés en base 2. Il est par ailleurs facile de construire un circuit de complexité 17.n + 2 calculant la factorielle d'un nombre de n chiffres. La présence de 2.n sommations d'effet exponentiel dans chacun de ces circuits en affecte gravement l'intérêt pratique. II est peu probable, ou du moins peu souhaitable. qu'on puisse éliminer ces sommations sans explosion, car cela provoquerait la catastrophe cryptographique que redoutent tous les banquiers; néanmoins, nous ne savons pas séparer la classe définie ici de celle des suites de polynômes calculables en un nombre polynomial d'opérations arithmétiques. Cela n'a rien de surprenant, vu la très grande affinité qu'elle a avec la classe PSPACE: nous montrons en effet que cette classe est identique à la classe VPSPACE, définie antérieurement par Koiran et Perifel, qui apparaît ici sous une forme bien plus maniable que l'originale.

In this paper we construct a non-CM -trivial stable theory in which no infinite field is interpretable. In fact our theory will also be trivial and ω-stable, but of infinite Morley rank. A long term aim would be to find a non CM-trivial theory which has finite Morley rank (or is even strongly minimal) and does not interpret a field. The construction in this paper is direct, and is a “3-dimensional” version of the free pseudoplane. In a sense we are cheating: the original point of the notion of CM-triviality was to describe the geometry of a strongly minimal set, or even of a regular type. In our example, non-CM-triviality will come from the behaviour of three orthogonal regular types.

A stable theory is said to be CM-trivial if whenever A ⊆ B and acl(Ac) ∩ acl(B) = acl(A) in Teq, then Cb(stp(c/A)) ⊆ Cb(stp(c/B)). ( An infinite stable field will not be CM-trivial.) The notion is due to Hrushovski [3], where he gave several equivalent definitions, as well as showing that his new strongly minimal sets constructed “ab ovo” were CM-trivial. The notion was studied further in [6] where it was shown that CM-trivial groups of finite Morley rank are nilpotent-by-finite. These results were generalized in various ways to the superstable case in [8].

Lawvere hyperdoctrines give categorical algebraic semantics for intuitionistic predicate logic. Here we extend the hyperdoctrinal semantics to a broad variety of substructural predicate logics over the Typed Full Lambek Calculus, verifying their completeness with respect to the extended hyperdoctrinal semantics. This yields uniform hyperdoctrinal completeness results for numerous logics such as different types of relevant predicate logics and beyond, which are new results on their own; i.e., we give uniform categorical semantics for a broad variety of non-classical predicate logics. And we introduce an analogue of Lawvere–Tierney topology and cotopology in the hyperdoctrinal setting, which gives a unifying perspective on different logical translations, in particular allowing for a uniform treatment of Girard’s exponential translation between linear and intuitionistic logics and of Kolmogorov’s double negation translation between intuitionistic and classical logics. In the hyerdoctrinal conception, type theories are categories, logics over type theories are functors, and logical translations between them, then, are natural transformations, in particular Lawvere–Tierney topologies and cotopologies on hyperdoctrines. The view of logical translations as hyperdoctrinal Lawvere–Tierney topologies and cotopologies has not been elucidated before, and may be seen as a novel contribution of the present work. From a broader perspective, this work may be regarded as taking first steps towards interplay between algebraic and categorical logics; it is, technically, a combination of substructural (or Lambekian) algebraic logic and hyperdoctrinal (or Lawverian) categorical logic, as the hyperdoctrinal completeness theorem is shown via the integration of the Lindenbaum–Tarski algebra construction with the syntactic category construction. As such this work lays a foundation for further interactions between algebraic and categorical logics.

The notion of logical reducibilities is derived from the idea of interpretations between theories. It was used by Lovász and Gács [LG77] and Immerman [Imm87] to give complete problems for certain complexity classes and hence establish new connections between logical definability and computational complexity.

However, the notion is also interesting in a purely logical context. For example, it is helpful to establish nonexpressibility results.

We say that a class of τ-structures is a >complete problem for a logic under L-reductions if it is definable in [τ] and if every class definable in can be ”translated” into by L-formulae (cf. §4).

We prove the following theorem:

1.1. Theorem. There are complete problemsfor partial fixed-point logic andfor inductive fixed-point logic under quantifier-free reductions.

The main step of the proof is to establish a new normal form for fixed-point formulae (which might be of some interest itself). To obtain this normal form we use theorems of Abiteboul and Vianu [AV91a] that show the equivalence between the fixed-point logics we consider and certain extensions of the database query language Datalog.

In [Dah87] Dahlhaus gave a complete problem for least fixed-point logic. Since least fixed-point logic equals inductive fixed-point logic by a well-known result of Gurevich and Shelah [GS86], this already proves one part of our theorem.

However, our class gives a natural description of the fixed-point process of an inductive fixed-point formula and hence sheds some light on completely different aspects of the logic than Dahlhaus's construction, which is strongly based on the features of least fixed-point formulae.

This paper is devoted to o-minimalism, the study of the first-order properties of o-minimal structures. The main protagonists are the pseudo-o-minimal structures, that is to say, the models of the theory of all o-minimal L-structures, but we start with a more in-depth analysis of the well-known fragment DCTC (Definable Completeness/Type Completeness), and show how it already admits many of the properties of o-minimal structures: dimension theory, monotonicity, Hardy structures, and quasi-cell decomposition, provided one replaces finiteness by discreteness in all of these. Failure of cell decomposition leads to the related notion of a eukaryote structure, and we give a criterium for a pseudo-o-minimal structure to be eukaryote.

To any pseudo-o-minimal structure, we can associate its Grothendieck ring, which in the non-o-minimal case is a nontrivial invariant. To study this invariant, we identify a third o-minimalistic property, the Discrete Pigeonhole Principle, which in turn allows us to define discretely valued Euler characteristics. As an application, we study certain analytic subsets, called Taylor sets.

In this paper we show that for n-th order languages L′ with p nonlogical constants, 2 ≦ n < ω, 0 ≦ p < ω, a notion of satisfaction can be defined in an n-th order language containing one additional nonlogical constant, say S. By the usual methods we also show that this notion cannot be defined in L′. Hence, in its present formulation, Beth's Theorem in [1] for first order languages has no analogue for L′.

Our defining expression is such that, given any values of the other nonlogical constants and any appropriate m-tuple, it allows us to determine whether or not the m-tuple belongs to the value S of S without considering the totality of objects which are of the same type as S. Whether every definition in an n-th order language is equivalent to one thus “predicative”, and hence whether there is a formulation of Beth's Theorem which generalizes to higher orders, we do not know.

The falsehood for L′ of the analogue of Beth's Theorem implies the falsehood of an analogue of an interpolation theorem for first order languages. The above definability of satisfaction for L′ implies a result on finite axiomatizability in slightly richer languages. Details are given in § 4.

Associated with each first-order theory is a Boolean algebra of sentences and a Boolean space of models. Homomorphisms between the sentence algebras correspond to continuous maps between the model spaces. To what do recursive homomorphisms correspond? We introduce axiomatizable maps as the appropriate dual. For these maps we prove a Cantor-Bernstein theorem. Duality and the Cantor-Bernstein theorem are used to show that the Boolean sentence algebras of any two undecidable languages or of any two functional languages are recursively isomorphic where a language is undecidable iff it has at least one operation or relation symbol of two or more places or at least two unary operation symbols, and a language is functional iff it has exactly one unary operation symbol and all other symbols are for unary relations, constants, or propositions.

Generic automorphisms of certain homogeneous structures are considered, for instance, the rationals as an ordered set, the countable universal homogeneous partial order, and the random graph. Two of these cases were discussed in [7], where it was shown that there is a generic automorphism of the second in the sense introduced in [10], In this paper, I study various possible definitions of ‘generic’ and ‘mutually generic’, and discuss the existence of mutually generic automorphisms in some cases. In addition, generics in the automorphism group of the rational circular order are considered.

In this article propositions will be identified with a certain kind of changes of belief. The intended interpretation is that a proposition is characterised by the change it would induce if added to a state of belief. Propositions will thus be defined as functions from states of belief to states of belief. A set of postulates concerning the properties and existence of propositions will be formulated. A proposition will be said to be a tautology iff it is the identity function on states of belief. The main result is that the logic determined by the set of postulates is intuitionistic propositional logic.

The basic epistemic concept is that of a belief model, which is defined as a pair 〈, 〉, where is a nonempty set and is a class of functions from to . The elements in will be called states of belief and they will be denoted K, K′,…. A discussion of the epistemological interpretation of the states of belief can be found in Gärdenfors [2]. Here, no assumptions about the structure of the elements in will be made.

The elements in will be called propositions, and A, B, C, … will be used as variables over . Functions from states of belief to states of belief can be characterised as epistemic inputs. The intended interpretation of the functions in is that they correspond to changes of belief where the new evidence is accepted as “certain” or “known” in the resulting state of belief. This means that not all functions defined on can properly be called propositions.

Classes of forcings which add a real by forcing with branching conditions are examined, and conditions are found which guarantee that the generic real is of minimal degree over the ground model. An application is made to almost-disjoint coding via a real of minimal degree.

We prove that every ultraproduct of p-adics is inp-minimal (i.e., of burden 1). More generally, we prove an Ax-Kochen type result on preservation of inp-minimality for Henselian valued fields of equicharacteristic 0 in the RV language.

The paper [Schütte + Simpson] deals with the following one-dimensional case of Friedman's extension (see in [Simpson 1]) of Kruskal's theorem ([Kruskal]). Given a natural number n, let Sn+1 be the set of all finite sequences of natural numbers <n + 1. If s1 = (a0,…,ak) ∈Sn+1 and s2 = (b0,…,bm) ∈Sn + 1, then a strictly monotone function f: {0,…, k} → {0,…, m} is called an embedding of s1 into s2 if the following two assertions are satisfied:

1) ai, = bf(i), for all i < k;

2) if f(i) < j < f(i + 1) then bj > bf(i+1), for all i < k, j < m.

Then for every infinite sequence s1, s2,…,sk,… of elements of Sn + 1 there exist indices i < j and an embedding of si into Sj. That is, Sn+1 forms a well-quasi-ordering (wqo) with respect to embeddability. For each n, this statement W(Sn+1) is provable in the standard second order conservative extension of Peano arithmetic. On the other hand, the proof-theoretic strength of the statements W(Sn+1) grows so fast that this formal theory cannot prove the limit statement ∀nW(Sn+1). The appropriate first order -versions of these combinatory statements preserve their proof-theoretic strength, so that actually one can speak in terms of provability in Peano arithmetic. These are the main conclusions from [Schütte + Simpson].

We wish to extend this into the transfinite. That is, we take an arbitrary countable ordinal τ > 0 instead of n + 1 and try to obtain an analogous “strong” combinatory statement about finite sequences of ordinals < τ.

The purpose of this note is (i) to point out an important similarity between the nominalistic system discussed by Quine in his recent paper On universals and the system of logic (the system н) developed by the author in A homogeneous system for formal logic, (ii) to offer certain corrections to the latter, and (iii) to show that that system (н) is adequate for the general theory of ancestrale and for the definition of any general recursive function of natural numbers.

Nominalism as a thesis in the philosophy of science, according to Quine, is the view that it is possible to construct a language adequate for the purposes of science, which in no wise admits classes, properties, relations, or other abstract objects as values for variables.

Unfoldable cardinals are preserved by fast function forcing and the Laver-like preparations that fast functions support. These iterations show, by set-forcing over any model of ZFC, that any given unfoldable cardinal κ can be made indestructible by the forcing to add any number of Cohen subsets to κ.

Topologists Nabutovsky and Weinberger discovered how to embed computably enumerable (c.e.) sets into the geometry of Riemannian metrics modulo diffeomorphisms. They used the complexity of the settling times of the c.e. sets to exhibit a much greater complexity of the depth and density of local minima for the diameter function than previously imagined. Their results depended on the existence of certain sequences of c.e. sets, constructed at their request by Csima and Soare, whose settling times had the necessary dominating properties. Although these computability results had been announced earlier, their proofs have been deferred until this paper.

Computably enumerable sets have long been used to prove undecidability of mathematical problems such as the word problem for groups and Hilbert's Tenth Problem. However, this example by Nabutovsky and Weinberger is perhaps the first example of the use of c.e. sets to demonstrate specific mathematical or geometric complexity of a mathematical structure such as the depth and distribution of local minima.

This paper constitutes a short report on the proof theory which developed in the course of an investigation of Essenin-Volpin's foundational studies (see his paper in Infinitistic methods.) The Infinitistic methods paper is primarily concerned with proving the consistency of ZF. His arguments employ some very unusual ideas, especially that of the possibility of different length natural number series. The modal setting which he uses for these ideas and which is really all important is not reflected in the present paper. Only a simple representation of this idea is considered, namely, the use of *N, the nonstandard natural numbers, together with N, the standard natural numbers, to play the roles of a “long” and a “short” number series.

It will be useful to make a few general remarks before beginning on the technical details. These remarks are especially directed towards those people who have read Essenin-Volpin's work, the above-mentioned paper in particular and the one appearing in the proceedings of the 1968 Conference on Intuitionism and Proof Theory at Buffalo, New York.

I want to draw a comparison between the ultra-intuitionistic position of Essenin-Volpin on the one hand with the intuitionistic and realistic positions on the foundations of mathematics on the other hand. Intuitionism makes a transition from the traditional mathematical position (realism) that the rules of mathematical reasoning must be constructed so as to preserve truth (as known by an omniscient being about “the real world” of abstract mathematical objects) to the position that the rules of mathematical reasoning must be in accord with the process of knowing (performed by the “ideal mathematician” or “creative subject”) about the world of mental constructions. Ultra-intuitionism deepens and extends this transition to the position that the fundamental rules of mathematical reasoning must be in accord with processes of knowing accessible to human beings.

Every complete first order theory has a corresponding complete theory in continuous logic, called the randomization theory. It has two sorts, a sort for random elements of models of the first order theory, and a sort for events. In this paper we establish connections between properties of countable models of a first order theory and corresponding properties of separable models of the randomization theory. We show that the randomization theory has a prime model if and only if the first order theory has a prime model. And the randomization theory has the same number of separable homogeneous models as the first order theory has countable homogeneous models. We also show that when T has at most countably many countable models, each separable model of TR is uniquely characterized by a probability density function on the set of isomorphism types of countable models of T. This yields an analogue for randomizations of the results of Baldwin and Lachlan on countable models of ω1-categorical first order theories.

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.

In this paper we investigate the computational complexity of deciding if the variety generated by a given finite idempotent algebra satisfies a special type of Maltsev condition that can be specified using a certain kind of finite labelled path. This class of Maltsev conditions includes several well known conditions, such as congruence permutability and having a sequence of n Jónsson terms, for some given n. We show that for such “path defined” Maltsev conditions, the decision problem is polynomial-time solvable.