4 ms·
Math proofs start given a set of axioms. The modern set of Axioms are ZFC. If you can find a new axiom A such that ZFC + A is a consistent system[1] and P=NP, a
by lalaithion 5y ago
Math proofs start given a set of axioms. The modern set of Axioms are ZFC. If you can find a new axiom A such that ZFC + A is a consistent system[1] and P=NP, and also find a new axiom B such that ZFC + B is a consistent system[1] and P!=NP, then logically, P?=NP cannot have a solution either way in just ZFC.
[1] Assuming ZFC is itself consistent
- kadoban 5y agoAre Turing machines representable in ZFC (pretty sure they are)? Seems like it'd be at least _really_ difficult to do that trick if so. That would mean that in ZFC+A there exist algorithms that can't exist in ZFC+B? Hard for me to imagine what those would even be, since they'd have to be representable in ZFC itself anyway, right, since that's all that an algorithm would be this model, a particular Turing machine?
- lalaithion 5y agoYeah, there's a reason most people don't think it's independent. Still, there are a significant number of things that are independent: https://en.wikipedia.org/wiki/List_of_statements_independent_of_ZFC https://en.wikipedia.org/wiki/List_of_statements_independent... But (I think) all of them have to do with infinity in some weird way.