Search

• < Previous
• 1
• Next >

The logical strength of B\"uchi's decidability theorem

We study the strength of axioms needed to prove various results related to automata on infinite words and B\"uchi's theorem on the decidability of the MSO theory of $(N, {\le})$. We prove that the following are equivalent over the weak second-order arithmetic theory $RCA_0$: (1) the induction&nbsp;[&hellip;]