INFINITARY LOGIC HAS NO EXPRESSIVE EFFICIENCY OVER FINITARY LOGIC
Abstract
Abstract: 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.
Many UC-authored scholarly publications are freely available on this site because of the UC's open access policies. Let us know how this access is important for you.