Department of Mathematics

The Graduate Center of The City University of New York

THIS SEMESTER, SOME TALKS WILL BE IN-PERSON AND SOME WILL BE ON ZOOM.

Time: Wednesdays 07:00 PM Eastern Time (US and Canada)

IN-PERSON INFORMATION:

365 Fifth Avenue (at 34th Street) map

(Diagonally across from the Empire State Building)

New York, NY 10016-4309

Room 5417 (not the usual Room 6417)

The videos of the lectures will be put up on YouTube a few hours after the lecture.

ZOOM INFORMATION:

https://brooklyn-cuny-edu.zoom.us/j/89472980386?pwd=Z3g3Q3h3V1dQUmg2ZlVGU1RwSEhMZz09

Meeting ID: 894 7298 0386

Passcode: NYCCTS

Seminar web page.

Videoed talks.

Previous semesters.

researchseminars.org page.

Contact N. Yanofsky to schedule a speaker

or to add a name to the seminar mailing list.

The underlying paper is forthcoming in the

I am grateful to Nick Kuhn and Ben Steinberg for their patient email correspondence with me on this topic.

Slides.

Slides.

In this talk, we will argue that Gödel-Carnap's original Diagonal Lemma is not the modern formulation and was more similar to, but not exactly identical with, the Strong Diagonal (or Direct Self-Reference) Lemma. This lemma, so-called recently, says that for every formula

From a purely formal point of view, a double category is a category object in CAT. Once a familiarity with double categories has developed, it is amusing and instructive to see how the various constructs of formal category theory play out in this setting.

But these two aspects of double categories, fancy 2-categories or internal categories, are only part of the picture. Perhaps the most important thing is the interplay between the horizontal and the vertical.

I will start with some examples of double categories to give a feeling for the objects I will be discussing, and then look at several concepts indicative of the rich interplay between the horizontal and the vertical.

Slides.

1. We build on work of L. Roman (89) on primitive recursion and of A. Cobham (65) and Bellantoni-Cook(92) on P Time.

2. We use base 2 numbers with the digits 1 & 2. Let N be the set of these numbers. We split the tapes of a multi-tape Turing machine each into 2 stacks of digits 1 & 2. These are (modulo allowing an odd numberof stacks) the multi-stack machines we use to study P Time.

3. Let Num be the category with objects the finite products of N and arrows the functions between these. From its arrow category Num^2 we abstract the doctrine (here a category of small categories with chosen structure) PTime of categories with with finite products, base 2 numbers, 2-comprehensions, flat recursion, & safe recursion. Since PTime is a locally finitely presentable category, it has an initial category I. Our characterization is that the bottom of the image of I in Num^2 consists of the P Time functions.

4. We can use I (thinking of its arrows as programs) to run multi-stack machines long enough to get P Time.This is the completeness of the characterization.

5. We cut down the numeric arrow category Num^2, using Bellantoni-Cook growth & time bounds on the functions, to get a bounded numeric arrow category B. B is in the doctrine PTime. This yields the soundness of the characterization.

6. For example, the doctrine of toposes with base 1 numbers, choice, & precisely 2 truth values (which captures much of ZC set theory) likely lacks an initial category, much as there is an initial ring, but no initial field.

7. On the other hand, the L. Roman doctrine PR of categories with finite products, base 1 numbers, & recursion (that is, product stable natural numbers objects) does have an initial category as it consists of the strong models of a finite set of entailments. And is thus locally finitely presentable. We sketch the signature graph for these entailments. And some of these entailments. Similarly (but with more complexity) there are entaiments for the doctrine PTime.

In this talk we will demonstrate that the establishment of full characterizations of these notions (and some natural variations thereof) in many familiar categories of spaces, such as those of T_i-spaces (i= 0, 1, 2), can be quite challenging and may lead to unexpected surprises. In fact, we will show that there are significant differences in this regard even amongst the categories defined by the standard separation conditions, with the T1-separation condition standing out. The findings about these specific categories lead us to insights also when considering rather arbitrary full reflective subcategories of Top.

(Based on joint work with J. Adamek, M. Husek, and J. Rosicky.)

CC(XA,B) <<--run_X-- CC*(X,P)

one for every pair A,B. In this talk, I will sketch a proof that program closure is a property: Any two programming languages are isomorphic along run-preserving morphisms. The result counters Kleene's interpretation of the Church-Turing Thesis, which has been formalized categorically as the suggestion that computability is a structure, like a group presentation, and not a property, like completeness. We prove that it is like completeness. The draft of a book on categorical computability is available from the web site dusko.org.