AMS eBook CollectionsOne of the world's most respected mathematical collections, available in digital format for your library or institution
Induction, Bounding, Weak Combinatorial Principles, and the Homogeneous Model Theorem
About this Title
Denis R. Hirschfeldt, Department of Mathematics, University of Chicago, 5734 S. University Ave., Chicago, Illinois 60637, Karen Lange, Department of Mathematics, Wellesley College, 106 Central St., Wellesley, Massachusetts 02481 and Richard A. Shore, Department of Mathematics, Malott Hall, Cornell University, Ithaca, New York 14853
Publication: Memoirs of the American Mathematical Society
Publication Year:
2017; Volume 249, Number 1187
ISBNs: 978-1-4704-2657-6 (print); 978-1-4704-4141-8 (online)
DOI: https://doi.org/10.1090/memo/1187
Published electronically: August 9, 2017
Keywords: Reverse mathematics,
computable model theory,
atomic models,
and homogeneous models.
MSC: Primary 03B30; Secondary 03C07, 03C15, 03C50, 03C57, 03D45, 03F30, 03F35
Table of Contents
Chapters
- 1. Introduction
- 2. Definitions
- 3. The Atomic Model Theorem and Related Principles
- 4. Defining Homogeneity
- 5. Closure Conditions and Model Existence
- 6. Extension Functions and Model Existence
- 7. The Reverse Mathematics of Model Existence Theorems
- 8. Open Questions
- A. Approximating Generics
- B. Atomic Trees
- C. Saturated Models
Abstract
Goncharov and Peretyat’kin independently gave necessary and sufficient conditions for when a set of types of a complete theory $T$ is the type spectrum of some homogeneous model of $T$. Their result can be stated as a principle of second order arithmetic, which we call the Homogeneous Model Theorem (HMT), and analyzed from the points of view of computability theory and reverse mathematics. Previous computability theoretic results by Lange suggested a close connection between HMT and the Atomic Model Theorem (AMT), which states that every complete atomic theory has an atomic model. We show that HMT and AMT are indeed equivalent in the sense of reverse mathematics, as well as in a strong computability theoretic sense. We do the same for an analogous result of Peretyat’kin giving necessary and sufficient conditions for when a set of types is the type spectrum of some model.
Along the way, we analyze a number of related principles. Some of these turn out to fall into well-known reverse mathematical classes, such as ACA$_0$, I$\Sigma ^0_2$, and B$\Sigma ^0_2$. Others, however, exhibit complex interactions with first order induction and bounding principles. In particular, we isolate several principles that are provable from I$\Sigma ^0_2$, are (more than) arithmetically conservative over RCA$_0$, and imply I$\Sigma ^0_2$ over B$\Sigma ^0_2$. In an attempt to capture the combinatorics of this class of principles, we introduce the principle $\Pi ^0_1$GA, as well as its generalization $\Pi ^0_n$GA, which is conservative over RCA$_0$ and equivalent to I$\Sigma ^0_{n+1}$ over B$\Sigma ^0_{n+1}$.
- C. J. Ash and J. Knight, Computable structures and the hyperarithmetical hierarchy, Studies in Logic and the Foundations of Mathematics, vol. 144, North-Holland Publishing Co., Amsterdam, 2000. MR 1767842
- David R. Belanger, Reverse mathematics of first-order theories with finitely many models, J. Symb. Log. 79 (2014), no. 3, 955–984. MR 3248791, DOI 10.1017/jsl.2014.32
- David R. Belanger, $\mathsf {WKL}_0$ and induction principles in model theory, Ann. Pure Appl. Logic 166 (2015), no. 7-8, 767–799. MR 3344579, DOI 10.1016/j.apal.2015.04.001
- C. C. Chang and H. J. Keisler, Model Theory, 3rd edn., Stud. Logic Found. Math., vol. 73, North-Holland, Amsterdam, 1990 [1st edn. 1973, 2nd edn. 1977].
- Peter A. Cholak, Carl G. Jockusch, and Theodore A. Slaman, On the strength of Ramsey’s theorem for pairs, J. Symbolic Logic 66 (2001), no. 1, 1–55. MR 1825173, DOI 10.2307/2694910
- Chris J. Conidis, Classifying model-theoretic properties, J. Symbolic Logic 73 (2008), no. 3, 885–905. MR 2444274, DOI 10.2178/jsl/1230396753
- Barbara F. Csima, Degree spectra of prime models, J. Symbolic Logic 69 (2004), no. 2, 430–442. MR 2058182, DOI 10.2178/jsl/1082418536
- Barbara F. Csima, Valentina S. Harizanov, Denis R. Hirschfeldt, and Robert I. Soare, Bounding homogeneous models, J. Symbolic Logic 72 (2007), no. 1, 305–323. MR 2298484, DOI 10.2178/jsl/1174668397
- Barbara F. Csima, Denis R. Hirschfeldt, Julia F. Knight, and Robert I. Soare, Bounding prime models, J. Symbolic Logic 69 (2004), no. 4, 1117–1142. MR 2135658, DOI 10.2178/jsl/1102022214
- François G. Dorais, Damir D. Dzhafarov, Jeffry L. Hirst, Joseph R. Mileti, and Paul Shafer, On uniform relationships between combinatorial problems, Trans. Amer. Math. Soc. 368 (2016), no. 2, 1321–1359. MR 3430365, DOI 10.1090/S0002-9947-2015-06465-4
- H. Friedman, Subsystems of Set Theory and Analysis, PhD Dissertation, M.I.T., 1967.
- Harvey M. Friedman, Higher set theory and mathematical practice, Ann. Math. Logic 2 (1970/71), no. 3, 325–357. MR 284327, DOI 10.1016/0003-4843(71)90018-0
- Harvey Friedman, Some systems of second order arithmetic and their use, Proceedings of the International Congress of Mathematicians (Vancouver, B. C., 1974) Canad. Math. Congress, Montreal, Que., 1975, pp. 235–242. MR 0429508
- Harvey Friedman, Stephen G. Simpson, and Xiaokang Yu, Periodic points and subsystems of second-order arithmetic, Ann. Pure Appl. Logic 62 (1993), no. 1, 51–64. Logic Colloquium ’89 (Berlin). MR 1229168, DOI 10.1016/0168-0072(93)90187-I
- S. S. Gončarov, Strong constructivizability of homogeneous models, Algebra i Logika 17 (1978), no. 4, 363–388, 490 (Russian). MR 538302
- S. S. Gončarov and A. T. Nurtazin, Constructive models of complete decidable theories, Algebra i Logika 12 (1973), 125–142, 243 (Russian). MR 0398816
- Petr Hájek and Pavel Pudlák, Metamathematics of first-order arithmetic, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1998. Second printing. MR 1748522
- Valentina S. Harizanov, Pure computable model theory, Handbook of recursive mathematics, Vol. 1, Stud. Logic Found. Math., vol. 138, North-Holland, Amsterdam, 1998, pp. 3–114. MR 1673621, DOI 10.1016/S0049-237X(98)80002-5
- Leo Harrington, Recursively presentable prime models, J. Symbolic Logic 39 (1974), 305–309. MR 351804, DOI 10.2307/2272643
- Denis R. Hirschfeldt, Slicing the truth, Lecture Notes Series. Institute for Mathematical Sciences. National University of Singapore, vol. 28, World Scientific Publishing Co. Pte. Ltd., Hackensack, NJ, 2015. On the computable and reverse mathematics of combinatorial principles; Edited and with a foreword by Chitat Chong, Qi Feng, Theodore A. Slaman, W. Hugh Woodin and Yue Yang. MR 3244278
- Denis R. Hirschfeldt and Carl G. Jockusch Jr., On notions of computability-theoretic reduction between $\Pi _2^1$ principles, J. Math. Log. 16 (2016), no. 1, 1650002, 59. MR 3518779, DOI 10.1142/S0219061316500021
- Denis R. Hirschfeldt and Richard A. Shore, Combinatorial principles weaker than Ramsey’s theorem for pairs, J. Symbolic Logic 72 (2007), no. 1, 171–206. MR 2298478, DOI 10.2178/jsl/1174668391
- Denis R. Hirschfeldt, Richard A. Shore, and Theodore A. Slaman, The atomic model theorem and type omitting, Trans. Amer. Math. Soc. 361 (2009), no. 11, 5805–5837. MR 2529915, DOI 10.1090/S0002-9947-09-04847-8
- Jeffry Lynn Hirst, COMBINATORICS IN SUBSYSTEMS OF SECOND ORDER ARITHMETIC, ProQuest LLC, Ann Arbor, MI, 1987. Thesis (Ph.D.)–The Pennsylvania State University. MR 2635978
- Ulrich Kohlenbach, Higher order reverse mathematics, Reverse mathematics 2001, Lect. Notes Log., vol. 21, Assoc. Symbol. Logic, La Jolla, CA, 2005, pp. 281–295. MR 2185441
- Karen Lange, The computational complexity of homogeneous models, ProQuest LLC, Ann Arbor, MI, 2008. Thesis (Ph.D.)–The University of Chicago. MR 2717499
- Karen Lange, The degree spectra of homogeneous models, J. Symbolic Logic 73 (2008), no. 3, 1009–1028. MR 2444283, DOI 10.2178/jsl/1230396762
- Karen Lange, A characterization of the $0$-basis homogeneous bounding degrees, J. Symbolic Logic 75 (2010), no. 3, 971–995. MR 2723778, DOI 10.2178/jsl/1278682211
- Karen Lange and Robert I. Soare, Computability of homogeneous models, Notre Dame J. Formal Logic 48 (2007), no. 1, 143–170. MR 2289903, DOI 10.1305/ndjfl/1172787551
- David Marker, Model theory, Graduate Texts in Mathematics, vol. 217, Springer-Verlag, New York, 2002. An introduction. MR 1924282
- Terrence Millar, Homogeneous models and decidability, Pacific J. Math. 91 (1980), no. 2, 407–418. MR 615688
- Antonio Montalbán, Indecomposable linear orderings and hyperarithmetic analysis, J. Math. Log. 6 (2006), no. 1, 89–120. MR 2250955, DOI 10.1142/S0219061306000517
- Antonio Montalbán, On the equimorphism types of linear orderings, Bull. Symbolic Logic 13 (2007), no. 1, 71–99. MR 2300904
- Antonio Montalbán, Open questions in reverse mathematics, Bull. Symbolic Logic 17 (2011), no. 3, 431–454. MR 2856080, DOI 10.2178/bsl/1309952320
- Antonio Montalbán and Richard A. Shore, The strength of Turing determinacy within second order arithmetic, Fund. Math. 232 (2016), no. 3, 249–268. MR 3453773, DOI 10.4064/fm27-12-2015
- Michael Morley, Decidable models, Israel J. Math. 25 (1976), no. 3-4, 233–240. MR 457190, DOI 10.1007/BF02757002
- Michael Mytilinaios, Finite injury and $\Sigma _1$-induction, J. Symbolic Logic 54 (1989), no. 1, 38–49. MR 987320, DOI 10.2307/2275013
- Itay Neeman, The strength of Jullien’s indecomposability theorem, J. Math. Log. 8 (2008), no. 1, 93–119. MR 2674002, DOI 10.1142/S0219061308000725
- Itay Neeman, Necessary use of $\Sigma ^1_1$ induction in a reversal, J. Symbolic Logic 76 (2011), no. 2, 561–574. MR 2830416, DOI 10.2178/jsl/1305810764
- J. B. Paris and L. A. S. Kirby, $\Sigma _{n}$-collection schemas in arithmetic, Logic Colloquium ’77 (Proc. Conf., Wrocław, 1977) Stud. Logic Foundations Math., vol. 96, North-Holland, Amsterdam-New York, 1978, pp. 199–209. MR 519815
- M. G. Peretjat′kin, A criterion of strong constructivizability of a homogeneous model, Algebra i Logika 17 (1978), no. 4, 436–454, 491 (Russian). MR 538306
- David Seetapun and Theodore A. Slaman, On the strength of Ramsey’s theorem, Notre Dame J. Formal Logic 36 (1995), no. 4, 570–582. Special Issue: Models of arithmetic. MR 1368468, DOI 10.1305/ndjfl/1040136917
- Richard A. Shore, Splitting an $\alpha$-recursively enumerable set, Trans. Amer. Math. Soc. 204 (1975), 65–77. MR 379154, DOI 10.1090/S0002-9947-1975-0379154-1
- Richard A. Shore, Reverse mathematics: the playground of logic, Bull. Symbolic Logic 16 (2010), no. 3, 378–402. MR 2731250
- Richard A. Shore, Reverse mathematics, countable and uncountable, Effective mathematics of the uncountable, Lect. Notes Log., vol. 41, Assoc. Symbol. Logic, La Jolla, CA, 2013, pp. 150–163. MR 3205058, DOI 10.1017/CBO9781139028592.009
- Stephen G. Simpson, Subsystems of second order arithmetic, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1999. MR 1723993
- Stephen G. Simpson, Subsystems of second order arithmetic, 2nd ed., Perspectives in Logic, Cambridge University Press, Cambridge; Association for Symbolic Logic, Poughkeepsie, NY, 2009. MR 2517689
- Theodore A. Slaman, $\Sigma _n$-bounding and $\Delta _n$-induction, Proc. Amer. Math. Soc. 132 (2004), no. 8, 2449–2456. MR 2052424, DOI 10.1090/S0002-9939-04-07294-6