Overview

Date: Sunday, October 28, 2012
Place: Wellesley College

Schedule

11:00am	Russell Miller (Queens College CUNY)
12:00–12:50	Rachel Epstein (Harvard University)
1:00–2:30	Lunch
2:30–3:20	Tyler Markkanen (Manhattan College)
3:30–4:20	François Dorais (Dartmouth College)

Abstracts

Russell Miller (Queens College CUNY)

Computable and finitary reducibility on equivalence relations

Numerous authors have considered the notion of computable reducibility (or FF-reducibility, or $m$-reducibility) on equivalence relations on the natural numbers. This holds of equivalence relations $E$ and $F$ (written $E\leq F$) if there exists a computable total function $f$ on $\omega$ such that $x~E~y$ if and only if $f(x)~F~f(y)$. Recent results include both the existence of such reductions and, for many pairs of equivalence relations, the impossibility of any such reduction.

Considering several of the proofs of non-reducibility, Keng Meng Ng and the speaker defined a weaker notion, finitary reducibility, to help analyze these negative results. We say that $E$ is \emph{$n$-arily reducible} to $F$, written $E \leq_c^n F$, if there are computable total functions $f_1,\ldots,f_n:\omega^n\to\omega$ such that, for all $j,k\leq n$ and all $i_1,\ldots,i_n\in\omega$, $i_j~E~i_k$ if and only if $f_j(i_1,\ldots,i_n)~F~f_k(i_1,\ldots,i_n)$. If the indices of such functions can be found uniformly for every $n$, then $E$ is \emph{finitarily reducible} to $F$, written $E\leq_c^{\omega}F$. In this talk we will give examples of how these new notions can be used.

Rachel Epstein (Harvard University)

Truth-table degrees and random strings

We will show that there is a pair of Turing complete sets that form a minimal pair in the truth-table degrees. This question arose when studying the sets of random strings with respect to a universal prefix-free machine, which Muchnik showed are Turing complete but not necessarily tt-complete. There is in fact no tt-minimal pair of such sets of random strings. This talk is based on joint work with Cai, Downey, Lempp, and Miller.

François Dorais (Dartmouth College)

Reverse mathematics and infinite algebraic field extensions

In this talk, I will present joint work with Jeff Hirst and Paul Shafer in the reverse mathematics analysis of infinite algebraic field extensions and infinitary Galois theory. I will show that arithmetic comprehension ($ACA_0$) is necessary and sufficient to show that embeddability and isomorphism of algebraic extensions of two algebraic field extensions can be reduced to finitary conditions but that the weak König lemma ($WKL_0$) suffices in some important special cases. I will then analyze a handful of common definitions of normal/Galois extensions that are only equivalent assuming $WKL_0$. Finally, I will analyze the infinite case of the Galois correspondence and show that it can be meaningfully understood in $WKL_0$ and some important cases can even be understood in the base system $RCA_0$. However, $ACA_0$ is again necessary and sufficient for infinitary Galois theory to work exactly as expected.

Tyler Markkanen (Manhattan College)

Domatic partitions of computable graphs

In this talk, we will consider “domatic” partitions, or “domatic” colorings, of graphs and answer questions about these partitions that arise in computability theory. Given a graph $G$, we say that a subset D of the vertex set $V(G)$ is a *dominating set* if it is near all the vertices, in that every vertex outside of $D$ is adjacent to a vertex in $D$. A *domatic 3-partition* of G is a partitioning, or coloring, of all of $V(G)$ into 3 dominating sets. We focus on answering two types of questions: First, if domatic 3-partitions exist in a computable graph, how complicated can they be? Second, a decision problem: Given a graph, how difficult is it to decide whether it has a domatic 3-partition? We will completely classify this decision problem for highly computable graphs, computable locally finite graphs, and computable graphs in general.