Fixed-point boundedness and the expressive power of infinitary logic
Fixed-point boundedness and the expressive power of infinitary logic
Let be a class of finite structures, let be polynomially bounded, and let denote the relevant iteration-depth parameter for a structure and positive integer . The class is -fixed-point bounded if, for every first-order formula positive in with free variables among , there is a constant such that, for every positive integer and every structure of size in , the depth of in is at most . Fixed-point boundedness conjecture. For every class of finite structures and every polynomially bounded , the following are equivalent: (i) is -fixed-point bounded; (ii) for every , there is a constant such that, for every positive integer and every structure of size in ,
(iii) on , every -formula is equivalent to an -formula. This conjecture seeks to characterize exactly when fixed-point iteration has polynomially bounded depth and when the corresponding infinitary and inductive logics have no greater expressive power on .
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Sources & referencesView supporting material
Primary source
Amena Mahmoud, “The Power of the Depth of Iteration in Defining Relations by Induction”, arXiv:1508.06556 (2015).
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.