[Zurück]

L. San Mauro:
"Complexity of Relations via Computable Reducibility";
Vortrag: Computability in Europe - CiE 2016: Pursuit of the Universal, Paris, Frankreich; 27.06.2016 - 01.07.2016.

Computable reducibility provides a natural way of ranking
binary relations on ! according to their complexity. Such reducibility is as follows: let R and S be two binary relations, we say that R is computably reducible to S i there is a computable function f such that,for all x; y 2 !, the following holds:
xRy , f(x)Sf(y):
Computable reducibility has been object of study for decades, being
mostly applied to the case of equivalence relations. In particular, a prominent problem in the area has been that of characterizing universal equivalence relations, i.e. relations to which all others relations, of a given complexity, can be computably reduced.
In this talk, we address the problem of universality for a more General context than that of equivalence relations. First, we prove that, contrary to the case of equivalence relations and preorders, for each level of the arithmetical hierarchy there is a universal binary relation. Then, we dene natural examples of universal 0n
binary relations and of universal
0nbinary relations, obtained by fairly simple manipolations of the two most fundamental set-theoretic relations. More precisely, let U2
n be the following 0nbinary relation,xU2 n y , x 2 W;(n􀀀1)y ;
and, for n > 2, let U n be the following binary relation
xU n y , Wx W(n􀀀2)y :
We show that:
1. For all n, U2
n is a universal 0nbinary relation;
2. For n > 2, U
n is a universal 0nbinary relation.

Computability theory, Computable reducibility, Universal binary relations