Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

> It is trivial to construct a complete system that is completely (!) uninteresting.

It's also easy enough to construct complete theories that are rather interesting.

> That is the interesting thing, and proving it does not depend (AFAICT) on the details of any particular encoding of truths about numbers as long as it is well defined.

No, the encoding scheme doesn't matter, that's correct.

What does matter is that the theory doesn't need to be as powerful as a full-blown Turing machine. That's why all the machinery about Gödel's proof is necessary.

You seem to be mistaken about the fact that Gödel numbering is the complicated part about that proof, when that is in fact the easy part (and, if you really want, can be entirely replaced by some other encoding scheme), and the complicated part is about proving that a relatively weak theory like Robinson arithmetic, which doesn't even have induction axioms, can nevertheless completely express all primitive recursive functions, and that predicates such as "x is a proof of y" can be expressed as primitive recursive functions.



Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: