Propositional Connectives and the Set Theory of the Continuum (CWI Quarterly (Special issue for SMC 50 jubilee) 9 (1996) 25-30)
PostScript or PDF
This talk is a survey of two topics of recent interest in mathematical logic, namely linear logic and cardinal characteristics of the continuum. I shall try to explain enough about each of them to be able to point out how they are connected. Since the underlying ideas of the two topics are quite different, I regard the existence of a connection as surprising.
Is Game Semantics Necessary? (Computer Science Logic: 7th Workshop, CSL '93, Springer Lecture Notes in Computer Science 832 (ed. E. Boerger, Y. Gurevich, and K. Meinke) (1994) 66-77)
PostScript or PDF
We discuss the extent to which game semantics is implicit in the formalism of linear logic and in the intuitions underlying linear logic.
Resource Consciousness in Classical Logic (in Games, Logic, and Constructive Sets, Proceedings of LLC9, the 9th conference on Logic, Language, and Computation, held at CSLI (ed. G. Mints and R. Muskens) (2003) 61-74)
PostScript or PDF
Using Herbrand's Theorem, we define simple Herbrand validity, a sort of resource consciousness that makes sense in classical predicate logic. We characterize the propositional formulas all of whose first-order instances are simply Herbrand valid. The characterization turns out to coincide with a known characterization of game semantical validity for multiplicative formulas.
Questions and Answers -- A Category Arising in Linear Logic, Complexity Theory, and Set Theory (Advances in Linear Logic (ed. J.-Y. Girard, Y. Lafont, and L. Regnier) London Math. Soc. Lecture Notes 222 (1995) 61-81)
PostScript or PDF
A category used by de Paiva to model linear logic also occurs in Vojtas's analysis of cardinal characteristics of the continuum. Its morphisms have been used in describing reductions between search problems in complexity theory. We describe this category and how it arises in these various contexts. We also show how these contexts suggest certain new multiplicative connectives for linear logic. Perhaps the most interesting of these is a sequential composition suggested by the set-theoretic application.
Some Semantical Aspects of Linear Logic (J. Interest Group in Pure and Applied Logic 5 (1998) 115-126)
PostScript or PDF
We describe and discuss several semantical views of linear logic. Our primary topic is game semantics, including modifications suggested by Abramsky, Jagadeesan, Hyland, Ong, and Japaridze. We also briefly discuss Girard's coherence spaces and de~Paiva's Dialectica-like semantics.