Ann. Pure Appl. Logic: Erratum to “Arity and alternation in second-order logic” 78 (1996) 189–202
- Publisher
- Elsevier Science
- Year
- 1998
- Tongue
- English
- Weight
- 52 KB
- Volume
- 92
- Category
- Article
- ISSN
- 0168-0072
No coin nor oath required. For personal study only.
✦ Synopsis
Unfortunately the paper contains three minor inaccuracies, none of which zlo u$k,v the main results. * The result wrongly attributed in the proof of Proposition 2 to Ajtai and Fagin [l], is due to R. Fagin in Monadic generalized spectra, Zeitschrift tiir Mathematische Logik and Grundlagen der Mathematik, 21 ( 1975) 89-96. It says that connectivity is not expressible (without auxiliary predicated) by an existential monadic second-order formula. * In Fact 5(i) ~~~(k,n) should be omitted. Fact 5(i) is true for i%(n) and AA(k,n), but not for SAA&n). a In Corollary 12 there is a misprint: @should be replaced by iJ; i.e. the polynomial hierarchy collapses provided X%4( 1, n) C SAA( 1, k).
We are indebted to L. Stockmeyer, who kindly drew our attention to these inaccuractes.