A double arity hierarchy theorem for transitive closure logic

Archive for Mathematical Logic 35 (3):157-171 (1996)
  Copy   BIBTEX


In this paper we prove that thek-ary fragment of transitive closure logic is not contained in the extension of the (k−1)-ary fragment of partial fixed point logic by all (2k−1)-ary generalized quantifiers. As a consequence, the arity hierarchies of all the familiar forms of fixed point logic are strict simultaneously with respect to the arity of the induction predicates and the arity of generalized quantifiers.Although it is known that our theorem cannot be extended to the sublogic deterministic transitive closure logic, we show that an extension is possible when we close this logic under congruence



    Upload a copy of this work     Papers currently archived: 86,377

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

Yet another hierarchy theorem.Max Kubierschky - 2000 - Journal of Symbolic Logic 65 (2):627-640.
The dimension of the negation of transitive closure.Gregory L. McColm - 1995 - Journal of Symbolic Logic 60 (2):392-414.
Antifoundation and Transitive Closure in the System of Zermelo.Olivier Esser & Roland Hinnion - 1999 - Notre Dame Journal of Formal Logic 40 (2):197-205.
The Beth-closure of l(qα) is not finitely generated.Lauri Hella & Kerkko Luosto - 1992 - Journal of Symbolic Logic 57 (2):442 - 448.
On the restraining power of guards.Erich Grädel - 1999 - Journal of Symbolic Logic 64 (4):1719-1742.
The Price of Universality.Edith Hemaspaandra - 1996 - Notre Dame Journal of Formal Logic 37 (2):174-203.
On transitive subrelations of binary relations.Christopher S. Hardin - 2011 - Journal of Symbolic Logic 76 (4):1429-1440.


Added to PP

22 (#581,027)

6 months
1 (#867,495)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

No citations found.

Add more citations

References found in this work

Definability hierarchies of general quantifiers.Lauri Hella - 1989 - Annals of Pure and Applied Logic 43 (3):235.
Stationary logic and its friends. II.Alan H. Mekler & Saharon Shelah - 1986 - Notre Dame Journal of Formal Logic 27 (1):39-50.
Arity hierarchies.Martin Grohe - 1996 - Annals of Pure and Applied Logic 82 (2):103-163.
Complete problems for fixed-point logics.Martin Grohe - 1995 - Journal of Symbolic Logic 60 (2):517-527.
Logical Hierarchies in PTIME.Lauri Hella - 1996 - Information And Computation 129 (1):1--19.

Add more references