A standard result in topological dynamics is the existence of minimal subsystem. It is a direct consequence of Zorn's lemma: given a compact topological space X with a map f: X→X, the set of compact non empty subspaces K of X such that f(K) ⊆ K ordered by inclusion is inductive, and hence has minimal elements. It is natural to ask for a point-free (or formal) formulation of this statement. In a previous work [3], we gave such a formulation for a quite special instance of this statement, which is used in proving a purely combinatorial theorem (van de Waerden's theorem on arithmetical progression).

In this paper, we extend our analysis to the case where X is a boolean space, that is compact totally disconnected. In such a case, we give a point-free formulation of the existence of a minimal subspace for any continuous map f: X→X. We show that such minimal subspaces can be described as points of a suitable formal topology, and the “existence” of such points become the problem of the consistency of the theory describing a generic point of this space. We show the consistency of this theory by building effectively and algebraically a topological model. As an application, we get a new, purely algebraic proof, of the minimal property of [3]. We show then in detail how this property can be used to give a proof of (a special case of) van der Waerden's theorem on arithmetical progression, that is “similar in structure” to the topological proof [6, 8], but which uses a simple algebraic remark (Proposition 1) instead of Zorn's lemma. A last section tries to place this work in a wider context, as a reformulation of Hilbert's method of introduction/elimination of ideal elements.

Finitary sketches, i.e., sketches with finite-limit and finite-colimit specifications, are proved to be as strong as geometric sketches, i.e., sketches with finite-limit and arbitrary colimit specifications. Categories sketchable by such sketches are fully characterized in the infinitary first-order logic: they are axiomatizable by σ-coherent theories, i.e., basic theories using finite conjunctions, countable disjunctions, and finite quantifications. The latter result is absolute; the equivalence of geometric and finitary sketches requires (in fact, is equivalent to) the non-existence of measurable cardinals.

We consider small-weight Cutting Planes (CP*) proofs; that is, Cutting Planes (CP) proofs with coefficients up to Poly(n). We use the well known lower bounds for monotone complexity to prove an exponential lower bound for the length of CP* proofs, for a family of tautologies based on the clique function. Because Resolution is a special case of small-weight CP, our method also gives a new and simpler exponential lower bound for Resolution.

We also prove the following two theorems: (1) Tree-like CP* proofs cannot polynomially simulate non-tree-like CP* proofs. (2) Tree-like CP* proofs and Bounded-depth-Frege proofs cannot polynomially simulate each other.

Our proofs also work for some generalizations of the CP* proof system. In particular, they work for CP* with a deduction rule, and also for any proof system that allows any formula with small communication complexity, and any set of sound rules of inference.

Translations from Lambda calculi into combinatory logics can be used to avoid some implementational problems of the former systems. However, this scheme can only be efficient if the translation produces short output with a small number of combinators, in order to reduce the time and transient storage space spent during reduction of combinatory terms. In this paper we present a combinatory system and an abstraction algorithm, based on the original bracket abstraction operator of Schönfinkel [9]. The algorithm introduces at most one combinator for each abstraction in the initial Lambda term. This avoids explosive term growth during successive abstractions and makes the system suitable for practical applications. We prove the correctness of the algorithm and establish some relations between the combinatory system and the Lambda calculus.

In this paper we investigate towers of normal filters. These towers were first used by Woodin (see [15]). Woodin proved that if δ is a Woodin cardinal and P is the full stationary tower up to δ (P<δ) or the countable version (Q<δ), then the generic ultrapower is closed under < δ sequences (so the generic ultrapower is well-founded) ([14]). We show that if ℙ is a tower of height δ, δ supercompact, and the filters generating ℙ are the club filter restricted to a stationary set, then the generic ultrapower is well-founded (ℙ is precipitous). We also give some examples of non-precipitous towers. We also show that every normal filter can be extended to a V-ultrafilter with well-founded ultrapower in some generic extension of V (assuming large cardinals). Similarly for any tower of inaccessible height. This is accomplished by showing that there is a stationary set that projects to the filter or the tower and then forcing with P<δ below this stationary set.

An important idea in our proof of precipitousness (Theorem 6.4) has the following form in Woodin's proof. If are maximal antichains (i Є ω and δ Woodin) then there is a κ < δ such that each Ai ∩ Vκ is semiproper, i.e.,

contains a club (relative to ∣ a∣ < κ).

The main concern of this paper is the design of a noetherian and confluent normalization for LK2 (that is, classical second order predicate logic presented as a sequent calculus).

The method we present is powerful: since it allows us to recover as fragments formalisms as seemingly different as Girard's LC and Parigot's λμ, FD ([10, 12, 32, 36]), delineates other viable systems as well, and gives means to extend the Krivine/Leivant paradigm of ‘programming-with-proofs’ ([26, 27]) to classical logic; it is painless: since we reduce strong normalization and confluence to the same properties for linear logic (for non-additive proof nets, to be precise) using appropriate embeddings (so-called decorations); it is unifying: it organizes known solutions in a simple pattern that makes apparent the how and why of their making.

A comparison of our method to that of embedding LK into LJ (intuitionistic sequent calculus) brings to the fore the latter's defects for these ‘deconstructive purposes’.

In this paper we prove Jensen's Coding Theorem, assuming ˜ 0#, via a proof that makes no use of the fine structure theory. We do need to quote Jensen's Covering Theorem, whose proof uses fine-structural ideas, but make no direct use of these ideas. The key to our proof is the use of “coding delays.”

Coding Theorem (Jensen). Suppose 〈M,A〉 is a model of ZFC + O#does not exist. Then there is an 〈M, A〉-definable class forcing P such that if G ⊆ P is P-generic over 〈M, A〉:

(a) 〈M[G],A,G〉 ⊨ NZFC.

(b) M[G] ⊨ V = L[R], R ⊆ ωand 〈M[G], A, G〉 ⊨ A,G are definable from the parameter R.

In the above statement when we say “〈M, A〉 ⊨ ZFC” we mean that M ⊨ ZFC and in addition M satisfies replacement for formulas that mention A as a predicate. And “P-generic over 〈M, A〉” means that all 〈M, A〉-definable dense classes are met.

The consequence of ˜ O# that we need follows directly from the Covering Theorem.

A boolean algebra is shown to be completely representable if and only if it is atomic, whereas it is shown that neither the class of completely representable relation algebras nor the class of completely representable cylindric algebras of any fixed dimension (at least 3) are elementary.

Gurevich and Shelah have shown that Peano Arithmetic cannot be interpreted in the monadic second-order theory of short chains (hence, in the monadic second-order theory of the real line). We will show here that it is consistent that the monadic second-order theory of no chain interprets Peano Arithmetic.

The model theoretic ‘back and forth’ construction of isomorphisms and automorphisms is based on the proof by Cantor that the theory of dense linear orderings without endpoints is ℵ0-categorical. However, Cantor's method is slightly different and for many other structures it yields an injection which is not surjective. The purpose here is to examine Cantor's method (here called ‘going forth’) and to determine when it works and when it fails. Partial answers to this question are found, extending those earlier given by Cameron. We also give fuller characterisations of when forth suffices for model theoretic classes such as structures containing Jordan sets for the automorphism group, and ℵ0-categorical ω-stable structures. The work is based on the author's Ph.D. thesis.

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.

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.

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.

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.

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 X be an infinite but separable metric space. An open cover of X is said to be large if for each x ϵ X the set {U ϵ : x ϵ U} is infinite. The symbol Λ denotes the collection of large open covers of X. An open cover of X is said to be an ω-cover if for each finite subset F of X there is a U ϵ such that F ⊆ U, and X is not a member of , X is said to have Rothberger's property if there is for every sequence (n : n = 1,2,3,…) of open covers of X a sequence (Un : n = 1,2,3,…) such that:

(1) for each n, Un is a member of n, and

(2) {Un: n = 1,2,3,…} is a cover of X.

Rothberger introduced this property in his paper [2]. For convenience we let denote the collection of all open covers of X.

In [3] it was shown that X has Rothberger's property if, and only if, the following partition relation is true for large open covers of X:

This partition relation means:

for every large cover of X, for every coloring

such that for each U ϵ and each large cover there is an i with a large cover of X,

either there is a large cover such that f({A, B}) = 0 whenever {A,B} ϵ ,

or else there is a which is not point–finite such that f{{A, B}) = 1 whenever {A, B} ϵ .

We prove an exponential lower bound on the length of cutting plane proofs. The proof uses an extension of a lower bound for monotone circuits to circuits which compute with real numbers and use nondecreasing functions as gates. The latter result is of independent interest, since, in particular, it implies an exponential lower bound for some arithmetic circuits.

We prove that the class of trees with no branches of cardinality ≤ κ is not RPC definable in L∞κ when κ is regular. Earlier such a result was known for under the assumption κ<κ = κ. Our main result is actually proved in a stronger form which covers also L∞κ (and makes sense there) for every strong limit cardinal λ < κ of cofinality κ.

The Kleene-Kreisel continuous functionals [6, 7] have been given several alternative characterisations: using Kuratowski's limit spaces (Scarpellini [20]), using their generalisation, filter spaces (Hyland [4]), via hyperfinite functionals (Normann [11]) and perhaps most elegantly using Scott-Ershov domains (Ershov [3], later generalised by Berger [1]). We propose to add yet another characterisation to this list, which may be called model-theoretic in contrast to the others, but which is in fact closely related to Ershov's approach.

We use the notion of logically presented domains developed in Palmgren and Stoltenberg-Hansen [17] (originating in the work of [15]). Certain logical types, i.e., finitely consistent sets of formulas, over the full type structure built from ℕ correspond to the continuous functionals in the sense of Kreisel, or to Kleene's associates, while the elements realising the types correspond to functionals having associates (cf. [6]). To define these—the total types—we make a nonstandard extension of the full type structure. The set of nonstandard elements is sufficiently rich to single out the total types. The nonstandard extension also makes it possible to relate the logical presentation to Ershov's approach. The logical form of the domain constructions allows us to use a (generalised) Fréchet power as a nonstandard extension. This extension is constructive, in the sense that it avoids the axiom of choice, as distinguished from the one employed in [11].