This post includes various diagnostic information for helping to program the site.
Speakers having an empty profile:
—————————————
Untagged posts:
NYLOGIC.ORG NOT WORKING RIGHT: LINK TO TEMPORARY WEB PAGE
We apologize for the current dysfunction of our usual website nylogic.org. For up-to-date information on upcoming logic talks in New York City, please visit https://boolesrings.org/victoriagitman/cuny-logic-seminars/.
Recursive Reducts of PA III
I will continue my overview of Schmerl’s work on generalizations of Tennenbaum’s theorm to general reducts of Peano Arithmetic.
Computable models of finite set theory
In 2001, Mancini and Zambella investigated computable models of fragments of set theory. They emplyed the Bernays-Rieger method of permutations to construct a computable model of finite set theory (i.e. $ZF_{fin}$ – the theory obtained from ZF by replacing the axiom of infinity by its negation). In 2009, Enayat, Schmerl and Visser showed how to build computable nonstandard models of this theory without the use of permutations. Furthermore, they demonstrated that in every computable model of ZF_{fin} every set (as viewed externally) has only finitely many elements (such models are called $\omega$-models). The corollaries of these results are, among others, that there are continuum-many nonisomorphic pointwise definable $\omega$-models of $ZF_{fin}$ and that $PA$ and $ZF_{fin}$ are not bi-interpretable. The purpose of the talk is to present proofs of the results of Macinini, Zambella and Enayat, Schmerl, Visser together with the corollaries.
Inner models from extended logics
Informal Session
We will meet in an informal discussion to talk about recent work in model theory as well as any current problems we are interested in. Also we can use the opportunity to discuss plans for the seminar next semester. Bring any ideas or recent preprints you are interested in talking about. In particular see the most recent model theory preprints posted on the
ArXiv.
Recursive Reducts of PA II
I will continue discussing work of Schmerl addressing the question of under what conditions a given reduct of PA has the property that for any non-standard model M of PA the restriction of M to the reduct must be non-computable.
Satisfaction Classes and Recursive Saturation IV
The study of possible semantics for arithmetized languages in nonstandard models has been a lively research field since the seminal paper of A. Robinson “On languages based on non-standard arithmetic”. Our primary inspiration for examining mathematical features of such structures, and recursively saturated in particular, is that every countable recursively saturated model of Peano Arithmetic supports a great variety of nonstandard satisfaction classes that can serve as models for formal theories of truth – those models allow to investigate the role of arithmetic induction in semantic considerations. On the other hand, nonstandard satisfaction classes are used as a tool in model theoretic constructions providing answers to questions in the model theory of formal arithmetic and often make it possible to solve problems that do not explicitly involve nonstandard semantics. In the series of talks, I will present proofs of classical results concerning satisfaction classes and recursive saturation in models of PA.
Rohit Parikh 80th Birthday Conference
On December 1-2, 2016, the Graduate Center will host a conference on logic in honor of the 80th birthday of Prof. Rohit Parikh. Details are available at the conference website.
Using model theory to find upper bounds on VC density
The VC dimension of a collection of sets is a concept used in probability and learning theory. It is closely related to the model-theoretic concept of the independence property. In this talk, I will illustrate these concepts in various examples, and show how the model-theoretic approach can give some bounds on VC density.
Recursive Reducts — An Introduction
I will begin talking about work of Schmerl on generalizations of Tennenbaum’s theorem on the non-exsistence of computable nonstandard models of PA to reducts of PA.
First order expansions of the ordered group of real numbers
We discuss (part of) the classification of first order expansions of $(\mathbb{R},<,+)$ according to the geometry and topology of their definable sets. Joint work with Philipp Hieronymi, following work of Hieronymi, Fornasiero, Miller, and Tychonievich.
Foundations of cologic
The existence of a robust categorical dual to first-order logic is hinted at in (at least) four independent bodies of work: (1) Projective Fraïssé theory [Solecki & coauthors, Panagiotopolous]. (2) The cologic of profinite groups (e.g. Galois groups), which plays an important role in the model theory of PAC fields [Cherlin – van den Dries – Macintyre, Chatzidakis]. (3) Ultracoproducts and coelementary classes of compact Hausdorff spaces [Bankston]. (4) Universal coalgebras and coalgebraic logic [Rutten, Kurz – Rosicky, Moss, others]. In this talk, I will propose a natural syntax and semantics for such a dual “cologic”, in which “coformulas” express properties of partitions of “costructures”, dually to the way in which formulas express properties of tuples from structures. I will show how the basic theorems and constructions of first-order logic (completeness, compactness, ultraproducts, Henkin constructions, Löwenheim-Skolem, etc.) can be dualized, and I will discuss some possible extensions of the framework.
No seminars on Nov. 25
Friday, November 25 is the day after Thanksgiving, so there will be no seminars at the Graduate Center that day.
Satisfaction Classes and Recursive Saturation III
The study of possible semantics for arithmetized languages in nonstandard models has been a lively research field since the seminal paper of A. Robinson “On languages based on non-standard arithmetic”. Our primary inspiration for examining mathematical features of such structures, and recursively saturated in particular, is that every countable recursively saturated model of Peano Arithmetic supports a great variety of nonstandard satisfaction classes that can serve as models for formal theories of truth – those models allow to investigate the role of arithmetic induction in semantic considerations. On the other hand, nonstandard satisfaction classes are used as a tool in model theoretic constructions providing answers to questions in the model theory of formal arithmetic and often make it possible to solve problems that do not explicitly involve nonstandard semantics. In the series of talks, I will present proofs of classical results concerning satisfaction classes and recursive saturation in models of PA.
Satisfaction Classes and Recursive Saturation II
The study of possible semantics for arithmetized languages in nonstandard models has been a lively research field since the seminal paper of A. Robinson “On languages based on non-standard arithmetic”. Our primary inspiration for examining mathematical features of such structures, and recursively saturated in particular, is that every countable recursively saturated model of Peano Arithmetic supports a great variety of nonstandard satisfaction classes that can serve as models for formal theories of truth – those models allow to investigate the role of arithmetic induction in semantic considerations. On the other hand, nonstandard satisfaction classes are used as a tool in model theoretic constructions providing answers to questions in the model theory of formal arithmetic and often make it possible to solve problems that do not explicitly involve nonstandard semantics. In the series of talks, I will present proofs of classical results concerning satisfaction classes and recursive saturation in models of PA.
Models of arithmetic with two expansions to $ACA_0$, Part 2
In this talk and its prequel I construct models of arithmetic with exactly two expansions to a model of $ACA_0$. Last time, we saw how to build models of arithmetic which are A-rather classless for some class A of the model. In this talk, I will use a kind of forcing argument to show how to pick this A so that the resulting model has exactly two expansions to $ACA_0$. Time permitting, I will explain the difficulties in moving from two to three.
Straw into gold: Turning a c.c.c. forcing construction of a model into a ZFC proof
We use $M$-normal ultrapowers to give a new proof of a theorem of Keisler that if one can construct a standard model of a sentence of $L_{\omega_1,\omega}(Q)$ using a c.c.c. forcing, then a standard model already exists in V.
We use this to investigate the class of atomic models of a countable, first order theory $T$. In particular, we show that various `unsuperstable-like’ behaviors imply the existence of many non-isomorphic atomic models of size $\aleph_1$.
This is joint work with John Baldwin and Saharon Shelah.
Isomorphisms of ordered valued fields
A real closed field with a convex valuation is a nice model-theoretic object. In this talk, I will look at some examples of such structures to get a sense of why they are nice. I will discuss two theorems which illustrate the analogues with algebraically closed valued fields, which lead us to a notion of domination by the residue field. This is joint work with Clifton Ealy and Jana Marikova.
Northeast Regional Model Theory Days
The Northeast Regional Model Theory Days will take place on Saturday the 21st of October and
Sunday the 22nd of October at the University of Pennsylvania in Philadelphia PA. See the Northeast Regional Model Theory Days website for full details.
Satisfaction Classes and Recursive Saturation
The study of possible semantics for arithmetized languages in nonstandard models has been a lively research field since the seminal paper of A. Robinson “On languages based on non-standard arithmetic”. Our primary inspiration for examining mathematical features of such structures, and recursively saturated in particular, is that every countable recursively saturated model of Peano Arithmetic supports a great variety of nonstandard satisfaction classes that can serve as models for formal theories of truth – those models allow to investigate the role of arithmetic induction in semantic considerations. On the other hand, nonstandard satisfaction classes are used as a tool in model theoretic constructions providing answers to questions in the model theory of formal arithmetic and often make it possible to solve problems that do not explicitly involve nonstandard semantics. In the series of talks, I will present proofs of classical results concerning satisfaction classes and recursive saturation in models of PA.
Σ11 in every real in a Σ11 class of reals is Σ11
We first prove a theorem about reals (subsets of N) and classes of reals: If a real X is Σ11 in every member G of a nonempty Σ11 class K of reals then X is itself Σ11. We also explore the relationship between this theorem, various basis results in hyperarithmetic theory and omitting types theorems in ω-logic. We then prove the analog of our first theorem for classes of reals: If a class A of reals is Σ11 in every member of a nonempty Σ11 class B of reals then A is itself Σ11. This is joint work with T. Slaman and L. Harrington .
Order-Based and Continuous Modal Logics
Many-valued modal logics generalize the Kripke frame semantics of classical modal logic to allow a many-valued semantics at each world based on an algebra with a complete lattice reduct, where the accessibility relation may also take values in this algebra. Such logics can be designed to model modal notions such as necessity, belief, and spatio-temporal relations in the presence of uncertainty, possibility, or vagueness, and also provide a basis for defining fuzzy description logics. More generally, many-valued modal logics provide a first foray into investigating useful and computationally feasible fragments of corresponding first-order logics. The aim of my talk will be to describe recent axiomatization, decidability, and complexity results for many-valued modal logics based on algebras over (infinite) sets of real numbers. In particular, I will report on joint work with X. Caicedo, R. Rodriguez, and J. Rogger establishing decidability and complexity results for a family of order-based modal logics, using an alternative semantics admitting the finite model property. I will also present an axiomatization, obtained in joint work with D. Diaconescu and L. Schnueriger, for a many-valued modal logic equipped with the usual group operations over the real numbers that provides a first step towards solving an open axiomatization problem for a Lukasiewicz modal logic with continuous operations.
No set theory seminar on October 21
Since many of the seminar members will be away, there will be no set theory seminar on October 21.
Imaginaries in valued differential fields II: Computing canonical bases
In 2000, Scanlon described a theory of existentially closed differential fields where the derivation is contractive: v(d(x)) ≥ v(x), for all x. He also proved a quantifier elimination result for this theory. Around the same time, Haskell, Hrushovski and Macpherson classified all the quotients of definable sets by definable equivalence relations in a algebraically closed valued field by proving elimination of imaginaries (relative to certain quotients of the linear group). In analogy with the pure field situation where elimination of imaginaries for differentially closed fields can be derived from elimination of imaginaries in the underlying algebraically closed field, it was conjectured that Scanlon’s theory of existentially closed contractive valued differential fields also eliminated imaginaries relatively to those same quotients of the linear group.
In this talk, I will describe the second part of the proof that this result indeed holds. Our goal will be to explain a result, joint with Pierre Simon, on definable types in enrichments of NIP theories, which is crucial to prove elimination of imaginaries. We show that under certain hypothesis if a type in some NIP theory T is definable in an enrichment of T, then it h is already be definable in T.
Imaginaries in valued differential fields I: Finding prolongations
In 2000, Scanlon described a theory of existentially closed differential fields where the derivation is contractive: v(d(x)) ≥ v(x), for all x. He also proved a quantifier elimination result for this theory. Around the same time, Haskell, Hrushovski and Macpherson classified all the quotients of definable sets by definable equivalence relations in a algebraically closed valued field by proving elimination of imaginaries (relative to certain quotients of the linear group). In analogy with the pure field situation where elimination of imaginaries for differentially closed fields can be derived from elimination of imaginaries in the underlying algebraically closed field, it was conjectured that Scanlon’s theory of existentially closed contractive valued differential fields also eliminated imaginaries relatively to those same quotients of the linear group.
In this talk, I will describe the first part of the proof that this result indeed holds. Our main goal will be to explain a construction that can be interpreted as finding “generic” prolongations for valued differential constructible sets.
Axiomatic theories of truth — conservativeness and deflationism
An axiomatic theory of truth is a formal deductive theory where the property of a sentence being true is treated as a primitive undefined predicate. Logical properties of many axiom systems for the truth predicate have been discussed in the context of the so-called truth-theoretic deflationism, i.e. a view according to which truth is a ‘thin’ or ‘innocent’ property without any explanatory or justificatory power with respect to non-semantic facts.
I will discuss the state of the art concerning proof-theoretic and model-theoretic properties of the most commonly studied axiomatic theories of truth (typed and untyped, both disquotational and compositional ones), focusing in particular on the problem of syntactic and semantic conservativeness of truth theories over a base (arithmetical) theory (treated mostly as a theory of syntax). I will relate the results to the research on satisfaction classes in models of arithmetic, and if the time allows, to analysis of some semantic paradoxes.
(The talk previously scheduled for this time has been canceled due to visa issues.)
Heart of DARCness
Abstract. Alan Hajek has recently criticised the thesis that Deliberation Crowds Out Prediction (renaming it the DARC thesis, for ‘Deliberation Annihilates Reflective Credence’). Hajek’s paper has reinforced my sense that proponents and opponents of this thesis often talk past one other. To avoid confusions of this kind we need to dissect our way to the heart of DARCness, and to distinguish it from various claims for which it is liable to be mistaken. In this talk, based on joint work with Yang Liu, I do some of this anatomical work. Properly understood, I argue, the heart is in good shape, and untouched by Hajek’s jabs at surrounding tissue. Moreover, a feature that Hajek takes to be problem for the DARC thesis – that it commits us to widespread ‘credal gaps’ – turns out to be a common and benign feature of a broad class of cases, of which deliberation is easily seen to be one.
On Collapse of Generalized Indiscernibles.
I discuss the characterization of model theoretic dividing lines by collapse of generalized indiscernibles. For example, S. Shelah showed that a theory is stable if and only if all order indiscernibles are set indiscernibles. In her thesis, L. Scow showed that a theory has NIP if and only if all graph order indiscernibles are order indiscernibles. I explore new results characterizing dp-rank and rosiness using similar methods. I also talk about some attempts to create a general framework for such results. This work is joint with C. Hill and L. Scow.
Models of arithmetic with two expansions to $ACA_0$, Part 1
In this talk and its sequel I will construct models of arithmetic with exactly two expansions to a model of $ACA_0$. To do so, I will use a modified version of Keisler’s construction of a rather-classless model. This talk will focus on this construction, while in Part 2 I will show how to use this construction to get the result.
Complexity of classification problems for a class of discretely ordered rings
I will give a standard introduction to the theory of Borel reducibility, including some details for non-logicians. The rest of the talk will be about some results in classification problems for countable nonstandard models of arithmetic due to Samuel Coskey and myself.
Ramsey Quantifiers and PA$(Q^2)$, part II
In this talk, I will discuss the relationship between “strong” models of PA($Q^2$) and $kappa$-like models. Namely, if $kappa$ is a regular uncountable cardinal, then every countable “weak” model has a $kappa$-like ($Q^2$)-elementary end extension that is a kappa like strong model, and if M is a strong model it is $kappa$ like for some $kappa$.
Learnability thesis, FM-representability and Turing Ideals
We consider the notion of the so-called intuitive learnability and its relation to the so-called intuitive computability. We briefly present and discuss Church’s Thesis in the context of the notion of learnability. A set is intuitively learnable if there is a (possibly infinite) intuitive procedure that for each input produces a finite sequence of yeses and nos such that the last answer in the sequence is correct. We further formulate the Learnability Thesis which states that the notion of intuitive learnability is equivalent to the notion of algorithmic learnability. The claim is analogous to Church’s Thesis. Afterwards we analyse the argument for Church’s Thesis presented by M. Mostowski (employing the concept of FM-representability which is equivalent to Turing-reducibility to $0’$ or to being $\Delta^0_2$). The argument goes in unusual lines – by giving a model of potential infinity, the so-called FM-domains, which are inifnite sequences of growing finite models, separating knowable (intuitively computable) sets from FM-representable (algorithmically learnable) ones via the so-called testing formulae and showing that knowable sets are exactly recursive. We indicate which assumptions of the Mostowski’s argument (concerning recursive enumeration of the finite models being elements of an FM-domain) implicitely include that Church’s Thesis holds. The impossibility of this kind of argument is strengthened by showing that the Learnability Thesis does not imply Church’s Thesis. Specifically, we show a natural interpretation of intuitive computability – containing a low set – under which intuitively learnable sets are exactly algorithmically learnable but intuitively computable sets form a proper superset of recursive sets. Last, using the Sacks Density Theorem, we show that there is a continuum of Turing ideals of low sets satisfying our assumptions. Therefore, if we admit certain non-recursive but intuitively computable relations (namely: some low relations) we are able to consider expanded FM-domains and there are continuum many of such. On the other hand, relations FM-representable in such FM-dommains are still $\Delta^0_2$. The general conclusion is that justifying Church’s Thesis solely on the grounds of procedures recursive in the limit is by far insufficient.
Ramsey Quantifiers and PA($Q^2$)
We can extend the language of first order logic to add in a new quantifier, $Q^2$, which binds two free variables. The intended interpretation of $Q^2 x,y\phi(x, y)$ is “There is an infinite (unbounded) set $X$ such that $\phi(x, y)$ holds for each $x \neq y \in X.$” The theory PA($Q^2$) is the theory of Peano Arithmetic in this augmented language (asserting that induction holds for all formulas, including with Ramsey quantifier) and can be thought of as a second order theory whose models are of the form $(M, \mathfrak{X})$ where $\mathfrak{X} \subseteq P(M)$. In this talk, I will present a few results due to Macintyre (1980) and Schmerl & Simpson (1982), namely that models of PA($Q^2$) correspond to models of the second order system $\Pi_1^1-CA_0$. If there is time, I will present Macintyre’s proof that so-called “strong” models of this theory correspond to $\kappa$-like models for some regular $\kappa$.
No logic seminars on October 14
Since CUNY will follow a Tuesday schedule on Friday, October 14, we will not have any of the usual Friday logic seminars that day. However, there will be a talk by George Metcalfe at 4 pm, described below.
Yet more forcing in arithmetic: life in a second-order world
In previous semesters of this seminar, I have talked about how the technique of forcing, originally developed by Cohen for building models of set theory, can be used to produce models of arithmetic with various properties. In this talk, I will present a forcing proof of Harrington’s theorem on the conservativity of $\mathsf{WKL}_0$ over $\mathsf{RCA}_0$. More formally, any countable model of $\mathsf{RCA}_0$ can be extended to a model of $\mathsf{WKL}_0$ with the same first-order part. As an immediate corollary, we get that any $\Pi^1_1$ sentence provable by $\mathsf{WKL}_0$ is already provable by $\mathsf{RCA}_0$.
Saturday, October 1, 2016
Sunday, October 2, 2016
Cherlin Weekend at Rutgers
Rutgers University will hold a conference in honor of Professor Gregory Cherlin on September 30 – October 2, 2016. Details are available here. Due to this meeting and the DART VII conference, there will be no Logic Workshop on September 30. For those not going to Rutgers, do notice the NY Group Theory Seminar talk by Miasnikov, announced below.
NY Grad Student Logic Conference
The New York Grad Student Logic Conference, co-organized by Profs. Shoshana Friedman and Sheila Miller, will take place on Thursday-Friday, May 12-13, 2016. Details are available at the conference website.
Automorphisms of models of Presuburger arithmetic V
I will present a characterization of the closed normal subgroups of the automorphism group of pseudo-recursively saturated models of Presburger arithmetic using the machinery developed in the prior three talks.
Stochastic λ-calculus
It is shown how the operators in the “graph model” for calculus (which can function as a programming language for Recursive Function Theory) can be expanded to allow for “random combinators.” The result then is a semantics for a new language for random algorithms. The author wants to make a plea for finding applications.
This talk is part of the Computer Science Colloquium at the CUNY Graduate Center.
Automorphisms of models of Presburger arithmetic IV
I will present a characterization of the closed normal subgroups of the automorphism group of pseudo-recursively saturated models of Presburger arithmetic using the machinery developed in the prior three talks.
$\omega$-stability and Morley rank of bilinear maps, rings and nilpotent groups
In this talk I will present our recent results on the algebraic structure of $\omega$-stable bilinear maps, arbitrary rings and nilpotent groups. I will also discuss some rather complete structure theorems for the above structures in the finite Morley rank case. The main technique in this work is associating a canonical scalar (commutative associative unitary) ring to a bilinear map. This canonical scalar ring happens to preserve many of the logical and algebraic properties of the bilinear map. This talk is based on the joint work with Alexei Miasnikov.
Edmund Husserl’s Philosophy of Arithmetic
Edmund Husserl, the principal founder of phenomenology, is well known for his contributions to philosophy. What is less known is his early work in mathematics. Husserl studied under Kronceker and Weierstrass in Berlin, and got his Ph.D. in 1883 in Vienna working on the calculus of variations under supervision of Leo Königsberger. Under influence of Franz Brentano, he moved to philosophy, and in from 1901 to 1916 he taught philosophy in Göttingen, where he interacted with Hilbert. In “Logic and Philosophy of Mathematics in the Early Husserl” Springer 2010, Stefania Centrone analyses Husserl’s work on foundations of mathematics from that period, and shows its connections to Hilbert’s ideas. I will say a few words about phenomenology, and I’ll talk about fragments of Husserl’s “Philosophy of Arithmetic.”
Computable processes can produce arbitrary outputs in nonstandard models: part II
This is a continuation of last week’s talk. I will continue with a proof of Woodin’s theorem, recently generalized by Blanck and Enayat, showing that for every computably enumerable theory $T$ extending ${\rm PA}$, there is a corresponding index $e$ such that ${\rm PA}\vdash “W_e$ is finite” and whenever a model $M\models T$ satisfies that $W_e$ is contained in some $M$-finite set $s$, then $M$ has an end-extension $N\models T$ in which $W_e=s$. Indeed, the hypotheses can be relaxed to say that $T$ extends ${\rm I}\Sigma_1$, but I will not discuss this in the talk.
Reconciling Nominalism and Platonism in the Philosophy of Mathematics
FRIDAY APRIL 22 (Philosophy Hall, Room 716)
14:00–14:15
Achille Varzi (Columbia University), Marco Panza (IHPST)
Welcome and Introduction
14:15-15:45
John Burgess (Princeton University)
Reconciling Anti-Nominalism and Anti-Platonism in the Philosophy of Mathematics
15:45–16:00 Break
16:00-17:30
Haim Gaifman (Columbia University)
Reconfiguring the Problem: “Platonism” as Objective, Evidence-transcendent Truth
17:30-19:00
Sébastien Gandon (Université Blaise Pascal)
Describing What One is Doing. A Philosophy of Action Based View of Mathematical Objectivity
SATURDAY, APRIL 23 (Philosophy Hall, Room 716)
9:30–11:00
Mirna Džamonja (University of East Anglia and IHPST)
An Unreasonable Effectiveness of ZFC Set Theory at the Singular Cardinals
11:00–11:30 Break
11:30–13:00
Hartry Field (New York University)
Platonism, Indispensability, Conventionalism
13:00–15:00 Lunch
15:00-16:30
Justin Clarke-Doane (Columbia University)
The Benacerraf Problem in Broader Perspective
16:30–17:00 Break
17:00-18:30
Michele Friend (George Washington University)
Is the Pluralist Reconciliation between Nominalism and Platonism too Easy?
18:30 Conclusions
Automorphism Groups of Models of Different Theories (Part II)
Jim Schmerl recently proved that there are continuum many theories extending PA, for which whenever M and N are countable arithmetically saturated models of two different such theories, their automorphism groups are non isomorphic. In part I, we give a survey of results concerning automorphism groups of countable arithmetically saturated models of PA, and introduce notions and prove results which will be used in part II to prove Schmerl’s Theorem.
Computable processes can produce arbitrary outputs in nonstandard models
The focus of this talk is the question of what a computable process can output by passing to a nonstandard model of arithmetic. It is not difficult to see that a computable process can change its output by passing to a nonstandard model, but in fact, for some processes, we can thus affect any arbitrary desired change. I will discuss and prove a theorem of Woodin, recently generalized by Blanck and Enayat, showing that for every computably enumerable theory $T$ extending ${\rm PA}$, there is a corresponding index $e$ such that ${\rm PA}\vdash “W_e$ is finite” and whenever a model $M\models T$ satisfies that $W_e$ is contained in some $M$-finite set $s$, then $M$ has an end-extension $N\models T$ in which $W_e=s$. Indeed, the hypotheses can be relaxed to say that $T$ extends ${\rm I}\Sigma_1$, but I will not discuss this in the talk.
Automorphism Groups of Models of Different Theories (Part I)
Jim Schmerl recently proved that there are continuum many theories extending PA, for which whenever M and N are countable arithmetically saturated models of two different such theories, their automorphism groups are non isomorphic. In part I, we give a survey of results concerning automorphism groups of countable arithmetically saturated models of PA, and introduce notions and prove results which will be used in part II to prove Schmerl’s Theorem.
Model Theory and j-functions.
I will describe two recent interactions between model theory, geometry and arithmetic. Both centered on properties of j-functions.
Measuring definable sets in nonarchimedean o-minimal fields and an application to the reals
We introduce a measure on the definable sets in an o-minimal expansion of a real closed field which takes values in an ordered semiring and assigns a positive value to a definable set iff the interior of the set is non-empty (joint work with M. Shiota). We then discuss an application to Hausdorff dimension of metric spaces definable in o-minimal expansions of the real field (joint work with E. Walsberg).
The Dixmier-Moeglin problem for D-varieties
By a D-variety we mean, following Buium, an algebraic variety V over an algebraically closed field k equipped with a regular section s: V–> TV to the tangent bundle of V. (This is equivalent to the category of finite dimensional differential-algebraic varieties over the constants.) There are natural notions of D-rational map and D-subvariety. Motivated by problems in noncommutative algebra we are lead to ask under what conditions (V,s) has a maximum proper D-subvariety over k. (Model-theoretically this asks when the generic type is isolated.) A necessary condition is that (V,s) does not admit a nonconstant D-constant, that is, a D-rational map from (V,s) to the affine line equipped with the
zero section. When is this condition sufficient? I will discuss this rather open-ended problem, including some known cases.
Imaginaries in valued fields of positive characteristic
I will discuss the basic properties of the theory SCVF of separably closed valued fields, and the closely related theory SCVH of separably closed valued fields equipped with Hasse derivations. The main new result is elimination of imaginaries (in a suitable language). This is joint work with Martin Hils and Silvain Rideau.
On a question of Gaifman concerning invariant measures
In his 1964 paper “Concerning measures in first order calculi” Gaifman introduces the notion of a symmetric measure-model: a measure on the formulas of a first order calculus that is invariant under permutations of the elements instantiating the free variables of each formula, where these elements come from some fixed domain. To each symmetric measure-model there is associated a measure on sentences, which we can think of as a random (consistent) theory that the measure-model satisfies. Gaifman shows that every such random theory has a symmetric measure-model satisfying it. However, the symmetric measure-models that he constructs sometimes, necessarily, assign positive measure to instantiations of the formula “x=y” by unequal elements. Gaifman goes on to pose the question of characterizing those classical theories that admit symmetric measure-models without this pathology — those with so-called `strict equality’. In this talk I will show that when the instantiating domain is the set of natural numbers, a symmetric measure-model with strict equality is essentially a probability measure on a space of structures, with underlying set the natural numbers, that is invariant under the logic action. I will then give necessary and sufficient conditions for a classical theory to admit such an invariant measure, thereby providing an answer to the question posed by Gaifman. This is joint work with Nathanael Ackerman and Cameron Freer.
The Lattice of Definable Equivalence Relations in Homogeneous n-Dimensional Permutation Structures
In 2002, Cameron classified the homogeneous permutations (structures in a language of 2 linear orders). In working toward the classification the homogeneous n-dimensional permutation structures (structures in a language of n linear orders), consideration of the lattice of definable equivalence relations leads to a generalization of Cameron’s structures, giving a large class of new homogeneous examples, and places some constraints on lattices that can appear.
Prime-model extensions of Abelian lattice-ordered groups
This talk will consider the extent to which Abelian lattice-ordered groups have prime-model extensions within the class of existentially closed Abelian lattice-ordered groups.
Structures Between (Z,+) and (Z,+,<)
I will discuss a recent result of Gabe Conant that there is no structure lying properly between (Z,+) and (Z,+,<).
Amalgamation Classes with Existential Resolutions
Let $K_d$ denote the class of all finite graphs and, for graphs $A \subseteq B$, say $A \leq_d B$ if distances in $A$ are preserved in $B$; i.e. for $a, a’ \in A$ the length of the shortest path in $A$ from $a$ to $a’$ is the same as the length of the shortest path in $B$ from $a$ to $a’$. In this situation $(K_d, \leq_d)$ forms an amalgamation class and one can perform a Hrushovski construction to obtain a generic of the class. One particular feature of the class $(K_d, \leq_d)$ is that a closed superset of a finite set need not include all minimal pairs obtained iteratively over that set but only enough such pairs to resolve distances; we will say that such classes have existential resolutions.
Larry Moss has conjectured the existence of graph $M$ which was $(K_d, \leq_d)$-injective (for $A \leq_d B$ any isometric embedding of $A$ into $M$ extends to an isometric embedding of $B$ into $M$) but without finite closures. We examine Moss’s conjecture in the more general context of amalgamation classes. In particular, we will show that the question is in some sense more interesting in classes with $\exists$-resolutions and will give some conditions under which the possibility of such structures is limited.
Automorphisms of models of Presburger arithmetic III
This talk will focus on some results on the automorphism groups of countable, pseudo-recursively saturated models of Presburger arithmetic and on the characterization of their closed normal subgroups.
No Logic Workshop March 4.
We do not have a speaker for Friday, March 4, so there will be no Logic Workshop that day. (The Set Theory and Model Theory Seminars will meet as usual.)
Automorphisms of models of Presburger arithmetic II
No model theory seminar on Feb. 26
The model theory seminar will not meet on February 26.
Rigidity properties of precipitous ideals
An ideal $I$ on a set $X$ is called rigid if forcing with $\mathcal{P}(X)/I$ produces an extension $V[G]$ in which there is a unique $V$-generic filter for $\mathcal{P}(X)/I$. Note that this implies that $\mathcal{P}(X)/I$ has only the trivial automorphism. As part of his analysis of $\mathbb{P}_{\text{max}}$ forcing, Woodin showed that under $\text{MA}_{\omega_1}$, every normal, uniform, saturated ideal on $\omega_1$ is rigid. Indeed, in all previously known models which have rigid precipitous ideals on $\omega_1$ one also has $\lnot\text{CH}$. This leaves open the question: is it consistent to have $\text{CH}$ along with a rigid precipitous ideal on $\omega_1$? I will discuss some recent work which shows that if $\kappa$ is almost huge then there is a forcing extension $V[G]$ in which $\kappa=\omega_1^{V[G]}$, there is a rigid presaturated ideal $I$ on $\omega_1^{V[G]}$ and $\text{CH}$ holds. The proof of this result involves a certain coding forcing first used in the Friedman-Magidor results on the number of normal measures. This is joint work with Sean Cox and Monroe Eskew.
Connections between a forcing class and its modal logic
Every definable forcing class $\Gamma$ gives rise to a corresponding modal logic. Mapping the ordered structure given by a ground model $W$ and its $\Gamma$-forcing extensions $W[G]$ to finite ordered structures (frames) in a class which can be characterized by a particular modal theory $\mathsf{S}$ reveals connections between the modal logic of $\Gamma$-forcing and the modal theory $\mathsf{S}$. For example, in 2008, Hamkins and Loewe showed that if ${\rm ZFC}$ is consistent, then the ${\rm ZFC}$-provably valid principles of the class of all forcing are precisely the assertions of the modal theory $\mathsf{S4.2}$. In this talk I describe how specific statements of set theory are used as `controls’ to achieve this mapping for various classes of forcing, giving new results for modal logics of forcing classes such as Cohen forcing, collapse forcing and ${\rm CH}$-preserving forcing.
Weak compactness without inaccessibility
Weakly compact cardinals are known to have a multitude of equivalent characterizations. The weakly compact cardinals were introduced by Hanf and Tarski in the 1960s as cardinals for which certain infinitary languages satisfied a form of the compactness theorem. Since then, they have been shown to be equivalently characterized as inaccessible cardinals that have, for example, the tree property, or the Keisler extension property, or the $\Pi^1_1$ indescribability property, or the weakly compact embedding property–meaning that they have elementary embeddings with critical point $\kappa$ defined on various transitive sets of size $\kappa$. In this talk we discuss what happens if one drops the requirement that $\kappa$ is inaccessible from weak compactness. We focus especially on the weakly compact embedding property and investigate its relation to the other properties mentioned above. This is joint work with Brent Cody, Sean Cox, and Joel Hamkins, and our results extend prior work of William Boos.
Automorphisms of models of Presburger arithmetic I
I will present an algebraic construction of end extensions of models of Presburger arithmetic, as well as key definitions and examples that are needed for studying the automorphism group of certain countable models of Pr.
Potential Cardinality for Countable First Order Theories
Give a theory $T$, understanding the countable model theory of $T$ has long been a topic of research. The number of countable models of $T$ is a classical but very coarse invariant, and this was refined significantly by Friedman and Stanley with the notion of Borel reductions.
Given theories $T_1$ and $T_2$, it is often straightforward to show that $T_1$ is Borel reducible to $T_2$. However, there are few tools to show that no such Borel reduction exists. Most of the existing tools only work when the isomorphism relation of one or both is particularly simple, or at least Borel.
We define the notion of “potential cardinality” of $T$, denoted $|T|$, as the number of formally consistent, possibly uncountable Scott sentences which imply $T$. It turns out that if $T_1$ Borel reduces to $T_2$, then $|T_1|$ is less than or equal to $|T_2|$. Additionally, it turns out that very frequently, $|T|$ can be computed and is not a proper class.
We use this idea to give a new class of examples of first-order theories whose isomorphism relations are neither Borel nor Borel complete. Along the way we answer an old question of Koerwien and new question of Laskowski and Shelah.
This is joint work with Douglas Ulrich and Chris Laskowski.
Loftiness VI
I will review some results on loftiness from my previous talks, and I will talk
about an intrinsic characterization of models with the omega-property.
Spring break April 22 & 29
CUNY’s spring break includes both Friday, April 22 and Friday, April 29, and so there will be no talks those days.
No talks March 25
Friday, March 25 is a CUNY holiday, for Good Friday, and so there will be no talks that day.
No talks Feb.12
Friday, Feb. 12 is a CUNY holiday, for Lincoln’s Birthday, and so there will be no talks that day.
The Lambek Calculus with Iteration (Kleene Star)
Besides multiplication (pairwise concatenation, A dot B) of formal languages, there are also two division operations on them: A dot B is included in C iff B is included in (A C) iff A is included in (C / B). The Lambek calculus was designed to describe all universally true statements of the form “A is included in B”, where A and B are formulas built using the three connectives (multiplication and two divisions). The completeness theorem was proved by Pentus (1995). It looks natural to consider also other well-known operations on formal languages, and one of these operations is the Kleene star, or iteration. Though this operation is very standard, the problem of enriching the Lambek calculus with this new unary connective in a proper way appears to be quite hard. We present two lines of calculi. The first one uses omega-rules or derivation trees with infinite branches, and we prove cut-elimination and completeness of the product-free fragment, but, as the derivations are infinite, we do not get any algorithmic properties, even recursive enumerability. The second approach is to formalize the Kleene star in an inductive manner. We present a Hilbert-style axiomatization and also a sequent calculus with cyclic derivations. This system is sound with respect to the intended interpretation. Completeness, or, in other words, whether the system with omega-rules is stronger than the inductive one, remains an open question.
Loftiness V
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.
Substructure Lattices of Recursively Saturated Models
Previously, it was known (Kossak-Schmerl 1995) that given two arithmetically saturated models with isomorphic substructure lattices, their standard systems must be the same. In Schmerl’s new paper (2015?), he analyzes this proof a little more carefully: in particular, if M is recursively saturated, and X subset omega, then there is an ideal in the substructure lattice of M corresponding to X if and only if X is Turing computable from the jump of some Y in SSy(M). We will go over this proof and, time permitting, how this is used in the proof of the main theorem: if M and N are countable arithmetically saturated models with isomorphic automorphism groups, then the jumps of their theories are Turing equivalent.
Cofinal elementary extensions II
We will also discuss K-tallness and tallness in relation to the existence of κ-pseudosaturated cofinal elementary extensions. Here, κ-pseudosaturated structures are the structures all of whose infinite definable sets have a cardinality ≥ κ.
Cofinal elementary extensions
We will discuss two weak versions of recursive saturation: K-tallness and tallness. K-tallness characterizes the countable models of IΔ0 + exp that have cofinal elementary extensions enlarging any infinite definable set, and tallness characterizes such models of linear ordering without the last element. I will present the proof of the latter. If time permits, we will also discuss the two properties in relation to the existence of κ-pseudosaturated cofinal elementary extensions. Here, κ-pseudosaturated structures are the structures all of whose infinite definable sets have a cardinality ≥κ.
Recursive definability of the standard cut
Say that the standard cut in a model of arithmetic is recursively definable if there is a recursive sequence coinitial in the nonstandard elements. We will construct minimal models in which the standard cut is recursively definable and minimal models in which the standard cut is not recursively definable.
Loftiness III
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$. Tall models with the $omega$-property are uniformly $omega$-lofty. I will present several results on models with the $omega$-property, including Jim Schmerl’s construction of a model with the $omega$-property that is not recursively saturated.
Loftiness II
I will introduce uniformly omega-lofty models and I will discuss some results about them due to Matt Kaufmann and Jim Schmerl.
On maximal immediate extensions of valued fields
A valued field extension is called immediate if the corresponding value group and residue field extensions are trivial. A better understanding of the structure of such extensions turned out to be important for questions in algebraic geometry, real algebra and the model theory of valued fields.
In this talk we focus mainly on the problem of the uniqueness of maximal immediate extensions.
Kaplansky proved that under a certain condition, which he called “hypothesis A”, all maximal immediate extensions of the valued field are isomorphic. We study a more general case, omitting one of the conditions of hypothesis~A. We describe the structure of maximal immediate extensions of valued fields under such weaker assumptions. This leads to another condition under which fields in this class admit unique maximal immediate extensions.
We further prove that there is a class of fields which admit an algebraic maximal immediate extension as well as one of infinite transcendence degree. We introduce a classification of Artin-Schreier defect extensions and describe its importance for the construction of such maximal immediate extensions.
We present also the consequences of the above results and and of the model theory of tame fields for the problem of uniqueness of maximal immediate extensions up to elementary equivalence.
Loftiness
Loftiness is a weak version of recursive saturation. It was introduced and studied by Kaufmann and Schmerl in two papers published in 1984 and 1987. I will present basic definitions and results leading to constructions of lofty models of PA that are not recursively saturated.
Enayat models II
Simpson proved that every countable model of PA has an expansion (to PA*) that is pointwise definable. The natural question, then, is if every countable model has an expansion to PA* in which no new elements are defined. Enayat proved this is false by showing the existence of many models that are not pointwise definable, but become so upon addition of any undefinable class. Inspired by this, I have begun thinking about which models have this property. I will describe some models with this property (and some without) and talk about my search for a non-trivial such model (I will also explain what I mean by “non-trivial” here).
No talks November 27
There will be no talks on November 27, the day after Thanksgiving.
No talks on September 25
On Friday, September 25, CUNY will follow a Tuesday schedule. Therefore, no logic seminars will meet that day.
New time for MOPA
MOPA moves to back its regular schedule: Wednesdays 6:15pm in GC 4214-03.
The first meeting will be next week 9/2.
Enayat Models
Simpson proved that every countable model of PA has an expansion (to PA*) that is pointwise definable. The natural question, then, is if every countable model has an expansion to PA* in which no new elements are defined. Enayat proved this is false by showing the existence of many models that are not pointwise definable, but become so upon addition of any undefinable class. Inspired by this, I have begun thinking about which models have this property. I will describe some models with this property (and some without) and talk about my search for a non-trivial such model (I will also explain what I mean by “non-trivial” here).
Ordinal analysis via provability logics and ordinal spectra of arithmetical theories
If we start with a sound `weak’ theory –say Primitive Recursive Arithmetic– we can iterate adding consistency statements to it to get stronger and stronger theories. We call the $Pi^0_1$ ordinal of an arithmetical theory U how often one has to iterate adding consistency to PRA “before you hit on U”. We shall see how provability logics are suited for performing large part of the computation. Using different notions of consistency statements yields different ordinals giving rise to an ordinal spectrum of an arithmetical theory. These spectra can be collected into a nice structure and well-known structure: Ignatiev’s universal model for GLP_omega. We shall see how this structure can be used as a roadmap to $Pi_n$ conservation results between fragments.
No Logic Workshop May 8
Our prospective speaker has had to postpone her talk, so there will be no CUNY Logic Workshop on May 8.
Linear fragments of PA – beyond LA_1
I will continue my series of talks on linear fragments of PA. Nevertheless, this talk will be mostly self contained.
In my previous talks, I paid attention almost exclusively to the case of the linear arithmetic LA_1 – a reduct of PA containing only unary multiplication by one distinguished element (scalar) instead of the complete binary multiplication. It was shown that LA_1 is a rather tame theory with most of the properties similar to those of Presburger arithmetic (model completeness, decidability, existence of non-standard recursive models, NIP, …).
In this talk, I will start to examine linear arithmetics with more then one scalar. Starting with LA_2 (two scalars) already, the picture changes dramatically – I will construct a model of LA_2 where a “Peano multiplication” is definable on an infinite initial segment. On the other hand, the quantifier elimination does not fail completely in linear arithmetics with more than one scalar – I will show that all linear arithmetics satisfy bounded QE.
I will summarize the results of this and previous talks in an almost complete characterization of linear fragments of PA which are/aren’t model complete.
If time permits, I will show some applications (in particular a result on (in)dependence of values of multiplication in different points in a saturated model of PA).
Order Type vs. Isomorphism Type for Models of PA II
I will continue to discuss work of Shelah on the problem of under what conditions can the underlying order
type of a model of PA determine its isomorphism type. In particular I will outline a proof of a theorem roughly
stating that a model, M, of PA whose underlying order exhibits a week form of rigidity has the property that any
other model of PA which is order isomorphic to M is in fact isomorphic (as models of PA) to M.
The boldface resurrection axioms
A perfectly generic talk
We will look at perfect generics for countable models of PA. Our goal will be to prove the following theorems: 1. Any countable collection of inductive subsets of a countable model are definable from a single generic. 2. Any countable model has minimally undefinable generics.
Order type vs. Isomorphism type for models of PA
I will discuss recent work of Shelah around the general problem of how the underlying order type of a model of PA may determine influence its isomorphism type as a full model of PA.
Actions on sets of Morley rank $2$
Recently, Borovik and Cherlin initiated a broad study of permutation groups of finite Morley rank with a key topic being high degrees of generic transitivity. One of the main problems that they pose is to show that there is a natural upper bound on the degree of generic transitivity that depends only upon the rank of the set being acted on. Specifically, the problem is to show that the only groups of finite Morley rank with a generically $(n+2)$-transitive action on a set of rank $n$ are those of the form ${PGL}_{n+1}$. A solution when $n=1$, due to Hrushovski, has been known for a few decades as in this case the set is strongly minimal. In this talk, I will present recent work, joint with Tuna Altinel, addressing the case of $n=2$. The analysis of these actions makes considerable use of the structure of groups of small rank, and as such, I will also discuss some new results on groups of Morley rank $4$.
Fermat’s Last Theorem and Catalan’s conjecture in weak exponential arithmetics
This is a joint work with Vitezslav Kala.
Wiles’s proof of Fermat’s Last Theorem (FLT) has stimulated a lively discussion on how much is actually needed for the proof.
Despite the fact that the original proof uses set-theoretical assumptions unprovable in Zermelo-Fraenkel set theory with axiom of choice (ZFC) (namely, the existence of Grothendieck universes), it is widely believed that
certainly much less than ZFC is used in principle, probably nothing beyond Peano arithmetic, and perhaps much less than that.
I will start with a brief summary of existing positive and negative results on provability of FLT in various arithmetical theories.
In this talk, we will consider structures and theories in the language L=(0,1,+,x,<,e), where the symbol e is intended for a (partial or total) binary exponential. We show that Fermat's Last Theorem for e (i.e. the statement "e(a,n)+e(b,n)=e(c,n) has no non-zero solution for n>2″) is not provable in the L-theory Th(N)+Exp, where Th(N) stands for the complete theory of the standard model N=(N,0,1,+,x,<) and Exp is a natural set of axioms for e (consisting mostly of elementary identities). On the other hand, under the assumption of ABC conjecture (in the standard model), we show that the Catalan conjecture for e is provable in Th(N)+Exp (even in a weaker theory). This gives an interesting separation of strengths of these two diophantine problems. Finally, we also show that Fermat's Last Theorem for e is provable (again, under the assumption of ABC in N) in Th(N)+Exp +"coprimality for e". Slides from this talk.
Model-completeness of transseries
The concept of a “transseries” is a natural extension of that of a Laurent series, allowing for exponential and logarithmic terms. Transseries were introduced in the 1980s by the analyst Écalle and also, independently, by the logicians Dahn and Göring. The germs of many naturally occurring real-valued functions of one variable have asymptotic expansions which are transseries. Since the late 1990s, van den Dries, van der Hoeven, and myself, have pursued a program to understand the algebraic and model-theoretic aspects of this intricate but fascinating mathematical object. Last year we were able to make a significant step forward, and established a model completeness theorem for the valued differential field of transseries in its natural language. My goal for this talk is to introduce transseries without prior knowledge of the subject, and to explain our recent work.
A Differential Hensel’s Lemma for Local Algebras
We will discuss a differential version of the classical Hensel’s lemma on lifting solutions from the residue field (working on a local artinian differential algebra over a differentially closed field). We will also talk about some generalizations; for example, one can remove the locality hypothesis by assuming finite dimensionality. If time permits, I will give an easy application on extensions of generalized Hasse-Schmidt operators. This is joint work with Rahim Moosa.
A Differential Algebra Sampler
We discuss several problems involving differential algebraic varieties and ideals in differential polynomial rings. The first one is the completeness of projective differential varieties. We consider examples showing the failure to generalize (even in the finite-rank case) of the classical “fundamental theorem of elimination theory”. We also treat identification of complete differential varieties and a connection to the differential catenary problem. We finish by examining what proof-theoretic techniques have to say about the constructive content of results such as the Ritt-Raudenbush basis theorem and differential Nullstellensatz. Our remarks include work with James Freitag and Omar León-Sánchez as well as ongoing work with Henry Towsner.
On the Existence of Differential Chow Varieties
Chow varieties are a parameter space for cycles of a given variety of a given codimension and degree. We construct their analog for differential algebraic varieties with differential algebraic subvarieties, answering a question of Gao, Li and Yuan. The proof uses the construction of classical algebro-geometric Chow varieties, the model theory of differential fields, the theory of characteristic sets of differential varieties, the theory of prolongation spaces, and the theory of differential Chow forms. This is joint work with Wei Li and Tom Scanlon.
Applications of Differential Algebra to Algebraic Independence of Arithmetic Functions
We generalize and unify the proofs of several results of algebraic independence of arithmetic functions using a theorem of Ax on differential Schanuel conjecture. Along the way of we investigation, we found counter-examples to some results in the literature.
JAF/MAMLS in NYC
The second joint JAF/MAMLS (Journées sur les Arithmétiques Faibles and Mid Atlantic Mathematical Logic Seminar) will be held at the CUNY Graduate Center 7-9th of July 2015. Confirmed speakers include:
Sam Buss, Petr Glivický, Joel Hamkins, Karen Lange, James Schmerl, Jerzy Tomasik, and Henry Towsner.
The conference is organized by Roman Kossak (Chair), Patrick Cegielski, Alfred Dolich, and Kerry Ojakian. The conference website is here. Funding is available to support participant travel. Please write to jafnycfund@gmail.com to apply for support.
The undecidability of lattice-ordered groups II
In this talk I will discuss conjugacy in the automorphism group of the rationals as a linearly ordered set, and then show that the integers, together with addition and multiplication, can be interpreted in Aut(Q), and thus that the theory of Aut(Q) is undecidable.
Countable Arithmetically Saturated Models and the Small Index Property.
In 1994 Lascar proved that countable arithmetically saturated models of PA have the Small Index Property. In this talk we outline the proof and discuss related results and open problems.
Syntactic Epistemic Logic and Games III
We discuss the Muddy Children puzzle MC, identify and fix the gap in its solution: a completeness analysis is required if the problem is specified syntactically, but analyzed by reasoning on a specific model. We show that the syntactic description of MC is complete w.r.t. its model used in the standard solution. We will present two proofs of completeness: syntactic, by induction on a formulas, and semantic, which makes use of bounded morphisms, a special case of bisimulations. We then present a modification of MC, MClite, and show that it is not deductively complete, has no semantic characterization and cannot be handled by traditional semantic methods. We give a syntactic solution of MClite.
Time permitting, we will venture further into extensive games and their epistemic models
The undecidability of lattice-ordered groups
In this talk I will discuss conjugacy in the automorphism group of the rationals as a linearly ordered set, and then show that the integers, together with addition and multiplication, can be interpreted in Aut(Q), and thus that the theory of Aut(Q) is undecidable.
Friday, April 10, 2015
Spring break
CUNY’s spring vacation is April 3-11, 2015. Therefore, no seminars will meet at the Graduate Center on April 3, nor on April 10.
Syntactic Epistemic Logic and Games II
The Syntactic Epistemic Logic, SEL, suggests making the syntactic formalization of an epistemic scenario its formal specification. Since SEL accommodates constructive model reasoning, we speak about extending the scope of formal epistemology. SEL offers a cure for two principal weaknesses of the traditional semantic approach.
1. The traditional semantic approach in epistemology covers only deductively complete scenarios in which all epistemic assertions of any depth are specified. However, intuitively, “most” of epistemic scenarios are not complete. SEL suggests a way to handle incomplete scenarios with reasonable syntactic descriptions.
2. In addition, SEL seals the conceptual and technical gap, identified by R. Aumann, between the syntactic character of game descriptions and the semantic method of analyzing games.
February 13
Neither the Logic Workshop nor the Model Theory Seminar will meet on Friday, Feb. 13, 2015. Both Feb. 12 and Feb. 16 are CUNY holidays. We will resume on Friday, Feb. 20.
Differential-Henselian Fields
I will discuss valued differential fields. What parts of valuation theory go through for these objects, under what conditions? Is there a good differential analogue of Hensel’s Lemma? Is there a reasonable notion of differential-henselization? What about differential-henselianity for systems of algebraic differential equations in several unknowns?
I will mention results as well as open questions. The results are part of joint work with Matthias Aschenbrenner and Joris van der Hoeven, and have turned out to be useful in the model theory of the valued differential field of transseries.
Model theory and algebraic geometry in groups and algebras
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
Sunday, December 7, 2014
Monday, December 8, 2014
Tuesday, December 9, 2014
Cornell MAMLS: 60 years of Dow, December 6-9, 2014
In December there will be a special meeting of the Mid Atlantic Logic Seminar (MAMLS) in honor of Alan Dow. The meeting will take place at Cornell University from December 6-9 (talks will begin on the morning of December 6th end at lunch time on the 9th).
The following people have agreed to give plenary talks:
Alexander Arhangelskii (Ohio University)
Alan Dow (University of North Carolina, Charlotte)
Todd Eisworth (Ohio University)
Klass Pieter Hart (Delft University of Technology)
Istvan Juhasz (Alfred Renyi Institute of Mathematics)
Piotr Koszmider (Polish Academy of Sciences)
Jan van Mill (University of Amsterdam)
Arnold Miller (University of Wisconsin)
Juris Steprans (York University)
Stevo Todorcevic (University of Toronto and CNRS, Paris)
Additional invited talks will be given as well. (There will be no contributed talks.)
To register (free) and for more information, visit www.math.cornell.edu/~dow.
Bounded Second-Order Arithmetic I
We will discuss axiom systems for weak second order arithmetic. In the study of bounded arithmetic, the base theory is called V^0; we will discuss coding and counting in V^0 and in an extension of it. We will give at least one example of a sentence that is not provable in V^0 but is provable in the extension.
Methods of constructing points from regions of space
Rafał Gruszczyńsk (Nicolaus Copernicus University, Toruń) will give an informal, non-colloquium talk this Friday, Nov. 21, at 2pm, in the seminar room (Philosophy 716) at Columbia University. The title of the talk is “Methods of constructing points from regions of space”. Everybody is invited. The talk should be of special interest to colleagues and students working in logic, ontology, the philosophy of mathematics, and the philosophy of space and time.
Forcing over models of arithmetic
I will talk about forcing over models of arithmetic. Our primary application will be the following theorem, due to Simpson: if a model M of PA is countable, then M has a subset U such that that (M,U) is a pointwise definable model of PA*. Time permitting, we will see that the MacDowell–Specker theorem fails for uncountable languages: for M countable and nonstandard, there are U_alpha for alpha < omega_1 such that (M, U_alpha)_{alpha < omega_1} is a model of PA* and has no elementary end extensions.
Decoding in the automorphism group of a model of arithmetic.
In the talk I will discuss results on recovering a countable recursively saturated model of Peano Arithmetic from its automorphism group.
The pentagon lattice II
The pentagon lattice
In this talk, I will discuss the proof that for every countable model M of PA, there is an end extension N such that Lt(N /M) is isomorphic to N5. I will begin by constructing an infinite representation of N5 and then discuss Theorem 4.5.21 in TSOMOPA which shows how to construct an extension from such a representation.
The rise and fall of accuracy-first epistemology
Accuracy-first epistemology aims to supply non-pragmatic justifications for a variety of epistemic norms. The contemporary roots of accuracy-first epistemology are found in Jim Joyce’s program to reinterpret de Finetti’s scoring-rule arguments in terms of a “purely epistemic” notion of “gradational accuracy.” On Joyce’s account, scoring rules are conceived to measure the accuracy of an agent’s belief state with respect to the true state of the world, and Joyce argues that this notion of accuracy is a purely epistemic good. Joyce’s non-pragmatic vindication of probabilism, then, is an argument to the effect that a measure of gradational accuracy so imagined satisfies conditions that are close enough to those necessary to run a de Finetti style coherence argument. A number of philosophers, including Hannes Leitgeb and Richard Pettigrew, have joined Joyce’s program and gone whole hog. Leitgeb and Pettigrew, for instance, have argued that Joyce’s arguments are too lax and have put forward conditions that narrowing down the class of admissible gradational accuracy functions, while Pettigrew and his collaborators have extended the list of epistemic norms receiving an accuracy-first treatment, a program that he calls Evidential Decision Theory.
In this talk I report on joint work with Conor Mayo-Wilson that aims to challenge the core assumption of Evidential Decision Theory, which is the very idea of supplying a truly non-pragmatic justification for anything resembling the Von Neumann and Morgenstern axioms for a numerical epistemic utility function. Indeed, we argue that none of axioms have a satisfactory non-pragmatic justification, and we point to reasons why to suspect that not all the axioms could be given a satisfactory non-pragmatic justification. Our argument, if sound, has ramifications for recent discussions of “pragmatic encroachment”, too. For if pragmatic encroachment is a debate to do with whether there is a pragmatic component to the justification condition of knowledge, our arguments may be viewed to attack the true belief condition of (fallibilist) accounts of knowledge.
The Hales-Jewett Theorem and Applications II
The Hales-Jewett Theorem and Applications
The Hales-Jewett Theorem has applications in Ramsey Theory, and is also used to prove properties about lattices of elementary substructures. We will prove the Hales-Jewett Theorem and discuss applications.
CUNY Pragmatics Workshop: Relevance, Games, & Communication
There will be a two day meeting on pragmatics at the CUNY Graduate center on October 14 and 15, in room 9207.
Details are available here.
Please note that the program on that site is tentative and there may be more speakers than the ones announced.
Plural Logic and Sensitivity to Order
David Nicolas, Institut Jean Nicod, Paris
Sentences that exhibit sensitivity to order (e.g. “John and Mary arrived at school in that order” and “Mary and John arrived at school in that order”) present a challenge for the standard formulation of plural logic. In response, some authors have advocated new versions of plural logic based on more fine-grained notions of plural reference, such as serial reference (Hewitt 2012) and articulated reference (Ben-Yami 2013). The aim of this work is to show that sensitivity to order should be accounted for without altering the standard formulation of plural logic. In particular, sensitivity to order does not call for a more fine-grained notion of plural reference. We point out that the phenomenon in question is quite broad and that current proposals are not equipped to deal with the full range of cases in which order plays a role. Then we develop an alternative, unified account, which locates the phenomenon not in the way in which plural terms can refer, but in the meaning of special expressions such as “in that order” and “respectively”.
Elementary end extensions and the pentagon lattice
By a theorem of Wilkie, every countable model M of PA has an elementary end extension N such that interstructure lattice Lt(N/N) is isomorphic to the pentagon lattice. I will explain why the theorem does not generalize to uncountable models.
MOPA has a new schedule
Models of Peano Arithmetic aka MOPA starts next week. We will meet on Wednesdays 4:50 – 5:50 in GC 6300 (new location).
Model Theory Seminar Resumes on October 10th
Note that the Kolchin Seminars on Differential Algebra for September 12th and September 19th should
be of interest to model theorists.
Independence in tame abstract elementary classes
Good frames are one of the main notions in Shelah’s classification theory for abstract elementary classes. Roughly speaking, a good frame describes a local forking-like notion for the class. In Shelah’s book, the theory of good frames is developed over hundreds of pages, and many results rely on GCH-like hypotheses and sophisticated combinatorial set theory.
In this talk, I will argue that dealing with good frames is much easier if one makes the global assumption of tameness (a locality condition introduced by Grossberg and VanDieren). I will outline a proof of the following result: Assume K is a tame abstract elementary class which has amalgamation, no maximal models, and is categorical in a cardinal of cofinality greater than the tameness cardinal. Then K is stable everywhere and has a good frame.
No seminars on Sept. 26 or October 3
CUNY will have holidays on two consecutive Fridays, September 26 and October 3, 2014, so the Logic Workshop and other seminars will not meet on those days.
Lattices of elementary substructures of arithmetically saturated models of PA
An introduction to arithmetically saturated models of PA
On compositions of symmetrically and elementarily indivisible structures
A structure M in a first order language L is indivisible if for every colouring of its universe in two colours, there is a monochromatic substructure M’ of M such that M’ is isomorphic to M. Additionally, we say that M is symmetrically indivisible if M’ can be chosen to be symmetrically embedded in M (That is, every automorphism of M’ can be can be extended to an automorphism of M}), and that M is elementarily indivisible if M’ can be chosen to be an elementary substructure.
The notion of indivisibility is a long-studied subject. We will present these strengthenings of the notion,
examples and some basic properties. in [1] several questions regarding these new notions arose: If M is symmetrically indivisible or all of its reducts to a sublanguage symmetrically indivisible? Is an elementarily indivisible structure necessarily homogeneous? Does elementary indivisibility imply symmetric indivisibility?
We will define a new “product” of structures, generalising the notions of lexicographic order and lexicographic product of graphs, which preserves indivisibility properties and use it to answer the questions above.
[1] Assaf Hasson, Menachem Kojman and Alf Onshuus, On symmetric indivisibility of countable structures, Model Theoretic Methods in Finite Combinatorics, AMS, 2011, pp.417–452.
Submodel Lattices of Nerode Semirings
Let TA be True Arithmetic, and let TA_2 be the set of Pi_2 sentences in TA.
If N is a model of TA_2, then the set Lt(N) of substructures of N that are also models of TA_2
forms a complete lattice. A Nerode semiring is a finitely generated model of TA_2.
I will be talking about some joint work with Volodya Shavrukov in which we investigate the possible lattices that are isomorphic to some Lt(N), where N is a Nerode semiring. Existentially closed models of TA_2 were studied long ago. The possible Lt(N) will also be considered for e.c. Nerode semirings.
The Humean Thesis on Belief
I am going to make precise, and assess, the following thesis on (all-or-nothing) belief and degrees of belief: It is rational to believe a proposition just in case it is rational to have a stably high degree of belief in it.I will start with some historical remarks, which are going to motivate calling this postulate the “Humean thesis on belief”. Once the thesis has been formulated in formal terms, it is possible to derive conclusions from it. Three of its consequences I will highlight in particular: doxastic logic; an instance of what is sometimes called the Lockean thesis on belief; and a simple qualitative decision theory.
Savage’s Subjectivism and Countable Additivity
This talk is mainly on the issue of additivity in Savage’s theory of subjective expected utility. It is divided into three parts. First, I will comment, by providing a brief historical survey, on Savage’s reasons for adopting finitely additive probability measure in his decision model. It will argue that Savage’s set-theoretic argument for rejecting countable additivity is inconclusive. In the second part, I will discuss some defects of finite additivity in Savage’s system. This will be followed, in the last part, by a detailed reconstruction and revision of Savage’s theory. It will be shown that Savage’s final representation theorem, which extends the derived utility function for simple acts to general acts, is derivable from the first six of his seven postulates provided countable additivity is in sight, a conjecture made by Savage himself.
Automorphism groups of large models: small index property and AECs
The general question of recovering a model (or its theory, or some appropriate AEC connected to it) from its automorphism group was originally studied by Hodges, Lascar, Shelah among others. The “Small Index Property” (SIP) emerged in their work as a bridge between topological and purely algebraic properties of those groups and ultimately as a tool to understand. I will speak about the SIP from two perspectives: first, I will present aspects of Lascar and Shelah’s proof of SIP for uncountable saturated structures (succinctly, if M is such a structure and G is a subgroup of Aut(M) with index less than or equal to λ=|M|, then G is open in the “λ-topology”) and then I will present an extension of the SIP to some abstract elementary classes. This second part of the lecture is joint work with Zaniar Ghadernezhad.
Lattices with congruence representations as interstructure lattices
In this talk I will discuss arguably the most general result on which finite lattices may
arise as substructure lattices of models of Peano arithmetic. The focus will be on lattices with
congruence representations.
Let A be an algebra (a structure in a purely functional signature). We may consider the set of all congruence relations on A, which naturally forms a lattice Cg(A). A lattice L is said to have a congruence representation if there is an algebra A so that L is isomorphic to Cg(A)*. (Cg(A)* is the lattice obtained from Cg(A) be interchanging the roles of join and meet.) The main theorem is that if L is a finite lattice with a congruence representation and M is a non-standard model of PA then there is a cofinal elementary extension N of M so that the interstructure lattice Lt(N/M) is isomorphic to L.
This talk is intended as an overview. I do not plan on going into any details of the proofs but rather will survey the necessary tools that go into proving the theorem.
May 12-13 Turing meeting at Columbia University
This is a preliminary announcement: on May 12-14, 2014, a workshop entitled Mind, Mechanism, and Mathematics will be held at Columbia University. This is the second workshop in the Turing Centenary Research Project, which focuses on the work and the legacy of Alan Turing. Details are available at the conference webpage.
Topologic: old and new results
In 1992, Moss and Parikh introduced Toplogic an epistemic modal logic whose semanticas are based on subsets. Since then, research on this logic and it many extensions has been going strong. I will survey most of these results in the first part of this talk. On the second part, I will present how topologic can form a basis for the formalization of belief change operators, such as update, conditionals and contraction. Arbitrary nestings and iterations of such operators are easily automatized which is not the case in other studies of belief change in object language.
Symmetric random constructions in model theory
Several well known universal homogeneous structures, such as the Rado graph and the rational Urysohn space, can be obtained via probabilistic constructions that do not make use of the labeling of the underlying set. Which other countable structures admit random constructions that are symmetric in this way? Several years ago in the CUNY Logic Workshop I presented a characterization of such structures, due to Ackerman, Patel and myself. Here I will report on two recent extensions. This is joint work with Nate Ackerman, Aleksandra Kwiatkowska, Jaroslav Nesetril, and Rehana Patel.
One natural question concerns theories rather than structures. I will present results describing when there are symmetric probabilistic constructions of models of a given theory that assign probability zero to each isomorphism class of models.
One may further ask which structures admit just one such probabilistic construction. I will provide a complete list: there are only five of them, up to interdefinability. Furthermore, any countable structure admitting more than one invariant measure must admit continuum-many ergodic invariant measures.
Blass-Gaifman and Ehrenfeucht lemmas
Proofs of the lemmas will be given and some consequences related to substructure lattices will be explained.
Probabilistic proof of the existence of expanding families of graphs
The speaker proved that almost certainly most infinite families of bipartite graphs are expanding families.
Ordered structures with dense/co-dense sets
The canonical class of densely ordered structures which may be considered “tame” are the o-minimal structures – namely those structures (M,<,...) where any definable subset X is a finite union of points and intervals. In this talk I will consider structure (M,<,...) in which there are definable subsets which are dense and co-dense in the line yet which may still be considered "tame". I will outline some of the general theory of these structures, compare the model theoretic properties of the examples, and discuss various open problems arising out of this study.
MOPA moves to Mondays
Models of Peano Arithmetic, aka MOPA, is moving from Wednesdays to Mondays. The seminar will
meet in GC 4214.03 from 6:30 to 8:00pm. The theme for this semester Lattices of Elementary Substructures. First talks will be really elementary. All are welcome.
Fullness
A model M of PA is full if, for every set X definable in (M, omega), there is an X’ definable in M with the same standard part (i.e. X intersect omega = X’ intersect omega). I will show a result due to R. Kaye that characterizes fullness: M is full if and only if its standard system is a model of full second order comprehension (CA0). I will give a brief outline of the proof, which involves translations (in both directions) between the language of second order arithmetic and the (first order) language of PA with a “standardness” predicate. If there is time, I also plan to discuss full saturation and some connections to other notions of saturation (in particular, transplendence and possibly arithmetic saturation).
Welcome to the Set Theory seminar Spring 2014
The set theory seminar will be coordinated in Spring 2014 by Thomas Johnstone.
Tom pointed out that it’s been about ten years that we have been having our weekly Set Theory seminar at CUNY, starting with a few of Joel Hamkins’s graduate students who met on a weekly basis (George, Jonas, Victoria, and himself), and we’ve had many interesting seminar meetings since then.
At this point the schedule is wide open, so please let Tom know if you’d be interested to give a talk.
A non-standard explanation of Reverse Mathematics
Reverse Mathematics (RM) is a program in the Foundations
of Mathematics initiated around 1975 by Harvey Friedman. We
discuss the aims and results of RM, in particular the “Big Five”
phenomenon. We consider non-standard explanations and
nonstandard robustness results for the Big Five phenomenon.
This is joint work with Damir Dzhafarov.
The Univalence Axiom
In this talk, we will begin by discussing application of functions on paths, and the transport lemma (Lemma 2.3.1 of the book). We will then discuss the notion of homotopies, and equivalences, with a few examples. From their we will be able to define a function which will be called “idtoeqv”. Roughly, this function takes equality of types to equivalence of types. This will allow us to state the univalence axiom. If time permits, we will end with how the various type forming constructions behave in the presence of the higher groupoid structure.
Equivalence relations in models of Peano arithmetic
The talk will be about the correspondence between definable equivalence relations on countable recursively saturated models of PA and the closed normal subgroups of their automorphism groups.
When are subsets of a model “coded”? II
An Introduction to Intuitionistic Type Theory
Homotopy type theory is a new foundation for mathematics based upon type theory and the univalence axiom. This is a topic that unifies the foundations of mathematics, computer science, algebraic topology, and type theory.
This will be the first focused reading of the Homotopy type theory reading group, covering sections 1.1-1.7 of the book. This will serve as an introduction to Intuitionistic Type Theory as developed by Martin-Löf, including notions of decidability and judgmental equality, up through dependent function and pair types (aka Pi and Sigma).
The reading group includes those with type theory background and no homotopy background, with homotopy background but no type theory background, and with no significant background in either but a healthy thirst for knowledge.
Types, Spaces, and Higher Groupoids
Last time we discussed fibrations of sets, spaces, and types. We noted that path induction allows us to prove that the type family of equalities over a given type A is “homotopy equivalent” to A.
This week, we will continue with this and discuss the groupoid structure of spaces (paths) and types (equalities). In doing so, we will establish the “interchange law” for 2-categories, and see that in the particular case of spaces and types that this allows us to prove that the composition law is commutative (up to a higher equivalence) for 2-paths and 2-equivalences that begin and end at the same point.
We shall also discuss how non-dependent functions between types give rise to functors on the associated groupoids of equivalences. This leads to the problem of what to do for dependent functions, and it turns out that fibrations give us a solution to this, and thus we will have come full circle.
Thanksgiving
The Graduate Center will be closed on Friday, November 29, 2013, the day after Thanksgiving. CUNY will operate on a Friday schedule on Wednesday, Nov. 27, but the Logic Workshop will not meet that day.
When are subsets of a model “coded”?
I will present a result by J. Schmerl that characterizes when a collection of subsets of a given model, M, will appear as the coded sets in some elementary end extension of M. This is an analogue to Scott’s theorem, which characterizes when a collection of sets of natural numbers can be the standard system of some model of PA. If there is time, I will also present some extensions of the result.
A Jónsson $\omega_1$-like model of set theory
A first-order structure of cardinality $\kappa$ is said to be Jónsson if it has no proper elementary substructure of cardinality $\kappa$. The speaker will prove a theorem of Julia Knight that there is a Jónsson $\omega_1$-like model of set theory, using a construction of Ali Enayat.
How to make a full satisfaction class
Paraconsistent Justification Logic
In the literature of belief revision, there is one approach called belief base belief revision, where the belief set is not required to be closed under a consequence relation. According to Sven Ove Hansson, in belief base belief revision, there are two ways to define the revision operator:
revision = expansion + contraction
revision = contraction + expansion
Hansson has a result that these two ways of defining the revision operator do not collapse into the same operator. Hansson also thinks that in the first way, there is an intermediate inconsistent epistemic state that occurs after expansion. Paraconsistent justification logic is intended to model the agent’s justification structure, when the agent is in such an inconsistent epi-state. My hope is that this logic could help us better model belief revision.
In my talk, the motivation will be better clarified. And, a paraconsistent justification logic system will be introduced.
Schmerl’s Lemma and Boundedly Saturated Models II
The Columbia-CUNY Workshop in Logic, Probability, and Games
There will be a meeting of this seminar on October 18 from 2 to 4 PM in room 4419. Haim Gaifman (Columbia) and Rohit Parikh (CUNY) will speak. Details will be announced next week.
This is a meeting of a joint CUNY-Columbia research group on Logic, Probability and Games.
Description: This workshop is concerned with applying formal methods to fundamental issues, with an emphasis on probabilistic reasoning decision theory and games. In this context “logic” is broadly interpreted as covering applications that involve formal representations. The topics of interest have been researched within a very broad spectrum of different disciplines, including philosophy (logic and epistemology), statistics, economics, and computer science. The workshop is intended to bring together scholars from different fields of research so as to illuminate problems of common interest from different perspectives. Throughout each academic year, meetings are regularly presented by the members of the workshop and distinguished guest speakers and are held alternatively at Columbia University and CUNY Graduate Center.
Cofinal extensions of recursively saturated ordered structures
More on fullness
Continuing with the discussion from last week, I will state a few conditions that imply fullness and use that to show a few basic examples of full models. I will also show one direction of Kaye’s theorem that a model M is full if and only if its standard system is a model of full second order comprehension (CA_0).
$\omega_1$-like models of PA
I will give a brief survey of what is known about $omega_1$-like models of PA (much) and what is not known (much).
A self-specializing Souslin tree
I will present a construction, assuming Jensen’s combinatorial principle diamond, of a Souslin tree T which, after forcing with T, will be Ahronszajn off the generic branch. More precisely, forcing with T will add a cofinal branch b through T, yet in the generic extension by b, whenever p is a node of T which does not belong to b, then the subtree of T which lies above p will be Q-embeddable, meaning that there is an order preserving function from that subtree to the rationals. This shows that the rigidity property of being Souslin off the generic branch is strictly stronger than the unique branch property, two notions of rigidty previously studied in joint work with Joel Hamkins, where it was conjectured that it would be possible to construct such a self specializing Souslin tree.
CUNY Fall 2013 semester begins
Welcome to our logic events at CUNY for the Fall 2013 semester, which begins on August 28, 2013.
We have some great talks planned for all our various seminars. Please check back for updated detailed titles and abstracts. Note the Rutgers MAMLS conference October 19-20.
Finite forms of Gowers’ Theorem on the oscillation stability of c_0
We give a constructive proof of the finite version of Gowers’ FIN_k Theorem and analyze the corresponding upper bounds. The FIN_k Theorem is closely related to the oscillation stability of c_0. The stabilization of Lipschitz functions on arbitrary finite dimensional Banach spaces was proved well before by V. Milman. We compare the finite FIN_k Theorem with the Finite Stabilization Principle found by Milman in the case of spaces of the form ell_{infty}^n, ninN, and establish a much slower growing upper bound for the finite stabilization principle in this particular case.
Wednesday, September 4, 2013
Thursday, September 5, 2013
Friday, September 6, 2013
Friday, September 13, 2013
Monday, October 14, 2013
Thursday, November 28, 2013
Friday, November 29, 2013
No CUNY classes
There are no CUNY classes scheduled on the official university calendar for these days. Usually, our seminars do not run on days when CUNY classes are not in session, although one should check whether the calendar does have events scheduled. CUNY Fall 2013 Academic Calendar
Conference in honor of Carol Wood, May 31 – June 1, Wesleyan Univ.
Professor Carol Wood will retire this summer after 40 years at Wesleyan University. In honor of her retirement and her many contributions to the university and the profession, the Department of Mathematics & Computer Science at Wesleyan University is hosting a conference on May 31 and June 1, 2013. The conference will start on the afternoon of Friday, May 31 and will continue through the day on Saturday, June 1. For further details, please visit http://cwoodconf.conference.wesleyan.edu/.
VC Dimension and Breadth in Modules
I will review the concept of vc-dimension of a formula, and the vc-function of a first order theory. The concept of breadth on the lattice of PP-definable subgroups of a module will be defined, and the relationship between these notions will be explored. Some model theory of Modules will be used to refine certain questions from the paper of Aschenbrenner, Dolich, Haskell, Macpherson, and Starchenko. The talk will include several pictures and examples to clarify the notions involved.
Mittag-Leffler objects in definable categories of modules
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.
Justification Logic for Argumentation
Argumentation is the process of giving arguments, counter-arguments, counter-counter-arguments and so on. In artificial intelligence, since the late 1980s there has been research that tries to use formal methods to approach argumentation theory. One very young approach in formal argumentation theory is to study argumentation under the framework of modal logic. Two possible advantages of doing so are: (1) this is a new angle, from which to look at argumentation we might have new insights, and (2) techniques in modal logic might become available for studying argumentation. In this talk, I would like to provide a different way of connecting argumentation theory and modal logic. More specifically, I would like to try to locate formal argumentation theory within the framework of justification logic. The resulting logic is a justification logic for argumentation.
BEST conference, June 16-19, 2013
BOISE EXTRAVAGANZA IN SET THEORY (BEST)
We are happy to announce that the twentieth meeting of the Boise Extravaganza in Set Theory (BEST) will be hosted as a symposium at the annual meeting of the Pacific Division of the American Association for the Advancement of Sciences. Initial details of BEST 2013 are below. For much more information, please consult the BEST 2013 website.
DATES: June 16 – 19, 2013
PLACE: University of Nevada, Las Vegas
Please consult the conference webpage at URL http://diamond.boisestate.edu/~best/index.html
The 20-th meeting of BEST will be hosted at University of Nevada Las Vegas as a AAAS-PD symposium during June 16 (Sunday) – June 19 (Wednesday), 2013
It is organized by Liljana Babinkostova, Andres Caicedo, Sam Coskey and Marion Scheepers.
Contributed and invited talks will be held on Monday, Tuesday and Wednesday at the University of Las Vegas, Nevada.
BEST PLENARY SPEAKERS:
The four invited plenary speakers are:
Todd Eisworth (Ohio University)
Masaru Kada (Osaka Prefecture University, Japan)
Thilo Weinert (University of Bonn, Germany)
Lynne Yengulalp (University of Dayton)
In addition to these four plenary talks, the program has ten reserved speaking slots for students, four reserved slots for post-docs and 2 reserved slots for pre-tenure tenure track faculty.
POTENTIAL TRAVEL AWARDS:
We have applied for funding from the NSF to assist with travel costs for speakers for these reserved speaking slots. The grant proposal has been recommended for funding, but the final award decision has not yet been made. We strongly recommend that speakers from the categories of student speaker, psot-doc speaker or pre-tenure tenure track speaker, interested in presenting at BEST 20, apply as soon as possible to the BEST selection committee for potential travel assistance to participate in BEST 20. Application requirements for these funds are as follows:
Student speakers:
1. Prior to April 16, 2013 submit an abstract for the proposed 14 minute presentation at the abstract submission site.
2. Prior to May 15, 2013 submit a resume including current affiliation, advisor name and stage of study, and a separate statement of goals.
3. Prior to May 15, 2013 have the advisor separately submit a recommendation letter, outlining the benefit of participation in the conference via presentation to the student.
Please note that student speakers are eligible for a AAAS-PD award of excellence for their presentation at BEST 20. Winners of these awards will be announced at the AAAS-PD banquet on June 18, 2013. Student participants will be guests at this banquet.
Post-Doc speakers:
1. Prior to April 16, 2013 submit an abstract for a proposed 25 minute presentation at the abstract submission site.
2. Prior to May 15, 2013 submit a resume including current affiliation, post-doc mentor name, and a list of publications, and a separate statement of goals.
Pre-tenure tenure track faculty:
1. Prior to April 16, 2013 submit an abstract for a proposed 25 minute presentation at the abstract submission site.
2. Prior to May 15, 2013 submit a resume including current affiliation, years towards tenure, a current list of publications, and a separate statement of goals.
Please note that the AAAS-PD also offers up to 20 travel awards of up to $150 to students to help defray travel expenses to participate in the AAAS-PD annual meeting: This includes BEST.
CONTRIBUTED TALKS:
In addition to these speakers there will also be a number of slots for contributed talks. Anyone wishing to speak at BEST 20 should submit an abstract as soon as possible (preferably prior to April 16) at the abstract submission site. It is strongly recommended to also contact one of the organizers as soon as possible to indicate interest/intention in presenting a talk at BEST 20.
Important deadlines:
DEADLINE 1: REGISTRATION: Please consult http://diamond.boisestate.edu/~best/registration.html Early registration ends May 31. After that only on-site registration will be possible. Registration fees are dependent on date of registration. We kindly request that tenure track mathematicians planning to participate in BEST 20 consider acting as judges for the student presentations. The registration form has a place where willingness to act as a judge can be indicated. There are also a number of excursions available that can be indicated on the registration form. Also please consider attending the award banquet – meal choices are available on the registration form.
DEADLINE 2: ABSTRACTS: Atlas Conferences, Inc. is providing abstract services for BEST 20. Abstracts submitted by the deadline will appear in the proceedings of the annual conference of the AAAS-PD. The deadline for submitting an abstract is APRIL 16. The url for the abstract submission website is http://atlas-conferences.com/cgi-bin/abstract/submit/cbgn-01.
LODGING: Las Vegas offers many lodging options. Please see the conference website http://diamond.boisestate.edu/~best/lodging.html for lodging suggestions by the AAAS-PD.
The Non-Axiomatizability of the First-Order Theory of O-Minimality
For a fixed language L, the first-order L-theory of o-minimality is the set of those L-sentences true in all o-minimal L-structures. It follows from a classical model-theoretic result that a model of this theory is either o-minimal or an elementary substructure of an ultraproduct of o-minimal L-structures. We call these structures pseudo-o-minimal, and note that they will generally not be o-minimal.
In this talk, I will discuss how the study of pseudo-o-minimality fits in to the ongoing project of classifying the tame weakenings of o-minimality. My main focus will be on the recent question of whether for certain fixed languages L, the first-order L-theory of o-minimality is recursively axiomatizable. I will show that it is not whenever L extends the language of ordered fields by at least one new predicate or function symbol. With the time remaining, I will outline some of what is known about the relative tameness of pseudo-o-minimal structures, and mention some open problems in the area.
Interview Series
We are pleased to announce the launch of the New York Logic Interview Series.
Interviews of various prominent logicians, undertaken by members of the New York logic community, will periodically be posted here—please check back regularly! We have big plans…
The New York Logic Blog
Welcome to the New York Logic Blog!
This is a group blog run by the New York Logic community, and includes and welcomes all manner of announcements, mathematical logic posts, philosophical logic posts, invitations, inquiries, discussions or any other type of post concerning mathematical or philosophical logic of interest to the New York logic community.
If you have an account on nylogic.org with author privileges, please feel free to make on-topic posts here.
By setting the appropriate event date field on the post, they will appear automatically in the NY Logic Calendar.
Friday, April 19, 2013
New York Graduate Student Logic Conference
→ go to the Conference Website
The fourth New York Graduate Student Logic Conference, which will be held at the CUNY Graduate Center, located in midtown Manhattan, New York, on Thursday, April 18 and Friday April 19, 2013. The goal of this conference is to promote graduate education in logic by bringing together the best graduate students working in any part of the subject. Students will meet and hear talks by other students in logic, give talks on their own research or on their research area, and have the opportunity to interact with senior logicians. All interested members of the mathematical community are invited to attend.
Thursday, April 4, 2013
Friday, April 5, 2013

Simplicity Conference
Ideals of Practice in Mathematics & the Arts
→ go to the Conference Website
Simplicity: Ideals of Practice in Mathematics & the Arts
A conference at the Graduate Center, City University of New York, April 3–5, 2013
Lectures by and conversations among twenty-five mathematicians, artists, art historians, philosophers, and architects, accompanied by a program of artist’s films.
To find “criteria of simplicity” was the goal of David Hilbert’s recently discovered twenty-fourth problem on his renowned list of open problems given at the 1900 International Congress of Mathematics in Paris. At the same time, simplicity and economy of means are powerful impulses in the creation of artworks.
Recognizing the aesthetic nature of Hilbert’s question, this conference aims to focus on criteria of simplicity in mathematics that are informed by perspectives from art and architecture, the philosophy and history of mathematics, and current mathematical practice. Each day of this conference will feature talks and roundtable discussions interspersed by screenings of films by artists.
Invited participants:
Andrew Arana, Philosophy, University of Illinois at Urbana-Champaign
Rachael DeLue, Art & Archaeology, Princeton University
Juliet Floyd, Philosophy, Boston University
Curtis Franks, Philosophy, University of Notre Dame
Étienne Ghys, Mathematics, École Normale Supérieure, Lyon
Mikhael Gromov, Mathematics, IHES, Paris and New York University
Rosalie Iemhoff, Philosophy, Utrecht University
Hanna Johansson, Philosophy, History, Culture & Art Studies, University of Helsinki
Maryanthe Malliaris, Mathematics, University of Chicago
Dusa McDuff, Mathematics, Barnard College, Columbia University
Juhani Pallasmaa, Juhani Pallasmaa Architects, Helsinki
David Reinfurt, designer, New York
Marja Sakari, Kiasma Museum of Contemporary Art, Helsinki
Amy Sandback, art historian, New York
Grigor Sargsyan, Mathematics, Rutgers University
Peter Sarnak, Mathematics, Institute for Advanced Study & Princeton University
Kate Shepherd, artist, New York
Riikka Stewen, Finnish Academy of Fine Arts, Helsinki
Dennis Sullivan, Mathematics, Graduate Center, CUNY & SUNY at Stony Brook
Andrés Villaveces, Mathematics, National University of Colombia, Bogotá
Dan Walsh, artist, New York
Stephen Wolfram, Wolfram Research, Concord, MA
Hugh Woodin, Mathematics, University of California, Berkeley
Andrea Worm, Art History, University of Augsburg
Jan Zwicky, Philosophy, University of Victoria
Film program:
Andy Goldsworthy (NY Premiere)
David Hammons
Richard Serra
Andy Warhol
William Wegman
Organizers:
Juliette Kennedy, Mathematics, University of Helsinki
Roman Kossak, Mathematics, Graduate Center and Bronx Community College, CUNY
Philip Ording, Mathematics, Medgar Evers College, CUNY
Ramsey ultrafilters
I will introduce the concept of a Ramsey ultrafilter and show that under Martin’s Axiom, and under the continuum hypothesis, Ramsey ultrafilters exists. I will actually show that this follows from some consequences of MA on cardinal invariants of the continuum. If time permits, I will make a connection to Ramsey’s theorem. This talk is intended to bridge the gap between the previous talk by Miha Habic on Martin’s Axiom and the upcoming talks by Victoria Gitman on Ramsey cardinals.
Computing Bounds from Arithmetical Proofs
We explore the role of the function a+2^x, and its generalizations to higher number classes, in analyzing and measuring the computational content of a broad spectrum of arithmetical theories. Newer formalizations of such theories, based on the well-known normal/safe variable separation of Bellantoni-Cook, enable uniform proof-theoretical treatments of poly-time arithmetics, through Peano arithmetic, and up to finitely iterated inductive definitions.
Martin’s Axiom
Martin’s Axiom is the prototypical forcing axiom, asserting that partial generics exist for ccc forcing. I will present the classical proof of its consistency, due to Solovay and Tennenbaum. If time permits I will also describe some of the consequences of Martin’s Axiom, in particular its effect on the cardinal characteristics of the continuum.
Expanding the realm of the idea of da Costa
Non-classical logics that deny ex falso quod libet are said to be paraconsistent. Since the monumental work of Stanislaw Jaskowski in 1948, a large number of paraconsistent systems have been developed. Those include systems of da Costa, Nelson, Belnap-Dunn, Priest, Batens and Scotch-Jennings. In this talk, we focus on the consistency operator which is the characteristic connective of da Costa’s systems. We understand that the main idea of da Costa is to make explicit, within the system, the area in which you can infer classically. The aim of the talk is twofold. First, we review some of the results within the framework of Logics of Formal Inconsistency. Then, we introduce and present some results on normality operator which generalizes consistency operator so that one can deal not only with inconsistency, but also with incompleteness. Second, we show that the normality operator may be employed, in a sense to be specified, in developing other paraconsistent logics such as modal logics, Nelson’s systems and expansions of the four-valued logic of Belnap and Dunn.
Stability revisited
I will discuss an observation Ivo Herzog and I made in the last millennium that yields a purely topological definition of stability of a complete first-order theory in terms of their Stone spaces.
On strength of weakness
I will explain why countable models of PA which are just recursively saturated do not have maximal automorphisms. If time permits I will also show why recursive saturation implies standard system saturation for models of rich theories.
No seminar on February 26, the planned talk was rescheduled for March 5.
Maximal Automorphisms
A maximal automorphism of a structure M is an automorphism under which no non-algebraic element of M is fixed. A problem which has attracted some attention is when for a theory T any countable recursively saturated model of T has a maximal automorphism. In this talk I will review what is known about this problem in various contexts and then prove a general result that guarantees, under certain mild conditions on T, that any countable recursively saturated model of T does indeed have a maximal automorphism.
Cardinals that might be viewed as miniature superstrong cardinals consistent with V=L
We will discuss cardinals that we may call superstrongly unfoldable cardinals. A cardinal kappa is superstrongly unfoldable if it is theta-superstrongly unfoldable for every ordinal theta, meaning that for subset A of kappa there is a nontrivial elementary embedding j:M–>N between transitive ZFC models having critical point kappa such that j(kappa)>theta and V_{j(kappa)} is a subset of N and the set A is an element of M. Superstrongly unfoldable cardinals lie in consistency strength between weakly compact cardinals and Ramsey cardinals, and they are relatively consistent with V=L. We will show the tighter consistency bounds of strongly unfoldable cardinals below and subtle cardinals above. This is joint work with Joel David Hamkins.
On model reasoning in epistemic scenarios
It was long noticed that the textbook “solution” of the Muddy Children puzzle MC via reasoning on the n-dimensional cube Q_n had a fundamental gap since it presupposed common knowledge of the Kripke model Q_n which was not assumed in the puzzle description. In the MC scenario, the verbal description and logical postulates are common knowledge, but this does not yield common knowledge of the model.
Of course, a rigorous solution of MC can be given by a formal deduction in an appropriate epistemic logic with updates after epistemic actions (public announcements). This way requires an advanced and generally accepted logical apparatus, certain deductive skills in modal logic, and, most importantly, steers away from the textbook “solution.”
We argue that the gap in the textbook “solution” of MC can be fixed. We establish that MC_n is complete with respect to Q_n and hence a reasoning on Q_n can be accepted as a substitute for the aforementioned deductive solution (given that kids are smart enough to establish that this completeness theorem is itself common knowledge). This yields the following clean solution of MC:
1. prove the completeness of MC_n w.r.t. Q_n;
2. argue that (1) is common knowledge;
3. use a properly worded version of the textbook “solution.”
This approach seems to work for some other well-known epistemic scenarios related to knowledge. However, it does not appear to be universal, e.g., it does not work in the case of beliefs. In general, we have to rely on the deductive solution which fits the syntactic description of the problem.
The completeness of MC_n w.r.t. Q_n was established by me some years ago, and shortly after my corresponding seminar presentation, Evan Goris offered an elegant and more general solution which will be presented at this talk.
Forcing for Constructive Set Theory
As is well known, forcing is the same as Boolean-valued models. If instead of a Boolean algebra one used a Heyting algebra, the result is a Heyting-valued model. The result then typically models only constructive logic and falsifies Excluded Middle. On the one hand, many of the same intuitions from forcing carry over, while on the other the result is quite foreign to a classical mathematician. I will give a survey of perhaps too many examples, and call for the importation of more methods from current classical set-theory into constructivism.
Partial Content
Some approaches to model theory for classes of finite structures
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.
Transplendence
Resplendence is a very useful form of second order saturation. Transplendence, introduced by Fredrik Engström and Richard Kaye, is a stronger notion, that guarantees existence of expansions omitting a type. I will give motivation and outline Engström and Kaye’s general theory of transplendent structures.
Reverse mathematics for second-order categoricity theorem
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.
Pfaffian functions vs. Rolle leaves
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.
A Set-Theoretic Approach to Model Theory
Although one always employs logic in proofs, the foundations of many branches of mathematics appear to be predominantly set-theoretic: one defines a topological space to be a pair (X, τ) consisting of a set X and a collection τ of subsets satisfying certain well-known properties; one defines a group to be a pair (G, μ) consisting of a set G and a subset μ ⊂ G × G × G as the binary operation satisfying certain well-known properties (of course, for a group one needs a bit more to handle the identity); etc. There are advantages to this commonality, particularly if one is well-versed in category theory: one can move from one area to the other and still have a fairly good idea of what the major problems are and the sort of techniques one might expect to see. In contrast, in Model Theory, the foundation appears to be heavily based on logic, and as a result the language and terminology can seem foreign to those who work in more widely publicized areas of mathematics. Rather than “sets of groups”, one hears about “sets of formulas”; rather than products (Cartesian, fibered, direct, or semi-direct), one hears of “ultraproducts”; rather than “reducing to a simpler case”, one is told about “eliminating quantifiers”.
In this talk I will indicate how some of the basic ideas of Model Theory can be formulated set-theoretically, that is, in the topological and algebraic spirit indicated above.
Organizational Meeting
We’ll meet to discuss topics to be covered for the semester.
Generic embeddings from indestructible weak compactness, II
I will give an introduction to and some applications of a type of generic embeddings that arises under the assumption of an indestructible weakly compact cardinal.
Generic embeddings from indestructible weak compactness, I
I will give an introduction to and some applications of a type of generic embeddings that arises under the assumption of an indestructible weakly compact cardinal.
This Week in Logic
This text is generated automatically from the database of talks and will be used as part of the weekly TWIL email announcements, managed by Jonas Reitz.
This Week In Logic at CUNY
— Saturday, January 16, 2021 —
— Sunday, January 17, 2021 —
— Monday, January 18, 2021 —
— Tuesday, January 19, 2021 —
— Wednesday, January 20, 2021 —
— Thursday, January 21, 2021 —
— Friday, January 22, 2021 —
— Saturday, January 23, 2021 —
— Sunday, January 24, 2021 —
— Monday, January 25, 2021 —
— Tuesday, January 26, 2021 —
— Wednesday, January 27, 2021 —
— Thursday, January 28, 2021 —
— Friday, January 29, 2021 —
— Saturday, January 30, 2021 —
— Other Logic News —
— Web Site —
Our website, http://nylogic.org, is up and running – please come visit! The site has been completely rebuilt on the WordPress platform.
We are pleased to announce the launch of the New York Logic Blog, a group blog run by the members New York Logic community, which will include and welcome all manner of announcements, mathematical logic posts, philosophical logic posts, invitations, inquiries, discussions or any other type of post concerning mathematical or philosophical logic of interest to the New York logic community. If you have an account on nylogic.org with author privileges, please feel free to make on-topic posts on the blog.
We also have plans for an interview series of prominent logicians.
——– ADMINISTRIVIA ——–
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.
Test post, please ignore
This is a post that the nylogic administrator is using to test certain things. Please ignore it.
——————————-
Testing for Semester view:
Start: 01 01, 2021
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
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?
The omega one of infinite chess
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 $langlemathbb{N},+rangle$. 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 $omega_1^{rm 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 $omega_1$: every countable ordinal is realized as the game value of such a position.
Very NIP Ordered Groups
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.
Understanding genericity for cuts
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.
Welcome to our new NY Logic site
We are currently upgrading to a new WordPress based system for nylogic.org. Please bear with us during this transition period.
In the mean time, you can find out information for this semester on our temporary sites:
- CUNY Logic Workshop temporary site
- Model theory seminar temporary site
- Computational Logic Seminar temporary site
- Set theory seminar temporary site
We plan that this site will be fully functional for next semester.
——————————————
Orphan Talks (not attached to any seminar):
This is not necessarily a problem, since we post talks from outside seminars that are not entered in our database. But some talks can be orphaned in error, when they should be listed amongst our official seminars.
Using model theory to find upper bounds on VC density
The VC dimension of a collection of sets is a concept used in probability and learning theory. It is closely related to the model-theoretic concept of the independence property. In this talk, I will illustrate these concepts in various examples, and show how the model-theoretic approach can give some bounds on VC density.
Randomness
Is the universe inherently deterministic or probabilistic? Perhaps more importantly – can we tell the difference between the two?
Humanity has pondered the meaning and utility of randomness for millennia. There is a remarkable variety of ways in which we utilize perfect coin tosses to our advantage: in statistics, cryptography, game theory, algorithms, gambling and more. Indeed, randomness seems indispensable! Which of these applications survive if the universe had no randomness in it at all? Which of them survive if only poor quality randomness is available, e.g. that arises from “unpredictable” phenomena like the weather or the stock market?
A computational theory of randomness, developed in the past three decades, reveals (perhaps counterintuitively) that very little is lost in such deterministic or weakly random worlds. In the talk, Dr. Wigderson will explain the main ideas and results of this theory.
Uncountable free abelian groups via κ-computability
One way to study structures of uncountable cardinality κ is to generalize the notion of computation. Saying that a subset of κ is κ-c.e. if it is Σ01 definable (with parameters, in the language of set theory) over Lκ provides the notion of κ-computability. We may also quantify over subsets of Lκ, providing a notion of a κ-analytic set (here we assume V=L). In this setting, we consider the difficulty of recognizing free groups and the complexity of their bases. For example, if κ is a successor cardinal, the set of free abelian groups of size κ is Σ11-complete. If κ is the successor of a regular cardinal which is not weakly compact, there is a computable free abelian group of cardinality κ, all of whose bases compute ∅”, and this is the best coding result possible. The resolution of questions of this type is more complex for other κ, and a few questions remain open. This is joint work with Greenberg and Turetsky.
Comparing notions of effective genericity
In recent work, Cholak, Dzhafarov, Hirst and Slaman showed that for n ≥ 3, every Mathias n-generic computes a Cohen n-generic. It is natural to wonder how other types of generic objects compare to one another. We consider generics for an effective version of Hechler forcing. Adapting a method developed by Cholak, Dzhafarov, and Soskova, we show that for n ≥ 3, every Mathias n-generic computes a Hechler n-generic, and every Hechler n-generic computes a Mathias n-generic. Finally, we explore the (open) question of whether, for n ≥ 3, the Mathias n-generics and the Hechler n-generics occupy exactly the same Turing degrees.
Structure within the class of K-trivial sets
The K-trivial sets are antirandom in the sense that the initial segment complexity in terms of prefix-free Kolmogorov complexity K grows as slowly as possible. Since 2002, many alternative characterisations of this class have been found: properties such as low for K, low for Martin-Löf (ML) randomness, and basis for ML randomness, which state in one way or the other that the set is close to computable.
Initially the class looked amorphous. More recently, internal structure has been found. Bienvenu et al (JEMS, 2016) showed that there is a “smart” K-trivial set, in the sense that any ML-random computing it must compute all K-trivials. Greenberg, Miller and Nies (submitted) showed that there is a dense hierarchy of subclasses. Even more recent results with Turetsky combine the two approaches via cost functions.
Recursion theoretic results for the game of Cops and Robbers on graphs
Cops and Robbers is a vertex-pursuit game played on a connected graph wherein two players, a cop and a robber, begin on a pair of vertices and alternate turns moving to adjacent vertices. A graph is cop-win if, from any pair of starting vertices, the cop can occupy the same vertex as the robber after finitely many rounds. In this talk, preliminary computability-theoretic and reverse-math results about the game of cops and robbers on infinite computable graphs will be discussed. We will consider several characterizations of infinite cop-win trees and graphs, and explore the complexity of winning strategies for both players.
Σ11 in every real in a Σ11 class of reals is Σ11
We first prove a theorem about reals (subsets of N) and classes of reals: If a real X is Σ11 in every member G of a nonempty Σ11 class K of reals then X is itself Σ11. We also explore the relationship between this theorem, various basis results in hyperarithmetic theory and omitting types theorems in ω-logic. We then prove the analog of our first theorem for classes of reals: If a class A of reals is Σ11 in every member of a nonempty Σ11 class B of reals then A is itself Σ11. This is joint work with T. Slaman and L. Harrington .
Set-theoretic mereology as a foundation of mathematics
In light of the comparative success of membership-based set theory in the foundations of mathematics, since the time of Cantor, Zermelo and Hilbert, it is natural to wonder whether one might find a similar success for set-theoretic mereology, based upon the set-theoretic inclusion relation $subseteq$ rather than the element-of relation $in$. How well does set-theoretic mereological serve as a foundation of mathematics? Can we faithfully interpret the rest of mathematics in terms of the subset relation to the same extent that set theorists have argued (with whatever degree of success) that we may find faithful representations in terms of the membership relation? Basically, can we get by with merely $subseteq$ in place of $in$? Ultimately, I shall identify grounds supporting generally negative answers to these questions, concluding that set-theoretic mereology by itself cannot serve adequately as a foundational theory.
This is joint work with Makoto Kikuchi, and the talk is based on our joint article:
J. D. Hamkins and M. Kikuchi, Set-theoretic mereology, Logic and Logical Philosophy, special issue “Mereology and beyond, part II”, pp. 1-24, 2016.
Order-Based and Continuous Modal Logics
Many-valued modal logics generalize the Kripke frame semantics of classical modal logic to allow a many-valued semantics at each world based on an algebra with a complete lattice reduct, where the accessibility relation may also take values in this algebra. Such logics can be designed to model modal notions such as necessity, belief, and spatio-temporal relations in the presence of uncertainty, possibility, or vagueness, and also provide a basis for defining fuzzy description logics. More generally, many-valued modal logics provide a first foray into investigating useful and computationally feasible fragments of corresponding first-order logics. The aim of my talk will be to describe recent axiomatization, decidability, and complexity results for many-valued modal logics based on algebras over (infinite) sets of real numbers. In particular, I will report on joint work with X. Caicedo, R. Rodriguez, and J. Rogger establishing decidability and complexity results for a family of order-based modal logics, using an alternative semantics admitting the finite model property. I will also present an axiomatization, obtained in joint work with D. Diaconescu and L. Schnueriger, for a many-valued modal logic equipped with the usual group operations over the real numbers that provides a first step towards solving an open axiomatization problem for a Lukasiewicz modal logic with continuous operations.
Heart of DARCness
Abstract. Alan Hajek has recently criticised the thesis that Deliberation Crowds Out Prediction (renaming it the DARC thesis, for ‘Deliberation Annihilates Reflective Credence’). Hajek’s paper has reinforced my sense that proponents and opponents of this thesis often talk past one other. To avoid confusions of this kind we need to dissect our way to the heart of DARCness, and to distinguish it from various claims for which it is liable to be mistaken. In this talk, based on joint work with Yang Liu, I do some of this anatomical work. Properly understood, I argue, the heart is in good shape, and untouched by Hajek’s jabs at surrounding tissue. Moreover, a feature that Hajek takes to be problem for the DARC thesis – that it commits us to widespread ‘credal gaps’ – turns out to be a common and benign feature of a broad class of cases, of which deliberation is easily seen to be one.
What do group rings know about the groups?
How much information about a group G is contained in the group ring K(G) for an arbitrary field K? Can one recover the algebraic or geometric structure of G from the ring? Are the algorithmic properties of K(G) similar to that of G? I will discuss all these questions in conjunction with the classical Kaplansky-type problems for some interesting classes of groups, in particular, for limit, hyperbolic, and solvable groups. At the end I will touch on the solution to the generalized 10th Hilbert problem in group rings and how equations in groups are related to equations in the group rings. The talk is based on joint results with O. Kharlampovich.
Proaperiodic monoids and model theory
We begin with the observation that the free profinite aperiodic monoid over a finite set A is isomorphic to the Stone dual space (spectrum) of the Boolean algebra of first-order definable sets of finite A-labelled linear orders (“A-words”). This means that elements of this monoid can be viewed as elementary equivalence classes of models of the first-order theory of finite A-words. From this perspective, the operations of multiplication and ω-power on proaperiodic monoids can be understood in a very concrete way. This point of view allows us to import methods from both topology and model theory, in particular saturated models, into the study of proaperiodic monoids. We use these methods to prove results about ω-terms in the free proaperiodic monoid and well-quasi-orders of factors in related proaperiodic monoids.
Stochastic λ-calculus
It is shown how the operators in the “graph model” for calculus (which can function as a programming language for Recursive Function Theory) can be expanded to allow for “random combinators.” The result then is a semantics for a new language for random algorithms. The author wants to make a plea for finding applications.
This talk is part of the Computer Science Colloquium at the CUNY Graduate Center.
Spring break April 22 & 29
CUNY’s spring break includes both Friday, April 22 and Friday, April 29, and so there will be no talks those days.
Freiling’s axiom of symmetry, or throwing darts at the real line
This will be a talk for the GC Math Program Graduate Student Colloquium. The talk will be aimed at a general audience of mathematics graduate students.
I shall give an elementary presentation of Freiling’s axiom of symmetry, which is the principle asserting that if we map every real $x$ to a countable set of reals $A_x$, then there are two reals $x$ and $y$ for which $x$ is not in $A_y$ and $y$ is not in $A_x$. To argue for the truth of this principle, Freiling imagined throwing two darts at the real number line, landing at $x$ and $y$ respectively: almost surely, the location $y$ of the second dart is not in the set $A_x$ arising from that of the first dart, since that set is countable; and by symmetry, it shouldn’t matter which dart we imagine as being first. So it may seem that almost every pair must fulfill the principle. Nevertheless, the principle is independent of the axioms of ZFC and in fact it is provably equivalent to the failure of the continuum hypothesis. I’ll introduce the continuum hypothesis in a general way and discuss these foundational matters, before providing a proof of the equivalence of the negation of CH with the axiom of symmetry. The axiom of symmetry admits natural higher dimensional analogues, such as the case of maps from pairs $(x,y)$ to countable sets $A_{x,y}$, where one seeks a triple $(x,y,z)$ for which no member is in the set arising from the other two, and these principles also have an equivalent formulation in terms of the size of the continuum.
Questions and commentary can be made at: jdh.hamkins.org/freilings-axiom-of-symmetry-graduate-student-colloquium-april-2016/.
Randomness and Fourier series
Carleson’s Theorem states that the Fourier series of certain integrable functions converge almost everywhere. I will consider this theorem in the context of computable analysis and show that the points that satisfy Carleson’s Theorem are precisely the Schnorr random points. This work is joint with Timothy H. McNicholl and Jason Rute.
Computable categoricity, linear orders and permitting
Remmel showed that a computable linear order L is computably categorical if and only if the order type of L has only a finite number of successivities. As part of the proof, Remmel assumes that L has infinitely many successivities and constructs another computable linear order R, which is not computably isomorphic to L, and a Δ02-isomorphism f such that f is an isomorphism from L onto R. Hence showing that L is not computably categorical. In this talk I will discuss the conditions under which we can use permitting arguments to construct f below certain types of Δ02 degrees.
Density and computability
We develop and discuss some of the theory relating asymptotic density and computability, with attention to the inherent complexity of sets with density invariant under computable permutation. We will make a brief excursion into reverse mathematics on the way, pointing out that a key equivalence of Kjos-Hanssen, Merkle, and Stephan holds over RCA0.
A one-generic that does not compute a modulus for one-genericity
A function g ∈ 2ω is 1-generic if, for every recursively enumerable W⊂ 2< ω, there is some σ⊂ g such that either σ∈W or σ has no extensions in W. That is, any possible Σ01 property of g is either forced to be true or forced to be false by some finite initial segment of g. A function f∈ωω is a modulus for 1-genericity if, whenever h pointwise dominates f, then h computes some 1-generic. If g is 1-generic and either Δ02-definable or 2-generic, then g computes a modulus for 1-genericity. We give a priority argument to produce a 1-generic g that does not compute a modulus for 1-genericity.
(Joint work with Theodore A. Slaman.)
Climbing (or finding paths) through trees
You can make a simple family tree by starting with a person at the root and then adding two branches for her parents, and then adding two branches for the parents of each of her two parents, and so on. Such a family tree is an example of a binary tree because each level of the tree has at most two branches. We’ll see that every binary tree with infinitely many nodes has an infinite path. But can we actually *compute* a path, given that we can prove one exists? Answering this question requires us to carefully define the verb “to compute.” This talk will highlight ideas from graph theory, theoretical computer science, and logic, but no background in any of these subjects is necessary.
This talk is aimed primarily at undergraduates.
Model Theory and j-functions.
I will describe two recent interactions between model theory, geometry and arithmetic. Both centered on properties of j-functions.
No talks March 25
Friday, March 25 is a CUNY holiday, for Good Friday, and so there will be no talks that day.
Weak compactness without inaccessibility
Weakly compact cardinals are known to have a multitude of equivalent characterizations. The weakly compact cardinals were introduced by Hanf and Tarski in the 1960s as cardinals for which certain infinitary languages satisfied a form of the compactness theorem. Since then, they have been shown to be equivalently characterized as inaccessible cardinals that have, for example, the tree property, or the Keisler extension property, or the $\Pi^1_1$ indescribability property, or the weakly compact embedding property–meaning that they have elementary embeddings with critical point $\kappa$ defined on various transitive sets of size $\kappa$. In this talk we discuss what happens if one drops the requirement that $\kappa$ is inaccessible from weak compactness. We focus especially on the weakly compact embedding property and investigate its relation to the other properties mentioned above. This is joint work with Brent Cody, Sean Cox, and Joel Hamkins, and our results extend prior work of William Boos.
Joint Laver diamonds
Say that a collection of Laver functions is jointly Laver if the functions can guess their targets simultaneously using just a single elementary embedding between them. In this talk we shall examine the notion of jointness in the simplest case of measurable cardinals, giving both equiconsistency results for the existence of large jointly Laver families and separating the existence of small such families from large ones. We shall also comment on how these results transfer to larger large cardinals, such as supercompact and strong cardinals, and, perhaps, how the notion of jointness may be interpreted for guessing principles not connected with large cardinals.
A position in infinite chess with game value $\omega^4$
I present a position in infinite chess with game value $\omega^4$. Informally speaking, this means that one side can force a win in $\omega^4$ many moves, or that the game is equivalent to the game of counting down from $\omega^4$. This result, joint with Hamkins and Evans, improved on the previous best result of $\omega^3$.
More information can be found at: http://jdh.hamkins.org/tag/infinite-chess.
Killing measurable and supercompact cardinals softly
This talk follows the theme of killing-them-softly between set-theoretic universes. The main theorems in this theme show how to force to reduce the large cardinal strength of a cardinal to a specified desired degree, for a variety of large cardinals including inaccessible, Mahlo, measurable and supercompact. The killing-them-softly theme is about both forcing and the gradations in large cardinal strength. This talk will focus on measurable and supercompact cardinals, and follows the larger theme of exploring interactions between large cardinals and forcing which is central to modern set theory.
Minimal models of second-order set theories
Everyone knows that there is a least transitive model of ZFC. Is the same true for second-order set theories? The main result of this talk is that the answer is no for Kelley-Morse set theory. Another notion of minimality we will consider is being the least model with a fixed first-order part. We will see that no countable model of ZFC has a least KM-realization. Along the way, we will look at the analogous questions for Gödel-Bernays set theory.
Rigidity properties of precipitous ideals
An ideal $I$ on a set $X$ is called rigid if forcing with $\mathcal{P}(X)/I$ produces an extension $V[G]$ in which there is a unique $V$-generic filter for $\mathcal{P}(X)/I$. Note that this implies that $\mathcal{P}(X)/I$ has only the trivial automorphism. As part of his analysis of $\mathbb{P}_{\text{max}}$ forcing, Woodin showed that under $\text{MA}_{\omega_1}$, every normal, uniform, saturated ideal on $\omega_1$ is rigid. Indeed, in all previously known models which have rigid precipitous ideals on $\omega_1$ one also has $\lnot\text{CH}$. This leaves open the question: is it consistent to have $\text{CH}$ along with a rigid precipitous ideal on $\omega_1$? I will discuss some recent work which shows that if $\kappa$ is almost huge then there is a forcing extension $V[G]$ in which $\kappa=\omega_1^{V[G]}$, there is a rigid presaturated ideal $I$ on $\omega_1^{V[G]}$ and $\text{CH}$ holds. The proof of this result involves a certain coding forcing first used in the Friedman-Magidor results on the number of normal measures. This is joint work with Sean Cox and Monroe Eskew.
Connections between a forcing class and its modal logic
Every definable forcing class $\Gamma$ gives rise to a corresponding modal logic. Mapping the ordered structure given by a ground model $W$ and its $\Gamma$-forcing extensions $W[G]$ to finite ordered structures (frames) in a class which can be characterized by a particular modal theory $\mathsf{S}$ reveals connections between the modal logic of $\Gamma$-forcing and the modal theory $\mathsf{S}$. For example, in 2008, Hamkins and Loewe showed that if ${\rm ZFC}$ is consistent, then the ${\rm ZFC}$-provably valid principles of the class of all forcing are precisely the assertions of the modal theory $\mathsf{S4.2}$. In this talk I describe how specific statements of set theory are used as `controls’ to achieve this mapping for various classes of forcing, giving new results for modal logics of forcing classes such as Cohen forcing, collapse forcing and ${\rm CH}$-preserving forcing.
Set-theoretic geology: Excavating a local neighborhood of the multiverse
This talk will give a brief overview of set-theoretic geology, the study of the collection of grounds of $V$. Forcing is naturally viewed as a method for passing from a model $V$ of set theory (the ground model) to an outer model $V[G]$ (the forcing extension). A change in perspective, however, allows us to use forcing to look inward: from a model $V$, we define an inner model $W$ of $V$ to be a ground of $V$ if $W$ is a transitive proper class satisfying ZFC and $V$ can be obtained by forcing over $W$, that is, if $V = W[G]$ for a suitable $W$-generic $G$. For a given model $V$, the collection of all of its ground models forms the context for what we call set-theoretic geology. This second-order collection, consisting of (possibly many) proper classes $W$, nonetheless admits a first-order definition – within a single universe, we have first-order access to an interesting local neighborhood of the set-theoretic multiverse. We will explore this neighborhood, pointing out various geological phenomena including bedrock models, the mantle and the outer core. This is joint work with Joel David Hamkins and Gunter Fuchs.
Virtual large cardinals
Given a very large cardinal property $\mathcal A$, e.g. supercompact or extendible, characterized by the existence of suitable set-sized embeddings, we define that a cardinal $\kappa$ is virtually $\mathcal A$ if the embeddings characterizing $\mathcal A$ exist in some set-forcing extension. In this terminology, the remarkable cardinals introduced by Schindler, which he showed to be equiconsistent with the absoluteness of the theory of $L(\mathbb R)$ under proper forcing, are virtually supercompact. We introduce the notions of virtually extendible, virtually $n$-huge, and virtually rank-into-rank cardinals and study their properties. In the realm of virtual large cardinals, we can even go beyond the Kunen Inconsistency because it is possible that in a set-forcing extension there is an embedding $j:V_\delta^V\to V_\delta^V$ with $\delta>\lambda+1$, where $\lambda$ is the supremum of the critical sequence. The virtual large cardinals are much smaller than their (possibly inconsistent) counterparts. Silver indiscernibles possess all the virtual large cardinal properties we will consider, and indeed the large cardinals are downward absolute to $L$. We give a tight measure on the consistency strength of the virtual large cardinals in terms of the $\alpha$-iterable cardinals hierarchy. Virtual large cardinals can be used, for instance, to measure the consistency strength of the Generic Vopěnka’s Principle, introduced by Bagaria, Schindler, and myself, which states that for every proper class $\mathcal C$ of structures of the same type, there are $B\neq A$ both in $\mathcal C$ such that $B$ embeds into $A$ in some set-forcing extension. This is joint work with Ralf Schindler.
Vapnik-Chervonenkis dimension and the mind’s eye
Google engineers routinely train query classifiers, for ranking advertisements or search results, on more examples than any human being hears in a lifetime. A human being who sees a meaningfully new image every second for one-hundred years will not see as many images as Google has in its libraries for training object detectors and image classifiers. Children learn more efficiently, achieving nearly perfect competence on about 30,000 categories in their first eight years. Upper bounds on the number of training samples needed to learn a classifier with similar competence can be derived using the Vapnik-Chervonenkis dimension, or the metric entropy, but these suggest that not only does Google need more examples, but all of evolution might fall short.
I will discuss machine learning and human learning, with a focus on representation. I will argue that brains simulate rather than classify, and I will suggest that the rich relational information available in an imagined world argues against abstraction and in favor of topological, almost literal, representation. I will speculate about physiological mechanisms that would support topologically organized neuronal activity patterns.
This talk is sponsored by the Initiative for the Theoretical Sciences at the CUNY Graduate Center.
Factoring polynomials and finding roots
We will use computability theory to investigate the difficulty of two standard questions from algebra. First, given a field F and a polynomial p∈ F[X], does the equation p=0 have a solution in F? And second, is p(X) irreducible in F[X]? Obviously these two questions are related, but it is not immediately clear which one is more difficult to answer. Indeed, it is not clear how one should measure the “difficulty” of answering these questions.
To address this problem, we will consider computable fields, which are countable fields in which we have algorithms for listing all the field elements and for the basic field operations. It has been known since 1960 that in this context, the two questions are equivalent under the standard notion of Turing reducibility: an algorithm for answering either question can be used to give an algorithm for answering the other one. However, computability theory also provides more precise measures of difficulty, and using one of these measures, known as 1-reducibility, we will show that one of the two questions can definitively be said to be more difficult in general than the other. To find out which is which, come to the talk!
No talks Feb.12
Friday, Feb. 12 is a CUNY holiday, for Lincoln’s Birthday, and so there will be no talks that day.
Loftiness VI
I will review some results on loftiness from my previous talks, and I will talk
about an intrinsic characterization of models with the omega-property.
The Lambek Calculus with Iteration (Kleene Star)
Besides multiplication (pairwise concatenation, A dot B) of formal languages, there are also two division operations on them: A dot B is included in C iff B is included in (A C) iff A is included in (C / B). The Lambek calculus was designed to describe all universally true statements of the form “A is included in B”, where A and B are formulas built using the three connectives (multiplication and two divisions). The completeness theorem was proved by Pentus (1995). It looks natural to consider also other well-known operations on formal languages, and one of these operations is the Kleene star, or iteration. Though this operation is very standard, the problem of enriching the Lambek calculus with this new unary connective in a proper way appears to be quite hard. We present two lines of calculi. The first one uses omega-rules or derivation trees with infinite branches, and we prove cut-elimination and completeness of the product-free fragment, but, as the derivations are infinite, we do not get any algorithmic properties, even recursive enumerability. The second approach is to formalize the Kleene star in an inductive manner. We present a Hilbert-style axiomatization and also a sequent calculus with cyclic derivations. This system is sound with respect to the intended interpretation. Completeness, or, in other words, whether the system with omega-rules is stronger than the inductive one, remains an open question.
Computability problems in number theory
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.
Complexity of constructible sheaves
Constructible sheaves play an important role in several areas of mathematics, most notably in the theory of D-modules. It was proved by Kashiwara and Schapira that the category of constructible sheaves is closed under the standard six operations of Grothendieck. This result can be viewed as a far reaching generalization of the Tarski-Seidenberg principle in real algebraic geometry. In this talk I will describe some quantitative/effectivity results related to the Kashiwara-Schapira theorem – mirroring similar results for ordinary semi-algebraic sets which are now well known. For this purpose, I will introduce a measure of complexity of constructible sheaves, and bound the complexity of some of the standard sheaf operations in terms of this measure of complexity. I will also discuss quantitative bounds on the dimensions of cohomology groups of constructible sheaves in terms of their complexity, again extending similar results on bounding the the ordinary Betti numbers of semi-algebraic sets.
Natural Logic
This talk is about a direction in logic which attempts to have something to say, and something to learn, from computational linguistics and natural language processing.
Much of modern logic originates in work on the foundations of mathematics. My talk reports on work in logic that has a different goal, the study of interference in language. This study leads to what I will call “natural logic,” the enterprise of studying logical interference in languages that look more like natural language than standard logical systems.
By now there is a growing body of work which presents logical systems that differ from first-order logic in various ways. Most of the systems are complete and decidable. Some are modern versions of syllogistic logic, but with additional features not present in syllogistic logics. And then there are flavors of logic which look rather far from ethical traditional or modern logic.
The talk will be programmatic and far-ranging rather than detailed. I hope to touch on computer implementations of natural logics, teaching materials on this topic, and interactions of logic and cognitive science.
The interplay of classes of algorithmically random objects
We study algorithmically random closed subsets (RCS’s) of Cantor space, algorithmically random continuous functions (RCF’s) from Cantor space to Cantor space, and algorithmically random Borel probability measures on Cantor space; especially the interplay between the three. Our main tools are preservation of randomness (PoR) and its converse no randomness ex nihilo (NREN), which say together that given an a.e.-defined computable map between an effective probability space and an effective polish space, a real is (Martin-Löf) random for the pushforward measure if and only if its preimage is random for the domain’s measure. PoR and NREN allow us to prove new facts that were previously open and reprove some known results more simply. Example 1: it was known that every RCS contains a random real and that every random real is contained in some RCS; we reprove this using PoR and NREN. Example 2: It was shown previously that the zero set (that is, the preimage of the sequence of all 0’s) of a RCF is a RCS. We reprove this using PoR and get the converse, which was previously left open, that ever RCS is the zero set of some RCF, via NREN. We also prove some miscellaneous results about the individual objects. Example 3: the Lebesgue measure of the range of a RCF is strictly between 0 and 1. This work is joint with Chris Porter.
Computably enumerable sets and vector spaces with thin complements
Simple, hypersimple, hyperhypersimple, and maximal sets play an important role in computability theory. Maximal sets are co-atoms in the lattice of computably enumerable sets modulo finite sets. Soare established that they are automorphic in this lattice. Similarly, maximal vector spaces play an important role in the study of the lattice of computably enumerable vector spaces modulo finite dimension. We will investigate principal filters determined by maximal spaces and how algebraic structure interacts with computability-theoretic properties. We will discuss the problem of finding orbits of maximal spaces under lattice automorphisms, the development of various notions of maximality for vector spaces, and recent progress that is joint work with R. Dimitrov.
Computing uniform (metastable) rates of convergence from the statement of the theorem alone
Consider a convergence theorem of the following form.
(T): If the property P holds, then the sequence (xn) converges.
For example, the monotone convergence principle states that any monotone, bounded sequence of reals converges.
This talk concerns the notion of metastable rates of convergence. The advantage of this notion is that metastable rates are often uniform and computable. Kohlenbach, using proof theory, showed that if the property P is of a certain form and the theorem (T) is provable in a certain formal type theory, then the rate of metastable convergence is both uniform and computable. Avigad and Iovino, using model theory, showed that if the theorem (T) is true and the property P is preserved by ultraproducts, then the rate of metastable convergence is uniform (no mention of computability). In this result, using computable analysis and computable continuous model theory, we show that if (T) is true and P is axiomatizable in continuous logic, then the corresponding metastable bounds are both uniform and computable from P. This generalizes both of the previous results.
A-Computable Graphs
A locally finite computable graph G is called A-computable if A can compute the neighbors of the vertices of G. William Gasarch and Andrew Lee introduced this notion to study graphs that are “between” computable and highly computable (i.e., ∅-computable). For any noncomputable c.e. set A, they proved that the A-computable graphs behave just like computable graphs when it comes to colorings. In this talk, we will see that their result also works for Euler paths and domatic partitions. Although it does not extend to arbitrary sets A (that are not necessarily c.e.), we will classify the sets for which it does.
Ordinal analysis via provability logics and ordinal spectra of arithmetical theories
If we start with a sound `weak’ theory –say Primitive Recursive Arithmetic– we can iterate adding consistency statements to it to get stronger and stronger theories. We call the $Pi^0_1$ ordinal of an arithmetical theory U how often one has to iterate adding consistency to PRA “before you hit on U”. We shall see how provability logics are suited for performing large part of the computation. Using different notions of consistency statements yields different ordinals giving rise to an ordinal spectrum of an arithmetical theory. These spectra can be collected into a nice structure and well-known structure: Ignatiev’s universal model for GLP_omega. We shall see how this structure can be used as a roadmap to $Pi_n$ conservation results between fragments.
The continuum hypothesis and other set-theoretic ideas for non-set-theorists
This is a talk for the Einstein Chair Mathematics Seminar at the CUNY Graduate Center, a talk on set theory for non-set-theorists, in two parts:
- An introductory background talk at 11 am
- The main talk at 2 – 4 pm
I shall present several set-theoretic ideas for a non-set-theoretic mathematical audience, focusing particularly on the continuum hypothesis and related issues.
At the morning talk, I shall discuss and prove the Cantor-Bendixson theorem, which asserts that every closed set of reals is the union of a countable set and a perfect set (a closed set with no isolated points), and explain how it led to Cantor’s development of the ordinal numbers and how it establishes that the continuum hypothesis holds for closed sets of reals. We’ll see that there are closed sets of arbitrarily large countable Cantor-Bendixson rank. We’ll talk about the ordinals, about $omega_1$, the long line, and, time permitting, we’ll discuss Suslin’s hypothesis. Dennis has requested that at some point the discussion turn to the role of set theory in the foundation for mathematics, compared for example to that of category theory, and I would look forward to that. I would be prepared also to discuss the Feferman theory in comparison to Grothendieck’s axiom of universes, and other issues relating set theory to category theory.
At the main talk in the afternoon, I’ll begin with a discussion of the continuum hypothesis, including an explanation of the history and logical status of this axiom with respect to the other axioms of set theory, and establish the connection between the continuum hypothesis and Freiling’s axiom of symmetry. I’ll explain the axiom of determinacy and some of its applications and its rich logical situation, connected with large cardinals. I’ll prove the determinacy of open sets and show that AD implies that every set of reals is Lebesgue measurable. I’ll briefly mention the themes and goals of the subjects of cardinal characteristics of the continuum and of Borel equivalence relation theory. If time permits, I’d like to explain some fun geometric decompositions of space that proceed in a transfinite recursion using the axiom of choice, mentioning the open questions concerning whether there can be such decompositions that are Borel.
See also the profile of this talk on my blog.
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 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.
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 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).
Methods of constructing points from regions of space
Rafał Gruszczyńsk (Nicolaus Copernicus University, Toruń) will give an informal, non-colloquium talk this Friday, Nov. 21, at 2pm, in the seminar room (Philosophy 716) at Columbia University. The title of the talk is “Methods of constructing points from regions of space”. Everybody is invited. The talk should be of special interest to colleagues and students working in logic, ontology, the philosophy of mathematics, and the philosophy of space and time.
The rise and fall of accuracy-first epistemology
Accuracy-first epistemology aims to supply non-pragmatic justifications for a variety of epistemic norms. The contemporary roots of accuracy-first epistemology are found in Jim Joyce’s program to reinterpret de Finetti’s scoring-rule arguments in terms of a “purely epistemic” notion of “gradational accuracy.” On Joyce’s account, scoring rules are conceived to measure the accuracy of an agent’s belief state with respect to the true state of the world, and Joyce argues that this notion of accuracy is a purely epistemic good. Joyce’s non-pragmatic vindication of probabilism, then, is an argument to the effect that a measure of gradational accuracy so imagined satisfies conditions that are close enough to those necessary to run a de Finetti style coherence argument. A number of philosophers, including Hannes Leitgeb and Richard Pettigrew, have joined Joyce’s program and gone whole hog. Leitgeb and Pettigrew, for instance, have argued that Joyce’s arguments are too lax and have put forward conditions that narrowing down the class of admissible gradational accuracy functions, while Pettigrew and his collaborators have extended the list of epistemic norms receiving an accuracy-first treatment, a program that he calls Evidential Decision Theory.
In this talk I report on joint work with Conor Mayo-Wilson that aims to challenge the core assumption of Evidential Decision Theory, which is the very idea of supplying a truly non-pragmatic justification for anything resembling the Von Neumann and Morgenstern axioms for a numerical epistemic utility function. Indeed, we argue that none of axioms have a satisfactory non-pragmatic justification, and we point to reasons why to suspect that not all the axioms could be given a satisfactory non-pragmatic justification. Our argument, if sound, has ramifications for recent discussions of “pragmatic encroachment”, too. For if pragmatic encroachment is a debate to do with whether there is a pragmatic component to the justification condition of knowledge, our arguments may be viewed to attack the true belief condition of (fallibilist) accounts of knowledge.
Ramsey’s Theorem applied to infinite traceable graphs
We consider three applications of Ramsey’s Theorem to infinite traceable graphs and finitely generated lattices from the point of view of reverse mathematics. For two of the applications, we will show that Ramsey’s Theorem is necessary while for the third application, it is not necessary. We will conclude with some related open questions.
Low for omega and equivalence class isomorphism properties
We look at the property of being low for isomorphism, restricted to certain classes of structures – if C is a class of structures, a set D is low for C isomorphism iff for any two structures in C, if D computes an isomorphism between them then there is a computable isomorphism between them. In particular we will show that exactly those sets which cannot compute non-zero Δ2 degrees are low for ω-isomorphism (when ω is viewed purely as an order), and we will show that no set which computes a non-zero Δ2 set or which computes a separating set for any two computably inseparable c.e. degrees is low for equivalence class isomorphism.
Computability theoretic properties of isomorphisms between partial computable injection structures
A partial computable injection structure consists of a computable set of natural numbers and a partial computable, injective (1-1) function. Clearly, the isomorphism type of such a structure is determined by the kinds and number of orbits of the elements under the function application. First, we investigate partial computable injection structures always having computable isomorphisms to other isomorphic structures, and we analyze what goes wrong in structures without such computable isomorphisms. Additionally, we do the same for partial computable injection structures under Δ2-isomorphisms and Δ3-isomorphisms.
The degree spectra of orders on a computable Abelian group
For any computable abelian group, the collection of possible linear orderings on the group can be represented as a Π01 class. However, not all Π01 classes can occur in this way, and we investigate the possible Turing degrees of their members. First, we describe the connection between orders for a group and bases for the group. Additionally, we extend a previously known result regarding the Turing degrees not represented in the space of orders of some group.
The implicitly constructible universe
The implicitly constructible universe, IMP, defined by Hamkins and Leahy, is produced by iterating implicit definability through the ordinals. IMP is an inner model intermediate between L and HOD. We look at some consistency questions about the nature of IMP.
NERDS
The Autumn 2014 meeting of NERDS, the New England Recursion & Definability Seminar, will take place on Saturday, October 18 at Assumption College, in Worcester, MA, beginning at 10:30 a.m. The principal organizers are Brooke Andersen, Damir Dzhafarov, and Reed Solomon. All talks are posted on nylogic.org (find NERDS under the “Conferences” tab), and they will take place in the Carriage House building on the campus of Assumption College. Directions.
CUNY Pragmatics Workshop: Relevance, Games, & Communication
There will be a two day meeting on pragmatics at the CUNY Graduate center on October 14 and 15, in room 9207.
Details are available here.
Please note that the program on that site is tentative and there may be more speakers than the ones announced.
Model theory and exponentiation
Methods from mathematical logic have proved surprisingly useful in understanding the geometry and topology of sets definable in the real field with exponentiation. When looking at the complex exponential field, the definability of the integers is a seemingly insurmountable impediment, but a novel approach due to Zilber leads to a large number of interesting new questions.
State of affairs in local uniformization and valuation theory in positive characteristic
This will be an informal talk summarizing roughly where we stand concerning the problem of local uniformization in positive characteristic. I will discuss the structure of valued algebraic function fields and the main open problems that are of particular interest for local uniformization. These include the dehenselization problem (an analogue of Temkin’s “decompletion”) as well as the question when the existence of a rational place implies that the ground field is existentially closed in the function field.
If time permits I will also discuss a stunning result about the badness of valuations in positive characteristic (due to Anna Blaszczok), and state a result (by Anna and myself) and an open question that are of interest for recent work by Koen Struyve et al. on “Euclidean buildings.”
Extremal fields, tame fields, large fields
In the year 2003 I first heard of the notion of extremal valued fields when Yuri Ershov gave a talk at a conference in Teheran. He proved that algebraically complete discretely valued fields are extremal. However, the proof contained a mistake, and it turned out in 2009 through an observation by Sergej Starchenko that Ershov’s original definition leads to all extremal fields being algebraically closed. In joint work with Salih Durhan (formerly Azgin) and Florian Pop, we chose a more appropriate definition and then characterized extremal valued fields in several important cases.
We call a valued field $(K,v)$ extremal if for all natural numbers n and all polynomials $f$ in $K[X_1,…,X_n]$, the set of those $f(a_1,…,a_n)$ with $a_1,…,a_n$ in the valuation ring has a maximum (which is allowed to be infinity, which is the case if $f$ has a zero in the valuation ring). This is such a natural property of valued fields that it is in fact surprising that it has apparently not been studied much earlier. It is also an important property because Ershov’s original statement is true under the revised definition, which implies that in particular all Laurent Series Fields over finite fields are extremal. As it is a deep open problem whether these fields have a decidable elementary theory and as we are therefore looking for complete recursive axiomatizations, it is important to know the elementary properties of them well. That these fields are extremal seems to be an important ingredient in the determination of their structure theory, which in turn is an essential tool in the proof of model theoretic properties.
Further, it came to us as a surprise that extremality is closely connected with Pop’s notion of “large fields”. Also the notion of tame valued fields plays a crucial role in the characterization of extremal fields. A valued field $K$ with algebraic closure $K^{acl}$ is tame if it is henselian and the ramification field of the extension $K^{acl}|K$ coincides with the algebraic closure.
In my talk I will introduce the above notions, try to explain their meaning and importance also to the non-expert, and discuss in detail what is known about extremal fields and how the properties of large and of tame fields appear in the proofs of the characterizations we give. Finally, I will present some challenging open problems, the solution of which may have an impact on the above mentioned problem for Laurent Series Fields over finite fields.
Descriptive Graph Combinatorics and Computability
Generalizing Turing machines: $\omega_1$-computation
While Turing machines are well established as the principal framework for theoretical computation on the natural numbers, no machine model for computation on uncountable domains has achieved any similarly dominant status. We will give an overview of various methods that have been explored, including computable analysis, the Blum-Shub-Smale model of computation on the real numbers, local computability, α-recursion theory, and certain models of computation over ordinal time (one of which turns out to be equivalent to α-recursion). Each of these has strengths and weaknesses, for which reason no one of them has come to dominate the discussion. Much of the talk will be expository, describing these different notions of computation, but we will finish with a specific example from ω1-recursive model theory which shows how phenomena that were unknown under Turing computation on ω can arise in the context of ω1-computable model theory.
Computability and Strong Randomness
In the 1960s Martin-Löf devised a formal definition of the notion of randomness for an individual infinite binary sequence. It formalizes the intuition that some sequences are more likely than others to be the result of a sequence of independent coin-flips – despite the fact that all are equally likely from the point of view of probability theory. Martin-Löf used effectively presented, effectively null sets.
At the same time he however noticed that the notions of computability that he used lacked certain closure properties and that this made the theory quite delicate. He suggested an alternative approach which used a much richer class of tests for randomness – the hyperarithmetic ones. Roughly speaking, these tests use the power of the halting problem and then repeat (taking the halting problem relative to the halting problem, and so on). This gives a pleasing theory of strong randomness, which has recently been studied by Hjorth, Nies, Chong and Yu.
I will describe some of the ideas and techniques involved.
Intuitionistic Logic and Computability
Intuitionistic logic is a logic formalised by Heyting, based on Brouwer’s programme of intuitionism. Roughly speaking, intuitionistic logic is what one obtains if one drops the so-called “law of excluded middle”, stating that for every statement P either P holds or P does not hold, from classical logic. There are various ways to provide a semantics for this formalism, of which we are particularly interested in the ones which are somehow connected to computation.
In this talk we will look at the Medvedev and Muchnik lattices, which are algebraic structures naturally arising in computability theory. These algebraic structures are so-called ‘Brouwer algebras’, which are structures to which we can assign a non-classical propositional logic in a natural way. It turns out that, unfortunately, the theory assigned to the Medvedev and Muchnik lattices is not intuitionistic propositional logic (IPC): in fact, their theory is IPC plus the “weak law of the excluded middle” stating that for every statement P either P does not hold or P does not not hold.
However, quite remarkably it turns out that this deficiency can be repaired, a fact first proven by Skvortsova. We will sketch how this works, discussing recent extensions of Skvortsova’s result.
Gödel, Mechanism, and Consciousness
Knowledge-Theoretic Aspects of Strategic Voting
It has long been noted that a voter can sometimes achieve a preferred election outcome by misrepresenting his or her actual preferences. In fact, the classic Gibbard-Sattherthwaite Theorem shows that under very mild conditions, every voting method that is not a dictatorship is susceptible to manipulation by a single voter. One standard response to this important theorem is to note that a voter must possess information about the other voters’ preferences in order for the voter to decide to vote strategically. This seems to limit the “applicability” of the theorem. In this talk, I will survey some recent literature that aims at making this observation precise. This includes models of voting under uncertainty (about other voters’ preferences) and models that take into account how voters may response to poll information.
$p$-adic model theory uniformly in $p$, and applications to algebra and number theory
In 1949, Julia Robinson proved that the field of rational numbers is undecidable. Later, in 1965, motivated by a conjecture of Artin on zeroes of p-adic forms, Ax and Kochen proved that the field of p-adic numbers is decidable. This enabled development of model theory for $p$-adic and related fields. These theories have turned out to have a surprising feature, namely, that most of the properties that hold do not depend on the prime $p$, and are in turn controlled by other universal theories. Later, Ax developed a model theory of finite fields for almost all $p$, and this theory beautifully relates to the theory of $p$-adics for almost all $p$. The uniform logical behaviour was then showed by Pas-Denef-Loeser to govern many properties of $p$-adic integrals uniformly in $p$, which enabled a theory of motivic integration, and it is is believed that this is a feature of many of the naturally occurring concepts and structures in number theory.
Recently, in continuation of this line of developments, new results have been obtained in the following topics:
1. On counting conjugacy classes and representations (and other counting problems) in algebraic groups over local fields (this is joint work with Mark Berman, Uri Onn, and Pirita Paajanen) where one can translate asymptotic questions in group theory formulated in terms of a generating Poincare series to questions on p-adic and motivic integrals approachable by model theory.
2. A model theory has been developed for the adeles of a number field (this is joint work with Angus Macintyre). The ring of adeles of the rational numbers is a locally compact ring made of all the $p$-adic fields for all $p$ and the real field and enables using results on the local fields to derive results for the global rational field. It is intimately related to questions on various kinds of zeta functions in arithmetic and geometry.
Going from the local ($p$-adic and real) fields back to the rationals has long been a fundamental local-global transition both for the logic and the algebra. The above results give new tools and results on this. I will give a survey of some of the results and challenging open problems.
The Humean Thesis on Belief
I am going to make precise, and assess, the following thesis on (all-or-nothing) belief and degrees of belief: It is rational to believe a proposition just in case it is rational to have a stably high degree of belief in it.I will start with some historical remarks, which are going to motivate calling this postulate the “Humean thesis on belief”. Once the thesis has been formulated in formal terms, it is possible to derive conclusions from it. Three of its consequences I will highlight in particular: doxastic logic; an instance of what is sometimes called the Lockean thesis on belief; and a simple qualitative decision theory.
Savage’s Subjectivism and Countable Additivity
This talk is mainly on the issue of additivity in Savage’s theory of subjective expected utility. It is divided into three parts. First, I will comment, by providing a brief historical survey, on Savage’s reasons for adopting finitely additive probability measure in his decision model. It will argue that Savage’s set-theoretic argument for rejecting countable additivity is inconclusive. In the second part, I will discuss some defects of finite additivity in Savage’s system. This will be followed, in the last part, by a detailed reconstruction and revision of Savage’s theory. It will be shown that Savage’s final representation theorem, which extends the derived utility function for simple acts to general acts, is derivable from the first six of his seven postulates provided countable additivity is in sight, a conjecture made by Savage himself.
Causal Decision Theory and Intrapersonal Nash Equilibria
Most philosophers today prefer ‘Causal Decision Theory’ to Bayesian or other non-Causal Decision Theories. What explains this is the fact that in certain Newcomb-like cases, only Causal theories recommend an option on which you would have done better, whatever the state of the world had been. But if so, there are cases of sequential choice in which the same difficulty arises for Causal Decision Theory. Worse: under further light assumptions the Causal Theory faces a money pump in these cases. It may be illuminating to consider rational sequential choice as an intrapersonal game between one’s stages, and if time permits I will do this. In that light the difficulty for Causal Decision Theory appears to be that it allows, but its non-causal rivals do not allow, for Nash equilibria in such games that are Pareto inefficient.
Spectra of differentially closed fields
The spectrum Spec(
This is joint work by Dave Marker and the speaker.
Quasiminimality and computability
We briefly define computability on uncountable domains via Σ1-recursion, with an emphasis on ω1-computability. We will then apply this notion of uncountable computability to quasiminimal excellent classes. We will concentrate on the pseudo-exponential fields and the topological group covers of the complex numbers. We show that the group covers are relatively ω1-computably categorical while the pseudo-exponential fields are not even ω1-computably categorical.
Notions of robust information-coding
We study several notions of computability-theoretic reducibility between subsets of natural numbers that are “robust” in the following sense: given a notion of largeness, a set $B$ is reducible to a set $A$ if every set that agrees with $A$ on a large domain uniformly computes a set that agrees with $B$ on a large domain. A familiar example is 1-reducibility, for which “large” can be taken to mean “cofinite”. This framework encompasses a wide range of reducibilities, including generic reducibility, for which “large” means “of density 1,” and which was first studied by Jockusch and Schupp. We obtain some new results concerning this reducibility, and introduce several related reducibilities that behave quite counterintuitively. For instance, infinite-information reducibility, for which “large” simply means “infinite”, enjoys the unusual property of admitting maximal pairs. I will discuss this and other results about these reducibilities, and sketch some of the techniques needed to prove them. This is joint work with Greg Igusa.
Probabilistic proof of the existence of expanding families of graphs
The speaker proved that almost certainly most infinite families of bipartite graphs are expanding families.
The Univalence Axiom
In this talk, we will begin by discussing application of functions on paths, and the transport lemma (Lemma 2.3.1 of the book). We will then discuss the notion of homotopies, and equivalences, with a few examples. From their we will be able to define a function which will be called “idtoeqv”. Roughly, this function takes equality of types to equivalence of types. This will allow us to state the univalence axiom. If time permits, we will end with how the various type forming constructions behave in the presence of the higher groupoid structure.
Types, Spaces, and Higher Groupoids
Last time we discussed fibrations of sets, spaces, and types. We noted that path induction allows us to prove that the type family of equalities over a given type A is “homotopy equivalent” to A.
This week, we will continue with this and discuss the groupoid structure of spaces (paths) and types (equalities). In doing so, we will establish the “interchange law” for 2-categories, and see that in the particular case of spaces and types that this allows us to prove that the composition law is commutative (up to a higher equivalence) for 2-paths and 2-equivalences that begin and end at the same point.
We shall also discuss how non-dependent functions between types give rise to functors on the associated groupoids of equivalences. This leads to the problem of what to do for dependent functions, and it turns out that fibrations give us a solution to this, and thus we will have come full circle.
Path Induction and the Path-Loop Space Fibration
As we continue our foray into the book, we begin to view types as spaces (or, “equivalently”, as omega groupoids). My goal for this section is to focus on the path induction rule and argue that it corresponds to the path-loop fibration.
More specifically, we can make an analogy between the path space over a space X and the type of all equivalences over a type A. The path space of X is homotopy equivalent to X, and I argue that path induction says “essentially the same thing” about the type of all equivalences over A. I aim to make this analogy as formal as possible, and then delve further into the material in chapter 2.
I would also like to go over some exercises. I’ve done a few, but if anyone wants to come up to the board and show off, then they are welcome!
An Introduction to Intuitionistic Type Theory
Homotopy type theory is a new foundation for mathematics based upon type theory and the univalence axiom. This is a topic that unifies the foundations of mathematics, computer science, algebraic topology, and type theory.
This will be the first focused reading of the Homotopy type theory reading group, covering sections 1.1-1.7 of the book. This will serve as an introduction to Intuitionistic Type Theory as developed by Martin-Löf, including notions of decidability and judgmental equality, up through dependent function and pair types (aka Pi and Sigma).
The reading group includes those with type theory background and no homotopy background, with homotopy background but no type theory background, and with no significant background in either but a healthy thirst for knowledge.
Welcome to the Homotopy Type Theory Reading Group
The goal of this group is to study this:
http://homotopytypetheory.org/book/
Homotopy type theory is a new foundation for mathematics based upon type theory and the univalence axiom. This is a topic that unifies the foundations of mathematics, computer science, algebraic topology, and type theory.
Our first meeting will be on Thursday, September 12th at the CUNY Graduate Center, 365 Fifth Ave, NYC. The time will be 7pm and the room is 8405.
The first talk will be given by Dustin Mulcahey, and will consist of an informal overview of the work. We can also take this time to discuss how we should organize the seminar and split up the talks.
We will be meeting (roughly) every two weeks.
Jointly organized by:
Applications in combinatorial number theory of iterated nonstandard extensions and idempotent ultrafilters
This talk will be part of CANT 2013, the Combinatorial and Additive Number Theory Conference, on May 21-24, 2013 at the Graduate Center.
Abstract: By using nonstandard analysis, and in particular iterated elementary (nonstandard) extensions, we give foundations to a peculiar way of manipulating idempotent ultrafilters. The resulting formalism is suitable for applications in Ram- sey theory of numbers. To illustrate the use of this technique, we give (rather) short proofs of two important results in combinatorial number theory, namely Milliken- Taylor’s Theorem (a generalization of Hindman’s theorem), and Rado’s theorem about partition regularity of diophantine equations, in a new version formulated in terms of idempotent ultrafilters.
Some familiarity with the notion of elementary extension will be assumed in the first part of the talk, but in the second part about applications I will not assume any specific prerequisite (also the notions of ultrafilter and of partition regularity will be recalled).
The theory of infinite games, with examples, including infinite chess
This will be a talk on April 30, 2013 for a joint meeting of the Yeshiva University Mathematics Club and the Yeshiva University Philosophy Club. I will give a general introduction to the theory of infinite games, suitable for mathematicians and philosophers. What does it mean to play an infinitely long game? What does it mean to have a winning strategy for such a game? Is there any reason to think that every game should have a winning strategy for one player or another? Could there be a game, such that neither player has a way to force a win? Must every computable game have a computable winning strategy? I will present several game paradoxes and example infinitary games, including an infinitary version of the game of Nim, and several examples from infinite chess.
Towards a model theory of global fields
The logic of diophantine or geometric structures appears to exhibit a sharp local-global dichotomy. For local or generic geometry, there are many quantifier-elimination results, describing an arbitrary definable set in geometric terms, and thus opening the way to a model-theoretic analysis. This includes Tarski’s theorem in real semi-algebraic geometry, and the Ax–Kochen theorem on the asymptotic theory of the p-adics. For global fields, all known results go in the opposite direction of undecidability; the first such statement is Godel’s interpretation of syntax (and finite mathematics in general) in the ring of integers. However the reason for the undecidability appears to reside in the accidental nature of finite sets, rather than with the adelic geometry that is generally used to analyze number- theoretic problems. One could conjecture that the parts of adelic geometry that are functorial with respect to finite field extensions should admit a model-theoretic analysis. The talk will report on a research program, joint with Itai Ben-Yaacov, with this aim. Existing results are mostly restricted to the function field version, and include the existential closedness of k(t)^alg as an adelic field in an appropriate language.
———————————-
Events scheduled at midnight:
This one is not yet working correct. The time may be a mistake. This is not quite working correctly….