Southern Wisconsin Logic Colloquium

SWLC Schedule

Refreshments will be served in the 9th floor lounge a half hour before talks. Please check the schedule below. All talks will be in 901 Van Vleck Hall unless stated otherwise.

Date Time Speaker Title Cookies,
dinner, etc.
Thursday, September 3
(room B123)
4:00 p.m. Isaac Goldbring, University of Illinois at Chicago Hindman's theorem and idempotent types (abstract) cookies/juice
at 3:30/
dinner at 6 at
Hopcat (222 W. Gorham St.)
Friday, September 4
(dept. coll.)
4:00 p.m.
(room B239)
Isaac Goldbring, University of Illinois at Chicago On Kirchberg's embedding problem (abstract)  
Tuesday, September 8
(room B2??)
4:00 p.m. Rutger Kuyper, UW Medvedev and Muchnik reducibility: An introduction (abstract) cookies/juice
at 3:30
Wednesday, September 16
(room B2??)
3:30 p.m. Daniel Palacín, University of Münster, Germany TBA cookies/juice at 3/
dinner at 6
4:30 p.m. Nadja Hempel, University of Lyon-1, France TBA
Tuesday, September 22 4:00 p.m. Mariya Soskova, visiting UW from University of Sofia, Bulgaria TBA cookies/juice
at 3:30
Tuesday, September 29 4:00 p.m. Vincent Guingona, Wesleyan University, Middletown, Connecticut TBA cookies/juice
at 3:30/
dinner at 6
Tuesday, October 6 4:00 p.m. Henry Townser, University of Pennsylvania, Philadelphia TBA cookies/juice
at 3:30/
dinner at 6
Tuesday, October 13 4:00 p.m. Joe Miller, UW TBA cookies/juice
at 3:30
Tuesday, October 20 4:00 p.m. Julia Knight, University of Notre Dame, Indiana TBA cookies/juice
at 3:30/
dinner at 6
Tuesday, October 27 4:00 p.m. Reese Johnston, UW TBA cookies/juice
at 3:30

Math 873 - Fall 2015 - Topics in Logic - Medvedev and Muchnik Degrees

Instructor: Rutger Kuyper

Prerequisites: Math 770, and Math 773 or concurrent registration in Math 773

Time and Place: MWF 13:20-14:10

Textbook: none

Course Description: The Medvedev and Muchnik degrees are extensions of the Turing degrees studied in computability theory. Both of these structures also have nice substructures, namely, the degrees of the so-called effectively closed sets, which form an analogue to the computably enumerable degrees studied in the Turing degrees.

We will discuss various aspects of these structures. In particular, we will cover the following topics, including their necessary prerequisites:

Math 975 - Reading Seminar in Logic

Our reading seminar is meeting on Thursdays at 3:30 in B119 Van Vleck Hall.

Abstracts of talks

Goldbring's seminar talk: Hindman's theorem and idempotent types

For a set A of natural numbers, let FS(A) denote the set of sums of finitely many distinct elements of A. A set B of natural numbers is said to be an IP set if B contains FS(A) for some infinite set A. A central result in combinatorial number theory is Hindman's theorem, which states that if one finitely colors an IP set, then at least one of the colors is an IP set. The slickest proof of this result uses idempotent ultrafilters. Di Nasso suggested a model-theoretic generalization of idempotent ultrafilters, aptly named idempotent types, and asked in what completions of PA idempotent types exist. In this talk, I will show that Hindman's theorem is actually equivalent to the existence of idempotent types in all countable complete extensions of PA. This is joint work with Uri Andrews.

Goldbring's colloquium talk: On Kirchberg's embedding problem

In his seminal work on the classification program for nuclear C*-algebras, Kirchberg showed that a particular C*-algebra, the Cuntz algebra O2, plays a seminal role. Subsequent work with Chris Phillips showed that O2 also plays a prominent role in regards to the wider class of exact C*-algebras, and this led Kirchberg to conjecture that every C*-algebra is finitely representable in O2, that is, is embeddable in an ultrapower of O2. The main goal of this talk is to sketch a proof of a local finitary reformulation of this conjecture of Kirchberg. The proof uses model theory and in particular the notion of model-theoretic forcing. No knowledge of C*-algebras or model theory will be assumed. This is joint work with Thomas Sinclair.

Kuyper's talk: Medvedev and Muchnik reducibility: An introduction

Much of the research on degree structures in computability theory has focused on degrees of reals, that is, subsets of the natural numbers. Examples range from the classical reducibilities, such as Turing reducibility, many-one reducibility and enumeration reducibility, via more recent ones arising from the study of randomness, such as K-reducibility and LR-reducibility, to ones related to robust notions of computation that have been attracting a lot of attention in recent years, such as coarse and generic reducibility.

On the other hand, Medvedev and Muchnik reducibility live "one level up" in the reducibility hierarchy: They are reducibilities on sets of functions from the natural numbers to the natural numbers. They were originally introduced by Medvedev in 1955 and Muchnik in 1963 as formalizations of an earlier informal idea of Kolmogorov, and were originally intended as a way to study intuitionistic logic. However, they are also very interesting from the viewpoint of computability theory, as people have started to realize in the last few decades.

This talk is intended as a gentle overview of the topic. We will discuss the definitions and their background, and will present some of the basic facts that are known about these structures. The topic will be treated in full detail in this semester's Math 873.

Prepared by Steffen Lempp (">