# This Week in Logic at CUNY

Models of PA
Wednesday, February 27, 2013 6:45 pm
Speaker: Erez Shochat St. Francis College
Title: Introduction to interstices and intersticial gaps II

Set theory seminar
Friday, March 1, 2013 10:00 am
Speaker: Joel David Hamkins The City University of New York
Title: The omega one of chess
This talk will be based on my recent paper with C. D. A. Evans,
Transfinite game values in infinite chess.

Infinite chess is chess played on an infinite chessboard. Since
checkmate, when it occurs, does so after finitely many moves, this is
technically what is known as an open game, and is therefore subject to
the theory of open games, including the theory of ordinal game values.
In this talk, I will give a general introduction to the theory of
ordinal game values for ordinal games, before diving into several
examples illustrating high transfinite game values in infinite chess.
The supremum of these values is the omega one of chess, denoted by
$omega_1^{mathfrak{Ch}}$ in the context of finite positions and by
$omega_1^{mathfrak{Ch}_{hskip-2ex atopsim}}$ in the context of all
positions, including those with infinitely many pieces. For lower
bounds, we have specific positions with transfinite game values of
$omega$, $omega^2$, $omega^2cdot k$ and $omega^3$. By embedding trees
into chess, we show that there is a computable infinite chess position
that is a win for white if the players are required to play according
to a deterministic computable strategy, but which is a draw without
that restriction. Finally, we prove that every countable ordinal
arises as the game value of a position in infinite three-dimensional
chess, and consequently the omega one of infinite three-dimensional
chess is as large as it can be, namely, true $omega_1$.

Model theory seminar
Friday, March 1, 2013 12:30 pm
Speaker: Alf Dolich The City University of New York
Title: Maximal Automorphisms
A maximal automorphism of a structure M is an automorphism under which
no non-algebraic element of M is fixed. A problem which has attracted
some attention is when for a theory T any countable recursively
saturated model of T has a maximal automorphism. In this talk I will
prove a general result that guarantees, under certain mild conditions
on T, that any countable recursively saturated model of T does indeed
have a maximal automorphism.

CUNY Logic Workshop
Friday, March 1, 2013 2:00 pm
Speaker: Tin Lok Wong Ghent University
Title: Understanding genericity for cuts
In a nonstandard model of arithmetic, initial segments with no maximum
elements are traditionally called cuts. It is known that even if we
restrict our attention to cuts that are closed under a fixed family of
functions (e.g., multiplication, the primitive recursive functions, or
the Skolem functions), the properties of cuts can still vary greatly.
I will talk about what genericity means amongst such great variety.
This notion of genericity comes from a version of model theoretic
forcing devised by Richard Kaye in his 2008 paper. Some ideas were
already implicit in the work by Laurence Kirby and Jeff Paris on
indicators in the 1970s.

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.

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
$(P,e,F)$ is isomorphic to the natural number system $(N,0,S)$. In
statements. We will first do reverse mathematics over $RCA_0$, and