Upcoming Events
Logic Colloquium
October 18, 2024, 4:10 PM
60 Evans Hall
Andrew Bacon
USC
How to take a mathematical model seriously
In modern logic and in philosophy it is common to take interpreted languages to be the primary vehicle for representing the world, with models often playing a supporting role for establishing metatheoretic results. In the sciences, by contrast, it is much more common to represent the world directly using interpreted mathematical models. Part of the reason for this difference has to do with the absence of intended models for key mathematical and philosophical languages. For instance, the languages of set theory, higher-order logic, quantified modal logic, and languages with empty names all lack intended models. Nonetheless, for these languages we can construct interpreted models that partially capture their subject matter, treating some aspects of the model (such as its cardinality) as an “artefact”. In this talk I will present a framework for theorizing about subject matters, partially interpreted models, and artefacts using some categorical ideas. I will then introduce the concept of notionally sound and complete model, a model that not only gets all the truths correct but is intended in a stronger sense that can be made precise.
Logic Colloquium
November 01, 2024, 4:10 PM
60 Evans Hall
Felix Weilacher
UC Berkeley
Shannon’s Theorem and the Unbalanced Matching Problem in the Measurable Context
A theorem of Shannon states that any multigraph of maximum degree d admits a proper edge coloring using at most 3d/2 colors. We investigate the status of this theorem in the setting of “descriptive” combinatorics. That is, we are interested in finding Borel, measurable, etc. edge colorings of Borel graphs on standard Borel spaces.
We focus on the measurable setting as this is where most of the work needed to be done. There, we obtain a full generalization of Shannon’s result: Any Borel multigraph of maximum degree d on a standard probability space admits a Borel edge coloring using at most 3d/2 colors almost everywhere. Similarly in the Baire category setting.
We also prove that losing a null/meager set is not necessary for graphs of subexponential growth rate.
The proof uses a coloring procedure first used in distributed computing by Ghaffari, Kuhn, Maus, and Uitto. In the measurable setting, the most difficult step turns out to be the following result, interesting in its own right: Let G be a Borel bipartite multigraph on a standard probability space where all vertices on one side have larger degree than all vertices on the other. Then there is a Borel matching of G covering almost all the large degree vertices. Though for measure preserving graphs this follows immediately from the well known Lyons-Nazarov theorem, the general result requires new ideas inspired by Grebik’s recent proof of the measurable Vizing’s theorem.
This is joint work with Anton Bernshteyn and Matt Bowen.
Logic Colloquium
November 15, 2024, 4:10 PM
60 Evans Hall
Eyal Kaplan
UC Berkeley
Logic Colloquium
December 06, 2024, 4:10 PM
60 Evans Hall
Isaac Goldbring
UC Irvine
Logic Colloquium
January 24, 2025, 4:10 PM
60 Evans Hall
Alexi Block Gorman
Ohio State
University
Logic Colloquium
February 14, 2025, 4:10 PM
60 Evans Hall
Gaia Belardinelli
Stanford
Logic Colloquium
February 28, 2025, 4:10 PM
60 Evans Hall
Simon Huttegger
UC Irvine
Logic Colloquium
March 14, 2025, 4:10 PM
60 Evans Hall
Eddy Keming Chen
UC Davis
Logic Colloquium
March 28, 2025, 4:10 PM
60 Evans Hall
TBD
Logic Colloquium
April 11, 2025, 4:10 PM
60 Evans Hall
Francesca Zaffora Blando
CMU
Logic Colloquium
April 25, 2025, 4:10 PM
60 Evans Hall
TBD