Skip to main content
MathOverflow

Return to Answer

fixed reference
Source Link
Jordan Barrett
Jordan Barrett
  • 798
  • 6
  • 15

As Emil Jeřábek and James Hanson mentioned in comments, this is well-known in the literature of first-order arithmetic as the $\Sigma_1$ least number principle, $\mathsf{L}\Sigma_1$. Simpson doesn't mention it in his book (he doesn't really talk about $\Sigma_n$ bounding either, which is more well known).

Over $\mathsf{PA}^- + \mathsf{I}\Sigma_0$, Kirby and Paris [1] proved that $\mathsf{L}\Sigma_n$, $\mathsf{L}\Pi_n$, $\mathsf{I}\Sigma_n$, $\mathsf{I}\Pi_n$ are all equivalent.

Over $\mathsf{PA}^- + \mathsf{I}\Sigma_0 + \mathsf{exp}$, Slaman [2] proved (building on results of Kirby and Paris) that $\mathsf{L}\Delta_n$, $\mathsf{I}\Delta_n$, $\mathsf{B}\Sigma_n$, are all equivalent.

Both reversals hold over $\mathsf{RCA}_0$, since it proves $\mathsf{PA}^- + \mathsf{I}\Sigma_0 + \mathsf{exp}$. In particular, $\mathsf{L}\Sigma_1$ holds in $\mathsf{RCA}_0$ (as Emil Jeřábek mentioned).

[1] L. A. S. Kirby and J. B. Paris. Initial segments of models of Peano’s axioms$\Sigma_n$-collection schemas in arithmetic. Set theory and hierarchy theoryAngus Macintyre, VLeszek Pacholski, Jeff Paris (Proc. Third Confeds., Bierutowice, 1976), Springer, BerlinLogic Colloquium '77 (proceedings of colloquium held in Wrocław, August 1977). Studies in Logic and the Foundations of Mathematics 96, pp. 211–226. Lecture Notes in Math 199-209. Elsevier North-Holland, Vol. 619NY, 1978.

[2] Theodore A. Slaman. $\Sigma_n$-bounding and $\Delta_n$-induction. Proceedings of the American Mathematical Society 132(8), pp. 2449-2456, 2004.

As Emil Jeřábek and James Hanson mentioned in comments, this is well-known in the literature of first-order arithmetic as the $\Sigma_1$ least number principle, $\mathsf{L}\Sigma_1$. Simpson doesn't mention it in his book (he doesn't really talk about $\Sigma_n$ bounding either, which is more well known).

Over $\mathsf{PA}^- + \mathsf{I}\Sigma_0$, Kirby and Paris [1] proved that $\mathsf{L}\Sigma_n$, $\mathsf{L}\Pi_n$, $\mathsf{I}\Sigma_n$, $\mathsf{I}\Pi_n$ are all equivalent.

Over $\mathsf{PA}^- + \mathsf{I}\Sigma_0 + \mathsf{exp}$, Slaman [2] proved (building on results of Kirby and Paris) that $\mathsf{L}\Delta_n$, $\mathsf{I}\Delta_n$, $\mathsf{B}\Sigma_n$, are all equivalent.

Both reversals hold over $\mathsf{RCA}_0$, since it proves $\mathsf{PA}^- + \mathsf{I}\Sigma_0 + \mathsf{exp}$. In particular, $\mathsf{L}\Sigma_1$ holds in $\mathsf{RCA}_0$ (as Emil Jeřábek mentioned).

[1] L. A. S. Kirby and J. B. Paris. Initial segments of models of Peano’s axioms. Set theory and hierarchy theory, V (Proc. Third Conf., Bierutowice, 1976), Springer, Berlin, 1977, pp. 211–226. Lecture Notes in Math., Vol. 619.

[2] Theodore A. Slaman. $\Sigma_n$-bounding and $\Delta_n$-induction. Proceedings of the American Mathematical Society 132(8), pp. 2449-2456, 2004.

As Emil Jeřábek and James Hanson mentioned in comments, this is well-known in the literature of first-order arithmetic as the $\Sigma_1$ least number principle, $\mathsf{L}\Sigma_1$. Simpson doesn't mention it in his book (he doesn't really talk about $\Sigma_n$ bounding either, which is more well known).

Over $\mathsf{PA}^- + \mathsf{I}\Sigma_0$, Kirby and Paris [1] proved that $\mathsf{L}\Sigma_n$, $\mathsf{L}\Pi_n$, $\mathsf{I}\Sigma_n$, $\mathsf{I}\Pi_n$ are all equivalent.

Over $\mathsf{PA}^- + \mathsf{I}\Sigma_0 + \mathsf{exp}$, Slaman [2] proved (building on results of Kirby and Paris) that $\mathsf{L}\Delta_n$, $\mathsf{I}\Delta_n$, $\mathsf{B}\Sigma_n$, are all equivalent.

Both reversals hold over $\mathsf{RCA}_0$, since it proves $\mathsf{PA}^- + \mathsf{I}\Sigma_0 + \mathsf{exp}$. In particular, $\mathsf{L}\Sigma_1$ holds in $\mathsf{RCA}_0$ (as Emil Jeřábek mentioned).

[1] L. A. S. Kirby and J. B. Paris. $\Sigma_n$-collection schemas in arithmetic. Angus Macintyre, Leszek Pacholski, Jeff Paris (eds.), Logic Colloquium '77 (proceedings of colloquium held in Wrocław, August 1977). Studies in Logic and the Foundations of Mathematics 96, pp. 199-209. Elsevier North-Holland, NY, 1978.

[2] Theodore A. Slaman. $\Sigma_n$-bounding and $\Delta_n$-induction. Proceedings of the American Mathematical Society 132(8), pp. 2449-2456, 2004.

typo
Source Link
Jordan Barrett
Jordan Barrett
  • 798
  • 6
  • 15

As Emil Jeřábek and James Hanson mentioned in comments, this is well-known in the literature of first-order arithmetic as the $\Sigma_1$ least number principle, $\mathsf{L}\Sigma_1$. Simpson doesn't mention it in his book (he doesn't really talk about $\Sigma_n$ bounding either, which is more well known).

Over $\mathsf{PA}^- + \mathsf{I}\Sigma_0$, Kirby and Paris [1] proved that $\mathsf{L}\Sigma_n$, $\mathsf{L}\Pi_n$, $\mathsf{L}\Sigma_n$$\mathsf{I}\Sigma_n$, $\mathsf{L}\Sigma_n$$\mathsf{I}\Pi_n$ are all equivalent.

Over $\mathsf{PA}^- + \mathsf{I}\Sigma_0 + \mathsf{exp}$, Slaman [2] proved (building on results of Kirby and Paris) that $\mathsf{L}\Delta_n$, $\mathsf{I}\Delta_n$, $\mathsf{B}\Sigma_n$, are all equivalent.

Both reversals hold over $\mathsf{RCA}_0$, since it proves $\mathsf{PA}^- + \mathsf{I}\Sigma_0 + \mathsf{exp}$. In particular, $\mathsf{L}\Sigma_1$ holds in $\mathsf{RCA}_0$ (as Emil Jeřábek mentioned).

[1] L. A. S. Kirby and J. B. Paris. Initial segments of models of Peano’s axioms. Set theory and hierarchy theory, V (Proc. Third Conf., Bierutowice, 1976), Springer, Berlin, 1977, pp. 211–226. Lecture Notes in Math., Vol. 619.

[2] Theodore A. Slaman. $\Sigma_n$-bounding and $\Delta_n$-induction. Proceedings of the American Mathematical Society 132(8), pp. 2449-2456, 2004.

As Emil Jeřábek and James Hanson mentioned in comments, this is well-known in the literature of first-order arithmetic as the $\Sigma_1$ least number principle, $\mathsf{L}\Sigma_1$. Simpson doesn't mention it in his book (he doesn't really talk about $\Sigma_n$ bounding either, which is more well known).

Over $\mathsf{PA}^- + \mathsf{I}\Sigma_0$, Kirby and Paris [1] proved that $\mathsf{L}\Sigma_n$, $\mathsf{L}\Pi_n$, $\mathsf{L}\Sigma_n$, $\mathsf{L}\Sigma_n$ are all equivalent.

Over $\mathsf{PA}^- + \mathsf{I}\Sigma_0 + \mathsf{exp}$, Slaman [2] proved (building on results of Kirby and Paris) that $\mathsf{L}\Delta_n$, $\mathsf{I}\Delta_n$, $\mathsf{B}\Sigma_n$, are all equivalent.

Both reversals hold over $\mathsf{RCA}_0$, since it proves $\mathsf{PA}^- + \mathsf{I}\Sigma_0 + \mathsf{exp}$. In particular, $\mathsf{L}\Sigma_1$ holds in $\mathsf{RCA}_0$ (as Emil Jeřábek mentioned).

[1] L. A. S. Kirby and J. B. Paris. Initial segments of models of Peano’s axioms. Set theory and hierarchy theory, V (Proc. Third Conf., Bierutowice, 1976), Springer, Berlin, 1977, pp. 211–226. Lecture Notes in Math., Vol. 619.

[2] Theodore A. Slaman. $\Sigma_n$-bounding and $\Delta_n$-induction. Proceedings of the American Mathematical Society 132(8), pp. 2449-2456, 2004.

As Emil Jeřábek and James Hanson mentioned in comments, this is well-known in the literature of first-order arithmetic as the $\Sigma_1$ least number principle, $\mathsf{L}\Sigma_1$. Simpson doesn't mention it in his book (he doesn't really talk about $\Sigma_n$ bounding either, which is more well known).

Over $\mathsf{PA}^- + \mathsf{I}\Sigma_0$, Kirby and Paris [1] proved that $\mathsf{L}\Sigma_n$, $\mathsf{L}\Pi_n$, $\mathsf{I}\Sigma_n$, $\mathsf{I}\Pi_n$ are all equivalent.

Over $\mathsf{PA}^- + \mathsf{I}\Sigma_0 + \mathsf{exp}$, Slaman [2] proved (building on results of Kirby and Paris) that $\mathsf{L}\Delta_n$, $\mathsf{I}\Delta_n$, $\mathsf{B}\Sigma_n$, are all equivalent.

Both reversals hold over $\mathsf{RCA}_0$, since it proves $\mathsf{PA}^- + \mathsf{I}\Sigma_0 + \mathsf{exp}$. In particular, $\mathsf{L}\Sigma_1$ holds in $\mathsf{RCA}_0$ (as Emil Jeřábek mentioned).

[1] L. A. S. Kirby and J. B. Paris. Initial segments of models of Peano’s axioms. Set theory and hierarchy theory, V (Proc. Third Conf., Bierutowice, 1976), Springer, Berlin, 1977, pp. 211–226. Lecture Notes in Math., Vol. 619.

[2] Theodore A. Slaman. $\Sigma_n$-bounding and $\Delta_n$-induction. Proceedings of the American Mathematical Society 132(8), pp. 2449-2456, 2004.

Source Link
Jordan Barrett
Jordan Barrett
  • 798
  • 6
  • 15

As Emil Jeřábek and James Hanson mentioned in comments, this is well-known in the literature of first-order arithmetic as the $\Sigma_1$ least number principle, $\mathsf{L}\Sigma_1$. Simpson doesn't mention it in his book (he doesn't really talk about $\Sigma_n$ bounding either, which is more well known).

Over $\mathsf{PA}^- + \mathsf{I}\Sigma_0$, Kirby and Paris [1] proved that $\mathsf{L}\Sigma_n$, $\mathsf{L}\Pi_n$, $\mathsf{L}\Sigma_n$, $\mathsf{L}\Sigma_n$ are all equivalent.

Over $\mathsf{PA}^- + \mathsf{I}\Sigma_0 + \mathsf{exp}$, Slaman [2] proved (building on results of Kirby and Paris) that $\mathsf{L}\Delta_n$, $\mathsf{I}\Delta_n$, $\mathsf{B}\Sigma_n$, are all equivalent.

Both reversals hold over $\mathsf{RCA}_0$, since it proves $\mathsf{PA}^- + \mathsf{I}\Sigma_0 + \mathsf{exp}$. In particular, $\mathsf{L}\Sigma_1$ holds in $\mathsf{RCA}_0$ (as Emil Jeřábek mentioned).

[1] L. A. S. Kirby and J. B. Paris. Initial segments of models of Peano’s axioms. Set theory and hierarchy theory, V (Proc. Third Conf., Bierutowice, 1976), Springer, Berlin, 1977, pp. 211–226. Lecture Notes in Math., Vol. 619.

[2] Theodore A. Slaman. $\Sigma_n$-bounding and $\Delta_n$-induction. Proceedings of the American Mathematical Society 132(8), pp. 2449-2456, 2004.