Timeline for Has decidability got something to do with primes?
Current License: CC BY-SA 2.5
3 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 15, 2020 at 15:03 | comment | added | user21820 | I know this is an old post, but I just want to say that the incompleteness theorem itself has completely no deep connection to number theory, because even the weak theory TC (theory of concatenation) which only has basic axioms about finite binary strings is essentially incomplete. So the crux of incompleteness is actually in the fancy part. However! The crux of Godel's incompleteness theorem (which is about arithmetical theories) is, in my opinion, in the coding lemma! That is, it is much harder to figure out how to code sequences than to figure out the fixed-point lemma. | |
| Mar 31, 2010 at 8:18 | comment | added | Charles Stewart | +1 Very good point. It's worth pointing out that Willard's system does express multiplication in terms of division, as a relation, but it fails to prove the multiplication relation expresses a total function, although all and only the expected constant instances are true. Since Willard's system thereby has the same prime numbers as usual arithmetic, and has their primality as theorems, we have the converse to Joel's point: presence of (a weak theory of) primes together with completeness. | |
| Mar 31, 2010 at 7:59 | history | answered | Neel Krishnaswami | CC BY-SA 2.5 |