Is there way to classify the quantifier rank $m$ first order sentence in first order logic

192 Views Asked by At

In its simplest situation, for example, if the signature contains only a binary relation $\sigma$, so the signature $\tau = \{ \sigma \}$, what are the inequivalent classes of all first order sentences with quantifier rank $m$ over $\tau$?

1

There are 1 best solutions below

2
On

Actually the first-order theory of graphs is undecidable (see for instance here), so given a formula, you cannot even decide if it is equivalent to $true$ on your signature. So it is impossible to enumerate inequivalent formulas of some rank.