When I was taught the incompleteness theorem (proof that there are true mathematical claims that cannot ever be proven), I wished for an example of one of its unprovable claims. Math is a very strange territory. You will often find proofs of the existence of extraordinary things, but no instance of those extraordinary things. You can know with certainty that they’re out there, but you might never get to see one. Without examples, we must always wonder if the troublesome cases can be confined to a very small region of mathematics and maybe this big impressive theorem will never really actually impinge on our lives in any way.
The problem is, an example of incompleteness would have to be a true claim that nobody could prove. If nobody could prove it, how would we recognise it as a true claim?
Well, how do we know that the sun will rise again tomorrow? We know that it rose before, many times, it’s never failed, there’s no reason to suspect it wont rise again. We don’t have a metaphysical proof that the sun will rise again tomorrow, but we don’t really need one. There is no proof, but the evidence is overwhelming.
It occurred to me that we could say a similar thing about the theorem P ≠ NP. We have tried and failed to prove or disprove it for so long that any other field would have accepted that the evidence was overwhelming and moved on long ago. A physicist would simply declare it a law of reality.
I was quite happy to find my example. It wasn’t some weird edge case. It’s a theorem that gets used every day by computer scientists to triage their energies, see, if you can prove that a problem you’re trying to solve is equivalent or stronger than a known NP problem, you would be well advised to assume it’s unsolvable, even though we wont ever be able to prove it (although, admittedly, we haven’t been able to prove that we wont ever be able to prove it, that too seems fairly evident, if not guaranteed)
When I was taught the incompleteness theorem (proof that there are true mathematical claims that cannot ever be proven), I wished for an example of one of its unprovable claims. Math is a very strange territory. You will often find proofs of the existence of extraordinary things, but no instance of those extraordinary things. You can know with certainty that they’re out there, but you might never get to see one. Without examples, we must always wonder if the troublesome cases can be confined to a very small region of mathematics and maybe this big impressive theorem will never really actually impinge on our lives in any way.
The problem is, an example of incompleteness would have to be a true claim that nobody could prove. If nobody could prove it, how would we recognise it as a true claim?
Well, how do we know that the sun will rise again tomorrow? We know that it rose before, many times, it’s never failed, there’s no reason to suspect it wont rise again. We don’t have a metaphysical proof that the sun will rise again tomorrow, but we don’t really need one. There is no proof, but the evidence is overwhelming.
It occurred to me that we could say a similar thing about the theorem P ≠ NP. We have tried and failed to prove or disprove it for so long that any other field would have accepted that the evidence was overwhelming and moved on long ago. A physicist would simply declare it a law of reality.
I was quite happy to find my example. It wasn’t some weird edge case. It’s a theorem that gets used every day by computer scientists to triage their energies, see, if you can prove that a problem you’re trying to solve is equivalent or stronger than a known NP problem, you would be well advised to assume it’s unsolvable, even though we wont ever be able to prove it (although, admittedly, we haven’t been able to prove that we wont ever be able to prove it, that too seems fairly evident, if not guaranteed)