Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

My adviser is out of town and there is a comment in the Van Wesep paper "wadge degrees and descriptive set theory" that I can't figure out.

Work in ZF+AD throughout.

As stated in the title, the comment says that for n odd, the (order type of the) $\bf\Delta^1_n$ wadge degrees are less that $\bf\delta^1_{n+1}$ and Van Wesep includes the comment "(Prewellorder the codes of of $\bf\Delta^1_n$ sets as preimages of initial segments of a $\bf\Pi^1_n$-prewellordered complete $\bf\Pi^1_n$ set)".

This is easy enough, let U be some $\bf\Pi^1_n$ complete set with corresponding well-order $\phi$. For x and y codes of $\bf\Delta^1_n$ sets, let $x\leq y$ iff $\exists w \in U_x$ such that (x,w) is $\leq_\phi$ greater than all (y,z) such that $z\in U_y$. This will be defined for all such x,y because of the boundedness principle.

Now, in order to finish the proof, one must show that for $\bf\Delta^1_n$ codes x,y, $U_y <_w U_x \rightarrow y < x$. While this seems intuitively true (if $y<x$ we can compute $U_y$ from $U_x$ using $<_\phi$), I cannot prove this fact.

I believe this is the correct approach. One alternative way of defining $\leq$ would be $y\leq x$ iff $(<_\phi |U_y) \leq$ (as an order type) $ (<_\phi |U_x)$ or something along those lines. But, this seems less hopeful.

Any help would be greatly appreciated. I apologize if this question is too basic for this website.

,

Cody

share|improve this question

1 Answer 1

Cody, in the 4th paragraph, when you consider a universal $\bf \Pi^1_n$ universal set $U$ (or $\bf \Pi^1_n$-complete like you wrote), for $n$ odd, I think you meant to say that $\phi$ is a norm corresponding to a $\it prewellorder$ on that universal set(since for $n$ odd, by the first periodicity theorem $\bf \Pi^1_n$ has the prewellordering property).

Concerning the question (maybe I'm missing the point here), it seems this is basically the "covering lemma". Any $\bf \Delta^1_n$ set is going to be bounded in the norm on the $\bf \Pi^1_n$ universal set given by the prewellordering property of $\bf \Pi^1_n$. The proof is exactly the same as the proof that $\bf \Delta^1_1$ sets are bounded in any norm given on a $\bf \Pi^1_1$ set (or say in the norm on the $\bf \Pi^1_1$ complete set $\bf WO$. Actually in our case here $\bf \Sigma^1_n$ sets would also be bounded in the norm. Using an appropriate norm (i.e sending a real to a corresponding Wadge degree) gives the result mentioned by Van Wesep. (One might need to also show that the norm on the $\bf \Pi^1_n$ set is onto $\bf \delta^1_n$, See theorem 4.A.4 in Moschovakis for a full proof of this fact for $\bf \Pi^1_1$, it generalizes nicely). I can tell you more about it at UNT if you want (My answer might not be the most complete one).

share|improve this answer
    
Thank you for the response. I am familiar with the proof showing that the $\bf\Sigma^1_n$ sets would be bounded in such a norm (this is what I refer to as the "boundedness principle" in my post). The part of the proof that I am missing is when you say "Using an appropriate norm (i.e sending a real to a corresponding Wadge degree) gives the result mentioned by Van Wesep" What would such a norm be? Would any norm work? –  Cody Dance Sep 29 '13 at 4:07
    
Also, if you don't mind me asking, who is this? –  Cody Dance Sep 29 '13 at 4:08
    
I guess I would take the norm which sends reals to the wadge ranks of the sets they code (under your particular coding of sets). Or what might work better here is consider the natural norm which comes from the fact that the sets in $\bf \Gamma$, for $\bf \Gamma$ closed under universal quantification and having the prewellordering property, are $\bf \Sigma^1_1$ bounded $\bf \delta$ unions of sets in $\bf \Delta$. (i.e send a real to $\alpha$, $\alpha$ the least index where the real appears). I haven't worked all the details but that should be good... –  Carlo Von Schnitzel Sep 29 '13 at 5:52
    
...(continued), In general when $\bf \Delta$ is closed under real quantification and under disjunctions and conjunctions it can be shown that the sup of lengths of the $\bf \Delta$ prewellorderings is the same as the sup of the Wadge degrees of the sets in $\bf \Gamma$ ($\bf \Delta= \bf \Gamma \bigcap \bf \Gamma^c$. –  Carlo Von Schnitzel Sep 29 '13 at 5:55
    
I'm sorry if I'm being dense, but I still do not understand your solution. Your suggestion "I guess I would take the norm which sends reals to the wadge ranks of the sets they code (under your particular coding of sets)"- this is the entire problem, showing that such a thing is a $\bf\Pi^1_n$ norm. For the other norm you suggest, the problem reduces to showing that such a norm separates wadge degrees. –  Cody Dance Sep 29 '13 at 16:52

Your Answer

 
discard

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.