I will continue my overview of Schmerl’s work on generalizations of Tennenbaum’s theorm to general reducts of Peano Arithmetic.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

We first prove a theorem about reals (subsets of N) and classes of reals: If a real X is Σ¹₁ in every member G of a nonempty Σ¹₁ class K of reals then X is itself Σ¹₁. 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 Σ¹₁ in every member of a nonempty Σ¹₁ class B of reals then A is itself Σ¹₁. ​ This is joint work with T. Slaman and L. Harrington ​.​
​

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.

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.

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.

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.)

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.

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.

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.

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.

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$.

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.

Slides

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$.

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$.

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.

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.

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.

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.

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, 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.”

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.

An extended abstract can be found here on my blog.

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.

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.

An extended abstract can be found here on my blog.

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.

I will describe two recent interactions between model theory, geometry and arithmetic. Both centered on properties of j-functions.

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).

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.

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.

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.

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.

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.

I will discuss a recent result of Gabe Conant that there is no structure lying properly between (Z,+) and (Z,+,<).

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.

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.

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.

Slides

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.

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.

Slides

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.

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.

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.

CUNY’s spring break includes both Friday, April 22 and Friday, April 29, and so there will be no talks those days.

Friday, March 25 is a CUNY holiday, for Good Friday, and so there will be no talks that day.

Friday, Feb. 12 is a CUNY holiday, for Lincoln’s Birthday, and so there will be no talks that day.

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.

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.

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.

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 ≥ κ.

We will discuss two weak versions of recursive saturation: K-tallness and tallness. K-tallness characterizes the countable models of IΔ₀ + 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 ≥κ.

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.

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.

I will introduce uniformly omega-lofty models and I will discuss some results about them due to Matt Kaufmann and Jim Schmerl.

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 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.

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).

There will be no talks on November 27, the day after Thanksgiving.

On Friday, September 25, CUNY will follow a Tuesday schedule. Therefore, no logic seminars will meet that day.

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).

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.

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).

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.

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.

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.

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$.

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.

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.

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.

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.

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.

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.

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.

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.

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

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.

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.

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.

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

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.

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.

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.

In the talk I will discuss results on recovering a countable recursively saturated model of Peano Arithmetic from its automorphism group.

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.

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 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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

Proofs of the lemmas will be given and some consequences related to substructure lattices will be explained.

The speaker proved that almost certainly most infinite families of bipartite graphs are expanding families.

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.

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).

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.

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.

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.

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.

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.

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 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.

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.

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.

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).

I will give a brief survey of what is known about $omega_1$-like models of PA (much) and what is not known (much).

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.

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.

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.

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.

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.

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.

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.

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 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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

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.

We’ll meet to discuss topics to be covered for the semester.

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.

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.

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.

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.

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.

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.

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 Σ⁰₁ 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 Σ¹₁-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.