Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
    
Montalbán's paper: math.ucla.edu/~asl/bsl/1703/1703-004.ps –  Andres Caicedo Jan 11 '13 at 7:20

2 Answers 2

up vote 3 down vote accepted

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

share|improve this answer
    
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. –  Wei Wang Jan 13 '13 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$?

share|improve this answer

Your Answer

 
discard

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.