On the computability of cofinal Fraïssé limits
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912861794598912 |
|---|---|
| author | Ackerman, Nathanael Freer, Cameron Mirabi, Mostafa |
| author_facet | Ackerman, Nathanael Freer, Cameron Mirabi, Mostafa |
| contents | For any collection of finite structures closed under isomorphism (i.e., an age) which has the Hereditary Property (HP), the Joint Embedding Property (JEP), and the Cofinal Amalgamation Property (CAP), there is a unique (up to isomorphism) countable structure which is cofinally ultrahomogeneous with the given age. Such a structure is called the cofinal Fraïssé limit of the age.
In this paper, we consider the computational strength needed to construct the cofinal Fraïssé limit of a computable age. We show that this construction can always be done using the oracle 0''', and that there are ages that require 0''.
In contrast, we show that if one assumes the strengthening of (CAP) known as the Amalgamation Property (AP), then the resulting limit, called the Fraïssé limit, can be constructed from the age using 0'. Our results therefore show that the more general case of cofinal Fraïssé limits requires greater computational strength than Fraïssé limits. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_22435 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | On the computability of cofinal Fraïssé limits Ackerman, Nathanael Freer, Cameron Mirabi, Mostafa Logic Logic in Computer Science 03C57, 03D45 For any collection of finite structures closed under isomorphism (i.e., an age) which has the Hereditary Property (HP), the Joint Embedding Property (JEP), and the Cofinal Amalgamation Property (CAP), there is a unique (up to isomorphism) countable structure which is cofinally ultrahomogeneous with the given age. Such a structure is called the cofinal Fraïssé limit of the age. In this paper, we consider the computational strength needed to construct the cofinal Fraïssé limit of a computable age. We show that this construction can always be done using the oracle 0''', and that there are ages that require 0''. In contrast, we show that if one assumes the strengthening of (CAP) known as the Amalgamation Property (AP), then the resulting limit, called the Fraïssé limit, can be constructed from the age using 0'. Our results therefore show that the more general case of cofinal Fraïssé limits requires greater computational strength than Fraïssé limits. |
| title | On the computability of cofinal Fraïssé limits |
| topic | Logic Logic in Computer Science 03C57, 03D45 |
| url | https://arxiv.org/abs/2601.22435 |