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, October 13 4:00 p.m. Joe Miller, UW Subclasses of the K-trivial degrees (see abstract) cookies/juice
at 3:30
Tuesday, October 20 4:00 p.m. Julia Knight, University of Notre Dame, Indiana Lengths of roots of polynomials in a Hahn field (see abstract) cookies/juice
at 3:30/
dinner at 6 at
Crandall's Peruvian & American Cuisine,
(334 State St.)
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 Wednesdays at 3:30 in B119 Van Vleck Hall.

Abstracts of talks

J. Miller's talk: Subclasses of the K-trivial degrees

I will talk about joint work with Greenberg and Nies on the fine structure of the class of K-trivial sets. The motivating example is the class of sets that are computable from both halves of a random sequence, which was already known to be a proper subclass of the K-trivial sets. We gave several characterizations of this class and proved that it is an ideal generated by its c.e. elements. This work generalizes to the class of sets that are computable from the join of every k out of n parts of a random sequence. We call such a set a k/n-base. Ranging over rationals k/n, we get a natural dense family of subideals of the K-trivial sets. The union of these ideals is the ideal of sets that are robustly computable from some random sequence.

I will finish by describing a further generalization of k/n-bases. In general, arbitrary families of projections (along the coordinate axes) do not give us new subideals of the K-trivial sets.

Knight's talk: Lengths of roots of polynomials in a Hahn field

I will speak on joint work with Karen Lange. It is well-known [M] that for a divisible ordered Abelian group G and a field K that is algebraically closed, or real closed, the Hahn field K((G)) is also algebraically closed, or real closed. The ideas go back to Newton and Puiseux. Each element r of K((G)) is a generalized power series with terms corresponding to elements of a well-ordered subset of G and with coefficients in K. The support of r is the set of g in G with non-zero coefficient, and the length of r is the order type of the support. We give a technical theorem, for the case where G is Archimedean, bounding the length of a root r of a polynomial p(x) in terms of the lengths of the coefficients in p(x). To obtain the technical theorem, we follow unpublished notes of Starchenko, adding further ordinal calculations.

An integer part for a real closed field R is a discrete ordered subring appropriate for the range of a floor function. Mourgues and Ressayre [MR] showed that every real closed field R has an integer part. To do this, they showed that there is a "truncation closed'' embedding d into the Hahn field k((G)), where G is the value group of R and k is the residue field. Given a residue field section k and a well ordering < of R, the M-R procedure becomes canonical. Knight and Lange wanted to measure the complexity of the Mourgues and Ressayre procedure. To do this they needed to bound the lengths of the power series in the range of the embedding. In [KL], they conjectured that if < has order type ω, then the elements of d(R) have length less than ωωω. The conjecture follows from the technical theorem.


[KL] J. F. Knight and K. Lange, " Complexity of structures associated with real closed fields", Proc. London Math. Soc., vol. 107 (2013), pp. 177-197.

[M] S. Maclane, "The universality of formal power series fields", Bull. Amer. Math. Soc., vol. 45 (1939), pp. 888-890.

[MR] M. H. Mourgues and J.-P. Ressayre, "Every real closed field has an integer part", J. Symb. Logic, vol. 58 (1993), pp. 641-647.

Prepared by Steffen Lempp (@math.wisc.edu">lemppmath.wisc.edu)