6
$\begingroup$

An equivalence relation $E$ is Borel-reducible to an equivalence relation $F$ if there is a $\Delta^1_1$ function $f$ such that $xEy$ holds iff $f(x)Ff(y)$ holds. A set $A\subset \omega^{\omega}$ is Wadge reducible to a set $B\subset \omega^{\omega}$ if there is a continuous function $g$ such that $A=g^-1[B]$. How far can the analogy between Borel-redution and Wadge-reduction be pushed? In particular is there a notion of the Borel order just like the Wadge order of a set of reals? Also can the Martin-Monk argument showing that the relation of Wadge reduction is wellfounded be replicated for the relation of Borel-reduction? If yes do projective ordinal ($AD$ in general) have any consequences on being Borel-reducible?

My motivation is that I just started reading about the area of classification problems and Borel-reduction and some concepts and definition look very similar to the Wadge hierarchy (this is kind of obvious actually because both notions are about descriptive set theoretic complexity).

$\endgroup$
2
  • $\begingroup$ Maybe $AD$ had no effect on Borel-reduction as Borel determinacy is provable in $ZFC$. This comment is admittedly very vague... $\endgroup$ Dec 16, 2011 at 1:25
  • $\begingroup$ It might help to clarify whether you want an analogy between continuous and Borel reductions of equivalence relations, between continuous and Borel reductions of sets, or between continuous reductions of sets and Borel reductions of equivalence relations. $\endgroup$ Jan 4, 2012 at 23:00

1 Answer 1

5
$\begingroup$

Equivalence relations of the same complexity, when considered as sets, need not be mutually continuously reducible. A proof that the quasiorder of Borel equivalence relations up to continuous and Borel reducibility is ill-founded can be found in Louveau and Velickovic: 'A note on Borel equivalence relations' (1994).

Note that Borel equivalence relations with only two classes are well-ordered up to continuous reducibility and the rank of an equivalence relation is the Wadge rank of the equivalence classes. Selivanov and others have results on Borel functions with finitely many values up to continuous reducibility, generalizing continuous reducibility of Borel sets.

$\endgroup$
1
  • $\begingroup$ Welcome to mathoverflow, Philipp! $\endgroup$ Feb 9, 2012 at 14:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.