Yet another hierarchy theorem

Publisher： Cambridge University Press

E-ISSN： 1943-5886|65|2|627-640

ISSN： 0022-4812

Source： The Journal of Symbolic Logic, Vol.65, Iss.2, 2000-06, pp. : 627-640

Disclaimer: Any content in publications that violate the sovereignty, the constitution or regulations of the PRC is not accepted or approved by CNPIEC.

Previous Menu Next

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.

Related content

100.07 Yet another proof of the Steiner-Lehmus theorem

By  

The Mathematical Gazette, Vol. 100, Iss. 547, 2016-03 ,pp. : 124-126 (3)

Cambridge University Press

Access to resources Recommend Favorite

The hierarchy theorem for generalized quantifiers

By  

The Journal of Symbolic Logic, Vol. 61, Iss. 3, 1996-09 ,pp. : 802-817 (16)

Cambridge University Press

Access to resources Recommend Favorite

Yet Another Triangle for the Genocchi Numbers

By Ehrenborg R.   Steingrimsson E.  

European Journal of Combinatorics, Vol. 21, Iss. 5, 2000-07 ,pp. : 593-600 (8)

Elsevier

Access to resources Recommend Favorite

101.32 Yet another Cantor series

By  

The Mathematical Gazette, Vol. 101, Iss. 552, 2017-10 ,pp. : 488-489 (2)

Cambridge University Press

Access to resources Recommend Favorite

Ramsey's theorem in the hierarchy of choice principles

By  

The Journal of Symbolic Logic, Vol. 42, Iss. 3, 1977-09 ,pp. : 387-390 (4)

Cambridge University Press

Access to resources Recommend Favorite