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 

Feb 6, 201511:00 am

→ go to the Calendar
Upcoming talks and events:
Critical sequences of ranktorank embeddings and a tower of finite left distributive algebras: Part II
The speaker will continue to discuss the properties of rankintorank embeddings and their connections to the study of the tower of finite leftdistributive algebras known as Laver Tables.
Elementary equivalence of derivative structures of classical and universal algebras and second order logic
We give a survey of results in this direction for last 5060 years (with some accents on recent results on elementary equivalence of endomorphism rings and automorphism groups of Abelian pgroups (E. I. Bunina, A. V. Mikhalev, and M. Royzner, 20132014).
Model theory and algebraic geometry in groups and algebras
We consider some fundamental modeltheoretic 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 firstorder theory.
In the case of free groups we proved (in 2006) that two nonabelian 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 firstorder 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
Finding definable henselian valuations
(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 firstorder 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 parameterdefinable (nontrivial) henselian valuations. We also give a partial characterization result for the parameterfree case.
Computability, computational complexity and geometric group theory
The three topics in the title have been inextricably linked since the famous 1912 paper of Max Dehn. In recent years the asymptoticgeneric 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 with the omegaproperty
A model M of PA has the omegaproperty 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 omegaproperty, 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 omegaproperty and I will discuss some open problems.
Justification Logics
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 modallike logic, with an infinite family of proof or justification terms, and can be seen as an explicit version of the wellknown 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.
Definability in linear fragments of Peano arithmetic
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 klinear arithmetic (LA_{k}) is a fullinduction arithmetical theory extending Presburger arithmetic by k nonstandard 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 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 nonstandard 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. nonNIP) ordered modules. On the other hand, the quantifier elimination result for LA_{1} implies interesting properties of the structure of saturated models of Peano arithmetic.
Definability in linear fragments of Peano arithmetic I
In this series of talks, I will provide an analysis of definable sets in models of linear arithmetics. Here, for a cardinal k, the klinear arithmetic (LA_k) is a fullinduction arithmetical theory extending Presburger arithmetic by k nonstandard 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 ppformulas) 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 nonstandard initial segment (and thus no ppelimination 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 nonNIP ordered module, or a result on automorphisms in saturated models of PA.
The tall and measurable cardinals can coincide on a proper class
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.
Coding sets in end extensions
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.
Definability in linear fragments of Peano arithmetic II
In this series of talks, I will provide an analysis of definable sets in models of linear arithmetics. Here, for a cardinal k, the klinear arithmetic (LA_k) is a fullinduction arithmetical theory extending Presburger arithmetic by k nonstandard 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 ppformulas) 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 nonstandard initial segment (and thus no ppelimination 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 nonNIP ordered module, or a result on automorphisms in saturated models of PA.
Definability in linear fragments of Peano arithmetic III
In this series of talks, I will provide an analysis of definable sets in models of linear arithmetics. Here, for a cardinal k, the klinear arithmetic (LA_k) is a fullinduction arithmetical theory extending Presburger arithmetic by k nonstandard 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 ppformulas) 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 nonstandard initial segment (and thus no ppelimination 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 nonNIP ordered module, or a result on automorphisms in saturated models of PA.