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.

We show that any (atomic) excellent class can be expanded with hyperimaginaries to form an (atomic) excellent class which has canonical bases. When is, in addition, of finite U-rank, then is also simple and has a full canonical bases theorem. This positive situation contrasts starkly with homogeneous model theory for example, where the eq-expansion may fail to be homogeneous. However, this paper shows that expanding an ω-stable, homogeneous class gives rise to an excellent class, which is simple if is of finite U-rank.

ℵ0-stable ℵ0-categorical linked quaternionic mappings are studied and are shown to correspond (in some sense) to special groups which are ℵ0-stable, ℵ0-categorical, satisfy AP(3) and have finite 2-symbol length. They are also related to special groups whose isometry relation is a finite union of cosets, which are then considered on their own, as well as their links with pseudofinite, profinite and weakly normal special groups.

Let (M, )⊨ ACA0 be such that , the collection of all unbounded sets in , admits a definable complete ultrafilter and let T be a theory extending first order arithmetic coded in such that M thinks T is consistent. We prove that there is an end-extension N ⊨ T of M such that the subsets of M coded in N are precisely those in . As a special case we get that any Scott set with a definable ultrafilter coding a consistent theory T extending first order arithmetic is the standard system of a recursively saturated model of T.

We classify ultrafilters on ω with respect to sequential contours (see [4]. [5]) of different ranks. In this way we obtain an ω1 sequence of disjoint classes. We prove that non-emptiness of for successor α ≥ 2 is equivalent to the existence of P-point. We investigate relations between P-hierarchy and ordinal ultrafilters (introduced by J. E. Baumgartner in [1]). we prove that it is relatively consistent with ZFC that the successor classes (for α ≥ 2) of P-hierarchy and ordinal ultrafilters intersect but are not the same.

In a previous paper with M. Džamonja, class forcings were given which fixed the complexity (a universality covering number) for certain types of structures of size λ together with the value of 2λ for every regular λ. As part of a programme for examining when such global results can be true in an inner model, we build generics for these class forcings.

We study the relationship between the semistationary reflection principle and stationary reflection principles. We show that for all regular cardinals λ ≥ ω2 the semistationary reflection principle in the space [λ]ω implies that every stationary subset of ≔ {α ∈ λ ∣ cf(α) = ω} reflects. We also show that for all cardinals λ ≥ ω3 the semistationary reflection principle in [λ]ω does not imply the stationary reflection principle in [λ]ω.

In this paper, I will give a new characterisation of the spaces of complete theories of pseudofinite fields and of algebraically closed fields with a generic automorphism (ACFA) in terms of the Vietoris topology on absolute Galois groups of prime fields.

For a model of Peano Arithmetic, let Lt() be the lattice of its elementary substructures, and let Lt+ () be the equivalenced lattice (Lt(),≅), where ≅ is the equivalence relation of isomorphism on Lt(). It is known that Lt+() is always a reasonable equivalenced lattice.

Theorem. Let L be a finite distributive lattice and let (L, E) be reasonable. If 0 is a nonstandard prime model of PA, then 0 has a cofinal extension such that Lt+() ≅ (L,E).

A general method for proving such theorems is developed which, hopefully, will be able to be applied to some nondistributive lattices.

I provide indestructibility results for large cardinals consistent with V = L, such as weakly compact, indescribable and strongly unfoldable cardinals. The Main Theorem shows that any strongly unfoldable cardinal κ can be made indestructible by <κ-closed, κ-proper forcing. This class of posets includes for instance all <κ-closed posets that are either κ−-c.c. or <κ-strategically closed as well as finite iterations of such posets. Since strongly unfoldable cardinals strengthen both indescribable and weakly compact cardinals, the Main Theorem therefore makes these two large cardinal notions similarly indestructible. Finally. I apply the Main Theorem to obtain a class forcing extension preserving all strongly unfoldable cardinals in which every strongly unfoldable cardinal κ is indestructible by <κ-closed, κ-proper forcing.

Some 40 years ago, Dana Scott proved that every countable Scott set is the standard system of a model of PA. Two decades later, Knight and Nadel extended his result to Scott sets of size ω1. Here, I show that assuming the Proper Forcing Axiom (PFA), every A-proper Scott set is the standard system of a model of PA. I define that a Scott set is proper if the quotient Boolean algebra /Fin is a proper partial order and A-proper if is additionally arithmetically closed. I also investigate the question of the existence of proper Scott sets.

We construct a model with an indecisive precipitous ideal and a model with a precipitous ideal with a non precipitous normal ideal below it. Such kind of examples were previously given by M. Foreman [2] and R. Laver [4] respectively. The present examples differ in two ways: first- they use only a measurable cardinal and second- the ideals are over a cardinal. Also a precipitous ideal without a normal ideal below it is constructed. It is shown in addition that if there is a precipitous ideal over a cardinal κ such that

• after the forcing with its positive sets the cardinality of κ remains above ℵ1

• there is no a normal precipitous ideal then there is 0†.

In Handbook of Philosophical Logic M. Dunn formulated a problem of describing pretabular extensions of relevant logics (cf. M. Dunn [1984], p. 211; M. Dunn, G. Restall [2002], p. 79). The main result of this paper is described in the title.

This article aims to classify those reducts of expansions of (ℚ, <) by unary predicates which eliminate quantifiers, and in particular to show that, up to interdefinability, there are only finitely many for a given language. Equivalently, we wish to classify the closed subgroups of Sym(ℚ) containing the group of all automorphisms of (ℚ, <) fixing setwise certain subsets. This goal is achieved for expansions by convex predicates, yielding expansions by constants as a special case, and for the expansion by a dense, co-dense predicate. Partial results are obtained in the general setting of several dense predicates.

We answer some problems set by Priest in [11] and [12], in particular refuting Priest's Conjecture that all LP-models of Th(ℕ) essentially arise via congruence relations on classical models of Th(ℕ). We also show that the analogue of Priest's Conjecture for IΔ0 + Exp implies the existence of truth definitions for intervals [0, a] ⊂eM ⊨ IΔ0 + Exp in any cut [0, a] ⊂eK ⊆eM closed under successor and multiplication.

Global co-stationarity of the ground model from an ℵ2-c.c. forcing which adds a new subset of ℵ1 is internally consistent relative to an ω1-Erdős hyperstrong cardinal and a sufficiently large measurable above.

There is an ergodic, measure preserving, countable Borel equivalence relation E on a standard Borel probability space (X, μ) such that E∣c is not essentially free on any conull C ⊂ X.

A truth for λ is a pair 〈Q, ψ〉 so that Q ⊆ Hλ, ψ is a first order formula with one free variable, and there exists B ⊆ Hλ+ such that (Hλ+; ∈, B) ⊨ ψ[Q]. A cardinal λ is , indescribable just in case that for every truth 〈Q, ψ〈 for λ, there exists < λ so that is a cardinal and 〈Q ∩ , ψ) is a truth for . More generally, an interval of cardinals [κ, λ] with κ ≤ λ is indescribable if for every truth 〈Q, ψ〈 for λ, there exists , and π: → Hλ so that is a cardinal, is a truth for , and π is elementary from () into (H; ∈, κ, Q) with id.

We prove that the restriction of the proper forcing axiom to ϲ-linked posets requires a indescribable cardinal in L, and that the restriction of the proper forcing axiom to ϲ+-linked posets, in a proper forcing extension of a fine structural model, requires a indescribable 1-gap [κ, κ+]. These results show that the respective forward directions obtained in Hierarchies of Forcing Axioms I by Neeman and Schimmerling are optimal.

We prove an exponential lower bound on the size of proofs in the proof system operating with ordered binary decision diagrams introduced by Atserias, Kolaitis and Vardi [2]. In fact, the lower bound applies to semantic derivations operating with sets defined by OBDDs. We do not assume any particular format of proofs or ordering of variables, the hard formulas are in CNF. We utilize (somewhat indirectly) feasible interpolation.

We define a proof system combining resolution and the OBDD proof system.

In 2004 Csima, Hirschfeldt, Knight, and Soare [1] showed that a set A ≤T 0′ is nonlow2 if and only if A is prime bounding, i.e., for every complete atomic decidable theory T, there is a prime model computable in A. The authors presented nine seemingly unrelated predicates of a set A, and showed that they are equivalent for sets. Some of these predicates, such as prime bounding, and others involving equivalence structures and abelian p-groups come from model theory, while others involving meeting dense sets in trees and escaping a given function come from pure computability theory.

As predicates of A, the original nine properties are equivalent for sets; however, they are not equivalent in general. This article examines the (degree-theoretic) relationship between the nine properties. We show that the nine properties fall into three classes, each of which consists of several equivalent properties. We also investigate the relationship between the three classes, by determining whether or not any of the predicates in one class implies a predicate in another class.