Computability for tree presentations of continuum-size structures
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866911251233243136 |
|---|---|
| author | Block, Jason Miller, Russell |
| author_facet | Block, Jason Miller, Russell |
| contents | We formalize an existing computability-theoretic method of presenting first-order structures whose domains have the cardinality of the continuum. Work using these methods until now has emphasized their topological properties. We shift the focus to first-order properties, using computable structure theory (on countable structures) as a guide. We present three basic questions to be asked when a structure is presented as the set of paths through a computable tree, as in our definition, and also propose the concept of tree-decidability as an analogue to the notion of decidability for a countable structure. As examples, we prove decidability results for certain additive and multiplicative groups of $p$-adic integers, products of these (such as the profinite completion of $\mathbb Z$), and the field of real numbers. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_04152 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Computability for tree presentations of continuum-size structures Block, Jason Miller, Russell Logic 03D45 (Primary) 03D78, 03C57 (Secondary) We formalize an existing computability-theoretic method of presenting first-order structures whose domains have the cardinality of the continuum. Work using these methods until now has emphasized their topological properties. We shift the focus to first-order properties, using computable structure theory (on countable structures) as a guide. We present three basic questions to be asked when a structure is presented as the set of paths through a computable tree, as in our definition, and also propose the concept of tree-decidability as an analogue to the notion of decidability for a countable structure. As examples, we prove decidability results for certain additive and multiplicative groups of $p$-adic integers, products of these (such as the profinite completion of $\mathbb Z$), and the field of real numbers. |
| title | Computability for tree presentations of continuum-size structures |
| topic | Logic 03D45 (Primary) 03D78, 03C57 (Secondary) |
| url | https://arxiv.org/abs/2511.04152 |