# Welcome to New York Logic

Welcome to New York Logic!

Nov 30 Monday Dec 1 Tuesday Dec 2 Wednesday Dec 3 Thursday Dec 4 Friday Dec 5 Saturday Dec 6 Sunday

Dec 1, 201512:00 pm
Models of PADec 2, 20156:30 pm
Set theory seminarDec 4, 201510:00 am
Model theory seminarDec 4, 201512:30 pm

go to the Calendar

## Upcoming talks and events:

Tuesday, December 1, 201512:00 pmBronx Community College, room CP 305Research Seminar, Mathematics and Computer Science Department of BCC.

# Computability problems in number theory

City University of New York

We will consider several number-theoretic questions which arise from computable model theory. One of these, recently solved by Poonen, Schoutens, Shlapentokh, and the speaker, involves attempting to “embed” a graph into a field: given a graph, one wishes to construct a field with the exact same computable-model-theoretic properties as the graph. (For instance, the automorphisms of the graph should correspond to the automorphisms of the field, by a bijective functorial correspondence which preserves the Turing degree of each automorphism.) Another arises out of consideration of Hilbert’s Tenth Problem for subrings of the rationals: we ask for subrings in which Hilbert’s Tenth Problem is no harder than it is for the rationals themselves. This is known for semilocal subrings, and Eisenträger, Park, Shlapentokh and the speaker have shown that it holds for certain non-semilocal subrings as well, but it remains open whether one can invert “very few” primes and still have it hold. We will explain this problem and discuss the number-theoretic question which arises out of it.

Computational Logic SeminarTuesday, December 1, 20152:00 pmGraduate Center, rm. 3309

# An Arithmetical Interpretation of Verification and Intuitionistic Knowledge

Intuitionistic epistemic logic, IEL, introduces to intuitionistic logic an epistemic operator which reflects the intended BHK semantics of intuitionism. The fundamental assumption concerning intuitionistic knowledge and belief is that it is the product of verification. The BHK interpretation of intuitionistic logic has a precise formulation in the Logic of Proofs, LP, and its arithmetical semantics. We show here that the Gödel embedding, realization, and an arithmetical interpretation can all be extended to S4 and LP extended with a verification modality, thereby providing intuitionistic epistemic logic with an arithmetical semantics too.

Models of PAWednesday, December 2, 20156:30 pmGC 4214-03

# Loftiness V

The City University of New York

A class C of countable models of PA is countably PC*_δ if there is a theory T in a countable language extending PA* such that for every countable model M of PA, M is in C if and only M is expandable to a model of T. The class of countable recursively saturated models of PA is countably PC*_δ, and Kaufman and Schmerl showed that many other natural classes, including the class uniformly ω-lofty models, are not. I will go over the proof of the Kaufman-Schmerl result, and I will discuss other potential approaches to characterizing classes of models of PA via expandability.

Set theory seminarFriday, December 4, 201510:00 amGC 3212

# Jónsson cardinals and club guessing

Ohio University

We say that a cardinal $\lambda$ is a Jónsson cardinal if it satisfies the following weak Ramsey-type property: given any coloring $F:[\lambda]^{<\omega}\to \lambda$ of the finite subsets of $\lambda$ in $\lambda$-many colors, there exists a set $H\in[\lambda]^\lambda$ such that the range of $F\upharpoonright [H]^{<\omega}$ is a proper subset of $\lambda$. One of the big driving forces present in early chapters Cardinal Arithmetic is an attempt to understand the combinatorial structure at and around Jónsson cardinals using scales and club guessing. The goal of this talk is to highlight the connection between Jónsson cardinals and the existence of certain sorts of club guessing ideals. Our focus will be on how club guessing ideals interact with Jónssonness at successors of singulars.

Model theory seminarFriday, December 4, 201512:30 pmGC 6417

# Zero-one laws for discrete metric spaces

University of Illinois Chicago

Fix an integer $r \geq 3$. Given an integer $n$, we define $M_r(n)$ to be the set of metric spaces with underlying set ${1,\ldots,n}$ such that the distance between any two points lies in ${1,\ldots,r}$. We present results describing the approximate structure of these metric spaces when $n$ is large. As a consequence of these structural results in the case when $r$ is even, we obtain a first-order labeled $0$-$1$ law. This is joint work with Dhruv Mubayi.

CUNY Logic WorkshopFriday, December 4, 20152:00 pmGC 6417

# Hilbert’s Tenth Problem inside the rationals

City University of New York

For a ring R, Hilbert’s Tenth Problem is the set HTP(R) of polynomials f ∈ R[X1,X2,…] for which f=0 has a solution in R. Matiyasevich, completing work of Davis, Putnam, and Robinson, showed that HTP(Z) is Turing-equivalent to the Halting Problem. The Turing degree of HTP(Q) remains unknown. Here we consider the problem for subrings of Q. One places a natural topology on the space of such subrings, which is homeomorphic to Cantor space. This allows consideration of measure theory and also Baire category theory. We prove, among other things, that HTP(Q) computes the Halting Problem if and only if HTP(R) computes it for a nonmeager set of subrings R.

Model theory seminarFriday, December 11, 201512:30 pmGC 6417

# Scott ranks of models of a theory

University of California Berkeley

I will talk about a few different results about the Scott ranks of models of a theory. (By a theory, I mean a sentence of Lω1ω.) These results are all related in that they all follow from the same general construction; this construction takes a pseudo-elementary class C of linear orders and produces a theory T such that the Scott ranks of models of T are related to the well-founded parts of linear orders in C.

The main result is a descriptive-set-theoretic classification of the collections of ordinals which are the Scott spectrum of a theory. We also answer some open questions. First, we show that for each ordinal β, there is a Π20 theory which has no models of Scott rank less than β. Second, we find the Scott height of computable infinitary sentences. Third, we construct a computable model of Scott rank ω1CK+1 which is not approximated by models of low Scott rank.

CUNY Logic WorkshopFriday, December 11, 20152:00 pmGC 6417

# Ramsey theory and topological dynamics

Universidade de São Paulo

I will introduce two prominent dynamical systems for a given toplogical group, the greatest ambit and the universal minimal flow, as spaces of (near) ultrafilters on certain Boolean algebras. Representing a topological group as a group of isometries of a highly symmetric structure, I will hint how metrizability and triviality of the universal minimal flow is linked to the (approximate) structural Ramsey property. My focus will lie on problems that arise in the study of universal minimal flows in Ramsey theory, model theory, set theory and continuum theory.