We present a game semantics in the style of Lorenzen for Girard's linear logic . Lorenzen suggested that the meaning of a proposition should be specified by telling how to conduct a debate between a proponent P who asserts and an opponent O who denies . Thus propositions are interpreted as games, connectives as operations on games, and validity as existence of a winning strategy for P. We propose that the connectives of linear logic can be naturally interpreted as the (...) operations on games introduced for entirely different purposes by Blass . We show that affine logic, i.e., linear logic plus the rule of weakening, is sound for this interpretation. We also obtain a completeness theorem for the additive fragment of affine logic, but we show that completeness fails for the multiplicative fragment. On the other hand, for the multiplicative fragment, we obtain a simple characterization of game-semantical validity in terms of classical tautologies. An analysis of the failure of completeness for the multiplicative fragment leads to the conclusion that the game interpretation of the connective is weaker than the interpretation implicit in Girard's proof rules; we discuss the differences between the two interpretations and their relative advantages and disadvantages. Finally, we discuss how Gödel's Dialectica interpretation , which was connected to linear logic by de Paiva , fits with game semantics. (shrink)

We show that the modal propositional logic G, originally introduced to describe the modality "it is provable that", is also sound for various interpretations using filters on ordinal numbers, for example the end-segment filters, the club filters, or the ineffable filters. We also prove that G is complete for the interpretation using end-segment filters. In the case of club filters, we show that G is complete if Jensen's principle □ κ holds for all $\kappa ; on the other hand, it (...) is consistent relative to a Mahlo cardinal that G be incomplete for the club filter interpretation. (shrink)

People usually regard algorithms as more abstract than the programs that implement them. The natural way to formalize this idea is that algorithms are equivalence classes of programs with respect to a suitable equivalence relation. We argue that no such equivalence relation exists.

This paper developed from Shelah’s proof of a zero-one law for the complexity class “choiceless polynomial time,” defined by Shelah and the authors. We present a detailed proof of Shelah's result for graphs, and describe the extent of its generalizability to other sorts of structures. The extension axioms, which form the basis for earlier zero-one laws are inadequate in the case of choiceless polynomial time; they must be replaced by what we call the strong extension axioms. We present an extensive (...) discussion of these axioms and their role both in the zero-one law and in general. (shrink)

Turing machines define polynomial time on strings but cannot deal with structures like graphs directly, and there is no known, easily computable string encoding of isomorphism classes of structures. Is there a computation model whose machines do not distinguish between isomorphic structures and compute exactly PTime properties? This question can be recast as follows: Does there exist a logic that captures polynomial time ? Earlier, one of us conjectured a negative answer. The problem motivated a quest for stronger and stronger (...) PTime logics. All these logics avoid arbitrary choice. Here we attempt to capture the choiceless fragment of PTime. Our computation model is a version of abstract state machines . The idea is to replace arbitrary choice with parallel execution. The resulting logic expresses all properties expressible in any other PTime logic in the literature. A more difficult theorem shows that the logic does not capture all of PTime. (shrink)

We prove several theorems about the cardinal $\mathfrak{g}$ associated with groupwise density. With respect to a natural ordering of families of nond-ecreasing maps fromω toω, all families of size $< \mathfrak{g}$ are below all unbounded families. With respect to a natural ordering of filters onω, all filters generated by $< \mathfrak{g}$ sets are below all non-feeble filters. If $\mathfrak{u}< \mathfrak{g}$ then $\mathfrak{b}< \mathfrak{u}$ and $\mathfrak{g} = \mathfrak{d} = \mathfrak{c}$ . (The definitions of these cardinals are recalled in the introduction.) Finally, (...) some consequences deduced from $\mathfrak{u}< \mathfrak{g}$ by Laflamme are shown to be equivalent to $\mathfrak{u}< \mathfrak{g}$. (shrink)

We prove some restrictions on the possible cofinalities of ultrapowers of the natural numbers with respect to ultrafilters on the natural numbers. The restrictions involve three cardinal characteristics of the continuum, the splitting number s, the unsplitting number r, and the groupwise density number g. We also prove some related results for reduced powers with respect to filters other than ultrafilters.

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.

We study ultrafilters onω2produced by forcing with the quotient of${\cal P}$(ω2) by the Fubini square of the Fréchet filter onω. We show that such an ultrafilter is a weak P-point but not a P-point and that the only nonprincipal ultrafilters strictly below it in the Rudin–Keisler order are a single isomorphism class of selective ultrafilters. We further show that it enjoys the strongest square-bracket partition relations that are possible for a non-P-point. We show that it is not basically generated but (...) that it shares with basically generated ultrafilters the property of not being at the top of the Tukey ordering. In fact, it is not Tukey-above [ω1]<ω, and it has only continuum many ultrafilters Tukey-below it. A tool in our proofs is the analysis of similar (but not the same) properties for ultrafilters obtained as the sum, over a selective ultrafilter, of nonisomorphic selective ultrafilters. (shrink)

This paper is motivated by the question whether there exists a logic capturing polynomial time computation over unordered structures. We consider several algorithmic problems near the border of the known, logically defined complexity classes contained in polynomial time. We show that fixpoint logic plus counting is stronger than might be expected, in that it can express the existence of a complete matching in a bipartite graph. We revisit the known examples that separate polynomial time from fixpoint plus counting. We show (...) that the examples in a paper of Cai, Fürer, and Immerman, when suitably padded, are in choiceless polynomial time yet not in fixpoint plus counting. Without padding, they remain in polynomial time but appear not to be in choiceless polynomial time plus counting. Similar results hold for the multipede examples of Gurevich and Shelah, except that their final version of multipedes is, in a sense, already suitably padded. Finally, we describe another possible candidate, involving determinants, for the task of separating polynomial time from choiceless polynomial time plus counting. (shrink)

There is an analogy between concepts such as end-extension types and minimal types in the model theory of Peano arithmetic and concepts such as P-points and selective ultrafilters in the theory of ultrafilters on N. Using the notion of conservative extensions of models, we prove some theorems clarifying the relation between these pairs of analogous concepts. We also use the analogy to obtain some model-theoretic results with techniques originally used in ultrafilter theory. These results assert that every countable nonstandard model (...) of arithmetic has a bounded minimal extension and that some types in arithmetic are not 2-isolated. (shrink)

Adjoin, to a countable standard model M of Zermelo-Fraenkel set theory (ZF), a countable set A of independent Cohen generic reals. If one attempts to construct the model generated over M by these reals (not necessarily containing A as an element) as the intersection of all standard models that include M ∪ A, the resulting model fails to satisfy the power set axiom, although it does satisfy all the other ZF axioms. Thus, there is no smallest ZF model including M (...) ∪ A, but there are minimal such models. These are classified by their sets of reals, and there is one minimal model whose set of reals is the smallest possible. We give several characterizations of this model, we determine which weak axioms of choice it satisfies, and we show that some better known models are forcing extensions of it. (shrink)

Any two models of arithmetic can be jointly embedded in a third with any prescribed isomorphic submodels as intersection and any prescribed relative ordering of the skies above the intersection. Corollaries include some known and some new theorems about ultrafilters on the natural numbers, for example that every ultrafilter with the "4 to 3" weak Ramsey partition property is a P-point. We also give examples showing that ultrafilters with the "5 to 4" partition property need not be P-points and that (...) the main theorem cannot be improved to allow a prescribed ordering of lower skies. (shrink)

By a model of set theory we mean a Boolean-valued model of Zermelo-Fraenkel set theory allowing atoms (ZFA), which contains a copy of the ordinary universe of (two-valued,pure) sets as a transitive subclass; examples include Scott-Solovay Boolean-valued models and their symmetric submodels, as well as Fraenkel-Mostowski permutation models. Any such model M can be regarded as a topos. A logical subtopos E of M is said to represent M if it is complete and its cumulative hierarchy, as defined by Fourman (...) and Hayashi, coincides with the usual cumulative hierarchy of M. We show that, although M need not be a complete topos, it has a smallest complete representing subtopos, and we describe this subtopos in terms of definability in M. We characterize, again in terms of definability, those models M whose smallest representing topos is a Grothendieck topos. Finally, we discuss the extent to which a model can be reconstructed when its smallest representing topos is given. (shrink)

We establish a course-of-values induction principle for K-finite sets in intuitionistic type theory. Using this principle, we prove a pigeonhole principle conjectured by Bénabou and Loiseau. We also comment on some variants of this pigeonhole principle.

We consider sets of reals that are “adequate” in various senses, for example dominating or unbounded or splitting or non-meager. Call a real x “needed” if every adequate set contains a real in which x is recursive. We characterize the needed reals for numerous senses of “adequate.” We also consider, for various notions of forcing that add reals, the problem of characterizing the ground-model reals that are recursive in generic reals.

A 2-affable ultrafilter has only finitely many predecessors in the Rudin-Keisler ordering of isomorphism classes of ultrafilters over the natural numbers. If the continuum hypothesis is true, then there is an ℵ 1 -sequence of ultrafilters D α such that the strict Rudin-Keisler predecessors of D α are precisely the isomorphs of the D β 's for $\beta.

We study the class of Sperner spaces, a generalized version of affine spaces, as defined in the language of pointline incidence and line parallelity. We show that, although the class of Sperner spaces is a pseudo-elementary class, it is not elementary nor even ℒ∞ω-axiomatizable. We also axiomatize the first-order theory of this class.

We exhibit a Horn sentence expressing the statement of the title; the construction generalizes to arbitrary primes in place of five.