Computational Logic Seminar
Tuesday, February 19, 2013 2:00 pm
Speaker: Sergei Artemov The CUNY Graduate Center
Title: On model reasoning in epistemic scenarios
It was long noticed that the textbook “solution” of the Muddy Children
puzzle MC via reasoning on the n-dimensional cube Q_n had a
fundamental gap since it presupposed common knowledge of the Kripke
model Q_n which was not assumed in the puzzle description. In the MC
scenario, the verbal description and logical postulates are common
knowledge, but this does not yield common knowledge of the model.
Of course, a rigorous solution of MC can be given by a formal
deduction in an appropriate epistemic logic with updates after
epistemic actions (public announcements). This way requires an
advanced and generally accepted logical apparatus, certain deductive
skills in modal logic, and, most importantly, steers away from the
We argue that the gap in the textbook “solution” of MC can be fixed.
We establish that MC_n is complete with respect to Q_n and hence a
reasoning on Q_n can be accepted as a substitute for the
aforementioned deductive solution (given that kids are smart enough to
establish that this completeness theorem is itself common knowledge).
This yields the following clean solution of MC:
1. prove the completeness of MC_n w.r.t. Q_n;
2. argue that (1) is common knowledge;
3. use a properly worded version of the textbook “solution.”
This approach seems to work for some other well-known epistemic
scenarios related to knowledge. However, it does not appear to be
universal, e.g., it does not work in the case of beliefs. In general,
we have to rely on the deductive solution which fits the syntactic
description of the problem.
The completeness of MC_n w.r.t. Q_n was established by me some years
ago, and shortly after my corresponding seminar presentation, Evan
Goris offered an elegant and more general solution which will be
presented at this talk.
Models of PA
Wednesday, February 20, 2013 6:45 pm
Speaker: Erez Shochat St. Francis College
Title: Introduction to interstices and intersticial gaps
Let M be a model of PA for which Th(M) is not Th(N) (N is the standard
model). Then M has nonstandard definable elements. Let c be a
non-definable element. The largest convex set which contains c and no
definable elements is called the interstice around c. In this talk we
discuss various properties of interstices. We also define intersticial
gaps which are special subsets of interstices. We show that the set of
the intersticial gaps which are contained in any given interstice of a
countable arithmetically saturated model of PA is a dense linear
Model theory seminar
Friday, February 22, 2013 12:30 pm
Speaker: Roman Kossak The City University of New York
Resplendence is a very useful form of second order saturation.
Transplendence, introduced by Fredrik Engström and Richard Kaye, is a
stronger notion, that guarantees existence of expansions omitting a
type. I will give motivation and outline Engström and Kaye’s general
theory of transplendent structures.
CUNY Logic Workshop
Friday, February 22, 2013 2:00 pm
Speaker: Alf Dolich The City University of New York
Title: Very NIP Ordered Groups
In recent years there has been renewed interest in theories without
the independence property (NIP theories), a class of theories
including all stable as well as all o-minimal theories. In this talk
we concentrate on theories, T, which expand that of divisible ordered
Abelian groups (a natural situation to consider if one is motivated by
the study of o-minimal theories) and consider the problem determining
the consequences of assuming that T is NIP on the structure of
definable sets in models of T. One quickly realizes that given the
great generality of the NIP assumption in order to address this type
of question one wants to consider much stronger variants of not having
the independence property. Thus we are led to the study of definable
sets in models of theories T expanding that of divisible ordered
Abelian groups satisfying various very strong forms of the NIP
condition such as finite dp-rank, convex orderability, and VC
minimality. In this talk I will survey results in this area and
discuss many open problems.
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.