Fixed-point boundedness and the expressive power of infinitary logic

From papers

Let KK be a class of finite structures, let t(n)t(n) be polynomially bounded, and let r(s,A)r(s, \mathcal{A}) denote the relevant iteration-depth parameter for a structure A\mathcal{A} and positive integer ss. The class KK is t(n)t(n)-fixed-point bounded if, for every first-order formula φ(X,x)\varphi(X,\overline{x}) positive in XX with free variables among x,X\overline{x},X, there is a constant cc such that, for every positive integer nn and every structure A\mathcal{A} of size nn in KK, the depth of φ\varphi in A\mathcal{A} is at most ct(n)ct(n). Fixed-point boundedness conjecture. For every class KK of finite structures and every polynomially bounded t(n)t(n), the following are equivalent: (i) KK is t(n)t(n)-fixed-point bounded; (ii) for every ss, there is a constant cc such that, for every positive integer nn and every structure A\mathcal{A} of size nn in KK,

r(s,A)ct(n);r(s,\mathcal{A})\leq ct(n);

(iii) on KK, every Lωω\textrm{L}_{\infty\omega}^{\omega}-formula is equivalent to an IND[t(n)]\textrm{IND}[t(n)]-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 KK.

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

No solutions have been posted yet.