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


2 Answers 2


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

  • $\begingroup$ Thanks for pointing out this reference. But I can not download the paper. However, now I have a construction of a second order model $M$ of $(1) + \neg B\Sigma_2$. As space is limited in a comment, I put it as another answer. $\endgroup$
    – Wei Wang
    Jan 13, 2013 at 3:16

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.