2 ms·
I think it helps to understand my namesake's Incompleteness Theorem[0]. They are actually connected [1,2] 1) no consistent system of axioms whose theorems ca
by godelski 1y ago
I think it helps to understand my namesake's Incompleteness Theorem[0]. They are actually connected [1,2]
1) no consistent system of axioms whose theorems can be listed by an effective procedure (i.e. an algorithm) is capable of proving all truths about the arithmetic of natural numbers.
For any such consistent formal system, there will always be statements about natural numbers that are true, but that are unprovable within the system.
2) the system cannot demonstrate its own consistency.
Any axiomatic system will have true statements that are unprovable. Which means basically any system of logic. If you've made an assumption you'll end up with this. You're always making assumptions, even if you don't realize it. It's usually a good idea to figure out what those are.
I hear a lot of people say "from first principles". If you're not starting from your axioms, you're not starting from first principles. Think Carl Sagan making a pie from scratch.
[0] https://en.wikipedia.org/wiki/G%C3%B6del%27s_incompleteness_theorems https://en.wikipedia.org/wiki/G%C3%B6del%27s_incompleteness_...
[1] https://scottaaronson.blog/?p=710 https://scottaaronson.blog/?p=710
[2] https://cstheory.stackexchange.com/questions/10635/halting-problem-uncomputable-sets-common-mathematical-proof/10636#10636 https://cstheory.stackexchange.com/questions/10635/halting-p...
- Tainnor 1y ago> Any axiomatic system will have true statements that are unprovable. Any effectively computable axiomatic system of sufficient strength. The "effectively computable" condition is probably uninteresting (if we couldn't effectively decide if something is an axiom we wouldn't be able to check proofs), but the "sufficient strength" part matters. There are interesting theories that are complete (i.e. for every sentence P, either P or not(P) is a consequence), such as the theory of the natural numbers with addition (but without multiplication).