Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2504.09626 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911250772918272 |
|---|---|
| author | Alvir, Rachael Csima, Barbara Harrison-Trainor, Matthew |
| author_facet | Alvir, Rachael Csima, Barbara Harrison-Trainor, Matthew |
| contents | Given a countable mathematical structure, its Scott sentence is a sentence of the infinitary logic $\mathcal{L}_{ω_1 ω}$ that characterizes it among all countable structures. We can measure the complexity of a structure by the least complexity of a Scott sentence for that structure. It is known that there can be a difference between the least complexity of a Scott sentence and the least complexity of a computable Scott sentence; for example, Alvir, Knight, and McCoy showed that there is a computable structure with a $Π_2$ Scott sentence but no computable $Π_2$ Scott sentence. It is well known that a structure with a $Π_2$ Scott sentence must have a computable $Π_4$ Scott sentence. We show that this is best possible: there is a computable structure with a $Π_2$ Scott sentence but no computable $Σ_4$ Scott sentence. We also show that there is no reasonable characterization of the computable structures with a computable $Π_n$ Scott sentence by showing that the index set of such structures is $Π^1_1$-$m$-complete. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_09626 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On the computability of optimal Scott sentences Alvir, Rachael Csima, Barbara Harrison-Trainor, Matthew Logic Given a countable mathematical structure, its Scott sentence is a sentence of the infinitary logic $\mathcal{L}_{ω_1 ω}$ that characterizes it among all countable structures. We can measure the complexity of a structure by the least complexity of a Scott sentence for that structure. It is known that there can be a difference between the least complexity of a Scott sentence and the least complexity of a computable Scott sentence; for example, Alvir, Knight, and McCoy showed that there is a computable structure with a $Π_2$ Scott sentence but no computable $Π_2$ Scott sentence. It is well known that a structure with a $Π_2$ Scott sentence must have a computable $Π_4$ Scott sentence. We show that this is best possible: there is a computable structure with a $Π_2$ Scott sentence but no computable $Σ_4$ Scott sentence. We also show that there is no reasonable characterization of the computable structures with a computable $Π_n$ Scott sentence by showing that the index set of such structures is $Π^1_1$-$m$-complete. |
| title | On the computability of optimal Scott sentences |
| topic | Logic |
| url | https://arxiv.org/abs/2504.09626 |