We propose a simple notion of “extender” for coding large elementary embeddings of models of set theory. As an application we present a self-contained proof of the theorem by D. Martin and J. Steel that infinitely many Woodin cardinals imply the determinacy of every projective set.

Games of infinite length and perfect information have been studied for many years. There are numerous determinacy results for these games, and there is a wide body of work on consequences of their determinacy.

Except for games with very special payoff functions, games of infinite length and imperfect information have been little studied. In 1969, David Blackwell [1] introduced a class of such games and proved a determinacy theorem for a subclass. During the intervening time, there has not been much progress in proving the determinacy of Blackwell's games. Orkin [17] extended Blackwell's result to a slightly wider class. Blackwell [2] found a new proof of his own result. Maitra and Sudderth [9, 10] improved Blackwell's result in a different direction from that of Orkin and also generalized to the case of stochastic games. Recently Vervoort [18] has obtained a substantial improvement. Nevertheless, almost all the basic questions have remained open.

In this paper we associate with each Blackwell game a family of perfect information games, and we show that the (mixed strategy) determinacy of the former follows from the (pure strategy) determinacy of the latter. The complexity of the payoff function for the Blackwell game is approximately the same as the complexity of the payoff sets for the perfect information games. In particular, this means that the determinacy of Blackwell games with Borel measurable payoff functions follows from the known determinacy of perfect information games with Borel payoff sets.

In this paper we give relational semantics and an accompanying relational proof theory for full Lambek calculus (a sequent calculus which we denote by FL). We start with the Kripke semantics for FL as discussed in [11] and develop a second Kripke-style semantics, RelKripke semantics, as a bridge to relational semantics. The RelKripke semantics consists of a set with two distinguished elements, two ternary relations and a list of conditions on the relations. It is accompanied by a Kripke-style valuation system analogous to that in [11]. Soundness and completeness theorems with respect to FL hold for RelKripke models. Then, in the spirit of the work of Orlowska [14], [15], and Buszkowski and Orlowska [3], we develop relational logic RFL. The adjective relational is used to emphasize the fact that RFL has a semantics wherein formulas are interpreted as relations. We prove that a sequent Γ → α in FL is provable if and only if a translation, t(γ1 ● … ● γn ⊃ α)ευu, has a cut-complete fundamental proof tree. This result is constructive: that is, if a cut-complete proof tree for t(γ1 ● … ● γn ⊃ α)ευu is not fundamental, we can use the failed proof search to build a relational countermodel for t(γ1 ● … ● γn ⊃ α)ευu and from this, build a RelKripke countermodel for γ1 ● … ● γn ⊃ α. These results allow us to add FL, the basic substructural logic, to the list of those logics of importance in computer science with a relational proof theory.

We study classes of ultrafilters on ω defined by a natural property of the Loeb measure in the Nonstandard Universe corresponding to the ultrafilter. This class, the Property M ultrafilters, is shown to contain all ultrafilters built up by taking iterated products over collections of pairwise nonisomorphic selective ultrafilters. Results on Property M ultrafilters are applied to the construction of extensions of probability measures, and to the study of measurable reductions between ultrafilters.

We define a first-order extension LK(CP) of the cutting planes proof system CP as the first-order sequent calculus LK whose atomic formulas are CP-inequalities ∑i ai · xi ≥ b (xi's variables, ai's and b constants). We prove an interpolation theorem for LK(CP) yielding as a corollary a conditional lower bound for LK(CP)-proofs. For a subsystem R(CP) of LK(CP), essentially resolution working with clauses formed by CP-inequalities, we prove a monotone interpolation theorem obtaining thus an unconditional lower bound (depending on the maximum size of coefficients in proofs and on the maximum number of CP-inequalities in clauses). We also give an interpolation theorem for polynomial calculus working with sparse polynomials.

The proof relies on a universal interpolation theorem for semantic derivations [16, Theorem 5.1].

LK(CP) can be viewed as a two-sorted first-order theory of Z considered itself as a discretely ordered Z-module. One sort of variables are module elements, another sort are scalars. The quantification is allowed only over the former sort. We shall give a construction of a theory LK(M) for any discretely ordered module M (e.g., LK(Z) extends LK(CP)). The interpolation theorem generalizes to these theories obtained from discretely ordered Z-modules. We shall also discuss a connection to quantifier elimination for such theories.

We formulate a communication complexity problem whose (suitable) solution would allow to improve the monotone interpolation theorem and the lower bound for R(CP).

The purpose of these notes is to describe an absoluteness principle due to Jacques Stern and discuss some applications to the general study of Borel sets. This paper will not be engaged in independence results, but in proving outright theorems about the Borel hierarchy.

Roughly speaking, Stern's absoluteness principle states that if a certain set can be introduced into the universe by forcing, then it can be introduced by some small forcing notion.

The notation , and so on, will be defined in Section 1; this gives a notational system for describing the complexity of Borel sets beyond Fσ or Gδ. The “universe” refers to the totality of all sets. “Forcing” refers to Paul Cohen's technique for, in some sense, changing this totality by the introduction of new sets. Here “small” means relatively small cardinality.

The size of this small forcing notion is roughly the ath iteration of the power set operation. Just to get an idea of what this theorem might be saying, we can argue that under certain conditions, if a closed set can be introduced by forcing, then it exists already. There are a number of other qualifications that need to be made to this rough description, and we will come to them later.

Unlike, say, Shoenfield absoluteness, Stern's absoluteness can only be made understood in the terminology of forcing. Since forcing is typically associated with the pursuit of independence results, we could easily assume that Stern's work has little relevance in proving positive theorems about the Borel hierarchy.

However, this would be untrue. Using abstract and indirect metamathematical arguments, and availing ourselves of Stern's absoluteness principle, we will prove a string of ZFC theorems for which no direct proof is known.

We extend Shelah's first many model result to show that an unstable theory has 2κ many non-permutation group isomorphic models of size κ, where κ is an uncountable regular cardinal.

A Frege proof system F is any standard system of prepositional calculus, e.g., a Hilbert style system based on finitely many axiom schemes and inference rules. An Extended Frege system EF is obtained from F as follows. An EF-sequence is a sequence of formulas ψ1, …, ψκ such that eachψi is either an axiom of F, inferred from previous ψu and ψv (= ψu → ψi) by modus ponens or of the form q ↔ φ, where q is an atom occurring neither in φ nor in any of ψ1,…,ψi−1. Such q ↔ φ, is called an extension axiom and q a new extension atom. An EF-proof is any EF-sequence whose last formula does not contain any extension atom. In [12], S. A. Cook and R. Reckhow proved that the pigeonhole principle PHP has a simple polynomial size EF-proof and conjectured that PHP does not admit polynomial size F-proof. In [5], S. R. Buss refuted this conjecture by furnishing polynomial size F-proof for PHP. Since then the important separation problem of polynomial size F and polynomial size EF has not shown any progress.

In [11], S. A. Cook introduced the system PV, a free variable equational logic whose provable functional equalities are ‘polynomial time verifiable’ and showed that the metamathematics of F and EF can be developed in PV and the soundness of EF proved in PV. In [3], S. R. Buss introduced the first order system and showed that is essentially a conservative extension of PV. There he also introduced a second order system (BD).