# UConn Logo University of Connecticut UC Title Fallback

UConn Logic Group / Department of Mathematics / CLAS

# New England Recursion and Definability Seminar

## NERDS 2.0

### Overview

Date: Sunday, October 28, 2012
Time: 11 am-4:20 pm
Place: Margaret Clapp Library Lecture Room, Wellesley College

### Schedule

 11:00–11:50 Russell Miller (Queens College CUNY) Computable and finitary reducibility on equivalence relations 12:00–12:50 Rachel Epstein (Harvard University) Truth-table degrees and random strings 1:00–2:30 Lunch and discussion time 2:30–3:20 Tyler Markkanen (Manhattan College) Domatic partitions of computable graphs 3:30–4:20 François Dorais (Dartmouth College) Reverse mathematics and infinite algebraic field extensions

### Abstracts

#### Russell Miller

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

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

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

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.