We order $\mathbb{N}^{<\mathbb{N}}$ as following: if $|\sigma| < |\tau|$ then $\sigma < \tau$; if they are of same length then they are ordered lexicographically. It is provable over $\operatorname{RCA}\_0 + I\Sigma\_2$, that this is a well ordering (of type $\omega^\omega$).


It is said that this linear ordering could be ill founded in models of $B\Sigma\_2$ (Montalban. Open questions in reverse mathematics. BSL, vol. 17, no. 3).


So, does the well foundedness of this ordering imply $B\Sigma\_2$? Or is it strictly between $B\Sigma\_2$ and $I\Sigma\_2$?



About the well ordering of finite sequences of numbers
The statement that the indicated order on $\mathbb{N}^{<\mathbb{N}}$ is well-founded is incomparable with $B\Sigma\_2$.


I will denote the order by $\prec$.
The statement that $\prec$ is well-founded can written as the statement that each non-empty set $X$ contains a $\prec$-minimal element, i.e.


(1) $\forall X \left( \exists x \in X \rightarrow \exists y \left( y \in X \land \forall z \prec y\ z\notin X\right)\right)$.


It think it is clear that $B\Sigma\_2$ does not imply (1).
Therefore, I will just show that (1) does not imply $B\Sigma\_2$. This will be done by constructing a first-order model and extend it to a model of $RCA\_0 + (1)$ in which $B\Sigma\_2$ fails.


Let $\phi\_i$ be (1) where $X$ is replaced by the $i$-th $\Delta\_1$-sentence. Each $\phi\_i$ is $\Sigma\_2$.
By Theorem 1 of [1] there exists an instance of $B\Sigma\_2$ which is not implied by $(\phi\_i)$. (Note that the principle $FAC^\Pi\_1$ there is equivalent to $B\Pi\_1$ or $B\Sigma\_2$.)


Thus, there is a first-order model of $I\Sigma\_1+(\phi\_i)\_i+\neg B\Sigma\_2$. Extending this model to a second-order model by taking all $\Delta\_1$-sets as second-order part we arrive at the desired counter-example.


[1] Charles Parsons, On a Number Theoretic Choice Schema and its Relation to Induction, In: A. Kino, J. Myhill and R.E. Vesley, Editor(s), Studies in Logic and the Foundations of Mathematics, Elsevier, 1970, Volume 60, Pages 459-473, ISSN 0049-237X, ISBN 9780720422573, 10.1016/S0049-237X(08)70771-7.
<http://www.sciencedirect.com/science/article/pii/S0049237X08707717>


