Southern Wisconsin Logic Colloquium

SWLC Schedule

Refreshments will be served in the 9th floor lounge a half hour before talks, or immediately following the 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, November 17 4:00 p.m. Logan Hoehn, University of Toronto A counterexample for Lelek's problem in continuum theory cookies/beverages at 3:30 p.m.
Tuesday, November 24 4:00 p.m. Rebecca Weber, Dartmouth College Reals that are low for information cookies/beverages at 3:30 p.m.
Tuesday, December 1 4:00 p.m. Andrea Medini, University of Wisconsin–Madison Products and h-homogeneity cookies/beverages at 3:30 p.m.

Abstracts of talks

Logan Hoehn: A counterexample for Lelek's problem in continuum theory

A compact connected metric space (continuum) is chainable if for each positive epsilon it has a finite open cover of mesh less than epsilon which can be linearly ordered so that each element meets only its immediate successor and immediate predecessor. Chainability is a classical and well-studied property of continua, though it remains a difficult problem in certain instances to determine whether or not a given continuum is chainable.

In 1964, A. Lelek introduced the notion of the span of a continuum. A continuum X has span zero if every subcontinuum of the square X2 with equal first & second coordinate projections meets the diagonal. Lelek proved that chainable continua have span zero, and asked whether the converse also holds. Such a characterization would provide a useful means to prove non-chainability of continua. Some important potential applications have since been explored, including the classification of planar homogeneous continua.

I will present a new example showing that in general span zero does not imply chainable, even among continua in the plane. This result requires new machinery for determining non-chainability of continua. I will describe a combinatorial tool which can be used to show that certain inverse limits of graphs are non-chainable, and present examples of its use. I will also indicate how this tool can be generalized to show, for a given graph G, that certain continua are not G-like.

Rebecca Weber: Reals that are low for information

Kolmogorov complexity measures the information content of a finite string. We define the mutual information of two finite strings as the sum of their individual complexities minus the complexity of their encoding as a pair. When the strings are closely related, the complexity of the pair will be smaller and hence the mutual information larger.

For infinite sequences there is no universally agreed-upon definition for mutual information. I'll present one contender and argue for its plausibility, and discuss ongoing work with Denis Hirschfeldt on sequences that are low for information: those that have finite mutual information with themselves. These have interesting relationships with K-triviality and other properties of computational weakness.

Andrea Medini: Products and h-homogeneity

A topological space X is h-homogeneous if all non-empty clopen subsets of X are homeomorphic. The Cantor set, the rationals, the irrationals or any connected space are examples of h-homogeneous spaces. Building on work of Terada, we prove that h-homogeneity is productive in the class of zero-dimensional spaces. Then, by generalizing a result of Motorov, we show that for every zero-dimensional space X there exists a zero-dimensional space Y such that X×Y is h-homogeneous. Also, we simultaneously generalize results of Motorov and Terada by showing that if X is a zero-dimensional space such that the isolated points are dense then Xκ is h-homogeneous for every infinite cardinal κ. Finally, we show that a question of Terada (whether Xω is h-homogeneous for every zero-dimensional first-countable X) is equivalent to a question of Motorov (whether such an infinite power is always divisible by 2) and give some partial answers.

Logic students, sign up for Math 873!

Prerequisites: Math 773 or equivalent
Instructor: Selwyn Ng
Time: MWF 8:50–9:40
Course Content:
This course will cover some current active topics of research in computability theory and randomness. This is for graduate students who already know some basic computability theory and simple priority constructions. The two highlights of the course are:

1. Some recent topics in c.e. degrees: We will begin by reviewing some priority arguments—infinite injury and 0''' priority. We will talk about array computability and multiple permitting, and certain kinds of lattice embeddings. We will focus mainly on the low and high sets, and the different ways of classifying them. We will talk about traceability and its dual notions.

2. Effective randomness, with particular attention to lowness and highness properties. We will review basic randomness notions such as prefix-free complexity, effectively null sets and effective martingales. We will talk about triviality and various lowness notions, and their relationships with the Turing degrees. We will cover new combinatorial methods—the Decanter and Golden run proofs—introduced by Nies, Downey and Hirschfeldt. We also look at different kinds of effective forcing arguments in randomness, such as forcing with bushy trees, clumpy trees, and Π01 classes of positive measure.

Textbooks:
Robert Soare—Recursively Enumberable Sets And Degrees: A Study Of Computable Functions and Computably Generated Sets.
Andre Nies—Computability and Randomness.
Rod Downey and Denis Hirschfeldt—Algorithmic Randomness And Complexity.

Prepared by Steffen Lempp (lempp@math.wisc.edu). Currently maintained by Joe Miller.