Timeline for Is there a theory in a finite language that is computably axiomatizable but not by a finite number of axiom schemas?
Current License: CC BY-SA 4.0
14 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 20, 2020 at 15:43 | comment | added | Ali Enayat | @EmilJeřábek OK, I did that. | |
| Jun 20, 2020 at 15:06 | answer | added | Ali Enayat | timeline score: 8 | |
| Jun 20, 2020 at 7:27 | comment | added | Emil Jeřábek | @Ali I think you should post this as an answer. | |
| Jun 20, 2020 at 5:55 | history | became hot network question | |||
| Jun 20, 2020 at 0:38 | vote | accept | user107952 | ||
| Jun 20, 2020 at 0:06 | comment | added | Ali Enayat | Following up on the comment by Andreas Blass: Vaught proved that if a theory $T$ is computable and has "a modicum of coding", then $T$ is axiomatizable by a scheme. Vaught's result was improved by Visser, in the paper below, who reduced "the modicum of coding" used by Vaught to "has a definable pairing function" A. Visser, Vaught's theorem on axiomatizability by a scheme, The Bulletin of Symbolic Logic, vol. 18 (2012), pp. 382-402. | |
| Jun 19, 2020 at 23:51 | comment | added | Noah Schweber | I've edited to link the reader to the relevant definition - remember that "scheme" is not actually a technical term, as the answers to your original question stated. | |
| Jun 19, 2020 at 23:51 | history | edited | Noah Schweber | CC BY-SA 4.0 |
added 333 characters in body
|
| Jun 19, 2020 at 23:35 | answer | added | Fedor Pakhomov | timeline score: 11 | |
| Jun 19, 2020 at 22:57 | comment | added | Andreas Blass | I believe there is a theorem of Kleene about this, saying that, if the language (or perhaps the theory) is rich enough then a computable set of axioms can be replaced with a schema. But I failed to find the paper now. There is a paper by Vaught, "Axiomatizability by a schema"; maybe this is what I remembered, and I was wrong about Kleene. I'd expect that the result fails if the language is very poor. Suppose you have only a constant 0, unary function S, and unary predicate P, with axioms $P(S^n0)$ for prime $n$ and $\neg P(S^n0)$ for composite $n$. That doesn't look schematic to me. | |
| Jun 19, 2020 at 22:29 | comment | added | Gerhard Paseman | Hmm. I missed schema. Maybe the poster has a limited meaning of schema which (for my example below hopefully) excludes hyperidentities. There may be a theory which does not have a finite hyperbase. Gerhard "Look Up Padmanabhan And Penner" Paseman, 2020.06.19. | |
| Jun 19, 2020 at 22:24 | answer | added | Gerhard Paseman | timeline score: 1 | |
| Jun 19, 2020 at 22:11 | comment | added | Monroe Eskew | If it’s computable, then can’t you write it down as one “schema”? | |
| Jun 19, 2020 at 21:55 | history | asked | user107952 | CC BY-SA 4.0 |