UW Logic Seminar

The seminar will run sporadically during Fall 2023. Talks will continue to be updated in this site.

We will live stream the local logic seminar with the following login information:

10/24/2023 4PM, Wim Ruitenburg, Marquette University
Title: Predicate Logic for Transitive Kripke Models (video and slides)
Abstract: We consider a predicate logic for transitive Kripke models similar to intuitionistic predicate logic for reflexive transitive Kripke models. This logic and its model theory can be studied as a generalization of classical logic and model theory without any philosophical concern.

11/02/2023 4PM, David Gonzalez, University of California, Berkeley. Room: Chamberlin 2104.
Title: Scott Sentence Complexities of Linear Orderings

Abstract: The concept of Scott sentence complexity was introduced by Alvir, Greenberg, Harrison-Trainor and Turetsky and gives a way of assigning countable structures to elements of the Borel hierarchy. By calculating the Scott sentence complexities occurring in a class of structures we obtain a detailed picture of the descriptive complexity of its isomorphism relation. We study possible Scott sentence complexities of linear orderings using two approaches. First, we investigate the effect of the Friedman-Stanley embedding on Scott sentence complexity and show that it only preserves complexities. We then take a more direct approach and exhibit linear orderings of all Scott sentence complexities except and for a limit ordinal. We show that the former can not be the Scott sentence complexity of a linear ordering. In the process we develop new techniques which appear to be helpful to calculate the Scott sentence complexities of structures in general.

This talk is based on joint work with Dino Rossegger.

11/7/2023 Midwest Computability Seminar, University of Chicago, John Crerar Library Building 390. (NOT THE USUAL LOCATION!)
(live streamed on Zoom, Meeting ID: 997 5433 2165, Passcode: midwest )
Brown bag lunch: in John Crerar Library Building 390 at noon
Speakers:
- 1PM, Peter Cholak, University of Notre Dame, Indiana.
  Title: Some Computability Theoretic Aspects of Dobrinen’s Result that the Universal Triangle Free Graph Has Finite Big Ramsey Degree (video)
  Abstract: We will discuss recent work of Cholak, Dobrinen, and McCoy. Mostly we will focus on colorings within the universal triangle free graph of nodes, edges, and non edges. The result that the universal triangle free graph has finite big Ramsey degree implies for colorings of nodes, edges, or non edges there is a copy of the universal triangle free graph with a minimal number of colors. The minimum depends on the objects we are coloring, not the coloring itself. We will discuss this number for our 3 cases. A copy of the universal triangle free graph with a minimal number of colors is called a minimal heterogeneous copy. We will also discuss what is known about the computability theoretic complexity of these minimal heterogeneous copies.
- 2:30PM, David Gonzalez, University of California, Berkeley.
  Title: The omega-Vaught's Conjecture (video and slides)
  Abstract: Robert Vaught conjectured that the number of countable models of any given list of axioms must be either countable or continuum, but never in between. Despite all the work that has gone into this conjecture over the past sixty years, it remains open. It is one of the most well-known, long-standing open questions in mathematical logic. We introduce the omega-Vaught's conjecture, a strengthening of Vaught's conjecture for infinitary logic. We have shown this conjecture holds for linear orderings, a strengthening of Vaught's conjecture for linear orderings originally proved by Steel. The approach notably differs from Steel's proof (and any other previously known proof of Vaught's conjecture for linear orderings) in that it makes no appeal to lemmas from higher computability theory or descriptive set theory. This talk is based on joint work with Antonio Montalbán.
- 4PM, Tiago Royer, University of Chicago, Illinois.
  Title: Asymptotic Notions of Computability (video (part 1), video (part 2), and slides)
  Abstract: In the classical setting, we consider that a Turing machine solves a problem if, for all inputs, the machine halts with the correct output for this problem. We can relax this notion by requiring the machine to halt and be correct only on asymptotically all inputs. If we still require the machine to always halt, we have coarse computability; if we allow the machine to not halt sometimes but require it to always be correct when it does, we have generic computability. I will talk about these notions and their degree structures, and I will present a proof that there are minimal degrees for coarse reducibility.
Dinner: TBA

11/21/2023 4PM, Meng-Che "Turbo" Ho, California State University Northridge, CA.
Title: Word problems of groups as ceers (video)

Abstract: Since Dehn proposed the word problem in 1912, it has been an important topic of study in both group theory and computability theory. Most naturally occurring groups are recursively enumerable (r.e.). Their word problem can be defined to be the r.e. set of words equal to the identity of the group, which is analyzed using Turing reductions. By the Higman embedding theorem, any r.e. degree is realized as a word problem of an r.e. group.

In this talk, we consider the word problem of a group as a computably enumerable equivalence relation (ceer), namely, two words are equivalent if and only if they are equal in the group. We compare ceers using the notion of computable reductions. We see that, while the Higman embedding theorem preserves Turing degrees, it does not preserve ceer degrees in general. Contrasting the classical context, we show that not every ceer degree is realized as the word problem of some group. This shows that the landscape of word problems as ceers is very different from the classical theory.

This is a joint work with Uri Andrews and Luca San Mauro.

12/12/2023 4PM, Ang Li, University of Wisconsin-Madison
Title: Genericity and Depth (slides)
Abstract: An infinite binary sequence is Bennett deep if the difference between time-bounded prefix-free Kolmogorov complexity and prefix-free Kolmogorov complexity of its initial segments is eventually unbounded for any computable time bound. In this talk, we show that there is a deep 1-generic set.

Archived UW Logic Seminar Pages

UW Logic Seminar Schedule