# This Week in Logic at CUNY

Computational Logic Seminar
Tuesday, April 30, 2013 2:00 pm rm. 3209, Graduate Center CUNY
Speaker: Melvin Fitting Lehman College, CUNY Graduate Center
Title: Realization Implemented

Justification logics are connected to modal logics via realization theorems. These have both constructive and non-constructive proofs. Here we do two things. First we provide a new path to constructive realization proofs, going through an intermediate quasi-realization stage. Quasi-realizers are easier to produce than realizers, though like them they are constructed from cut-free proofs. Quasi-realizers in turn constructively convert to realizers, and this conversion is independent of the justification logic in question. The construction depends only on the structure of the formula involved.

The second thing we do is provide a Prolog implementation of quasi-realization, and quasi-realization to realization conversion, for the logic LP. Many other justification logics can obviously be treated similarly.

Our quasi-realization algorithm, and its implementation, assumes the underlying modal proof system S4 is based on tableaus. Since these may not be familiar to everybody, we provide a sketch of how tableaus work. Then we present our algorithms, our implementation, and a discussion of implementation behavior and design decisions.

We believe our algorithms are simple and straightforward. The original realization algorithm, for instance, needed the entire cut-free proof as input. Our quasi-realization algorithm works one formal proof step at a time. There is, in the literature, another realization construction that works one step at a time, but it requires extensive use of substitution while our quasi-realization algorithm does not. The conversion algorithm is, as noted above, independent of particular justification logics and so only needs to be understood once. It is only here that substitution is needed.

Both the program to compute realizations, and a tech report discussing the algorithm, necessary background, and the implementation, are available on the speaker’s web page:

http://comet.lehman.cuny.edu/fitting/

Tuesday, April 30, 2013 5:45 pm Yeshiva University Furst Hall, Amsterdam Ave. & 185th Street.
Speaker: Joel David Hamkins The City University of New York
Title: The theory of infinite games, with examples, including infinite chess

This will be a talk on April 30, 2013 for a joint meeting of the Yeshiva University Mathematics Club and the Yeshiva University Philosophy Club. I will give a general introduction to the theory of infinite games, suitable for mathematicians and philosophers. What does it mean to play an infinitely long game? What does it mean to have a winning strategy for such a game? Is there any reason to think that every game should have a winning strategy for one player or another? Could there be a game, such that neither player has a way to force a win? Must every computable game have a computable winning strategy? I will present several game paradoxes and example infinitary games, including an infinitary version of the game of Nim, and several examples from infinite chess.

Set theory seminar
Friday, May 3, 2013 10:00 am GC 5383
Speaker: Victoria Gitman The New York City College of Technology (CityTech), CUNY
Title: Indestructibility for Ramsey cardinals

A large cardinal $kappa$ is said to be indestructible by a certain poset P if $kappa$ retains the large cardinal property in all forcing extensions by P. Since most relative consistency results for ZFC are obtained via forcing, the knowledge of a large cardinal’s indestructibility properties is used to establish the consistency of that large cardinal with other set theoretic properties. In this talk, I will use an elementary embeddings characterization of Ramsey cardinals to prove some basic indestructibility results.

Model theory seminar
Friday, May 3, 2013 12:30 pm GC 6417
Speaker: Manuel Alves CUNY Grad Center
Title: VC Dimension and Breadth in Modules

I will review the concept of vc-dimension of a formula, and the vc-function of a first order theory. The concept of breadth on the lattice of PP-definable subgroups of a module will be defined, and the relationship between these notions will be explored. Some model theory of Modules will be used to refine certain questions from the paper of Aschenbrenner, Dolich, Haskell, Macpherson, and Starchenko. The talk will include several pictures and examples to clarify the notions involved.

CUNY Logic Workshop
Friday, May 3, 2013 2:00 pm GC 6417
Speaker: Henry Towsner University of Pennsylvania
Title: Models of Reverse Mathematics

We discuss two results relating ideas in Reverse Mathematics to the properties of models of first order arithmetic. The first shows that we can extend second order arithmetic by the existence of a non-principal ultrafilter — a third order property — while remaining conservative. The second result shows that we can extend models of RCA so that any particular set is definable; this allows us to recover some properties of models of Peano arithmetic for models of RCA.