Welcome to New York Logic

Welcome to New York Logic!

Jan 31 Saturday Feb 1 Sunday Feb 2 Monday Feb 3 Tuesday Feb 4 Wednesday Feb 5 Thursday Feb 6 Friday

go to the Calendar

 

Upcoming talks and events:

Set theory seminarFriday, February 6, 201510:00 amGC 6417
Sheila Miller

Critical sequences of rank-to-rank embeddings and a tower of finite left distributive algebras: Part II

City Tech - CUNY

The speaker will continue to discuss the properties of rank-into-rank embeddings and their connections to the study of the tower of finite left-distributive algebras known as Laver Tables.

Friday, February 6, 201511:00 amGC 4102 (Science Center)
Alexander Mikhalyov

Elementary equivalence of derivative structures of classical and universal algebras and second order logic

Lomonosov Moscow State University

We give a survey of results in this direction for last 50-60 years (with some accents on recent results on elementary equivalence of endomorphism rings and automorphism groups of Abelian p-groups (E. I. Bunina, A. V. Mikhalev, and M. Royzner, 2013-2014).

Model theory seminarFriday, February 6, 201512:30 pmGC 4102 (Science Center)Note different location (this week only).
Alexei Miasnikov

Model theory and algebraic geometry in groups and algebras

Stevens Institute of Techology

We consider some fundamental model-theoretic questions that can be asked about a given algebraic structure (a group, a ring, etc.), or a class of structures, to understand its principal algebraic and logical properties. These Tarski type questions include: elementary classification and decidability of the first-order theory.

In the case of free groups we proved (in 2006) that two non-abelian free groups of different ranks are elementarily equivalent, classified finitely generated groups elementarily equivalent to a finitely generated free group (also done by Sela) and proved decidability of the first-order theory.

We describe partial solutions to Tarski’s problems in the class of free associative and Lie algebras of finite rank and some open problems. In particular, we will show that unlike free groups, two free associative algebras of finite rank over the same field are elementarily equivalent if and only if they are isomorphic. Two free associative algebras of finite rank over different infinite fields are elementarily equivalent if and only if the fields are equivalent in the weak second order logic, and the ranks are the same. We will also show that for any field the theory of a free associative algebra is undecidable.

These are joint results with O. Kharlampovich

CUNY Logic WorkshopFriday, February 6, 20152:00 pmGC 6417
Franziska Jahnke

Finding definable henselian valuations

Universität Münster

(Joint work with Jochen Koenigsmann.) There has been a lot of recent progress in the area of definable henselian valuations. Here, a valuation is called definable if its valuation ring is a first-order definable subset of the field in the language of rings. Applications of results concerning definable henselian valuations typically include showing decidability of the theory of a field or facts about its absolute Galois group.

We study the question of which henselian fields admit definable henselian valuations with and without parameters. In equicharacteristic 0, we give a complete characterization of henselian fields admitting parameter-definable (non-trivial) henselian valuations. We also give a partial characterization result for the parameter-free case.

Friday, February 6, 20154:50 pmGC 4102 (Science Center)

Computability, computational complexity and geometric group theory

University of Illinois at Urbana-Champaign

The three topics in the title have been inextricably linked since the famous 1912 paper of Max Dehn. In recent years the asymptotic-generic point of view of geometric group theory has given rise to new areas of computability and computational complexity. I will discuss how this arose and then focus on one recent development in computability theory, namely, coarse computability and the coarse computability bound.

Models of PAWednesday, February 11, 20154:50 pmGC 6300
Roman Kossak

Models with the omega-property

The City University of New York

A model M of PA has the omega-property if it has an elementary end extension coding a subset
of M of order type omega. The countable short recursively saturated models are a proper subclass
of the countable models with the omega-property, and both classes share many common
model theoretic properties. For example, they all have automorphism groups of size continuum. I will give a brief survey of what is known about models with the omega-property and I will discuss some open problems.

NY Philosophical Logic GroupThursday, February 12, 20155:00 pmNYU Philosophy Dept.5 Washington Place, Room 302
Melvin Fitting

Justification Logics

Lehman College - CUNY Graduate Center

Gödel inaugurated a project of finding an arithmetic semantics for intuitionistic logic, but did not complete it. It was finished by Sergei Artemov, in the 1990’s. As part of this work, Artemov introduced the first justification logic, LP, (standing for logic of proofs). This is a propositional modal-like logic, with an infinite family of proof or justification terms, and can be seen as an explicit version of the well-known modal logic S4. There is a possible world semantics for LP (due to me). Since then, many other justification logic/modal logic pairs have been investigated, and justification logic has become a subject of independent interest, going beyond the original connection with intuitionistic logic. It is now known that there are infinitely many justification logics, but the exact extent of the family is not known. Justification logics are connected with their corresponding modal logics via Realization Theorems. A Realization Theorem connecting LP and S4 has a constructive proof, but there are other cases for which realization holds, but it is not known if a constructive proof exists. More recently, a first order version of LP has been developed, but I will not talk about it in detail. I will present a sketch of the basic propositional ideas.

CUNY Logic WorkshopFriday, February 13, 20152:00 pmGC 6417
Petr Glivický

Definability in linear fragments of Peano arithmetic

Charles University

In this talk, I will give an overview of recent results on linear arithmetics with main focus on definability in their models. Here, for a cardinal k, the k-linear arithmetic (LAk) is a full-induction arithmetical theory extending Presburger arithmetic by k non-standard scalars (= unary functions of multiplication by distinguished elements). The hierarchy of linear arithmetics lies between Presburger and Peano arithmetics and stretches from tame to wild.

I will present a quantifier elimination result for LA1 and give a complete characterisation of definable sets in its models. On the other hand, I will construct an example of a model of LA2 (or any LAk with k at least 2) where multiplication is definable on a non-standard initial segment (and thus no similar quantifier elimination is possible).

There is a close connection between models of linear arithmetics and certain discretely ordered modules (as each model of a linear arithmetic naturally corresponds to a discretely ordered module over the ordered ring generated by the scalars) which allows to construct wild (e.g. non-NIP) ordered modules. On the other hand, the quantifier elimination result for LA1 implies interesting properties of the structure of saturated models of Peano arithmetic.

Models of PAWednesday, February 18, 20154:50 pmGC 6300
Petr Glivický

Definability in linear fragments of Peano arithmetic I

Charles University

In this series of talks, I will provide an analysis of definable sets in models of linear arithmetics. Here, for a cardinal k, the k-linear arithmetic (LA_k) is a full-induction arithmetical theory extending Presburger arithmetic by k non-standard scalars (= unary functions of multiplication by distinguished elements). Note that each model of a linear arithmetic naturally corresponds to a discretely ordered module over the ordered ring generated by the scalars.

I will prove a quantifier elimination result (QE up to disjunctions of bounded pp-formulas) for LA_1 and give a complete characterisation of definable sets in its models. On the other hand, I will construct an example of a model of LA_2 (or any LA_k with k at least 2) where multiplication is definable on a non-standard initial segment (and thus no pp-elimination is possible). Finally, I will show that all the theories LA_k satisfy quantifier elimination (at least) up to bounded formulas.

I will mention several applications and corollaries of these results including a construction of a non-NIP ordered module, or a result on automorphisms in saturated models of PA.

Set theory seminarFriday, February 20, 201511:00 amGC 6417
Arthur W. Apter

The tall and measurable cardinals can coincide on a proper class

The City University of New York

Starting from an inaccessible limit of strong cardinals, we force to construct a model containing a proper class of measurable cardinals in which the tall and measurable cardinals coincide precisely. This is joint work with Moti Gitik which extends and generalizes an earlier result of Joel Hamkins.

Model theory seminarFriday, February 20, 201512:30 pmGC 6417
Roman Kossak

Coding sets in end extensions

The City University of New York

Much work in the model theory of Peano Arithmetic is based on constructions of elementary end extensions. Let N be an elementary end extension of M. An important isomorphism invariant of the pair (N,M), is Cod(N/M)—the set of intersections with M of the definable subsets of N. For a given model M, one wants to characterize those subsets X of M for which there is an elementary end extension of N of M such that X is in Cod(N/M), and those subsets A of the power set of M for which there is an N, such that A=Cod(N/M). Such characterizations involve properties of subsets of M, but also, a bit surprisingly, properties of M itself. I will talk about some old and some new results in this area.

CUNY Logic WorkshopFriday, February 20, 20152:00 pmGC 6417
Linda Brown Westrick

Title TBA

University of Connecticut
Models of PAWednesday, February 25, 20154:50 pmGC 6300
Petr Glivický

Definability in linear fragments of Peano arithmetic II

Charles University

In this series of talks, I will provide an analysis of definable sets in models of linear arithmetics. Here, for a cardinal k, the k-linear arithmetic (LA_k) is a full-induction arithmetical theory extending Presburger arithmetic by k non-standard scalars (= unary functions of multiplication by distinguished elements). Note that each model of a linear arithmetic naturally corresponds to a discretely ordered module over the ordered ring generated by the scalars.

I will prove a quantifier elimination result (QE up to disjunctions of bounded pp-formulas) for LA_1 and give a complete characterisation of definable sets in its models. On the other hand, I will construct an example of a model of LA_2 (or any LA_k with k at least 2) where multiplication is definable on a non-standard initial segment (and thus no pp-elimination is possible). Finally, I will show that all the theories LA_k satisfy quantifier elimination (at least) up to bounded formulas.

I will mention several applications and corollaries of these results including a construction of a non-NIP ordered module, or a result on automorphisms in saturated models of PA.

Models of PAWednesday, March 4, 20154:50 pmGC 6300
Petr Glivický

Definability in linear fragments of Peano arithmetic III

Charles University

In this series of talks, I will provide an analysis of definable sets in models of linear arithmetics. Here, for a cardinal k, the k-linear arithmetic (LA_k) is a full-induction arithmetical theory extending Presburger arithmetic by k non-standard scalars (= unary functions of multiplication by distinguished elements). Note that each model of a linear arithmetic naturally corresponds to a discretely ordered module over the ordered ring generated by the scalars.

I will prove a quantifier elimination result (QE up to disjunctions of bounded pp-formulas) for LA_1 and give a complete characterisation of definable sets in its models. On the other hand, I will construct an example of a model of LA_2 (or any LA_k with k at least 2) where multiplication is definable on a non-standard initial segment (and thus no pp-elimination is possible). Finally, I will show that all the theories LA_k satisfy quantifier elimination (at least) up to bounded formulas.

I will mention several applications and corollaries of these results including a construction of a non-NIP ordered module, or a result on automorphisms in saturated models of PA.

CUNY Logic WorkshopFriday, March 6, 20152:00 pmGC 6417
Karen Lange

Title TBA

Wellesley College
CUNY Logic WorkshopFriday, March 13, 20152:00 pmGC 6417
Sergei Starchenko

TBA

University of Notre Dame
CUNY Logic WorkshopFriday, March 20, 20152:00 pmGC 6417
Johanna Franklin

Title TBA

Hofstra University
Model theory seminarFriday, May 8, 201512:30 pmGC 6417
Leah Marshall

Title TBA

George Washington University
Kolchin seminar in Differential AlgebraFriday, May 22, 201510:15 amGC 5382

Title TBA

University of Illinois at Urbana-Champaign