Neeman, Itay Finite state automata and monadic definability of singular cardinals. (English) Zbl 1148.03030 J. Symb. Log. 73, No. 2, 412-438 (2008). The author proves that no singular cardinal can be defined by a monadic second-order formula over the structure \(\langle \text{ON}, <\rangle\), where ON is the class of all ordinals. In particular, he introduces a class of finite state automata acting on transfinite sequences and uses these automata to uniformly reduce monadic statements about an ordinal \(\alpha\) to statements in a language that has second-order quantifiers and quantifiers of the sort “for almost all \(\xi<\alpha\)”, but does not allow the usual first-order quantifiers.The truth of sentences of this language is invariant under restriction to club subsets of the underlying domain. So if a sentence of the “almost-all” language holds in a structure with domain \(\tau\), it also holds in a structure with domain \(\text{cof}\, (\tau)\). It follows that a sentence of the “almost-all” language cannot become true for the first time at a singular cardinal. This yields the author’s desired result. Reviewer: J. M. Plotkin (East Lansing) Cited in 1 ReviewCited in 2 Documents MSC: 03D05 Automata and formal grammars in connection with logical questions 03E10 Ordinal and cardinal numbers 03B25 Decidability of theories and sets of sentences Keywords:singular cardinal; monadic second-order formula; definability; class of ordinals PDF BibTeX XML Cite \textit{I. Neeman}, J. Symb. Log. 73, No. 2, 412--438 (2008; Zbl 1148.03030) Full Text: DOI References: [1] Roczniki Polskiego Towarzystwa Matematycznego. Seria IV. Fundamenta Informaticae 7 pp 191– (1984) [2] Roczniki Polskiego Towarzystwa Matematycznego. Seria IV. Fundamenta Informaticae 8 pp 379– (1985) [3] DOI: 10.2307/1971037 · Zbl 0345.02034 [4] DOI: 10.1016/S0019-9958(66)80013-X · Zbl 0212.33902 [5] DOI: 10.1090/S0002-9904-1965-11384-2 · Zbl 0207.30904 [6] The monadic theory of {\(\omega\)}2 48 pp 387– (1983) · Zbl 0549.03010 [7] Model-theoretic logics pp 479– (1985) [8] DOI: 10.1002/malq.19830290503 · Zbl 0541.03004 [9] The monadic second order theory of all countable ordinals (Decidable theories, II) 328 pp 1– (1973) [10] Reflecting stationary sets 47 pp 755– (1982) This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.