Logic Seminar 2015

Fall 2015 Schedule

Fridays 5th period (11:45 am-12:35 pm) in Little 368
For past abstracts, see Fall 2105 Abstracts

  • Friday, August 28: Chris Porter, The preservation of algorithmic randomness, Part 1
  • Friday, September 04: Chris Porter, The preservation of algorithmic randomness, Part 2
  • Friday, September 11: Jindra Zapletal, Interpretations of topological spaces in models of set theory
  • Friday, September 18: Jindra Zapletal, Interpretations of topological spaces, II in Little 305
  • Friday, September 25: Doug Cenzer, Reducibility on Computably Enumerable Equivalence Relations
  • Friday, October 02: Bill Mitchell, Inconsistency of Arithmetic
  • Friday, October 09: Rupert Holzl (Univeristät der Bundeswehr München), Vitali Covering in the Weihrauch Degrees
  • Friday, October 16: Francis Adams, Extending Anticliques in Definable Graphs 1
    Abstract

    Abstract: In a graph, an anticlique A is a collection of vertices such there are no edges between elements of A. In these talks I will look at the problem of extending anticliques in definable graphs on Polish spaces. This problem includes the important special case of extending partial selectors for Borel equivalence relations. For a graph G, the smallest cardinality of an anticlique contained in no Borel anticlique is a natural cardinal characteristic associated with G. After an introduction to cardinal characteristics and to the theory of Borel equivalence relations I will discuss both provable relations among these graph characteristics and independence results for them.
  • Friday, October 23: Francis Adams, Extending Anticliques in Definable Graphs 2
    Abstract

    Abstract:
    In a graph, an anticlique A is a collection of vertices such there are no edges between elements of A. In these talks I will look at the problem of extending anticliques in definable graphs on Polish spaces. This problem includes the important special case of extending partial selectors for Borel equivalence relations. For a graph G, the smallest cardinality of an anticlique contained in no Borel anticlique is a natural cardinal characteristic associated with G. After an introduction to the theory of Borel equivalence relations, I will look at provable results concerning the graph characteristics for some specific equivalence relations. If time permits I will also discuss some independence results.
  • Friday, October 30: Jason Linehan, Information and compression distances
    Abstract

    Abstract:
    Defining a distance on binary strings is an important first step for solving many problems using machine learning. We choose a distance to measure certain relevant features in the data, but what if we do not know a priori which features are relevant? There is a single feature present in all binary strings which can be used to define a distance: the Kolmogorov complexity of the string. We can use it to define a universal pairwise distance between binary strings, and prove that this universal distance is in fact the best possible distance among a reasonably general class. By using a data compressor to approximate the Kolmogorov complexity, we can then construct a computable approximation of this “information distance”, and use it to cluster and classify arbitrary binary data. This talk will provide an introduction to the main concepts, identify some of the difficulties involved in effectivizing the distance, and demonstrate some applications.
  • Friday, November 06: Homecoming (no seminar)
  • Friday, November 13: Jason Linehan, Information and compressions distances
    Abstract

    Abstract:
    Defining a distance on binary strings is an important first step for solving many problems using machine learning. We choose a distance to measure certain relevant features in the data, but what if we do not know a priori which features are relevant? There is a single feature present in all binary strings which can be used to define a distance: the Kolmogorov complexity of the string. We can use it to define a universal pairwise distance between binary strings, and prove that this universal distance is in fact the best possible distance among a reasonably general class. By using a data compressor to approximate the Kolmogorov complexity, we can then construct a computable approximation of this “information distance”, and use it to cluster and classify arbitrary binary data. This talk will provide an introduction to the main concepts, identify some of the difficulties involved in effectivizing the distance, and demonstrate some applications.
  • Friday, November 20:Jean Larson, Topological Partition Relations
  • Friday, November 27: Thanksgiving (no seminar)
  • Friday, December 04: Douglas Cenzer, Index sets for finite normal predicate logic programs with function symbols (last Friday of Classes)

Spring 2015 Schedule

Mondays 7th period (1:55-2:45) in Little 305

  • Monday, January 12: Francis Adams and Jean Larson, Organizational Meeting
  • Monday, January 19: Martin Luther King Day (no seminar)
  • Monday, January 26: Bill Mitchell, More Prikry Forcing — and FriendsAbstract: Last term Trevor Davila introduced Prikry forcing, which can turn a measurable cardinal kappa into one of cofinality omega, without introducing any bounded subsets of kappa; doing this by adding a omega-sequence of indiscernibles. I will discuss the ideas behind Prikry forcing and how they can be used to generate longer sequences.
  • Monday, February 02: Planning Session for SEALS (regular time)
  • Monday, February 02: Laurent Bienvenu, Algorithmic Randomness for Brownian Motion at 4:05 (Colloquium)Note: Laurent Bienvenu is visiting Jan 18 – Feb 4 from Paris 7
  • Monday, February 09: Doug Cenzer, Generic Computability
  • Monday, February 16: Jindra Zapletal
  • Monday, February 23: Jean Larson and Bill Mitchell, Report on the Second Arctic Set Theory WorkshopAbstract: We will give a review of some of the mathematics discussed at the workshop with a focus on the combinatorial aspects and on inner model theory.
  • Friday, February 27: Henry Towsner, U Penn, Computability and stability for the ergodic theorem at 4:05 (Colloquium)
  • Saturday, February 28: SEALS 2015, schedule
  • Sunday, March 01: SEALS 2015
  • Monday, March 02: Spring Break (post SEALS informal work)
  • Monday, March 09: Chris Porter, Algorithmic Randomness and Non-Uniform Probability MeasuresAbstract: In a series of two talks, I will talk about various aspects of algorithmically random sequences for different computable, non-uniform probability measures. In this first talk, I will consider an abstract approach to studying the interplay between randomness preservation and randomness extraction.More specifically, I will discuss a result known as Demuth’s Theorem, which says roughly that if we effectively transform an unbiased random sequence in such a way that the resulting sequence is not computationally trivial (i.e. it is not a computable sequence), then we can effectively recover unbiased randomness from this transformed sequence. I will introduce several possible generalizations of Demuth’s Theorem and explain why certain of these generalizations hold while others fail to hold. This is joint work with Laurent Bienvenu.
  • Monday, March 16: Chris Porter, Algorithmic Randomness and Non-Uniform Probability Measures, Part 2Abstract I will continue to discuss various aspects of algorithmically random sequences for different computable probability measures. The focus of this talk will be on the initial segment complexity of such sequences.According to the Levin-Schnorr theorem, a sequence x is Martin-Löf random with respect to the Lebesgue measure if and only if the initial segments of x have sufficiently high Kolmogorov complexity:
    each initial segment of x cannot be compressed more than c bits, where the value c is independent of the choice of initial segment. It is well-known among researchers in the field that this theorem can be extended to proper sequences, that is, sequences that are random with respect to some computable measure (where we have to modify what is understood by “sufficiently high” initial segment complexity). However, one can show that there are proper sequences with extremely slow-growing initial segment complexity (i.e. there is no computable lower bound for their initial segment complexity). How can these two phenomena be reconciled?I will explain how these two phenomena are compatible and discuss recent work with Rupert Hölzl and Wolfgang Merkle in which we classify the various growth rates of the initial segment complexity of proper sequences.
  • Monday, March 23: Francis Adams, Effective Categoricity of Ultrahomogeneous Structures: Part 1Abstract:I will start with some background on computable model theory and on countable ultrahomogeneous structures. I will then prove a theorem on the effective categoricity of such structures. The end of the talk, and the talk next week, will concern a weakening of ultrahomogeneity. I will characterize various classes of these weakly ultrahomogeneous structures, investigate their effective categoricity, and answer some other questions.
  • Monday, March 30: Francis Adams, Effective Categoricity of Ultrahomogeneous Structures: Part 2
  • Monday, April 06: Tom Winckler, The Choquet gameAbstract:  It’s an open question whether the Axiom of Choice is necessary  to prove Oxtoby’s Theorem about the Choquet game.  I’d like to show exactly  where equivalent versions of A.C. can be used in the proof of Oxtoby’s Theorem, and give 2 examples from topology where A.C. is necessary and not necessary.
  • Monday, April 13: Kiara Hall, Modal Logic and ForcingThis talk will be focused on discussing some of the results from the paper The Modal Logic of Forcing by Benedikt Loewe and Joel Hamkins. I will start by introducing some of the basic concepts in Modal Logic including qualified truth along with examples. Then I will introduce a common modal logic, S4.2 and prove that it is a subset of ZFC-provable principles. Lastly, I will define buttons and switches, and discuss some interesting results.
  • Monday, April 20: Bill Mitchell, Woodin Cardinals