Necessary use of [image] induction in a reversal

Journal of Symbolic Logic 76 (2):561 - 574 (2011)
  Copy   BIBTEX

Abstract

Jullien's indecomposability theorem (INDEC) states that if a scattered countable linear order is indecomposable, then it is either indecomposable to the left, or indecomposable to the right. The theorem was shown by Montalbán to be a theorem of hyperarithmetic analysis, and then, in the base system RCA₀ plus ${\mathrm{\Sigma }}_{1}^{1}\text{\hspace{0.17em}}$ induction, it was shown by Neeman to have strength strictly between weak ${\mathrm{\Sigma }}_{1}^{1}$ choice and ${\mathrm{\Delta }}_{1}^{1}$ comprehension. We prove in this paper that ${\mathrm{\Sigma }}_{1}^{1}$ induction is needed for the reversal of INDEC, that is for the proof that INDEC implies weak ${\mathrm{\Sigma }}_{1}^{1}$ choice. This is in contrast with the typical situation in reverse mathematics, where reversals can usually be refined to use only ${\mathrm{\Sigma }}_{1}^{0}$ induction

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 91,139

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

Determinacy in strong cardinal models.P. D. Welch - 2011 - Journal of Symbolic Logic 76 (2):719 - 728.
On the jump classes of noncuppable enumeration degrees.Charles M. Harris - 2011 - Journal of Symbolic Logic 76 (1):177 - 197.
The veblen functions for computability theorists.Alberto Marcone & Antonio Montalbán - 2011 - Journal of Symbolic Logic 76 (2):575 - 602.
A hierarchy of tree-automatic structures.Olivier Finkel & Stevo Todorčević - 2012 - Journal of Symbolic Logic 77 (1):350-368.
Generic Expansions of Countable Models.Silvia Barbina & Domenico Zambella - 2012 - Notre Dame Journal of Formal Logic 53 (4):511-523.
Diamonds, uniformization.Saharon Shelah - 1984 - Journal of Symbolic Logic 49 (4):1022-1033.

Analytics

Added to PP
2013-09-30

Downloads
15 (#884,991)

6 months
3 (#857,336)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

Reverse mathematics: the playground of logic.Richard A. Shore - 2010 - Bulletin of Symbolic Logic 16 (3):378-402.
The Strength of an Axiom of Finite Choice for Branches in Trees.G. O. H. Jun Le - 2023 - Journal of Symbolic Logic 88 (4):1367-1386.
Almost Theorems of Hyperarithmetic Analysis.Richard A. Shore - forthcoming - Journal of Symbolic Logic:1-33.

Add more citations

References found in this work

Indecomposable linear orderings and hyperarithmetic analysis.Antonio Montalbán - 2006 - Journal of Mathematical Logic 6 (1):89-120.
On the equimorphism types of linear orderings.Antonio Montalbán - 2007 - Bulletin of Symbolic Logic 13 (1):71-99.
The strength of Jullien's indecomposability theorem.Itay Neeman - 2008 - Journal of Mathematical Logic 8 (1):93-119.
Forcing with tagged trees.John R. Steel - 1978 - Annals of Mathematical Logic 15 (1):55.

Add more references