Monadic second order limit laws for natural well orderings

arXiv2007.14111MaRDI QIDQ6345989FDOQ6345989

Authors: Andreas Weiermann 

Publication date: 28 July 2020

Abstract: By combining classical results of B"uchi, some elementary Tauberian theorems and some basic tools from logic and combinatorics we show that every ordinal $alpha$ with $varepsilo{n}_{0}geqalphageqomeg{a}^{o}mega$ satisfies a natural monadic second order limit law and that every ordinal $alpha$ with $omeg{a}^{o}mega>alphageqomega$ satisfies a natural monadic second order Cesaro limit law. In both cases we identify as usual $alpha$ with the class of substructures $$. We work in an additive setting where the norm function $N$ assigns to every ordinal $alpha$ the number of occurrrences of the symbol $omega$ in its Cantor normal form. This number is the same as the number of edges in the tree which is canonically associated with $alpha$. For a given $alpha$ with $omegaleqalphaleqvarepsilo{n}_0$ the asymptotic probability of a monadic second order formula $varphi$ from the language of linear orders is $$ if this limit exists. If this limit exists only in the Cesaro sense we speak of the Cesaro asympotic probability of $varphi$. Moreover we prove monadic second order limit laws for the ordinal segments below below $Gamm{a}_0$ (where the norm function is extended appropriately) and we indicate how this paper's results can be extended to larger ordinal segments and even to certain impredicative ordinal notation systems having notations for uncountable ordinals. We also briefly indicate how to prove the corresponding multiplicative results for which the setting is defined relative to the Matula coding. The results of this paper concerning ordinals not exceeding $varepsilo{n}_0$ have been obtained partly in joint work with Alan R. Woods.

Mathematics Subject Classification ID

Combinatorial probability (60C05) Enumeration in graph theory (05C30) Recursive ordinals and ordinal notations (03F15)

This page was built for publication: Monadic second order limit laws for natural well orderings

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6345989)