ALGOS 2020 – ALgebras, Graphs and Ordered Sets – August 26th to 28th (Online)
Time: Wednesday, August 26, 9:30am – Friday, August 29, 19:30pm, CEST
Information: Please see here for the program and advance registration.
Bar-Ilan-Jerusalem Set Theory Seminar
Time: Wednesday, August 26, 11:00am Israel Time (10:00 CEST)
Speaker: Menachem Magidor, Hebrew University
Title: Around weak diamond and uniformization
Abstract: I’ll present some old results about weak diamond, uniformization and maybe some connections to Whitehead problem. In particular I’ll present Woodin’s elegant proof to the Devlin-Shelah equivalence of Weak diamond with 2^\aleph_0<2^\aleph_1.
Information: Contact Menachem Magidor, Asaf Rinot or Omer Ben-Neria ahead of time for the zoom link.
CUNY Logic Seminar (MOPA)
Time: Wednesday, August 26, 12:00 New York time (18:00 CEST) – note the time
Speaker: Emil Jeřábek, Czech Academy of Sciences
Title: Feasible reasoning with arithmetic operations
Abstract: In bounded arithmetic, we study weak fragments of arithmetic that often correspond in a certain sense to computational complexity classes (e.g., polynomial time). Questions about provability in such theories can be thought of as a form of feasible reasoning: considering a natural object of interest from a complexity class C, can we prove its fundamental properties using only concepts from C?
Our objects of interest in this talk will be the elementary integer arithmetic operations +,−,×,/, whose complexity class is (uniform) TC0, a small subclass of P. The corresponding arithmetical theory is VTC0. Since we do not know yet if the theory can prove the totality of division and iterated multiplication ∏i<nXi which are in TC0 by an intricate result of Hesse, Allender, and Barrington, we will also consider an extension of the theory VTC0+IMUL.
Our main question is what can VTC0±IMUL prove about the elementary arithmetic operations. The answer is that more than one might expect: VTC0+IMUL proves induction for quantifier-free formulas in the basic language of arithmetic (IOpen), and even induction and minimization for Σb0 (sharply bounded) formulas in Buss’s language. This result is connected to the existence of TC0 constant-degree root-finding algorithms; the proof relies on a formalization of a form of the Lagrange inversion formula in VTC0+IMUL, and on model-theoretic abstract nonsense involving valued fields.
The remaining problem is if VTC0 proves IMUL. We will discuss issues with formalization of the Hesse–Allender–Barrington construction in VTC0, and some partial results (this is a work in progress).
Information: The seminar will take place virtually. Please email Victoria Gitman (email@example.com) for the meeting id.
CUNY Set Theory Seminar
Time: Friday, August 28, 14:00 New York time (20:00 CEST)
Speaker: Miha Habic, Bard College at Simon’s Rock
Title: Normal ultrapowers with many sets of ordinals
Abstract: Any ultrapower M of the universe by a normal measure on a cardinal κ is quite far from V in the sense that it computes V_κ+2 incorrectly. If GCH holds, this amounts to saying that M is missing a subset of κ+. Steel asked whether, even in the absence of GCH, normal ultrapowers at κ must miss a subset of κ+. In the early 90s Cummings gave a negative answer, building a model with a normal measure on κ whose ultrapower captures the entire powerset of κ+. I will present some joint work with Radek Honzík in which we improved Cummings’ result to get this capturing property to hold at the least measurable cardinal.
Information: Please email Victoria Gitman (firstname.lastname@example.org) for meeting id (this talk will have a different meeting ID!).