Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

These are two questions I encounter in Reverse Mathematics recently.

  • In the characterization of the $\omega-model$ $M$ for $RCA_0$, the necessary and sufficient condition is $M$ is non-empty and closed under $\bigoplus$ and $\leq_T$. I do not quite get why the closure under $\bigoplus$ plays an important role here. It is one of the ways to build up sets of higher hierarchy but so is Turing Jump. I am not very sure about the choice of direct sum in the characterization.
  • The second question is regarding the following: Given $f:[N]^{k+1}\rightarrow \{0,\cdots, l-1\}$ where $[N]^{k+1}$ is the set of strictly increasing sequence of length $k+1$. Define a tree $T\subseteq N^{<N}$ by putting $t\in T$ iff for all $n<length(t), t(n)$ is the least $j$ such that 1, $t(m)<j$ for all $m<n$; 2, $f(t(m_1),\cdots,t(m_k),j)=f(t(m_1),\cdots,t(m_k),t(m))$ for all $m_1<\cdots<m_k<m\leq n$. In Section III.7 of Simpson's Subsystems of Second Order Arithmetics, it is claimed that $T$ exists and is finitely branching and given $t\in T$ there are $\leq l^{n^k}$ distinct $j$ such that $t+<j>\in T$(concatenation). I don't know where that number comes from since given $f$ and $t$ by definition there should only be at most one $j$ such that $t+<j>\in T$ since $t(n)$ is always taking the least number satisfying the condition by definition. Where could I possibly go wrong here?

Thanks in advance!

share|cite|improve this question
up vote 4 down vote accepted

For question 1: The reason $\oplus$ is involved here and Turing jump isn't is that $RCA_0$ proves the existence of $X\oplus Y$ for any two sets $X$ and $Y$ (because the membership criterion for $X\oplus Y$, namely $(\exists v\leq n)\,((n=2v\land v\in X)\lor(n=2v+1\land v\in Y))$, is $\Delta^0_0$) but doesn't prove the existence of $X'$ (the membership criterion would be $\Sigma^0_1$). Of course, there are lots of other constructions, besides $\oplus$, whose existence is provable in $RCA_0$, so you could ask why those aren't used in the characterization. The reason is that all those other constructions can be obtained by combining $\oplus$ and Turing reduction; that's the main point of the theorem.

For question 2: This definition of $T$ is somewhat strange, as the requirement on $t(n)$ refers to $t(m)$ for a range of $m$'s that includes $m=n$. Because of this circularity, $t(n)$ is not uniquely determined. Specifically, for those $k$-tuples $(m_1,\dots,m_k)$ that have $m_k=n-1$, statement 2 imposes no requirement on $j$. As a result, two different $j$'s can serve as $t(n)$ provided they give the same values for $f(t(m_1),\dots,t(m_k),j)$ whenever $m_k<n-1$; they can give different values when $m_k=n-1$. So there are $(n-1)^{k-1}$ tuples where such $j$'s could give different values. Since there are $l$ possible values, there would seem to be $l^{(n-1)^{k-1}}$ possibilities. I'm not sure why Simpson says $l^{n^k}$. I'd like to think it's because he just needs an upper bound and is being a little generous, but there's also the possibility that I didn't calculate this correctly.

share|cite|improve this answer
Doesn't it still impose no requirement on $j$ whenever $m = n$? I think that would solve the off-by-one issue. – Carl Mummert Jan 22 '13 at 23:03
Nice answer! I will agree with @CarlMummert that if we persist on the requirement only when n=m then it is then consistent. – Jing Zhang Jan 23 '13 at 15:12

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.