Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2402.08247 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914677572763648 |
|---|---|
| author | Li, Ang |
| author_facet | Li, Ang |
| contents | We define $Ψ$-autoreducible sets given an autoreduction procedure $Ψ$. Then, we show that for any $Ψ$, a measurable class of $Ψ$-autoreducible sets has measure zero. Using this, we show that classes of cototal, uniformly introenumerable, introenumerable, and hyper-cototal enumeration degrees all have measure zero. By analyzing the arithmetical complexity of the classes of cototal sets and cototal enumeration degrees, we show that weakly 2-random sets cannot be cototal and weakly 3-random sets cannot be of cototal enumeration degree. Then, we see that this result is optimal by showing that there exists a 1-random cototal set and a 2-random set of cototal enumeration degree. For uniformly introenumerable degrees and introenumerable degrees, we utilize $Ψ$-autoreducibility again to show the optimal result that no weakly 3-random sets can have introenumerable enumeration degree. We also show that no 1-random set can be introenumerable. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_08247 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Introenumerability, autoreducibility, and randomness Li, Ang Logic 03D30, 03D32 We define $Ψ$-autoreducible sets given an autoreduction procedure $Ψ$. Then, we show that for any $Ψ$, a measurable class of $Ψ$-autoreducible sets has measure zero. Using this, we show that classes of cototal, uniformly introenumerable, introenumerable, and hyper-cototal enumeration degrees all have measure zero. By analyzing the arithmetical complexity of the classes of cototal sets and cototal enumeration degrees, we show that weakly 2-random sets cannot be cototal and weakly 3-random sets cannot be of cototal enumeration degree. Then, we see that this result is optimal by showing that there exists a 1-random cototal set and a 2-random set of cototal enumeration degree. For uniformly introenumerable degrees and introenumerable degrees, we utilize $Ψ$-autoreducibility again to show the optimal result that no weakly 3-random sets can have introenumerable enumeration degree. We also show that no 1-random set can be introenumerable. |
| title | Introenumerability, autoreducibility, and randomness |
| topic | Logic 03D30, 03D32 |
| url | https://arxiv.org/abs/2402.08247 |