Let $\omega^\omega$ be Baire space. If $A,B\subseteq\omega^\omega$ we say that $A$ is Wadge reducible to $B$ (written $A\leq_w B$) if there is a continuous function $f:\omega^\omega\rightarrow\omega^\omega$ with $x\in A$ if and only if $f(x)\in B$. (In other words $A$ is a continuous preimage of $B$). By identifying sets with $A\leq_w B$ and $B\leq_w A$ we induce a partial ordering on the set of corresponding equivalence classes, or Wadge degrees. Under the axiom of determinacy AD, it turns out by the so-called Wadge lemma that this hierarchy is almost linearly ordered, meaning we get a linear order if we identify a degree $a$ and the degree consisting of complements of members of $a$. Clearly the Borel sets will form an initial segment of this hierarchy. What I am curious about is if this is still the case if we drop the AD assumption.

Even without AD, determinacy holds for the Borel sets and so the Borel Wadge degrees will still be almost linear ordered - indeed almost well-ordered. For non-Borel degrees using AC it is possible to get a lot of bad behavior; for example many incomparable Wadge degrees. But all the ways I can figure to do such things is to enumerate all continuous functions and build simultaneously the incomparable sets by diagonalizing against the continuous functions. An argument like this is (I think) rather unlikely to produce a Borel set.

So specifically my question is: is it possible for there to be a non-Borel set which is Wadge-incomparable to some Borel set? This is the same as asking if it is possible for there to be a Borel set $B$ and a non-Borel set $A$ with $B\not\leq_w A$.


The same type of diagonalization should allow you to do this.

Suppose $B$ is a Borel set that is not $F_\sigma$.

Let $(f_\alpha:\alpha<2^{\aleph_0})$ list all continuous functions.

At any stage $\alpha<\aleph_0$ we will have $A_\alpha$ and $C_\alpha$ disjoint subsets of $\omega^\omega$ of size less than $2^{\aleph_0}$. Elements in $A_\alpha$ will end up in our set $A$ while elements of $C_\alpha$ will not. That is $A=\bigcup A_\alpha$ and $A\cap C_\alpha=\emptyset$ for all $\alpha$.

At stage $\alpha$ we make sure $f_\alpha$ will not be a reduction of $B$ to $A$.

case 1: there is $y$ in the image of $f_\alpha$ but not in $A_\alpha\cup C_\alpha$. Say $y=f(x)$. If $x\in B$, put $y\in C_{\alpha+1}$, otherwise put $y\in A_{\alpha+1}$. In either case, we have insured $f_\alpha$ is not a reduction.

case 2: there is $x$ in B with $f_\alpha(x)\in C_\alpha$ or $x\not\in B$ with $f_\alpha(x)\in A_\alpha$. In this case we already see $f_\alpha$ is not a reduction and do nothing.

case 3: otherwise $f_\alpha$ maps $B$ into $A_\alpha$ and the complement into $C_\alpha$. But the continuous image of a Borel is either countable or has size continuum. Thus the images of $B$ and its complement both must be countable. But then $B$ is $F_\sigma$ and its complement is $F_\sigma$, a contradiction.

  • $\begingroup$ Great, thank you very much. I guess one could also use the idea from case 3 to show that if $B$ is Borel and $X$ has no perfect subset then $B\leq_w X$ implies that $B$ is $F_\sigma$ (because the image of $B$ under the reduction would have to be countable and disjoint from the image of $B$s complement) $\endgroup$ May 24 '10 at 2:54
  • $\begingroup$ Right. It looks like I just combined those two arguments.--Dave $\endgroup$ May 24 '10 at 6:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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