4 ms·
But let's note that "undecidable" has a specific meaning here, that batches of logic axioms can't prove their own consistency. There's still a possibility of u
by Dylan16807 3y ago
But let's note that "undecidable" has a specific meaning here, that batches of logic axioms can't prove their own consistency. There's still a possibility of using more powerful logic to prove that one of those will never cause a contradiction.
In particular, ZF can't prove itself, but it can prove that Peano is consistent.
These are very interesting machines, but mostly for reasons that go beyond the normal meaning of the word "undecidable". We have lots of unsolved math problems that can be encoded into vastly shorter turing machines.
- winwang 3y agoThat's an interesting elaboration. It's also true that we can go beyond undecidability with an oracle, but that introduces a new "undecidable" barrier. Is there a relation between the tower of more powerful logics and the tower of more powerful oracles?
- pas 3y agoAFAIK yes. see the Large Cardinal Axioms (and combinatorial statements!) """ The proposition that such cardinals exist cannot be proved in the most common axiomatization of set theory, namely ZFC, and such propositions can be viewed as ways of measuring how "much", beyond ZFC, one needs to assume to be able to prove certain desired results. In other words, they can be seen, in Dana Scott's phrase, as quantifying the fact "that if you want more you have to assume more" """ https://en.wikipedia.org/wiki/Large_cardinal https://en.wikipedia.org/wiki/Large_cardinal And https://en.wikipedia.org/wiki/Gentzen%27s_consistency_proof https://en.wikipedia.org/wiki/Gentzen%27s_consistency_proof for a similar theme with Peano arithmetic and the epsilon_nought ordinal.
- srcreigh 3y ago> But let's note that "undecidable" has a specific meaning here, that batches of logic axioms can't prove their own consistency It's not actually that specific. There are many statements that we know are unprovable in ZF. ZFs own consistency is just one of them. The original work to find the 8000 state TM independent of ZF encodes an entirely different statement about graphs. We are talking about finding TMs which encode a statement which is unprovable in say ZF. Specifically, the TM loops forever iff the statement (which is unprovable in ZF) is true. Not necessarily looking for inconsistencies Godel-style
- anonymouskimmer 3y ago> In particular, ZF can't prove itself, but it can prove that Peano is consistent. Consistent within Peano, or consistent within ZF? That is to say, could another large system of axioms exist which fully contains the Peano axioms, but in which the Peano axioms are inconsistent (in a non-trivial manner)? I really don't know much about formal logical consistency, but am mildly curious as I see these sorts of claims mentioned.
- Kranar 3y agoThe technical answer to your question is yes, another axiomatic system can exist that is able to prove that Peano is inconsistent. However, assuming that ZF is consistent, then that other axiomatic system would have to be inconsistent.
- Dylan16807 3y agoConsistent means that it doesn't contradict itself. Peano is consistent within Peano. The system that checks if Peano is consistent doesn't have to be similar at all or share any axioms.