+ Show/hide abstracts and details

Title: Defining totality in the enumeration degrees

Speaker: Mariya Soskova (Sofia University and University of California, Berkeley)

Time: Wednesday, January 22, 2014 at 5:00 pm

Place: MSB 203Abstract: We show that the total degrees are first order definable in the enumeration degrees.

Title: The logic of graph decompositions

Speaker: Stephen Flood (University of Connecticut)

Time: Monday, February 24, 2014 at 4:45 pm

Place: MSB 203Abstract:

The theory of simplicial graph decompositions studies the infinite graphs that can be built using a sequence of irreducible graphs which are pasted together at complete subgraphs. We study the strength of several ``existence theorems'', which say that certain graphs admit such a decomposition.

We will discuss the strength of one such existence theorem, known as Halin's Theorem, from the perspective of reverse mathematics and computability theory. In addition, we will give upper and lower bounds on the possible ordinal lengths of general prime decompositions.

Title: The power of uniformity in algorithmic randomness

Speaker: Jason Rute (Penn State)

Time: Monday, March 10, 2014 at 4:45 pm

Place: MSB 203Abstract: It is well known that computable analysis and algorithmic randomness are closely connected. Moreover, computable analysis suggests that uniform reducibility should play a large role in algorithmic randomness. In this talk I will show an application of this insight. I will prove a product theorem for Schnorr randomness for non computable measures. This product theorem is an extension of van Lambalgen's well-known theorem. Both the proof and the statement of the theorem rely heavily on uniformity. It also uses computable analysis in important and insightful ways.

Title: Compressibility and Kolmogorov Complexity

Speaker: Marie Nicholson (University of Connecticut)

Time: Monday, March 24, 2014 at 4:45 pm

Place: MSB 203Abstract: Binns uses the connection between Hausdorff dimension and Kolmogorov complexity to define a pseudo-metric on the Cantor set, which has interesting geometric and algebraic properties. This metric induces a complete, path-connected, non-compact topology on the Cantor set within which we can define concepts such as angle, projection and scalar multiplication. In this talk, we will introduce Binns's metric and also discuss how it can be used to define a notion of data compression in which every infinite binary sequence with sufficient regularity is able to be maximally compressed.

Title: Incomparable omega_1-like models of set theory

Speaker: Victoria Gitman (City Tech, CUNY)

Time: Monday, March 31, 2014 at 4:45 pm

Place: MSB 203Abstract: Hamkins recently showed that given any two countable models of set theory, one of them must embed into the other. I will introduce omega_1-like models, which have size omega_1 but all countable initial segments, and show that Hamkins' theorem does not extend to this class of models. I will prove that if the set-theoretic principle Diamond holds, then there are 2^omega_1 many "incomparable" omega_1-like models of set theory, so that there does not exist an embedding between any pair of them. This is joint work with Gunter Fuchs and Joel David Hamkins.

Title: Transferring model-theoretic results about $L_{\infty, \omega}$ to a Grothendieck topos

Speaker: Nate Ackerman (Harvard)

Time: Monday, April 7, 2014 at 4:45 pm

Place: MSB 203Abstract: One of the most significant discoveries of categorical logic is that for a first order language L the operations of $L_{\infty, \omega}(L)$ can be described categorically. This observation allows us to study models of sentences of $L_{\infty, \omega}(L)$ in categories other than the category of sets and functions. One class of categories which are especially well suited to interpret sentences of $L_{\infty, \omega}(L)$ are Grothendieck toposes, i.e. categories which are equivalent to the category of sheaves on some site. However, while it makes sense to study the model theory of $L_{\infty, \omega}(L)$ in a Grothendieck topos, this model theory can behave very differently than model theory in the category of sets and functions. (For example, in general it will be intuitionistic and need not satisfy the law of excluded middle). A natural question to ask is: If we fix a Grothendieck topos, which results about the model theory of $L_{\infty, \omega}(L)$ in the category of sets and functions have analogs for the model theory of $L_{\infty, \omega}(L)$ in our fixed Grothendieck topos?" In this talk we will discuss a method of encoding models of a sentence of $L_{\infty, \omega}(L)$ in a (fixed) Grothendieck topos by models of a sentence of $L_{\infty, \omega}(L′)$ in the category of sets and functions, (where L′ is a language related to L). We will then discuss how to use this encoding to prove analogs in a fixed Grothendieck topos of the downward Lowenheim-Skolem theorem, the completeness theorem as well as Barwise compactness. One of the most significant difficulties we will have to overcome is the fact that sheaves are fundamentally second order objects. We will discuss how our encoding deals with this fact and the tradeoffs which must be made in the final theorems to accommodate the non-first order nature of sheaves and the corresponding models in a Grothendieck topos.

Title: Computability Theoretic Reduction between $\Pi^1_2$ Principles

Speaker: Denis Hirschfeldt (University of Chicago)

Time: Monday, April 14, 2014 at 4:45 pm

Place: MSB 203Abstract: Many mathematical principles can be stated in the form "for all $X$ such that $C(X)$ holds, there is a $Y$ such that $D(X,Y)$ holds", where $X$ and $Y$ range over second order objects, and $C$ and $D$ are arithmetic conditions. We think of such a principle as a problem, where an instance of the problem is an $X$ such that $C(X)$ holds, and a solution to this instance is a $Y$ such that $D(X,Y)$ holds. Examples of particular relevance to this talk are versions of Koenig's Lemma (such as $KL$ and $WKL$) and of Ramsey's Theorem (such as $RT^n_2$). We'll discuss several notions of computability theoretic reducibility between such problems, and their connections with reverse mathematics. Among other things, I will explain how recasting the idea of ``every omega-model of $P$ is a model of $Q$'' in terms of games allows us to define a notion of uniform reducibility from $Q$ to $P$ that permits the use of multiple instances of $P$ to solve a single instance of $Q$. This is joint work with Carl Jockusch.

Title: Hilbert's 10th Problem

Speaker: Nicole Bowen (University of Connecticut)

Time: Monday, April 28, 2014 at 4:45 pm

Place: MSB 203Abstract: TBA

Organizer: David R. Solomon