Hostname: page-component-cd9895bd7-gbm5v Total loading time: 0 Render date: 2024-12-27T01:38:32.826Z Has data issue: false hasContentIssue false
  • English
  • Français

FINDING DESCENDING SEQUENCES THROUGH ILL-FOUNDED LINEAR ORDERS

Part of: Ordered sets Computability and recursion theory

Published online by Cambridge University Press:  01 February 2021

JUN LE GOH ,
ARNO PAULY  and
MANLIO VALENTI
JUN LE GOH
Affiliation:
DEPARTMENT OF MATHEMATICS UNIVERSITY OF WISCONSINMADISON, WI, USAE-mail:[email protected]
ARNO PAULY
Affiliation:
DEPARTMENT OF COMPUTER SCIENCE UNIVERSITY OF SWANSEASWANSEA, UKE-mail:[email protected]
MANLIO VALENTI
Affiliation:
DEPARTMENT OF MATHEMATICS, COMPUTER SCIENCE AND PHYSICS UNIVERSITY OF UDINEUDINE, ITALYE-mail:[email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

In this work we investigate the Weihrauch degree of the problem Decreasing Sequence ( $\mathsf {DS}$ ) of finding an infinite descending sequence through a given ill-founded linear order, which is shared by the problem Bad Sequence ( $\mathsf {BS}$ ) of finding a bad sequence through a given non-well quasi-order. We show that $\mathsf {DS}$ , despite being hard to solve (it has computable inputs with no hyperarithmetic solution), is rather weak in terms of uniform computational strength. To make the latter precise, we introduce the notion of the deterministic part of a Weihrauch degree. We then generalize $\mathsf {DS}$ and $\mathsf {BS}$ by considering $\boldsymbol {\Gamma }$ -presented orders, where $\boldsymbol {\Gamma }$ is a Borel pointclass or $\boldsymbol {\Delta }^1_1$ , $\boldsymbol {\Sigma }^1_1$ , $\boldsymbol {\Pi }^1_1$ . We study the obtained $\mathsf {DS}$ -hierarchy and $\mathsf {BS}$ -hierarchy of problems in comparison with the (effective) Baire hierarchy and show that they do not collapse at any finite level.

Keywords

Weihrauch reducibilitycomputable analysiswell-quasiordersreverse mathematics

MSC classification

Primary: 03D30: Other degrees and reducibilities
Secondary: 03D78: Computation over the reals 06A75: Generalizations of ordered sets
Type
Article
Information
The Journal of Symbolic Logic , Volume 86 , Issue 2 , June 2021 , pp. 817 - 854
Check for updates
Copyright
© The Association for Symbolic Logic 2021

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Anglès D'Auriac, P.-E. and Kihara, T., A comparison of various analytic choice principles. Preprint, 2019. arXiv:1907.02769v1.Google Scholar
Astor, E. P., Dzhafarov, D. D., Solomon, R., and Suggs, J., The uniform content of partial and linear orders . Annals of Pure and Applied Logic , vol. 168 (2017), no. 6, pp. 1153–1171.CrossRefGoogle Scholar
Brattka, V., Effective Borel measurability and reducibility of functions . Mathematical Logic Quarterly , vol. 51 (2005), no. 1, pp. 19–44.10.1002/malq.200310125CrossRefGoogle Scholar
Brattka, V., de Brecht, M., and Pauly, A., Closed choice and a Uniform Low Basis Theorem . Annals of Pure and Applied Logic , vol. 163 (2012), no. 8, pp. 986–1008.CrossRefGoogle Scholar
Brattka, V. and Gherardi, G., Weihrauch degrees, omniscience principles and weak computability, this Journal, vol. 76 (2011), no. 1, pp. 143–176.Google Scholar
Brattka, V. and Gherardi, G., Weihrauch goes Brouwerian. Preprint, 2018. arXiv:1809.00380.Google Scholar
Brattka, V. and Gherardi, G., Completion of choice. Annals of Pure and Applied Logic , vol. 172 (2021), no. 3, 102914.Google Scholar
Brattka, V., Gherardi, G., and Hölzl, R., Probabilistic computability and choice . Information and Computation , vol. 242 (2015), pp. 249–286.CrossRefGoogle Scholar
Brattka, V., Gherardi, G., and Marcone, A., The Bolzano-Weierstrass theorem is the jump of weak König's lemma . Annals of Pure and Applied Logic , vol. 163 (2012), no. 6, pp. 623–655.CrossRefGoogle Scholar
Brattka, V., Gherardi, G., and Pauly, A., Weihrauch complexity in computable analysis. Preprint, 2017. arXiv:1707.03202v1.Google Scholar
Brattka, V., Hölzl, R., and Kuyper, R., Monte Carlo computability , Proceedings of the 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017) (Vollmer, H. and Vallée, B., editors), Leibniz International Proceedings in Informatics (LIPIcs), vol. 66, Schloss Dagstuhl–Leibniz-Zentrum für Informatik, Dagstuhl, 2017, pp. 17:1–17:14.Google Scholar
Brattka, V. and Pauly, A., On the algebraic structure of Weihrauch degrees . Logical Methods in Computer Science , vol. 14 (2018), no. 4, pp. 1–36.Google Scholar
Brattka, V. and Rakotoniaina, T., On the uniform computational content of Ramsey's theorem, this Journal, vol. 82 (2017), no. 4, pp. 1278–1316.Google Scholar
Dorais, F. G., Dzhafarov, D. D., Hirst, J. L., Mileti, J. R., and Shafer, P., On uniform relationships between combinatorial problems . Transactions of the American Mathematical Society , vol. 368 (2016), pp. 1321–1359.CrossRefGoogle Scholar
Downey, R. G., Computability theory and linear orderings , Handbook of Recursive Mathematics (Ershov, Y. L., Goncharov, S. S., Nerode, A., Remmel, J. B., and Marek, V. W., editors), Studies in Logic and the Foundations of Mathematics, vol. 139, Elsevier, Amsterdam, 1998, pp. 823–976.Google Scholar
Dzhafarov, D. D., Goh, J. L., Hirschfeldt, D. R., Patey, L., and Pauly, A, Ramsey's theorem and products in the Weihrauch degrees . Computability , vol. 9 (2020), no. 2, pp. 85–110.CrossRefGoogle Scholar
Dzhafarov, D. D., Solomon, R., and Yokoyama, K., On the first-order parts of Weihrauch degrees, In preparation.Google Scholar
Friedman, H., Uniformly defined descending sequences of degrees, this Journal, vol. 41 (1976), no. 2, pp. 363–367.Google Scholar
Gherardi, G and Marcone, A., How Incomputable Is the Separable Hahn-Banach Theorem? . Notre Dame Journal of Formal Logic , vol. 50 (2009), no. 4, pp. 393–425.CrossRefGoogle Scholar
Goh, J. L., Some computability-theoretic reductions between principles around ATR0. Preprint, 2019. arXiv:1905.06868.Google Scholar
Goh, J. L., Inseparable ${\varPi}_1^1$ sets, In preparation.Google Scholar
Gregoriades, V., Kispéter, T., and Pauly, A., A comparison of concepts from computable analysis and effective descriptive set theory . Mathematical Structures in Computer Science , vol. 5 (2016.), no. 8, pp. 1414–1436.Google Scholar
Harrison, J., Recursive pseudo-well-orderings . Transactions of the American Mathematical Society , vol. 131 (1968), no. 2, pp. 526–543.10.1090/S0002-9947-1968-0244049-7CrossRefGoogle Scholar
Hirschfeldt, D. R. and Shore, R. A., Combinatorial principles weaker than Ramsey's theorem for pairs , this Journal, vol. 72 (2007), no. 1, pp. 171–206.Google Scholar
Jockusch, C. G., Kastermans, B., Lempp, S., Lerman, M., and Solomon, R., Stability and posets , this Journal, vol. 74 (2009), no. 2, pp. 693–711.Google Scholar
Kihara, T., Marcone, A., and Pauly, A., Searching for an analogue of $AT{R}_0$ in the Weihrauch lattice, this Journal, vol. 85 (2020), no. 3, pp. 1006–1043.Google Scholar
Kihara, T., Ng, K. M., and Pauly, A., Enumeration degrees and non-metrizable topology. Preprint, 2019. arXiv:1904.04107.Google Scholar
Kihara, T. and Pauly, A., Point degree spectra of represented spaces. Preprint, 2014. arXiv:1405.6866.Google Scholar
Le Roux, S. and Pauly, A, Finite choice, convex choice and finding roots . Logical Methods in Computer Science , vol. 11 (2015), no. 4.10.2168/LMCS-11(4:6)2015CrossRefGoogle Scholar
Marcone, A., On the logical strength of Nash-Williams' Theorem on transfinite sequences, Logic: From Foundations to Applications: European Logic Colloquium (Hodges, W., Hyland, M., Steinhorn, C., and Truss, J., editors), Oxford University Press, New York, 1996, pp. 327–351.Google Scholar
Marcone, A. and Shore, R. A., The maximal linear extension theorem in second order arithmetic . Archive for Mathematical Logic , vol. 50 (2011), no. 5, pp. 543–564.10.1007/s00153-011-0231-1CrossRefGoogle Scholar
Miller, J. S., Degrees of unsolvability of continuous functions , this Journal, vol. 69 (2004), no. 2, pp. 555–584.Google Scholar
Moschovakis, Y. N., Descriptive Set Theory , Mathematical Surveys and Monographs, vol. 155, American Mathematical Society, Providence, RI, 2009.CrossRefGoogle Scholar
Neumann, E. and Pauly, A., A topological view on algebraic computation models . Journal of Complexity , vol. 44 (2018), pp. 1–22.10.1016/j.jco.2017.08.003CrossRefGoogle Scholar
Patey, L., The weakness of being cohesive, thin or free in reverse mathematics . Israel Journal of Mathematics , vol. 216 (2016), pp. 905–955.CrossRefGoogle Scholar
Pauly, A., On the topological aspects of the theory of represented spaces . Computability , vol. 5 (2016), no. 2, pp. 159–180.10.3233/COM-150049CrossRefGoogle Scholar
Pauly, A. and de Brecht, M., Descriptive set theory in the category of represented spaces, Proceedings of the 30th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS) , IEEE, Kyoto, Japan, 2015, pp. 438–449.Google Scholar
Sacks, G. E., Higher Recursion Theory , First ed., Springer Verlag, Berlin, 1990.CrossRefGoogle Scholar
Simpson, S. G., Nonprovability of certain combinatorial properties of finite trees . Harvey Friedman's Research on the Foundations of Mathematics (Harrington, L. A., Morley, M. D., Šcedrov, A., and Simpson, S. G., editors), Studies in Logic and the Foundations of Mathematics, vol. 117, Elsevier, Amsterdam, 1985, pp. 87–117.CrossRefGoogle Scholar
Simpson, S. G., Mass problems and intuitionism . Notre Dame Journal of Formal Logic , vol. 49 (2008), no. 2, pp. 127–136.10.1215/00294527-2008-002CrossRefGoogle Scholar
Simpson, S. G., Subsystems of Second Order Arithmetic , second ed., Cambridge University Press, 2009.10.1017/CBO9780511581007CrossRefGoogle Scholar