Journal of Symbolic Logic 84 (1):54-87 (2019)

Motivated by the search for a logic for polynomial time, we study rank logic which extends fixed-point logic with counting by operators that determine the rank of matrices over finite fields. WhileFPRcan express most of the known queries that separateFPCfromPtime, almost nothing was known about the limitations of its expressive power.In our first main result we show that the extensions ofFPCby rank operators over different prime fields are incomparable. This solves an open question posed by Dawar and Holm and also implies that rank logic, in its original definition with a distinct rank operator for every field, fails to capture polynomial time. In particular we show that the variant of rank logic${\text{FPR}}^{\text{*}}$with an operator that uniformly expresses the matrix rank over finite fields is more expressive thanFPR.One important step in our proof is to consider solvability logicFPSwhich is the analogous extension ofFPCby quantifiers which express the solvability problem for linear equation systems over finite fields. Solvability logic can easily be embedded into rank logic, but it is open whether it is a strict fragment. In our second main result we give a partial answer to this question: in the absence of counting, rank operators are strictly more expressive than solvability quantifiers.
Keywords No keywords specified (fix it)
Categories (categorize this paper)
DOI 10.1017/jsl.2018.33
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

PhilArchive copy

Upload a copy of this paper     Check publisher's policy     Papers currently archived: 55,856
External links

Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
Through your library

References found in this work BETA

Finite Model Theory.Heinz-Dieter Ebbinghaus & Jörg Flum - 2001 - Studia Logica 69 (3):449-449.

Add more references

Citations of this work BETA

No citations found.

Add more citations

Similar books and articles

The Mitchell Order Below Rank-to-Rank.Itay Neeman - 2004 - Journal of Symbolic Logic 69 (4):1143-1162.
The Mitchell Order Below Rank-To-Rank.Itay Neeman - 2004 - Journal of Symbolic Logic 69 (4):1143 - 1162.
Witnessing Dp-Rank.Itay Kaplan & Pierre Simon - 2014 - Notre Dame Journal of Formal Logic 55 (3):419-429.
Atomic Models Higher Up.Jessica Millar & Gerald E. Sacks - 2008 - Annals of Pure and Applied Logic 155 (3):225-241.
Rank, Join, and Cantor Singletons.Jim Owings - 1997 - Archive for Mathematical Logic 36 (4-5):313-320.
Fields of Finite Morley Rank.Frank Wagner - 2001 - Journal of Symbolic Logic 66 (2):703-706.
Rank-Into-Rank Hypotheses and the Failure of GCH.Vincenzo Dimonte & Sy-David Friedman - 2014 - Archive for Mathematical Logic 53 (3-4):351-366.
Fields of Finite Morley Rank.Frank Wagner - 2001 - Journal of Symbolic Logic 66 (2):703-706.
The Morley Rank of a Banach Space.José Iovino - 1996 - Journal of Symbolic Logic 61 (3):928-941.
On Pseudolinearity and Generic Pairs.Evgueni Vassiliev - 2010 - Mathematical Logic Quarterly 56 (1):35-41.


Added to PP index

Total views
16 ( #612,861 of 2,401,723 )

Recent downloads (6 months)
2 ( #361,899 of 2,401,723 )

How can I increase my downloads?


My notes