1 results
INFINITARY LOGIC HAS NO EXPRESSIVE EFFICIENCY OVER FINITARY LOGIC
- Part of
-
- Journal:
- The Journal of Symbolic Logic , First View
- Published online by Cambridge University Press:
- 11 April 2023, pp. 1-18
-
- Article
-
- You have access
- Open access
- HTML
- Export citation
-
We can measure the complexity of a logical formula by counting the number of alternations between existential and universal quantifiers. Suppose that an elementary first-order formula
$\varphi $ (in 
$\mathcal {L}_{\omega ,\omega }$) is equivalent to a formula of the infinitary language 
$\mathcal {L}_{\infty ,\omega }$ with n alternations of quantifiers. We prove that 
$\varphi $ is equivalent to a finitary formula with n alternations of quantifiers. Thus using infinitary logic does not allow us to express a finitary formula in a simpler way.
