A subset of Baire space Wadge incomparable to a Borel set? - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-19T19:45:21Z http://mathoverflow.net/feeds/question/25208 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/25208/a-subset-of-baire-space-wadge-incomparable-to-a-borel-set A subset of Baire space Wadge incomparable to a Borel set? Justin Palumbo 2010-05-19T06:03:23Z 2010-05-23T19:30:18Z <p>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.</p> <p>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.</p> <p>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$.</p> http://mathoverflow.net/questions/25208/a-subset-of-baire-space-wadge-incomparable-to-a-borel-set/25712#25712 Answer by Dave Marker for A subset of Baire space Wadge incomparable to a Borel set? Dave Marker 2010-05-23T19:30:18Z 2010-05-23T19:30:18Z <p>The same type of diagonalization should allow you to do this.</p> <p>Suppose $B$ is a Borel set that is not $F_\sigma$.</p> <p>Let $(f_\alpha:\alpha&lt;2^{\aleph_0})$ list all continuous functions.</p> <p>At any stage $\alpha&lt;\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$.</p> <p>At stage $\alpha$ we make sure $f_\alpha$ will not be a reduction of $B$ to $A$.</p> <p>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.</p> <p>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.</p> <p>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.</p>