Yet Another Hierarchy Theorem

Journal of Symbolic Logic 65 (2):627-640 (2000)
  Copy   BIBTEX

Abstract

n + 1 nested k-ary fixed point operators are more expressive than n. This holds on finite structures for all sublogics of partial fixed point logic PFP that can express conjunction, existential quantification and deterministic transitive closure of binary relations using at most k-ary fixed point operators and that are closed against subformulas. Among those are a lot of popular fixed point logics.

Categories

Keywords

Reprint years

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 91,122

External links

  • This entry has no external links. Add one.
Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

My notes

Similar books and articles

Yet another hierarchy theorem.Max Kubierschky - 2000 - Journal of Symbolic Logic 65 (2):627-640.
A double arity hierarchy theorem for transitive closure logic.Martin Grohe & Lauri Hella - 1996 - Archive for Mathematical Logic 35 (3):157-171.
Expressive equivalence of least and inflationary fixed-point logic.Stephan Kreutzer - 2004 - Annals of Pure and Applied Logic 130 (1-3):61-78.
Fixed point logics.Anuj Dawar & Yuri Gurevich - 2002 - Bulletin of Symbolic Logic 8 (1):65-88.
A fixed point theorem for o-minimal structures.Kam-Chau Wong - 2003 - Mathematical Logic Quarterly 49 (6):598.
On the λY calculus.Rick Statman - 2004 - Annals of Pure and Applied Logic 130 (1-3):325-337.
An Inductive Theorem on the Correctness of General Recursive Programs.Jaime Alejandro Bohórquez - 2007 - Logic Journal of the IGPL 15 (5-6):373-399.
A Proof of Tarski’s Fixed Point Theorem by Application of Galois Connections.Marek Nowak - 2015 - Studia Logica 103 (2):287-301.
Note on Some Fixed Point Constructions in Provability Logic.Per Lindström - 2006 - Journal of Philosophical Logic 35 (3):225-230.
Hierarchies in transitive closure logic, stratified Datalog and infinitary logic.Erich Grädel & Gregory L. McColm - 1996 - Annals of Pure and Applied Logic 77 (2):169-199.
Supervaluation fixed-point logics of truth.Philip Kremer & Alasdair Urquhart - 2008 - Journal of Philosophical Logic 37 (5):407-440.
Guarded quantification in least fixed point logic.Gregory McColm - 2004 - Journal of Logic, Language and Information 13 (1):61-110.
A transfinite hierarchy of reals.George Barmpalias - 2003 - Mathematical Logic Quarterly 49 (2):163-172.
Jump Theorems for REA Operators.Alistair H. Lachlan & Xiaoding Yi - 1993 - Mathematical Logic Quarterly 39 (1):1-6.
A fixed point theorem and its use in Kripke's theory of truth.S. Heikkilä - manuscript

Analytics

Added to PP
2017-02-21

Downloads
4 (#1,517,814)

6 months
1 (#1,346,405)

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

No references found.

Add more references