This Week in Logic at CUNY

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.

Leave a Reply

Your email address will not be published. Required fields are marked *

Time limit is exhausted. Please reload CAPTCHA.