×

Monomial ideals and independence of \(\mathsf{I}\Sigma_2\). (English) Zbl 1437.03166

Summary: We show that a miniaturised version of Maclagan’s theorem on monomial ideals is equivalent to 1-Con\((\mathsf{I}\Sigma_2)\) and classify a phase transition threshold for this theorem. This work highlights the combinatorial nature of Maclagan’s theorem.

MSC:

03F30 First-order arithmetic and fragments
03F15 Recursive ordinals and ordinal notations
03D20 Recursive functions and relations, subrecursive hierarchies
05D10 Ramsey theory
06A06 Partial orders, general
13F20 Polynomial rings and ideals; rings of integer-valued polynomials
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] T. Arai, Introduction to proof theory, unpublished notes, 2001.
[2] T. Arai, Introduction to ordinal analyses, unpublished notes, 2003.
[3] M. Aschenbrenner and W. Y. Pong, Orderings of monomial ideals, {\it Fund. Math.}181, 27-74 (2004). · Zbl 1049.06001
[4] W. Buchholz, A survey on ordinal notations around the Bachmann‐Howard ordinal, unpublished notes, 2015. · Zbl 1429.03206
[5] S. R. Buss (ed.), Handbook of Proof Theory, Studies in Logic and the Foundations of Mathematics, Vol. 137 (North‐Holland, 1998). · Zbl 0898.03001
[6] H. M. Friedman, Adjacent Ramsey theory, posting on the Foundations of Mathematics mailing list FOM, 22 March 1999.
[7] H. M. Friedman and F. Pelupessy, Independence of Ramsey theorem variants using ε_{0}, {\it Proc. Amer. Math. Soc.}144, 853-860 (2016). · Zbl 1402.03083
[8] P. Hájek and P. Pudlák, Metamathematics of First Order Arithmetic, Perspectives in Mathematical Logic (Springer‐Verlag, 1993). · Zbl 0781.03047
[9] D. Maclagan, Antichains of monomial ideals are finite, {\it Proc. Amer. Math. Soc.}129, 1609-1615 (2001). · Zbl 0984.13013
[10] F. Pelupessy and A. Weiermann, On the lengths of bad sequences of monomial ideals over polynomial rings, {\it Fund. Math.}216, 101-108 (2012). · Zbl 1244.03122
[11] W. Pohlers, Proof Theory, Lecture Notes in Mathematics, Vol. 1407 (Springer‐Verlag, 1989). · Zbl 0695.03024
[12] H. E. Rose, Subrecursion: Functions and Hierarchies, Oxford Logic Guides, Vol. 9 (Clarendon Press, 1984). · Zbl 0539.03018
[13] G. Takeuti, Proof Theory, second edition, Dover Books on Mathematics (Dover, 2013). · Zbl 0355.02023
[14] A. Weiermann, Phase transition thresholds for some natural subclasses of the computable functions, Logical Approaches to Computational Barriers. Proceedings of the Second Conference on Computability in Europe, CiE 2006, held in Swansea, UK, 30 June-5 July 2006, edited by A. Beckmann, U. Berger, B. Löwe and J. V. Tucker, Lecture Notes in Computer Science, Vol. 3988 (Springer, 2006), pp. 556-570. · Zbl 1110.03052
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.