Nonstandard Models of Arithmetic

There seems to be a murky abyss lurking at the bottom of mathematics. While in many ways we cannot hope to reach solid ground, mathematicians have built impressive ladders that let us explore the depths of this abyss and marvel at the limits and at the power of mathematical reasoning at the same time.

This is a quote from Matthew Katz and Jan Reimann’s book An Introduction to Ramsey Theory: Fast Functions, Infinity, and Metamathematics. I’ve been been talking to my old friend Michael Weiss about nonstandard models of Peano arithmetic on his blog. We just got into a bit of Ramsey theory. But you might like the whole series of conversations, which are precisely about this murky abyss.

Here it is so far:

• Part 1: I say I’m trying to understand ‘recursively saturated’ models of Peano arithmetic, and Michael dumps a lot of information on me. The posts get easier to read after this one!

• Part 2: I explain my dream: to show that the concept of ‘standard model’ of Peano arithmetic is more nebulous than many seem to think. We agree to go through Ali Enayat’s paper Standard models of arithmetic.

• Part 3: We talk about the concept of ‘standard model’, and the ideas of some ultrafinitists: Alexander Yessenin-Volpin and Edward Nelson.

• Part 4: Michael mentions “the theory of true arithmetic”, and I ask what that means. We decide that a short dive into the philosophy of mathematics may be required.

• Part 5: Michael explains his philosophies of mathematics, and how they affect his attitude toward the natural numbers and the universe of sets.

• Part 6: After explaining my distaste for the Punch-and-Judy approach to the philosophy of mathematics (of which Michael is thankfully not guilty), I point out a strange fact: our views on the infinite cast shadows on our study of the natural numbers. For example: large cardinal axioms help us name larger finite numbers.

• Part 7: We discuss Enayat’s concept of “a T-standard model of PA”, where T is some axiom system for set theory. I describe my crazy thought: maybe your standard natural numbers are nonstandard for me. We conclude with a brief digression into Hermetic philosophy: “as above, so below”.

• Part 8: We discuss the tight relation between PA and ZFC with the axiom of infinity replaced by its negation. We then chat about Ramsey theory as a warmup for the Paris–Harrington Theorem.

• Part 9: Michael sketches the proof of the Paris–Harrington Theorem, which says that a certain rather simple theorem about combinatorics can be stated in PA, and proved in ZFC, but not proved in PA. The proof he sketches builds a nonstandard model in which this theorem does not hold!

• Part 10: Michael and I talk about “ordinal analysis”: a way of assigning ordinals to theories of arithmetic, that measures how strong they are.

• Part 11: Michael begins explaining Enayat’s paper Standard models of arithmetic. I pull him into explaining “Craig’s trick” and “Rosser’s trick”, two famous tricks in mathematical logic.

Quantum Physics and Logic 2019

There’s another conference involving applied category theory at Chapman University!

• Quantum Physics and Logic 2019, June 9-14, 2019, Chapman University, Beckman Hall 404. Organized by Matthew Leifer, Lorenzo Catani, Justin Dressel, and Drew Moshier.

The QPL series started out being about quantum programming languages, but it later broadened its scope while keeping the same acronym. This conference series now covers quite a range of topics, including the category-theoretic study of physical systems. My students Kenny Courser, Jade Master and Joe Moeller will be speaking there, and I’ll talk about Kenny’s new work on structured cospans as a tool for studying open systems.

Program

The program is here.

Invited talks

• John Baez (UC Riverside), Structured cospans.

• Anna Pappa (University College London), Classical computing via quantum means.

• Joel Wallman (University of Waterloo), TBA.

Tutorials

• Ana Belen Sainz (Perimeter Institute), Bell nonlocality: correlations from principles.

• Quanlong Wang (University of Oxford) and KangFeng Ng (Radboud University), Completeness of the ZX calculus.

The Monoidal Grothendieck Construction

My grad student Joe Moeller is talking at the 4th Symposium on Compositional Structures this Thursday! He’ll talk about his work with Christina Vasilakopolou, a postdoc here at U.C. Riverside. Together they created a monoidal version of a fundamental construction in category theory: the Grothendieck construction! Here is their paper:

• Joe Moeller and Christina Vasilakopoulou, Monoidal Grothendieck construction.

The monoidal Grothendieck construction plays an important role in our team’s work on network theory, in at least two ways. First, we use it to get a symmetric monoidal category, and then an operad, from any network model. Second, we use it to turn any decorated cospan category into a ‘structured cospan category’. I haven’t said anything about structured cospans yet, but they are an alternative approach to open systems, developed by my grad student Kenny Courser, that I’m very excited about. Stay tuned!

The Grothendieck construction turns a functor

into a category equipped with a functor

The construction is quite simple but there’s a lot of ideas and terminology connected to it: for example a functor is called an indexed category since it assigns a category to each object of while the functor is of a special sort called a fibration.

I think the easiest way to learn more about the Grothendieck construction and this new monoidal version may be Joe’s talk:

• Joe Moeller, Monoidal Grothendieck construction, SYCO4, Chapman University, 22 May 2019.

Abstract. We lift the standard equivalence between fibrations and indexed categories to an equivalence between monoidal fibrations and monoidal indexed categories, namely weak monoidal pseudofunctors to the 2-category of categories. In doing so, we investigate the relation between this global monoidal structure where the total category is monoidal and the fibration strictly preserves the structure, and a fibrewise one where the fibres are monoidal and the reindexing functors strongly preserve the structure, first hinted by Shulman. In particular, when the domain is cocartesian monoidal, lax monoidal structures on a functor to Cat bijectively correspond to lifts of the functor to MonCat. Finally, we give some indicative examples where this correspondence appears, spanning from the fundamental and family fibrations to network models and systems.

To dig deeper, try this talk Christina gave at the big annual category theory conference last year:

• Christina Vasilakopoulou, Monoidal Grothendieck construction, CT2018, University of Azores, 10 July 2018.

Then read Joe and Christina’s paper!

Here is the Grothendieck construction in a nutshell:

Enriched Lawvere Theories

My grad student Christian Williams and I finished this paper just in time for him to talk about it at SYCO:

• John Baez and Christian Williams, Enriched Lawvere theories for operational semantics.

Abstract. Enriched Lawvere theories are a generalization of Lawvere theories that allow us to describe the operational semantics of formal systems. For example, a graph-enriched Lawvere theory describes structures that have a graph of operations of each arity, where the vertices are operations and the edges are rewrites between operations. Enriched theories can be used to equip systems with operational semantics, and maps between enriching categories can serve to translate between different forms of operational and denotational semantics. The Grothendieck construction lets us study all models of all enriched theories in all contexts in a single category. We illustrate these ideas with the SKI-combinator calculus, a variable-free version of the lambda calculus, and with Milner’s calculus of communicating processes.

When Mike Stay came to U.C. Riverside to work with me about ten years ago, he knew about computation and I knew about category theory, and we started trying to talk to each other. I’d heard that categories and computer science were deeply connected: for example, people like to say that the lambda-calculus is all about cartesian closed categories. But we soon realized something funny was going on here.

Computer science is deeply concerned with processes of computation, and category theory uses morphisms to describe processes… but when cartesian closed categories are applied to the lambda calculus, their morphisms do not describe processes of computation. In fact, the process of computation is effectively ignored!

We decided that to fix this we could use 2-categories where

• objects are types. For example, there could be a type of integers, INT. There could be a type of pairs of integers, INT × INT. There could also be a boring type 1, which represents something there’s just one of.

• morphisms are terms. For example, a morphism f: 1 → INT picks out a specific natural number, like 2 or 3. There could also be a morphism +: INT × INT → INT, called ‘addition’. Combining these, we can get expressions like 2+3.

• 2-morphism are rewrites. For example, there could be a rewrite going from 2+3 to 5.

Later Mike realized that instead of 2-categories, it can be good to use graph-enriched categories: that is, things like categories where instead of a set of morphisms from one object to another, we have a graph.

In other words: instead of hom-sets, a graph-enriched category has ‘hom-graphs’. The objects of a graph-enriched category can represent types, the vertices of the hom-graphs can represent terms, and the edges of the hom-graphs can represent rewrites.

Mike teamed up with Greg Meredith to write a paper on this:

• Mike Stay and Greg Meredith, Representing operational semantics
with enriched Lawvere theories.

Christian decided to write a paper building on this, and I’ve been helping him out because it’s satisfying to see an old dream finally realized—in a much more detailed, beautiful way than I ever imagined!

The key was to sharpen the issue by considering enriched Lawvere theories. Lawvere theories are an excellent formalism for describing algebraic structures obeying equational laws, but they do not specify how to compute in such a structure, for example taking a complex expression and simplifying it using rewrite rules. Enriched Lawvere theories let us study the process of rewriting.

Maybe I should back up a bit. A Lawvere theory is a category with finite products generated by a single object , for ‘type’. Morphisms represent n-ary operations, and commutative diagrams specify equations these operations obey. There is a theory for groups, a theory for rings, and so on. We can specify algebraic structures of a given kind in some ‘context’—that is, in some category with finite products—by a product-preserving functor For example, if is the theory of groups and is the category of sets then such a functor describes a group, but if is the category of topological space then such a functor describes a topological group.

All this is a simple and elegant form of what computer scientists call denotational semantics: roughly, the study of types and terms, and what they signify. However, Lawvere theories know nothing of operational semantics: that is, how we actually compute. The objects of our Lawvere are types and the morphisms are terms. But there are no rewrites going between terms, only equations!

This is where enriched Lawvere theories come in. Suppose we fix a cartesian closed category V, such as the category of sets, or the category of graphs, or the category of posets, or even the category of categories. Then V-enriched category is a thing like a category, but instead of having a set of morphisms from any object to any other object, it has an object of V. That is, instead of hom-sets it can have hom-graphs, or hom-posets, or hom-categories. If it has hom-categories, then it’s a 2-category—so this setup includes my original dream, but much more!

Our paper explains how to generalize Lawvere theories to this enriched setting, and how to use these enriched Lawvere theories in operational semantics. We rely heavily on previous work, especially by Rory Lucyshyn-Wright, who in turn built on work by John Power and others. But we’re hoping that our paper, which is a bit less high-powered, will be easier for people who are familiar with category theory but not yet enriched categories. The novelty lies less in the math than its applications. Give it a try!

Here is a small piece of a hom-graph in the graph-enriched theory of the SKI combinator calculus, a variable-free version of the lambda calculus invented by Moses Schönfinkel and Haskell Curry back in the 1920s:

Props in Network Theory (Part 2)

Here’s my talk for SYCO4 next week:

• Props in network theory.

Abstract. To describe systems composed of interacting parts, scientists and engineers draw diagrams of networks: flow charts, Petri nets, electrical circuit diagrams, signal-flow graphs, chemical reaction networks, Feynman diagrams and the like. All these different diagrams fit into a common framework: the mathematics of symmetric monoidal categories. Two complementary approaches are presentations of props using generators and relations (which are more algebraic in flavor) and structured cospan categories (which are more geometrical). In this talk we focus on the former. A “prop” is a strict symmetric monoidal category whose objects are tensor powers of a single generating object. We will see that props are a flexible tool for describing many kinds of networks.

You can read a lot more here:

• John Baez, Props in network theory (part 1), Azimuth, April 27, 2018.

Symposium on Compositional Structures 4: Program

Here’s the program for this conference:

• Symposium on Compositional Structures 4, 22–23 May, 2019, Chapman University, California. Organized by Alexander Kurz.

A lot of my students and collaborators are speaking here! The meeting will take place in Beckman Hall 101.

Wednesday May 22, 2019

• 10:30–11:30 — Registration.

• 11:30–12:30 — John Baez, “Props in Network Theory“.

• 12:30–1:00 — Jade Master, “Generalized Petri Nets”.

• 1:00–2:00 — Lunch.

• 2:00–2:30 — Christian Williams, “Enriched Lawvere Theories for Operational Semantics”.

• 2:30–3:00 — Kenny Courser, “Structured Cospans”.

• 3:00–3:30 — Daniel Cicala, “Rewriting Structured Cospans”.

• 3:30–4:00 — Break.

• 4:00–4:30 — Samuel Balco and Alexander Kurz, “Nominal String Diagrams”.

• 4:30–5:00 — Jeffrey Morton, “2-Group Actions and Double Categories”.

• 5:00–5:30 — Michael Shulman, “All (∞,1)-Toposes Have Strict Univalent Universes”.

• 5:30–6:30 — Reception.

Thursday May 23, 2019

• 9:30–10:30 — Nina Otter, “A Unified Framework for Equivalences in Social Networks”.

• 10:30–11:00 — Kohei Kishida, Soroush Rafiee Rad, Joshua Sack and Shengyang Zhong, “Categorical Equivalence between Orthocomplemented Quantales and Complete Orthomodular Lattices”.

• 11:00–11:30 — Break.

• 11:30–12:00 — Cole Comfort, “Circuit Relations for Real Stabilizers: Towards TOF+H”.

• 12:00–12:30 — Owen Biesel, “Duality for Algebras of the Connected Planar Wiring Diagrams Operad”.

• 12:30–1:00 — Joe Moeller and Christina Vasilakopoulou, “Monoidal Grothendieck Construction”.

• 1:00–2:00 — Lunch.

• 2:00–3:00 — Tobias Fritz, “Categorical Probability: Results and Challenges”.

• 3:00–3:30 — Harsh Beohar and Sebastian Küpper, “Bisimulation Maps in Presheaf Categories”.

• 3:30–4:00 — Break.

• 4:00–4:30 — Benjamin MacAdam, Jonathan Gallagher and Rory Lucyshyn-Wright, “Scalars in Tangent Categories”.

• 4:30–5:00 — Jonathan Gallagher, Benjamin MacAdam and Geoff Cruttwell, “Towards Formalizing and Extending Differential Programming via Tangent Categories”.

• 5:00–5:30 — David Sprunger and Shin-Ya Katsumata, “Differential Categories, Recurrent Neural Networks, and Machine Learning”.

Symposium on Compositional Structures 4

There’s yet another conference in this fast-paced series, and this time it’s in Southern California!

• Symposium on Compositional Structures 4, 22–23 May, 2019, Chapman University, California. Organized by Alexander Kurz.

The Symposium on Compositional Structures (SYCO) is an interdisciplinary series of meetings aiming to support the growing community of researchers interested in the phenomenon of compositionality, from both applied and abstract perspectives, and in particular where category theory serves as a unifying common language.
The first SYCO was in September 2018, at the University of Birmingham. The second SYCO was in December 2018, at the University of Strathclyde. The third SYCO was in March 2019, at the University of Oxford. Each meeting attracted about 70 participants.

We welcome submissions from researchers across computer science, mathematics, physics, philosophy, and beyond, with the aim of fostering friendly discussion, disseminating new ideas, and spreading knowledge between fields. Submission is encouraged for both mature research and work in progress, and by both established academics and junior researchers, including students.

Submission is easy, with no format requirements or page restrictions. The meeting does not have proceedings, so work can be submitted even if it has been submitted or published elsewhere. Think creatively—you could submit a recent paper, or notes on work in progress, or even a recent Masters or PhD thesis.

While no list of topics could be exhaustive, SYCO welcomes submissions
with a compositional focus related to any of the following areas, in
particular from the perspective of category theory:

• logical methods in computer science, including classical and quantum programming, type theory, concurrency, natural language processing and machine learning;

• graphical calculi, including string diagrams, Petri nets and reaction networks;

• languages and frameworks, including process algebras, proof nets, type theory and game semantics;

• abstract algebra and pure category theory, including monoidal category theory, higher category theory, operads, polygraphs, and relationships to homotopy theory;

• quantum algebra, including quantum computation and representation theory;

• tools and techniques, including rewriting, formal proofs and proof assistants, and game theory;

• industrial applications, including case studies and real-world problem descriptions.

This new series aims to bring together the communities behind many previous successful events which have taken place over the last decade, including “Categories, Logic and Physics”, “Categories, Logic and Physics (Scotland)”, “Higher-Dimensional Rewriting and Applications”, “String Diagrams in Computation, Logic and Physics”, “Applied Category Theory”, “Simons Workshop on Compositionality”, and the “Peripatetic Seminar in Sheaves and Logic”.

SYCO will be a regular fixture in the academic calendar, running regularly throughout the year, and becoming over time a recognized venue for presentation and discussion of results in an informal and friendly atmosphere. To help create this community, and to avoid the need to make difficult choices between strong submissions, in the event that more good-quality submissions are received than can be accommodated in the timetable, the programme committee may choose to
defer some submissions to a future meeting, rather than reject them. This would be done based largely on submission order, giving an incentive for early submission, but would also take into account other requirements, such as ensuring a broad scientific programme. Deferred submissions can be re-submitted to any future SYCO meeting, where they would not need peer review, and where they would be prioritised for inclusion in the programme. This will allow us to ensure that speakers have enough time to present their ideas, without creating an unnecessarily competitive reviewing process. Meetings will be held sufficiently frequently to avoid a backlog of deferred papers.

Invited speakers

• John Baez, University of California, Riverside: Props in network theory.

• Tobias Fritz, Perimeter Institute for Theoretical Physics: Categorical probability: results and challenges.

• Nina Otter, University of California, Los Angeles: A unified framework for equivalences in social networks.

Important dates

All times are anywhere-on-earth.

• Submission deadline: Wednesday 24 April 2019
• Author notification: Wednesday 1 May 2019
• Registration deadline: TBA
• Symposium dates: Wednesday 22 and Thursday 23 May 2019

Submission

Submission is by EasyChair, via the following link:

• https://easychair.org/conferences/?conf=syco4

Submissions should present research results in sufficient detail to allow them to be properly considered by members of the programme committee, who will assess papers with regards to significance, clarity, correctness, and scope. We encourage the submission of work in progress, as well as mature results. There are no proceedings, so work can be submitted even if it has been previously published, or has been submitted for consideration elsewhere. There is no specific formatting requirement, and no page limit, although for long submissions authors should understand that reviewers may not be able to read the entire document in detail.

Programme Committee

• Miriam Backens, University of Oxford
• Ross Duncan, University of Strathclyde and Cambridge Quantum Computing
• Brendan Fong, Massachusetts Institute of Technology
• Stefano Gogioso, University of Oxford
• Amar Hadzihasanovic, Kyoto University
• Chris Heunen, University of Edinburgh
• Dominic Horsman, University of Grenoble
• Martti Karvonen, University of Edinburgh
• Kohei Kishida, Dalhousie University (chair)
• Andre Kornell, University of California, Davis
• Martha Lewis, University of Amsterdam
• Samuel Mimram, École Polytechnique
• Benjamin Musto, University of Oxford
• Nina Otter, University of California, Los Angeles
• Simona Paoli, University of Leicester
• Dorette Pronk, Dalhousie University
• Mehrnoosh Sadrzadeh, Queen Mary
• Pawel Sobocinski, University of Southampton
• Joshua Tan, University of Oxford
• Sean Tull, University of Oxford
• Dominic Verdon, University of Bristol
• Jamie Vicary, University of Birmingham and University of Oxford
• Maaike Zwart, University of Oxford