**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

textbook “solution.”

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

Link:

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

order.

**Model theory seminar**

** Friday, February 22, 2013 12:30 pm**

Speaker: Roman Kossak The City University of New York

Title: Transplendence

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.