Arithmetical algorithms for elementary patterns (Q2257107)

Elementary patterns of resemblance (of order 1) are an ordinal notation system derived from the finite sub-structures of the structure \((\mathrm{ORD},0,+,\leq,\leq_1)\) where \(\leq_1\) is defined inductively by \(a \leq_1 b\) iff \((a,0,+,\leq,\leq_1)\) is a \(\Sigma_1\)-elementary substructure of \((b,0,+,\leq,\leq_1)\) [\textit{T. J. Carlson}, Ann. Pure Appl. Logic 108, No. 1--3, 19--77 (2001; Zbl 1009.03026)]. Patterns are known to notate ordinals up to the Bachmann-Howard ordinal [\textit{G. Wilken}, Arch. Math. Logic 45, No. 7, 807--829 (2006; Zbl 1110.03053)]. This article provides algorithms for computing addition, multiplication and \(\omega\)-exponentiation over patterns.