Summary: In an earlier paper [J. Bradfield, “The modal mu-calculus alternation hierarchy is strict”, in: U. Montanari et al. (eds.), Proc. CONCUR ’96, Lect. Notes Comput. Sci. 1119, 233-246 (1996)], the strictness of the modal mu-calculus alternation hierarchy was shown by transferring a hierarchy from arithmetic; the latter was a corollary of a deep and highly technical analysis of R. S. Lubarsky [“\(\mu\)-definable sets of integers”, J. Symb. Log. 58, 291-313 (1993; Zbl 0776.03022)]. In this paper, we show that the alternation hierarchy in arithmetic can be established by entirely elementary means; further, simple examples of strict alternation depth \(n\) formulae can be constructed, which in turn give very simple examples to separate the modal hierarchy. In addition, the winning strategy formulae of parity games are shown to be such examples.
For the entire collection see [Zbl 0885.68008].