The computable Scott sentence conjecture

A computable structure is a structure whose atomic diagram is computable, and a Scott sentence is a sentence characterizing the structure up to isomorphism among countable structures. The classes Πn\Pi_n and Σ2n\Sigma_{2n} refer to the corresponding infinitary quantifier-complexity levels.

Computable Scott sentence conjecture. For each even n2n\geq 2, there is a computable structure M\mathcal{M} with a Πn\Pi_n Scott sentence but no computable Σ2n\Sigma_{2n} Scott sentence.

This conjecture from Scott analysis is presented as an implication of the first back-and-forth complexity assertion. The source gives no resolution, so the conjecture remains open.

Sources & referencesView supporting material

Primary source

Ruiyuan Chen, David Gonzalez and Matthew Harrison-Trainor, “Optimal Syntactic Definitions of Back-and-Forth Types”, arXiv:2505.00893 (2025).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.