# This Week in Logic at CUNY

Computational Logic Seminar
Tuesday, March 5, 2013 2:00 pm
Speaker: Sergei Artemov The CUNY Graduate Center
Title: Lost in translation: a critical view of epistemic puzzles solutions.

There are two basic ways to specify an epistemic scenario:
1. Syntactic: a verbal description with some epistemic logic on the
background and some additional formalizable assumptions; think of the
Muddy Children puzzle.
2. Semantic: providing an epistemic model; think of Aumann structures
– a typical way to define epistemic components of games.

Such classical examples as Muddy Children, Wise Men, Wise Girls, etc.,
are given by syntactic descriptions (type 1), each of which is
“automatically” replaced by a simple finite model (type 2). Validity
of such translations from (1) to (2) will be the subject of our study.

We argue that in reducing (1) to (2), it is imperative to check
whether (1) is complete with respect to (2) without which solutions
of puzzles by model reasoning in (2) are not complete, at best. We
have already shown that such reductions can be justified in the Muddy
Children puzzle MC due to its model categoricity: we have proved that
MC has the unique “cube” model Q_n for each n. This fixes an obvious
gap in the “textbook” solution of Muddy Children which did not provide
a sufficient justification for using Q_n.

We also show that an adequate reduction of (1) to (2) is rather a
lucky exception, which makes the requirement to check the completeness
of (1) w.r.t. (2) necessary. To make this point, we provide a
simplified version of Muddy Children (by dropping the assumption “no
kid knows whether he is muddy”) which admits the usual deductive
solution by reasoning from the syntactic description, but which cannot
be reduced to any finite model.

Models of PA
Wednesday, March 6, 2013 6:45 pm
Speaker: Keita Yokoyama Mathematical Institute, Tohoku University
Title: Several versions of self-embedding theorem

In this talk, I will give several versions of Friedman’s
self-embedding theorem which can characterize subsystems of Peano
arithmetic. Similarly, I will also give several variations of Tanaka’s
self-embedding theorem to characterize subsystems of second-order
arithmetic.

Set theory seminar
Friday, March 8, 2013 10:00 am
Speaker: Robert Lubarsky Florida Atlantic University
Title: Forcing for Constructive Set Theory
As is well known, forcing is the same as Boolean-valued models. If
instead of a Boolean algebra one used a Heyting algebra, the result is
a Heyting-valued model. The result then typically models only
constructive logic and falsifies Excluded Middle. On the one hand,
many of the same intuitions from forcing carry over, while on the
other the result is quite foreign to a classical mathematician. I will
give a survey of perhaps too many examples, and call for the
importation of more methods from current classical set-theory into
constructivism.

Model theory seminar
Friday, March 8, 2013 12:30 pm
Speaker: Roman Kossak The City University of New York
Title: On strength of weakness

I will explain why countable models of PA which are just recursively
saturated do not have maximal automorphisms. If time permits I will
also show why recursive saturation implies standard system saturation
for models of rich theories.

CUNY Logic Workshop
Friday, March 8, 2013 2:00 pm
Speaker: Keita Yokoyama Mathematical Institute, Tohoku University
Title: Reverse mathematics for second-order categoricity theorem

It is important in the foundations of mathematics that the natural
number system is characterizable as a system of 0 and a successor
function by second-order logic. In other words, the following
Dedekind’s second-order categoricity theorem holds: every Peano system
$(P,e,F)$ is isomorphic to the natural number system $(N,0,S)$. In
this talk, I will investigate Dedekind’s theorem and other similar
statements. We will first do reverse mathematics over $RCA_0$, and
then weaken the base theory. This is a joint work with Stephen G.
Simpson.

Models of PA
Wednesday, March 13, 2013 6:45 pm
Speaker: Tin Lok Wong Ghent University
Title: Generalizing the notion of interstices

I will present a generalization of the notion of interstices that
originated from the study of generic cuts.

Model theory seminar
Friday, March 15, 2013 12:30 pm
Speaker: Philipp Rothmaler The City University of New York
Title: Stability revisited
I will discuss an observation Ivo Herzog and I made in the last
millennium that yields a purely topological definition of stability of
a complete first-order theory in terms of their Stone spaces.

CUNY Logic Workshop
Friday, March 15, 2013 2:00 pm
Speaker: Charles Steinhorn Vassar College
Title: TBA