3 ms·
The consistency of ZFC cannot be proven in ZFC - this follows from the second incompleteness theorem. The consistency of ZFC is a very useful theorem. There ar
by sn41 6y ago
The consistency of ZFC cannot be proven in ZFC - this follows from the second incompleteness theorem. The consistency of ZFC is a very useful theorem.
There are also very easy to understand number-theoretic and combinatorial results, like the Paris-Harrington Theorem [1] and Goodstein's Theorem [2] which are provably independent of Peano Arithmetic.
The latter has an interpretation as a "hydra" game: there is a rooted tree (hydra), and you can cut off a number of heads in one shot. The hydra grows back a finite number of heads according to a specified rule. The question is, is there a strategy to slay the hydra?
The surprising answer is that any strategy will work(!), but you cannot prove this fact inside Peano arithmetic.
[1] https://en.wikipedia.org/wiki/Paris%E2%80%93Harrington_theorem https://en.wikipedia.org/wiki/Paris%E2%80%93Harrington_theor...
[2] https://en.wikipedia.org/wiki/Goodstein%27s_theorem https://en.wikipedia.org/wiki/Goodstein%27s_theorem
- dwohnitmok 6y ago> The consistency of ZFC cannot be proven in ZFC - this follows from the second incompleteness theorem. The consistency of ZFC is a very useful theorem. Perhaps less useful than one might think. Given that an inconsistent system can prove anything, if you weren't convinced of ZFC's consistency to begin with I hardly think you'd be convinced by a proof of its consistency in itself. Godel's Second Incompleteness Theorem is important "in the other direction," that is its consequence for systems bigger than ZFC (or indeed PA)/larger statements that imply the consistency of your formal system in question. (A previous comment I made on this in greater detail https://news.ycombinator.com/item?id=25118038 https://news.ycombinator.com/item?id=25118038)
- oh_sigh 6y agoThe answer is surprising only if you believe the specified rule can be any rule. But really, the specified rule may have enough complexity in it that makes it difficult to intuitively reason about the problem at all, at which point it isn't really a counter-intuitive result, merely a counter-intuitive rule.