About the well ordering of finite sequences of numbers

Question

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$?

Answer 1

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

Answer 2

A construction of $M \models \neg B\Sigma_2 + (1)$:

Firstly, let $N$ be a countable non-standard model of $PA$. We build $M$ as $N[G]$ by forcing.

Fix some non-standard $b \in N$. The poset consists of triples $(f,c,d)$, where $f$ is an $N$-finite partial function with domain contained by $b \times N$, $0 < c < d < b$ and $d - c > \omega$.

$(f',c',d') \leq (f,c,d)$ iff

1. $f'$ extends $f$, $c \leq c' < d' \leq d$,
2. $f'(x,s) = 0$ for $(x,s) \in \operatorname{dom} f' - \operatorname{dom} f$ and $c \leq x < c'$,
3. $f'(y,s) = 1$ for $(y,s) \in \operatorname{dom} f' - \operatorname{dom} f$ and $d' < y \leq d$.

For each $(f,c,d)$ and $e$, we can extend $(f,c,d)$ to $(f',c,d)$ forcing one of the followings:

(a) $\Phi_e(G)$ is partial;

(b) $\Phi_e(f'; n) \downarrow = \sigma$ and $\sigma$ is the $\prec$-least $\tau$ s.t. there are $g, m$ with $(g,c,d) \leq (f,c,d)$ and $\Phi_e(g; m) \downarrow = \tau$.

Of course, we can achieve (b) because $N \models PA + (1)$. For sufficiently generic $G$, $N[G]$ contains a $\Delta_2$ cut $I < b$. By (b), $N[G] \models (1)$.

However, does $B\Sigma_2 + (1)$ imply $I\Sigma_2$?