This Week in Logic at CUNY:

**Computational Logic Seminar**

Time 2:00 – 4:00 PM, May 15, Room 3209.

Speaker: Grigory Olkhovikov (Stanford)

Title: Failure of interpolation for intuitionistic logic of constant domains

Abstract: Intuitionistic logic CD of constant domains is axiomatized

by adding the schema (Ax)(C v A(x)) => C v (Ax)A(x) (x is not free in

C) to familiar axiomatization of intuitionistic predicate logic. CD is

sound and complete for Kripke semantics with constant individual

domains. Interpolation theorem says that for any provable implication

A=>B there is an interpolant I such that A=>I and I=>B are both

provable, and I contains only predicates common to A and B.

There are at least two claimed proofs of the interpolation theorem for

CD, both published in The Journal of Symbolic Logic (v. 42, 1977 and

v.46, 1981). We prove that in fact interpolation theorem fails for CD:

provable implication

((Ax)(Ey)(Py & (Qy=>Rx)) & ~(Ax)Rx) => ((Ax)(Px=>(Qx v r))=>r)

does not have an interpolant. We are also going to cover in more or

less detail the proof of Beth definability failure in CD which is a

natural strengthening of the non-interpolation result and is obtained

by a similar technique.

– – – – Wednesday, May 16, 2012 – – – –

**Models of Peano Arithmetic**

Wednesday, May 16, 2012 6:30 pm Room 4214-03

Professor Ali Enayat (American University)

From Friedman to Tanaka, and beyond

Abstract. This is a preliminary report of recent joint work with

Volodya Shavrukov on self-embeddings of nonstandard models of

arithmetic onto initial segments of themselves. I will give a survey

of the topic by presenting a unified method of establishing the known

results, and will then discuss a number of new results.

– – – – Friday, May 18, 2012 – – – –

**Set Theory Seminar**

Friday, May 18, 2012 10:00 am GC 6417

Professor Joel David Hamkins (The City University of New York)

The omega one of infinite chess

Abstract. Infinite chess is chess played on an infinite edgeless

chessboard. The familiar chess pieces move about according to their

usual chess rules, and each player strives to place the opposing king

into checkmate. The mate-in-n problem of infinite chess is the problem

of determining whether a designated player can force a win from a

given finite position in at most n moves. A naive formulation of this

problem leads to assertions of high arithmetic complexity with 2n

alternating quantifiers—there is a move for white, such that for every

black reply, there is a countermove for white, and so on. In such a

formulation, the problem does not appear to be decidable; and one

cannot expect to search an infinitely branching game tree even to

finite depth. Nevertheless, in joint work with Dan Brumleve and

Philipp Schlicht, confirming a conjecture of myself and C. D. A.

Evans, we establish that the mate-in-n problem of infinite chess is

computably decidable, uniformly in the position and in n .

Furthermore, there is a computable strategy for optimal play from such

mate-in-n positions. The proof proceeds by showing that the mate-in-n

problem is expressible in what we call the first-order structure of

chess, which we prove (in the relevant fragment) is an automatic

structure, whose theory is therefore decidable. An equivalent account

of the result arises from the realization that the structure of chess

is interpretable in the standard model of Presburger arithmetic

. Unfortunately, this resolution of the mate-in-n problem does

not appear to settle the decidability of the more general

winning-position problem, the problem of determining whether a

designated player has a winning strategy from a given position, since

a position may admit a winning strategy without any bound on the

number of moves required. This issue is connected with transfinite

game values in infinite chess, and the exact value of the omega one of

chess ω1^chess is not known. I will also discuss recent joint work

with C. D. A. Evans and W. Hugh Woodin showing that the omega one of

infinite positions in three-dimensional infinite chess is true ω1:

every countable ordinal is realized as the game value of such a

position.

**Model Theory Seminar**

Friday, May 18, 2012 12:30 pm GC 6417

Mr. Manuel Alves (Ph.D. Program in Mathematics, Graduate Center of CUNY)

Morphic rings and modules

Abstract. Following Nicholson and Sanchez Campos (2004), a ring is

morphic when it satisfies the following dual of the isomorphism

theorem: for every ring element a, the left module R/Ra is isomorphic

to the left annihilator l(a). These rings (and an obvious

generalization to modules) will be introduced and it will be shown how

they lend themselves to an investigation using Prest’s elementary

duality for pp formulas, as introduced in an earlier talk of this

semester’s seminar.

**Logic Workshop**

Friday, May 18, 2012 2:00 pm GC 6417

Professor Joel David Hamkins (The City University of New York)

The countable models of ZFC, up to isomorphism, are linearly ordered

by the submodel relation; every countable model of ZFC is isomorphic

to a submodel of its own L

Abstract. A remarkable 1983 result of Ressayre shows that if M is any

nonstandard model of PA, with the corresponding nonstandard hereditary

finite sets , then for any consistent computably

axiomatized theory T in the language of set theory, there is a

submodel N ⊂ such that N ⊨ T. In particular, one may find

models of ZFC or even ZFC + large cardinals as submodels of HF^M, a

land where everything is thought to be finite. Incredible! Ressayre’s

proof uses partial saturation and resplendency to prove that one can

find the submodel of the desired theory T.

I will present a strengthening of Ressayre’s theorem, omitting the

need to consider T. The fact is that the nonstandard models of finite

set theory are universal for all countable acyclic binary relations:

Theorem.(JDH) Every countable model of set theory is isomorphic to a

submodel of any nonstandard model of finite set theory. Indeed, the

nonstandard models of finite set theory are each universal for all

countable acyclic binary relations.

The proof involves the construction of what I call the countable

random Q-graded digraph, a countable homogeneous acyclic digraph that

is universal for all countable acyclic digraphs. Having realized this

universal digraph as a submodel of the nonstandard model , it

follows that every countable structure with an acyclic binary

relation, including every countable model of ZFC, is realized as a

submodel of M. The proof idea adapts, with complications, to the case

of well-founded models, via the countable random λ-graded digraph, as

well as the internal construction of what I call the hypnagogic

digraph, a proper class homogeneous surreal-numbers-graded digraph,

which is universal for all class acyclic digraphs.

Theorem.(JDH) Every countable model of ZFC, including the

transitive models, is isomorphic to a submodel of its own

constructible universe . In other words, there is an

embedding j:M → L^M that is quantifier-free-elementary.

Corollary.(JDH) The countable models of ZFC are linearly ordered and

even well-ordered, up to isomorphism, by the submodel relation.

Namely, any two countable models of ZFC with the same well-founded

height are bi-embeddable as submodels of each other, and all models

embed into any nonstandard model.

The embedding j of the theorem is constructed completely external to

M. This leads to numerous questions on the extent to which we may

expect in ZFC that V might be isomorphic to a subclass of L. To what

extent can we expect to have or to refute embeddings j:V → L,

elementary for quantifier-free assertions?

To subscribe/unsubscribe to this list, please email your request to

jreitz@nylogic.org.

If you have a logic-related event that you would like included in

future mailings, please email jreitz@nylogic.org.