TY - JOUR

T1 - Generalized fusible numbers and their ordinals

AU - Bufetov, Alexander I.

AU - Nivasch, Gabriel

AU - Pakhomov, Fedor

N1 - Publisher Copyright:
© 2023 Elsevier B.V.

PY - 2024/1

Y1 - 2024/1

N2 - Erickson defined the fusible numbers as a set F of reals generated by repeated application of the function [Formula presented]. Erickson, Nivasch, and Xu showed that F is well ordered, with order type ε0. They also investigated a recursively defined function M:R→R. They showed that the set of points of discontinuity of M is a subset of F of order type ε0. They also showed that, although M is a total function on R, the fact that the restriction of M to Q is total is not provable in first-order Peano arithmetic PA. In this paper we explore the problem (raised by Friedman) of whether similar approaches can yield well-ordered sets F of larger order types. As Friedman pointed out, Kruskal's tree theorem yields an upper bound of the small Veblen ordinal for the order type of any set generated in a similar way by repeated application of a monotone function g:Rn→R. The most straightforward generalization of [Formula presented] to an n-ary function is the function [Formula presented]. We show that this function generates a set Fn whose order type is just φn−1(0). For this, we develop recursively defined functions Mn:R→R naturally generalizing the function M. Furthermore, we prove that for any linear function g:Rn→R, the order type of the resulting F is at most φn−1(0). Finally, we show that there do exist continuous functions g:Rn→R for which the order types of the resulting sets F approach the small Veblen ordinal.

AB - Erickson defined the fusible numbers as a set F of reals generated by repeated application of the function [Formula presented]. Erickson, Nivasch, and Xu showed that F is well ordered, with order type ε0. They also investigated a recursively defined function M:R→R. They showed that the set of points of discontinuity of M is a subset of F of order type ε0. They also showed that, although M is a total function on R, the fact that the restriction of M to Q is total is not provable in first-order Peano arithmetic PA. In this paper we explore the problem (raised by Friedman) of whether similar approaches can yield well-ordered sets F of larger order types. As Friedman pointed out, Kruskal's tree theorem yields an upper bound of the small Veblen ordinal for the order type of any set generated in a similar way by repeated application of a monotone function g:Rn→R. The most straightforward generalization of [Formula presented] to an n-ary function is the function [Formula presented]. We show that this function generates a set Fn whose order type is just φn−1(0). For this, we develop recursively defined functions Mn:R→R naturally generalizing the function M. Furthermore, we prove that for any linear function g:Rn→R, the order type of the resulting F is at most φn−1(0). Finally, we show that there do exist continuous functions g:Rn→R for which the order types of the resulting sets F approach the small Veblen ordinal.

KW - Countable ordinal

KW - Fusible number

KW - Halting problem

KW - Small Veblen ordinal

UR - http://www.scopus.com/inward/record.url?scp=85171467307&partnerID=8YFLogxK

U2 - 10.1016/j.apal.2023.103355

DO - 10.1016/j.apal.2023.103355

M3 - ???researchoutput.researchoutputtypes.contributiontojournal.article???

AN - SCOPUS:85171467307

SN - 0168-0072

VL - 175

JO - Annals of Pure and Applied Logic

JF - Annals of Pure and Applied Logic

IS - 1

M1 - 103355

ER -