Timeline for Recursive axiomatizability over non-recursive base theory
Current License: CC BY-SA 4.0
9 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 19, 2022 at 17:13 | comment | added | Oliver Korten | @NoahSchweber on second though I’m not sure your claim holds in general. If we have an enumeration reduction E we can use it to generate a recursive list of $(\alpha_1, \ldots, \alpha_n, \beta)$ where the $\alpha_i,\beta$ are formula, such that whenever all $\alpha_i$ lie in $A$, $\beta$ must lie in $B$ (I think this is what you mean). However this in no way implies that $\bigwedge \alpha_i \vdash \beta$ (I’m using $\vdash$ in the semantic/model theoretic sense) since this implication could be based on some reasoning “beyond” basic FOL deductions. | |
| Dec 19, 2022 at 15:50 | comment | added | Oliver Korten | Just as sets of sentences. | |
| Dec 19, 2022 at 12:26 | comment | added | Joel David Hamkins | Could you clarify whether you are treating theories as sets of sentences, or do they have to be deductively closed? This can affect the Turing degree. | |
| Dec 19, 2022 at 7:02 | history | edited | YCor | CC BY-SA 4.0 |
fixed spelling
|
| Dec 19, 2022 at 4:25 | comment | added | Oliver Korten | Thank you! I was not aware of this notion of “enumeration reduction” and the work i’m seeing on it seems to be highly relevant to the question I’m thinking about. | |
| Dec 19, 2022 at 4:04 | comment | added | Noah Schweber | Note that if $B$ is enumeration reducible to $A$, then $B$ is recursively axiomatizable over $A$: the enumeration reduction itself is basically such an axiomatization (think of clauses of the form "$(\bigwedge_{1\le i\le n}\alpha_i)\rightarrow\beta$"). So in examples of this phenomenon - which do exist, if memory serves - rely crucially on the ability of a Turing reduction to use positive and negative facts about the oracle. | |
| Dec 19, 2022 at 4:00 | history | edited | Oliver Korten | CC BY-SA 4.0 |
added 4 characters in body
|
| S Dec 19, 2022 at 4:00 | review | First questions | |||
| Dec 19, 2022 at 8:28 | |||||
| S Dec 19, 2022 at 4:00 | history | asked | Oliver Korten | CC BY-SA 4.0 |