MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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).

share|cite|improve this question
Maybe $AD$ had no effect on Borel-reduction as Borel determinacy is provable in $ZFC$. This comment is admittedly very vague... – Carlo Von Schnitzel Dec 16 '11 at 1:25
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. – Trevor Wilson Jan 4 '12 at 23:00
up vote 5 down vote accepted

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.

share|cite|improve this answer
Welcome to mathoverflow, Philipp! – Joel David Hamkins Feb 9 '12 at 14:06

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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