The Monadic Second-Order Theory of Ordinals w sub 2
J Büchi, Charles Zaiontz · Purdue e-Pubs (Purdue University System) · 1973
2) ~~(X,Z): with initial condition E[-J and te~inal condition L[e] one can construct an automata A = [a,F'~O'~lJ of form (3) YO = a A Yt' = F[Xt,Yt] A Yx = ~o[sup~] A yz = ~l[suP~Y] with terminal condition L ' [.] such that, for any ~< w 2 and any input X[O,~], [E,r,L] accepts X if and only if [A,L'] accepts X, i.e. (az) E[ZO] A rg(x,z) A L[Z~] holds just in case the recursion A applied to X yields a final state Za such that L' [Z~].The following simple counterexample shows that this is only X E Clearly Counterexample: possible in a very strange set theory: w l h " (az).(1ft)zt Thus if the above claim were true we could find a,F,..&-O'i!. such that w l (n).YO F[Xt,yt] x w l X E 9 1 = = a A Yt' = A Yx = .bO[suPOY]A £[suPl Y].W l W For such Y, let D = sUPo Y.By remark 1.5, [x; sUP~= D) E 9/ w l W and so [x; ¥x = .bO[D]}E 91 Consequently sUPlly = [~O[D}}.From this we have, is not W l X ~91 -(ay).yo= a A Yt' = F[Xt,Yt] A Yx = .bo[sup~y]A