# CUNY Logic Workshop

The CUNY Logic Workshop is a weekly seminar in mathematical logic at the CUNY Graduate Center.
(63 items)

CUNY Logic WorkshopFriday, May 9, 20142:00 pmGC 6417

# The domatic numbers of computable graphs

Manhattan College

A dominating set $D$ of a graph is a set of vertices “near” all other vertices, in that every vertex outside of $D$ is adjacent to a vertex in $D$. In this talk, we will compare two values associated with a graph $G$: the domatic number $d(G)$ and computable domatic number $d^c(G)$, which give the size of the largest partition and computable partition (respectively) of $G$ into dominating sets. Our goal is to maximize the value of $d(G)-d^c(G)$ for highly computable graphs (in which we can computably count each vertex’s neighbors). Specifically, is it even possible for this difference to be greater than 1? To find an answer, we will work with total dominating sets (where $D$ must now be near all vertices, instead of only the ones outside of $D$) and regular graphs (where each vertex has exactly the same number of neighbors). In our proofs and constructions, we will play the “game” of computable graph theory, as we set up gadgets and spring traps against adversaries who are determined to thwart our every move.

The slides for the talk are available here.

CUNY Logic WorkshopFriday, May 2, 20142:00 pmGC 6417

# A natural strengthening of Kelley-Morse set theory

The City University of New York

I shall introduce a natural strengthening of Kelley-Morse set theory KM to the theory we denote KM+, by including a certain class collection principle, which holds in all the natural models usually provided for KM, but which is not actually provable, we show, in KM alone.  The absence of the class collection principle in KM reveals what can be seen as a fundamental weakness of this classical theory, showing it to be less robust than might have been supposed.  For example, KM proves neither the Łoś theorem nor the Gaifman lemma for (internal) ultrapowers of the universe, and furthermore KM is not necessarily preserved, we show, by such ultrapowers.  Nevertheless, these weaknesses are corrected by strengthening it to the theory KM+.  The talk will include a general elementary introduction to the various second-order set theories, such as Gödel-Bernays set theory and Kelley-Morse set theory, including a proof of the fact that KM implies Con(ZFC). This is joint work with Victoria Gitman and Thomas Johnstone.

CUNY Logic WorkshopFriday, April 25, 20142:00 pmGC 6417

# Maximal Automorphisms

The City University of New York

Given a model M, a maximal automorphism is one which fixes as few points in M as possible. We begin by outlining what the correct definition of “as few points as possible” should be and then proceed to study the notion. An interesting question arises when one considers the existence of maximal automorphisms of countable recursively saturated models. In particular an interesting dichotomy arises when one asks whether for a given theory T all countable recursively saturated models of T have a maximal automorphism. Our primary goal is to determine which classes of theories T lie on the positive side of this dichotomy. We give several examples of such classes. Attacking this problem requires a detailed understanding of recursive saturation, which we will also review in this talk.

CUNY Logic WorkshopFriday, April 4, 20142:00 pmGC 6417

# The lattice problem

The City University of New York

Ordered by inclusion, the set of elementary substructures of a model of PA is a lattice.
It is an ℵ1-compactly generated lattice, meaning that every element of the lattice is a supremum of its compact elements, and for every compact element, there are at most countably many compact elements below it. The lattice problem for models of PA is to determine which lattices can be represented as lattices of elementary substructures of a model of PA. The condition above puts a restriction on the types of lattices that can be represented this way. As far as we know, this can be the only restriction. Much work on the problem has been done in the 1970s by Gaifman, Knight, Mills, Paris, Schmerl, and Wilkie, and has been continued by Schmerl. It involves some specialized knowledge of models of PA, highly nontrivial lattice representation theory, combinatorics, and sometimes number theory. There are many positive results, but we still do not know if there is a finite lattice which cannot be represented as a substructure lattice of a model of PA. My talk will be an introduction to the lattice problem. I’ll introduce basic definitions and I’ll prove a couple of introductory negative results.

Friday, March 28, 201412:30 pm

# Model theoretic advances for groups with bounded chains of centralizers

Fairfield University

Stable groups have a rich literature, extending ideas about algebraic groups to a wider setting, using the framework of model theory. Stable groups gain much of their strength through their chain conditions, notably the Baldwin-Saxl chain condition. In this talk, we will concern ourselves with one mild, yet very important, chain condition shared by many infinite groups studied by group theorists. A group $G$ is said to be $M_C$ if every chain of centralizers $C_G(A_1)$ ≤ $C_G(A_2)$ ≤ ⋅ ⋅ ⋅ is finite. This class is not elementary, yet there is increasing evidence that they share many important properties of stable groups. All the present results concern nilpotence in $M_C$ groups. The first results in this area were purely group-theoretic, but recent results by Wagner, Altinel and Baginski have uncovered that some of the desired definability results are also present. We will recount the progress that has been made and the obstacles that researchers in this area face.

CUNY Logic WorkshopFriday, March 21, 20142:00 pmGC 6417

# The search for computable domatic partitions

Manhattan College

A domatic $k$-partition of a graph is a partition of the vertex set into $k$ many classes, in which each vertex $v$ is adjacent to some vertex in every partition class of which $v$ is not a member; the domatic number is the largest $k$ for which there is a domatic $k$-partition (compare to the chromatic number of a graph, which is the size of the smallest partition into independent sets). The authors previously showed that there is a computable, locally finite graph $G$ with a domatic $k$-partition, but no computable domatic $3$-partition. In this talk we will investigate whether the same result holds for highly computable graphs, and $A$-computable graphs (we say a graph $G$ is $A$-computable if $A$ can compute the neighborhood function of $G$). This work is joint with Oscar Levin and Tyler Markkanen.

CUNY Logic WorkshopFriday, March 14, 20142:00 pmGC6417

# Structurability and countable Borel equivalence relations

Rutgers University

The dynamical and descriptive set theoretic complexity of a countable Borel equivalence relation E can often be understood in terms of the kinds of countable first order structures which are compatible with E in a suitable sense. In this talk I will make this suitable sense precise by discussing the notion of Borel structurability. I will also discuss some recent joint work with Brandon Seward in which we show that the equivalence relation generated by the free part of the translation action of a countable group G on its powerset is structurably-universal among equivalence relations generated by free Borel actions of G.

CUNY Logic WorkshopFriday, March 7, 20142:00 pmGC 6417

# Generalized descriptive set theory with very large cardinals

Rutgers University

We will discuss the structure L(Vλ+1) and attempts to generalize facts of descriptive set theory to this structure in the presence of very large cardinals. In particular we will introduce an axiom called Inverse Limit Reflection which we will argue is analogous to the Axiom of Determinacy in this context. The slides for this talk are available here.

CUNY Logic WorkshopFriday, February 28, 20142:00 pmGC 6417

# The theory of fields is complete for isomorphisms

City University of New York

We give a highly effective coding of countable graphs into countable fields. For each countable graph $G$, we build a countable field $F(G)$, uniformly effectively from an arbitrary presentation of $G$. There is a uniform effective method of recovering the graph $G$ from the field $F(G)$. Moreover, each isomorphism $g$ from $G$ onto any $G’$ may be turned into an isomorphism $F(g)$ from $F(G)$ onto $F(G’)$, again by a uniform effective method so that $F(g)$ is computable from $g$. Likewise, an isomorphism $f$ from $F(G)$ onto any $F(G’)$ may be turned back into an isomorphism $g$ with $F(g)=f$. Not every field $F$ isomorphic to $F(G)$ is actually of the form $F(G’)$, but for every such $F$, there is a graph $G’$ isomorphic to $G$ and an isomorphism $f$ from $F$ onto $F(G’)$, both computable in $F$.

It follows that many computable-model-theoretic properties which hold of some graph $G$ will carry over to the field $F(G)$, including spectra, categoricity spectra, automorphism spectra, computable dimension, and spectra of relations on the graph. By previous work of Hirschfeldt, Khoussainov, Shore, and Slinko, all of these properties can be transferred from any other countable, automorphically nontrivial structure to a graph (and then to various other standard classes of structures), so our result may be viewed as saying that, like these other classes, fields are complete for such properties.

This work is properly joint with Jennifer Park, Bjorn Poonen, Hans Schoutens, and Alexandra Shlapentokh. The slides for the talk are available here.

CUNY Logic WorkshopFriday, February 21, 20142:00 pmGC 6417

# The proof/plan correspondence in databases

Oxford University

We consider answering queries over datasources (for logicians: finite relational structures) that are connected to one another by integrity constraints (logical relationships). A relation in a datasource may have multiple means of access with different required arguments, and the means of access within and across relations may differ radically in cost. We present a method for generating the lowest cost query plan, where a plan is a reformulation of the query referencing only the allowable access methods, equivalent to the original query on all datasources satisfying the integrity constraints. A solution to this problem can be applied in many database contexts, including answering queries using views, optimizing queries using constraints, and querying on top of web services or web forms. It could also be applied to give a more logic-based foundation for traditional database query planning.

Proof-driven query reformulation generates plans by applying interpolation procedures to a “proof that the query can be answered,” an approach that goes back at least to Craig’s proof of the Beth Definability theorem via interpolation. A few additional ingredients are needed to apply interpolation to database problems, including:

– variations of Beth Definability that allow us to target plans (explicit definitions) of specific forms

– an extension of interpolation that considers the “access patterns” within quantification

– specialized proof procedures for classes of integrity constraints of interest to databases

– cost-based search procedures for concurrently exploring the collection of proofs and plans

The resulting query planning system blends automated deduction, query optimization, and heuristic search.

This is joint work with Balder ten Cate, Julien Leblay and Efi Tsamoura.

CUNY Logic WorkshopFriday, February 14, 20142:00 pmGC 6417

# Ramsey cardinals and the continuum function

The City University of New York

In his famous theorem, Easton used the Easton Product forcing to show that if $V\models{\rm GCH}$ and $F$ is any weakly increasing function on the regular cardinals such that $\text{cf}(F(\alpha))>\alpha$, then there is a cofinality preserving forcing extension in which $F$ is realized as the continuum function. The investigation then shifted to identifying which continuum patterns are compatible with large cardinals. It is not difficult to see that large cardinals affect the behavior of the continuum function. Obviously, if $\kappa$ is inaccessible, then by definition, the continuum function must have a closure at $\kappa$. Some other large cardinal influences are much more subtle. Easton’s original forcing does not work well in the presence of large cardinals; it, for instance, destroy weak compactness over $L$. So set theorists have had to develop some general and other very specific forcing techniques to address the behavior of the continuum function for a given large cardinal. In this talk, we will show that if $V\models{\rm GCH}$, $\kappa$ is Ramsey, and $F$ is any weakly increasing class function on the regular cardinals with a closure point at $\kappa$ such that $\text{cf}(F(\alpha))>\alpha$, then there is a cofinality preserving forcing extension in which $\kappa$ remains Ramsey and $F$ is realized as the continuum function. This is joint work with Brent Cody.

An extended abstract can be found here.

CUNY Logic WorkshopFriday, February 7, 20142:00 pmGC 6417

# New directions in reverse mathematics

University of Connecticut

Mathematics today benefits from having “firm foundations,” by which we usually mean a system of axioms sufficient to prove the theorems we care about. But given a particular theorem, can we specify precisely which axioms are needed to derive it? This is a natural question, and also an ancient one: over 2000 years ago, the Greek mathematicians were asking it about Euclid’s geometry. Reverse mathematics provides a modern approach to this kind of question. A striking fact repeatedly demonstrated in this area is that the vast majority of mathematical propositions can be classified into just five main types, according to which set-existence axioms are needed to carry out their proofs. But more recently, a growing number of principles falling outside this classification have emerged, whose logical strength is more difficult to understand. These turn out to include many important mathematical results, such as various combinatorial problems related to Ramsey’s theorem, and several set-theoretic equivalents of the axiom of choice. I will discuss some of these “irregular” principles, and some new approaches that have arisen from trying to understand why their strength is so different from that of most other theorems. In particular, this investigation reveals new connections between different mathematical areas, and exposes the rich and complex combinatorial and algorithmic structure underlying mathematics as a whole.

CUNY Logic WorkshopFriday, December 13, 20132:00 pmGC 6417

# Higher-order Reverse Mathematics: Where existence meets computation via infinitesimals.

Department of Mathematics, Ghent University

Classically, the existence of an object tells us very little about how to construct said object.
We consider a nonstandard version of Ulrich Kohlenbach’s higher-order Reverse Mathematics
in which there is a very elegant and direct correspondence between, on one hand, the existence
of a functional computing an object and, on the other hand, the classical existence of this object
with the same standard and nonstandard properties. We discuss how these results -potentially-
contribute to the programs of finitistic and predicativist mathematics.

CUNY Logic WorkshopFriday, December 6, 20132:00 pmGC 6417

# On forcing and the (elusive) free two-generated left distributive algebra

City Tech - CUNY

We begin with an extended introduction to free left distributive algebras (LDs) including a normal form theorem for the one-generated free LD, which itself arises naturally from the assumption of a very large cardinal axiom. After discussing some applications and open problems, we make remarks on the difficulty of using forcing to attempt to construct a two-generated free LD by lifting the rank-to-rank elementary embedding used to create the one-generated free LD.

This is joint work with Joel David Hamkins.

CUNY Logic WorkshopFriday, November 22, 20132:00 pmGC 6417

# Measure semantics for modal logics

Columbia University

Long before Kripke semantics became standard in modal logic, Tarski showed us that the basic propositional modal language can be interpreted in topological spaces. In Tarski’s semantics for the modal logic $S4$, each propositional variable is evaluated to an arbitrary subset of a fixed topological space. I develop a related, measure theoretic semantics, in which modal formulas are interpreted in the Lebesgue measure algebra, or algebra of Borel subsets of the real interval $[0,1]$, modulo sets of measure zero. This semantics was introduced by Dana Scott in the last several years. I discuss some of my own completeness results, and ways of extending the semantics to more complex modal languages.

CUNY Logic WorkshopFriday, November 15, 20132:00 pmGC 6417

# The recursive spectrum of a strongly minimal modular theory of groups in a finite language

City College -- CUNY
CUNY Logic WorkshopFriday, November 8, 20132:00 pmGC 6417

# Prikry-type sequences, iterations and critical sequences

The City University of New York

I will present some old, some new and some classic results on the kinds of sequences which are added by some forcings which are related to Prikry forcing, in some sense. After finding combinatorial properties characterizing these sequences, I will show how to iterate the universe in such a way that the critical sequence of that iteration will satisfy that combinatorial property with respect to the target model, rendering it generic. This connection enables us to analyze precisely the collection of generic sequences which are present in one specific forcing extension. Time permitting, I will also explore connections to Boolean ultrapowers.

CUNY Logic WorkshopFriday, November 1, 20132:00 pmGC 6417

# Reverse VC Calculations

Haverford College

Note Hill’s Workshop talk is cancelled due to illness.

Let F be a family of sets, for example, a uniformly definable semi-algebraic family in real or p-adic n-space. The Vapnik-Chervonenkis (VC) dimension of F is a measurement of the combinatorial complexity of F. Once you know the VC dimension of F, theorems from computational geometry, like the Epsilon-Net Theorem, give nice geometric consequences for F. I will discuss a statistical strategy for reversing the flow of information in this theorem. Instead of starting with knowledge of the VC dimension, we merely hypothesize “dimension=d” for some value d. Then, we observe the geometric behavior of F using computer experiments and compare the observed behavior with the behavior that is predicted by the theorem (under the hypothesis “dimension=d”). If our observed results have sufficiently low probability (conditioned on “dimension=d”), then we can reject the hypothesis “dimension=d” with a high degree of confidence. Ultimately, we hope to use such methods to shed light on conjectures about VC density in the p-adics. This project is joint work with Deirdre Haskell and Nigel Pynn-Coates.

CUNY Logic WorkshopFriday, October 25, 20132:00 pmGC 6417

# Automorphism Groups of Countable, Recursively Saturated Models of Peano Arithmetic

University of Connecticut

It is still unknown whether there are nonisomorphic countable recursively saturated models M and N whose automorphism groups Aut(M) and Aut(N) are isomorphic. I will discuss what has happened over the last 20 years towards showing that such models do not exist, including some very recent results.

CUNY Logic WorkshopFriday, October 18, 20132:00 pmGC 6417

# Generic choice functions and ultrafilters on the integers

Miami University of Ohio

We will discuss a question asked by Stefan Geschke, whether the existence of a selector for the equivalence relation $E_0$ implies the existence of a nonprincipal ultrafilter on the integers. We will present a negative solution which is undoubtedly more complicated than necessary, using a variation of Woodin’s $mathbb{P}_{mathrm{max}}$. This proof shows that, under suitable hypotheses, if $E$ is a universally Baire equivalence relation on the reals, with countable classes, then forcing over $L(E,mathbb{R})$ to add a selector for $E$ does not add a nonprincipal ultrafilter on the integers.

CUNY Logic WorkshopFriday, October 11, 20132:00 pmGC 6417

# Randomness and ergodic theorems under measure-preserving transformations

Hofstra University

Ergodic theorems describe regular measure-theoretic behavior, and a point is said to be algorithmically random if it has no rare measure-theoretic properties of a certain kind. The connections between these two types of regularity have been well studied over the past five years. I will discuss Birkhoff’s ergodic theorem with respect to transformations that are measure-preserving but not necessarily ergodic in the context of a computable probability space. Then I will show that each point in such a space that is not Martin-L”of random does not satisfy Birkhoff’s ergodic theorem with respect to every computable set and measure-preserving transformation.

This work is joint with Henry Towsner.

CUNY Logic WorkshopFriday, October 4, 20132:00 pmGC 6417

# Why model-theorists shouldn’t think that ACF is easy

The City University of New York

We all learned that stability theory derived many of its ideas from what happens in ACF, where everything is nice and easy. After all ACF has quantifier elimination and is strongly minimal, decidable, superstable, uncountably categorical, etc. However, my own struggles with ACF have humbled my opinion about it: it is an awfully rich theory that encodes way more than our current knowledge. I will discuss some examples showing how “difficult” ACF is: Grothendieck ring, isomorphism problem, set-theoretic intersection problem. Oddly enough, RCF seems to not have any of these problems. It is perhaps my ignorance, but I have come to think of RCF as much easier. Well, all, of course, is a matter of taste.

CUNY Logic WorkshopFriday, September 27, 20132:00 pmGC 6417

# Satisfaction is not absolute

The City University of New York

I will discuss a number of theorems showing that the satisfaction relation of first-order logic is less absolute than might have been supposed. Two models of set theory $M_1$ and $M_2$, for example, can agree on their natural numbers $langlemathbb{N},{+},{cdot},0,1,{lt}rangle^{M_1}=langlemathbb{N},{+},{cdot},0,1,{lt}rangle^{M_2}$, yet disagree on arithmetic truth: they have a sentence $sigma$ in the language of arithmetic that $M_1$ thinks is true in the natural numbers, yet $M_2$ thinks $negsigma$ there. Two models of set theory can agree on the natural numbers $mathbb{N}$ and on the reals $mathbb{R}$, yet disagree on projective truth. Two models of set theory can have the same natural numbers and have a computable linear order in common, yet disagree about whether this order is well-ordered. Two models of set theory can have a transitive rank initial segment $V_delta$ in common, yet disagree about whether this $V_delta$ is a model of ZFC. The theorems are proved with elementary classical methods.

This is joint work with Ruizhi Yang (Fudan University, Shanghai). We argue, on the basis of these mathematical results, that the definiteness of truth in a structure, such as with arithmetic truth in the standard model of arithmetic, cannot arise solely from the definiteness of the structure itself in which that truth resides; rather, it must be seen as a separate, higher-order ontological commitment.

CUNY Logic WorkshopFriday, September 20, 20132:00 pm

# A survey of the model theory of tracial von Neumann algebras

University of Illinois Chicago

Von Neumann algebras are certain algebras of bounded operators on Hilbert spaces. In this talk we will survey some of the model theoretic results about (tracial) von Neumann algebras, focusing mainly on (in)stability, quantifier-complexity, and decidability. No prior knowledge of von Neumann algebras will be necessary. Some of the work presented is joint with Ilijas Farah, Bradd Hart, David Sherman, and Thomas Sinclair.

CUNY Logic WorkshopFriday, May 10, 20132:00 pmGC 6417

# What is the theory ZFC without power set?

The New York City College of Technology (CityTech), CUNY

The theory ZFC-, consisting of the usual axioms of ZFC but with the power set axiom removed — specifically axiomatized by extensionality, foundation, pairing, union, infinity, separation, replacement and the assertion that every set can be well-ordered — is weaker than commonly supposed and is inadequate to establish several basic facts often desired in its context.

For example, there are models of ZFC- in which a countable union of countable sets is not countable. There are models of ZFC- for which the Los ultrapower theorem fails, even for wellfounded ultrapowers on a measurable cardinal. Moreover, the theory ZFC- is not sufficient to establish that the union of Σn and Πn sets is closed under bounded quantification. Lastly, there are models of ZFC- for which the Gaifman theorem fails, in that there exists cofinal embeddings j:M–>N between ZFC- models that are Σ1-elementary, but not fully elementary.

Nevertheless, these deficits of ZFC- are completely repaired by strengthening it to the theory obtained by using collection rather than replacement in the axiomatization above. This is joint work with Joel David Hamkins and Victoria Gitman, and it extends prior work of Andrzej Zarach.

arxiv preprint | post at jdh.hamkins.org | post on Victoria Gitman’s blog

CUNY Logic WorkshopFriday, May 3, 20132:00 pmGC 6417

# Models of Reverse Mathematics

University of Pennsylvania

We discuss two results relating ideas in Reverse Mathematics to the properties of models of first order arithmetic. The first shows that we can extend second order arithmetic by the existence of a non-principal ultrafilter — a third order property — while remaining conservative. The second result shows that we can extend models of RCA so that any particular set is definable; this allows us to recover some properties of models of Peano arithmetic for models of RCA.

CUNY Logic WorkshopFriday, April 26, 20132:00 pmGC 6417

# Mittag-Leffler objects in definable categories of modules

The City University of New York

Definable categories are classes of modules closed under direct product, direct limit, and pure submodule. These play an important role in the theory of modules as they are in bijection with the closed sets of the Ziegler spectrum (and thus with the product closed complete theories of modules). Mittag-Leffler objects for such categories (some sort of generalized atomic module) will be introduced and a necessary and sufficient condition in terms of generators and generalized relations will be given for them to exist.

CUNY Logic WorkshopFriday, April 12, 20132:00 pmGC 6417

# An algebraic characterization of recursively saturated real closed fields

Wellesley College

We (with D’Aquino and Kuhlmann) give a valuation theoretic characterization for a real closed field to be recursively saturated. Previously, Kuhlmann, Kuhlmann, Marshall, and Zekavat gave such a characterization for kappa-saturation, for all infinite cardinals kappa. Our result extends the characterization for a divisible ordered abelian group to be recursively saturated found in some unpublished work of Harnik and Ressayre.

Friday, April 12, 201312:30 pmGC 6417

# Pfaffian functions vs. Rolle leaves

McMaster University

In the early 1980s, after Khovanskii’s ICM lecture, van den Dries formulated the conjecture that the expansion P of the real field by all pfaffian functions was model complete. Thinking about the problem led him to formulate a minimality notion in expansions of the real order, which directly inspired Pillay and Steinhorn in their discovery of o-minimality. However, while P has been known to be o-minimal since Wilkie’s groundbreaking work in 1996, van den Dries’s conjecture is still open today. Recently, Lion and I proved a variant of this conjecture, in which “pfaffian functions” are replaced with “nested Rolle leaves”, which in essence correspond to the objects originally studied by Khovanskii. The mystery lies in how these two expansions are related. I will explain each of them and exhibit a third related notion, found recently in joint work with Jones, which might clarify this relationship.

CUNY Logic WorkshopFriday, March 22, 20132:00 pmGC 6417

# Namba-like singularizations of successor cardinals

Rheinische Friedrich-Wilhelms-Universität Bonn

Bukowski-Namba forcing preserves aleph_1 and changes the cofinality of  aleph_2 to omega. We lift this to cardinals kappa > aleph_1 : Assuming a measurable cardinal lambda we construct models over which there is a further “Namba-like” forcing which preserves all cardinals <= kappa and changes the cofinality of kappa^+ to omega. Cofinalities different from omega can also be achieved by starting from measurable cardinals of sufficiently strong Mitchell order. Using core model theory one can show that the respective measurable cardinals are also necessary. This is joint work with Dominik Adolf (Münster).

Slides

CUNY Logic WorkshopFriday, March 22, 20134:00 pmGC 6417Note special time

# Determinacy in analysis and beyond

University of Bristol

Recently Montalban and Shore derived precise limits to the amount of determinacy provable in second order arithmetic.  We review some of the results in this area and recent work on lifting this to a setting of ZF^- with a single measurable cardinal.

Slides

CUNY Logic WorkshopFriday, March 15, 20132:00 pm

# Some approaches to model theory for classes of finite structures

Vassar College

This talk surveys work on the development of model theory for classes of finite structures due primarily to Macpherson and the speaker, and to several of Macpherson’s students. The underlying theme of this work has been to bring to the model-theoretic study of classes of finite structures aspects of the model theory of infinite structures.

CUNY Logic WorkshopFriday, March 8, 20132:00 pmGC 6417

# Reverse mathematics for second-order categoricity theorem

Mathematical Institute, Tohoku University

It is important in the foundations of mathematics that the natural number system is characterizable as a system of 0 and a successor function by second-order logic. In other words, the following Dedekind’s second-order categoricity theorem holds: every Peano system $(P,e,F)$ is isomorphic to the natural number system $(N,0,S)$. In this talk, I will investigate Dedekind’s theorem and other similar statements. We will first do reverse mathematics over $RCA_0$, and then weaken the base theory. This is a joint work with Stephen G. Simpson.

CUNY Logic WorkshopFriday, March 1, 20132:00 pmGC 6417

# Understanding genericity for cuts

Ghent University

In a nonstandard model of arithmetic, initial segments with no maximum elements are traditionally called cuts. It is known that even if we restrict our attention to cuts that are closed under a fixed family of functions (e.g., multiplication, the primitive recursive functions, or the Skolem functions), the properties of cuts can still vary greatly. I will talk about what genericity means amongst such great variety. This notion of genericity comes from a version of model theoretic forcing devised by Richard Kaye in his 2008 paper. Some ideas were already implicit in the work by Laurence Kirby and Jeff Paris on indicators in the 1970s.

CUNY Logic WorkshopFriday, February 22, 20132:00 pmGC 6417

# Very NIP Ordered Groups

The City University of New York

In recent years there has been renewed interest in theories without the independence property (NIP theories), a class of theories including all stable as well as all o-minimal theories.  In this talk we concentrate on theories, T, which expand that of divisible ordered Abelian groups (a natural situation to consider if one is motivated by the study of o-minimal theories) and consider the problem determining the consequences of assuming that T is NIP on the structure of definable sets in models of T.  One quickly realizes that given the great generality of the NIP assumption  in order to address this type of question one wants to consider much stronger variants of not having the independence property.  Thus we are led to the study of definable sets in models of  theories T expanding that of divisible ordered Abelian groups satisfying various very strong forms of the NIP condition such as finite dp-rank, convex orderability, and VC minimality.  In this talk I will survey results in this area and discuss many open problems.

CUNY Logic WorkshopFriday, February 15, 201312:00 amGC 6417

# On the axiom of constructibility and Maddy’s conception of restrictive theories

The City University of New York

This talk will be based on my paper, A multiverse perspective on the axiom of constructibility.

Set-theorists often argue against the axiom of constructibility V=L on the grounds that it is restrictive, that we have no reason to suppose that every set should be constructible and that it places an artificial limitation on set-theoretic possibility to suppose that every set is constructible.  Penelope Maddy, in her work on naturalism in mathematics, sought to explain this perspective by means of the MAXIMIZE principle, and further to give substance to the concept of what it means for a theory to be restrictive, as a purely formal property of the theory.

In this talk, I shall criticize Maddy’s specific proposal.  For example, it turns out that the fairly-interpreted-in relation on theories is not transitive, and similarly the maximizes-over and strongly-maximizes-over relations are not transitive.  Further, the theory ZFC + `there is a proper class of inaccessible cardinals’ is formally restrictive on Maddy’s proposal, although this is not what she had desired.

Ultimately, I argue that the $Vneq L$ via maximize position loses its force on a multiverse conception of set theory, in light of the classical facts that models of set theory can generally be extended to (taller) models of V=L.  In particular, every countable model of set theory is a transitive set inside a model of V=L.  I shall conclude the talk by explaining various senses in which V=L remains compatible with strength in set theory.

CUNY Logic WorkshopFriday, February 8, 201312:00 amGC 6417

# Model theory of satisfaction classes

The City University of New York

All countable recursively saturated models of Peano Arithmetic have nonstandard satisfaction classes. In fact, each such model has a great variety of nonstandard satisfaction classes. I will survey model theoretic techniques that can be applied to construct many different inductive satisfaction classes, and I will show how, in return, inductive satisfaction classes are used to prove important result about recursively saturated models of PA. I will also pose an open problem concerning a possible converse to Tarski’s undefinability of truth theorem.

Pdf slides for the talk are here: Satisfaction Classes

CUNY Logic WorkshopFriday, September 28, 201212:00 amGC 6417This is the usual place

# Transfinite linear algebra

The City University of New York
CUNY Logic WorkshopFriday, September 14, 201212:00 amGC 6417

# Boolean subalgebras of the computable atomless Boolean algebra

City University of New York

An abstract of this talk will be added.

CUNY Logic WorkshopFriday, September 7, 201212:00 amGC 6417

# Recent progress on the modal logic of forcing and grounds

The City University of New York

The modal logic of forcing arises when one considers a model of set theory in the context of all its forcing extensions, with “true in all forcing extensions” and“true in some forcing extension” as the accompanying modal operators. In this modal language one may easily express sweeping general forcing principles, such as the assertion that every possibly necessary statement is necessarily possible, which is valid for forcing, or the assertion that every possibly necessary statement is true, which is the maximality principle, a forcing axiom independent of but equiconsistent with ZFC. Similarly, the dual modal logic of grounds concerns the modalities “true in all ground models” and “true in some ground model”. In this talk, I shall survey the recent progress on the modal logic of forcing and the modal logic of grounds. This is joint work with Benedikt Loewe and George Leibman.

CUNY Logic WorkshopFriday, May 18, 201212:00 amGC 6417

# The countable models of ZFC, up to isomorphism, are linearly pre-ordered by the submodel relation; indeed, every countable model of ZFC, including every transitive model, is isomorphic to a submodel of its own L

The City University of New York

This will be a talk on some extremely new work. The proof uses finitary digraph combinatorics, including the countable random digraph and higher analogues involving uncountable Fraisse limits, the surreal numbers and the hypnagogic digraph.

The story begins with Ressayre’s remarkable 1983 result that if $M$ is any nonstandard model of PA, with $langletext{HF}^M,{in^M}rangle$ the corresponding nonstandard hereditary finite sets of $M$, then for any consistent computably axiomatized theory $T$ in the language of set theory, with $Tsupset ZF$, there is a submodel $Nsubsetlangletext{HF}^M,{in^M}rangle$ such that $Nmodels T$. In particular, one may find models of ZFC or even ZFC + large cardinals as submodels of $text{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$.

My new theorem strengthens Ressayre’s theorem, while simplifying the proof, by removing the theory $T$. We need not assume $T$ is computable, and we don’t just get one model of $T$, but rather all models—the fact is that the nonstandard models of set theory are universal for all countable acyclic binary relations. So every model of set theory is a submodel of $langletext{HF}^M,{in^M}rangle$.

Theorem.(JDH) Every countable model of set theory is isomorphic to a submodel of any nonstandard model of finite set theory. Indeed, every nonstandard model of finite set theory is universal for all countable acyclic binary relations.

The proof involves the construction of what I call the countable random $mathbb{Q}$-graded digraph, a countable homogeneous acyclic digraph that is universal for all countable acyclic digraphs, and proving that it is realized as a submodel of the nonstandard model $langle M,in^Mrangle$. Having then realized a universal object as a submodel, it follows that every countable structure with an acyclic binary relation, including every countable model of ZFC, is realized as a submodel of $M$.

Theorem.(JDH) Every countable model $langle M,in^Mrangle$ of ZFC, including the transitive models, is isomorphic to a submodel of its own constructible universe $langle L^M,in^Mrangle$. In other words, there is an embedding $j:Mto L^M$ that is quantifier-free-elementary.

The proof is guided by the idea of finding a universal submodel inside $L^M$. The embedding $j$ is constructed completely externally to $M$.

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 work opens up 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:Vto L$, elementary for quantifier-free assertions?

# No seminars April 18

Friday, April 18 is part of CUNY’s spring break, and there will be no seminars at the Graduate Center that day.