Infinitary Logic Has No Expressive Efficiency Over Finitary Logic
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2022
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866909474943401984 |
|---|---|
| author | Harrison-Trainor, Matthew Kretschmer, Miles |
| author_facet | Harrison-Trainor, Matthew Kretschmer, Miles |
| contents | 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 $φ$ (in $\mathcal{L}_{ω,ω}$) is equivalent to a formula of the infinitary language $\mathcal{L}_{\infty,ω}$ with $n$ alternations of quantifiers. We prove that $φ$ 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2209_05615 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Infinitary Logic Has No Expressive Efficiency Over Finitary Logic Harrison-Trainor, Matthew Kretschmer, Miles Logic 03C75, 03C25 (Primary) 03C40 (Secondary) 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 $φ$ (in $\mathcal{L}_{ω,ω}$) is equivalent to a formula of the infinitary language $\mathcal{L}_{\infty,ω}$ with $n$ alternations of quantifiers. We prove that $φ$ 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. |
| title | Infinitary Logic Has No Expressive Efficiency Over Finitary Logic |
| topic | Logic 03C75, 03C25 (Primary) 03C40 (Secondary) |
| url | https://arxiv.org/abs/2209.05615 |