Kurt Gödel Research Center

2012 seminar talk: Finitary reducibility on equivalence relations

Talk held by Russell Miller (Queens College, City College of New York, USA) at the KGRC seminar on 2012-07-10.

Abstract

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, we have defined a weaker notion, finitary reducibility, to help analyze these negative results. We say that $E$ is $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 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.