$\omega-$model for $RCA_0$ and Proof of Ramsey's Theorem in $ACA_0$

Question

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!

Answer 1

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.