Rango del cuantificador

Dejar${\displaystyle \varphi }$ser una fórmula de primer orden . El rango del cuantificador de${\displaystyle \varphi }$, escrito${\displaystyle \operatorname {qr} (\varphi )}$, se define como:

• ${\displaystyle \operatorname {qr} (\varphi )=0}$, si${\displaystyle \varphi }$es atómico.
• ${\displaystyle \operatorname {qr} (\varphi _ {1}\land \varphi _ {2})=\operatorname {qr} (\varphi _ {1}\lor \varphi _ {2})=\max(\operatorname {qr} (\varphi _ {1}),\operatorname {qr} (\varphi _ {2}))}$.
• ${\displaystyle \operatorname {qr} (\lnot \varphi )=\operatorname {qr} (\varphi )}$.
• ${\displaystyle \operatorname {qr} (\exists _{x}\varphi )=\operatorname {qr} (\varphi )+1}$.
• ${\displaystyle \operatorname {qr} (\forall _ {x}\varphi )=\operatorname {qr} (\varphi )+1}$.

Observaciones

• Escribimos${\displaystyle \operatorname {FO} [n]}$para el conjunto de todas las fórmulas de primer orden${\displaystyle \varphi }$con${\displaystyle \operatorname {qr} (\varphi )\leq n}$.
• Relacional${\displaystyle \operatorname {FO} [n]}$(sin símbolos de función) siempre tiene un tamaño finito, es decir, contiene un número finito de fórmulas.
• En la forma normal prenexa , el rango del cuantificador de${\displaystyle \varphi }$es exactamente el número de cuantificadores que aparecen en${\displaystyle \varphi }$.

Para lógica de punto fijo , con un operador de punto fijo mínimo${\displaystyle \operatorname {LFP} }$:${\displaystyle \operatorname {qr} ([\operatorname {LFP} _{\phi }]y)=1+\operatorname {qr} (\phi )}$.