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.
Tuesday, April 29
(Midwest Computability Seminar,
University of Chicago)
1:00 p.m. Rod Downey, Victoria University of Wellington, New Zealand Integer valued randomness (see abstract) depart at 8:30 a.m.
from Van Vleck
loading dock/
lunch at noon in Ryerson/
dinner at 6 TBA
2:00 p.m. Greg Igusa, University of Notre Dame TBA
3:10 p.m. Noam Greenberg, Victoria University of Wellington, New Zealand Ordinals in computability (see abstract)
4:10 p.m. Kyle Riggs, Indiana University, Bloomington The decomposability problem for torsion-free Abelian groups is analytic-complete (see abstract)
4:50 p.m. Sasha Mel'nikov, Victoria University of Wellington, New Zealand TBA
Wednesday, April 30 3:30 p.m./
room B131
Paul Tveite, UW TBA (specialty exam)  
Thursday, May 1 4:00 p.m./
room B239
Ashutosh Kumar, UW Avoiding rational distances (thesis defense, see abstract)  
Tuesday, May 6 4:00 p.m. Rutger Kuyper, Radboud University of Nijmegen, Netherlands TBA cookies/ beverages at 3:30/
dinner at 6 TBA
Wednesday, May 7 3:30 p.m./
room B131
Brian Rice, UW The Thin Set Theorem for pairs and substructures of the Muchnik lattice (thesis defense)  
Thursday, May 8 TBA strength Mushfeq Khan, UW Some results on algorithmic randomness and computability-theoretic strength (thesis defense, see abstract)  
Tuesday, May 13 4:00 p.m. Anush Tserunyan, University of Illinois at Urbana-Champaign TBA cookies/ beverages at 3:30/
dinner at 6 TBA

Math 873 - Spring 2014 - On the length of Borel hierarchies

Instructor: Arnie Miller

Course Description: I will be talking about the length of Borel hierarchies.

My interest in this topic started with my thesis in 1979:

On the length of Borel hierarchies
Annals of Math Logic, 16(1979), 233-267.

and continues to this day:

Universal Functions
(with P.Larson, J.Steprans, W.Weiss)
eprint Apr 2012 last revised Feb 2013.

There is no textbook, however see:
Descriptive Set Theory and Forcing: How to prove theorems about Borel sets the hard way
Lecture Notes in Logic 4(1995), Springer-Verlag.

Math 975 - Reading Seminar in Logic

Our reading seminar is meeting on Wednesdays at 3:30 in room B131 Van Vleck Hall.

Abstracts of talks

Downey's talk: Integer valued randomness

In 2012, Bienvenu, Stephan and Teutsch began the study of an interesting notion of algorithmic randomness called integer valued randomness. This notion asks that we use martingales where the bets need to have discrete values. We will review the known results in this area, and look at recent material classifying the relationship of the randomness notion with the computably enumerable degrees, and notions of genericity. The notions of genericity intertwine themselves with the hierarchy of Δ02-degrees of Downey and Greenberg. (This is joint work with George Barmpalias and Michael McInerney.)

Greenberg's talk: Ordinals in computability

I will survey a number of projects all involving ordinal numbers, ranging from the study of the c.e. degrees to higher randomness and examining effective properties of uncountable structures.

Riggs's talk: The decomposability problem for torsion-free Abelian groups is analytic-completea

We discuss the decomposability of torsion-free abelian groups. We show that among computable groups of finite rank this property is arithmetical. However, when we consider groups of infinite rank, it becomes analytic-complete, so it cannot be characterized by a first-order formula in the language of arithmetic.

Kumar's talk: Avoiding rational distances

P. Komjath has asked the following question: Given any subset X of Euclidean space, can we always find a subset Y of X such that X and Y have the same Lebesgue outer measure and the distance between any two points in Y is irrational? Using some set-theoretic tools developed by M. Gitik and S. Shelah, we were able to answer this positively in dimension one. We'll try to sketch some of the ideas around the proof.

Khan's talk: Some results on algorithmic randomness and computability-theoretic strength

Shift-complex sequences, also known as everywhere complex sequences, are such that there is a uniform lower bound for the Kolmogorov complexity of contiguous substrings in terms of their lengths. I will begin by discussing a couple of results on how shift-complexity relates to Martin-Löf randomness in the setting of the Turing degrees.

This will lead us into the second topic, diagonally noncomputable (or DNC) functions. With Joe Miller, I showed that there are arbitrarily slow-growing DNC functions that do not compute any Kurtz random real. I also extended Kumabe's result that there is a DNC function of minimal degree by showing that given any oracle X, there is a function that is DNC relative to X and of minimal degree. I will briefly sketch the ideas involved, focusing on how we add to Kumabe's proof for the second theorem.

The last topic is (Lebesgue) density and how it interacts with randomness and computational strength. Bienvenu, Hölzl, Miller, and Nies have shown that the ML-random positive density points are exactly the ones that do not compute the halting problem. Using this theorem as a starting point, I will discuss my own results on the interactions between density, domination properties, minimality, completeness, 1-genericity, and randomness.

Prepared by Steffen Lempp (">