Timeline for Gödel's Incompleteness Theorem and the complexity of arithmetic
Current License: CC BY-SA 2.5
11 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 17 at 9:55 | vote | accept | Hans-Peter Stricker | ||
| Nov 15 at 20:28 | comment | added | user76284 | Interestingly, empty set + adjunction suffices to interpret Robinson arithmetic, which is essentially undecidable. | |
| Mar 2, 2012 at 7:07 | answer | added | none | timeline score: 4 | |
| Sep 4, 2010 at 11:25 | comment | added | Carl Mummert | There are several meanings of complexity here. One is computational complexity, e.g. polynomial-time computation. Another is the sort of complexity measured by the arithmetical hierarchy. A third is the internal combinatorial structure of a particular model. In this informal third sense, dense linear orders have little complexity, while nonstandard models of PA have great complexity. In the quote above, I think the third sense is being alluded to. However, Väänänen does mention computational complexity in the context of finite models later in his paper. | |
| Sep 4, 2010 at 3:25 | comment | added | John Goodrick | I presume Väänänen meant computational complexity, that is, computability? In fact, it's hard for me to imagine an interesting formulation of Godel's incompleteness that doesn't involve computability: you could just say that PA is incomplete, but that seems too localized to be interesting; or there's the cocktail-party version that "arithmetic can't be axiomatized" which, taken literally, is false (just take the set of all sentences true in the structure (N, +, times)). | |
| Sep 3, 2010 at 12:59 | comment | added | Hans-Peter Stricker | What kind of complexity does Väänänen mean, one might ask? (Might it be case that he has in mind a more abstract concept of complexity?) | |
| Sep 3, 2010 at 12:47 | comment | added | Iddo Tzameret | Your main question "Can Godel ....in terms of complexity" is somewhat ambiguous: because the term complexity might be construed here either as logical (or quantifier) complexity, or as computational complexity. In the former case, as J.D. Hamkins showed, the answer to your question is "yes". In the latter case, I would presume the answer might be "no". (On the other hand, Godel's incompleteness phenomenon does hold for weak theories (bounded arithmetic), which have formal relations with computational complexity classes.) | |
| Sep 3, 2010 at 10:46 | answer | added | Stefan Geschke | timeline score: 7 | |
| Sep 3, 2010 at 10:26 | answer | added | Joel David Hamkins | timeline score: 30 | |
| Sep 3, 2010 at 10:19 | history | edited | Hans-Peter Stricker | CC BY-SA 2.5 |
edited title
|
| Sep 3, 2010 at 10:08 | history | asked | Hans-Peter Stricker | CC BY-SA 2.5 |