Automatic structures and the problem of natural well-orderings

2024/07/14 by Lev D. Beklemishev, Beklemishev, Lev D., Fedor Pakhomov +1
Computer Science · #Rough Sets and Fuzzy Logic

paper · pdf · doi:10.48550/arxiv.2407.10198

Abstract

We explore the idea of using automatic and similar kind of presentations of structures to deal with the conceptual problem of natural proof-theoretic ordinal notations. We conclude that this approach still does not meet the goals.

Related

• Ordinal Notation
• Well-Ordering Principles in Proof Theory and Reverse Mathematics
• The field of the Reals and the Random Graph are not Finite-Word Ordinal-Automatic
• Model Theoretic Complexity of Automatic Structures
• Ordinal Notations in Caucal Hierarchy