Number of proofs for a statement

227 Views Asked by At

On this site, people ask questions and then answers and proofs for those answers come from readers. Readers mark the best answer and then people focus on the next interesting topic. Sometimes, a question will have many answers with proofs from different points of view and people commenting on whether the proofs are valid or not.

My question is this, "given a statement, how many valid proofs are there for that statement?" For example, if one is interested in the irrationality of root two there are many proofs available, all equally valid, some longer than others, some requiring basic math skills, others requiring in-depth knowledge. We have a proof for Fermat's last theorem, but how many other proofs are there? Is it possible to look at a statement and know that it has a finite number of proofs or an unlimited number?

2

There are 2 best solutions below

3
On BEST ANSWER

In a formal (in normal systems) sense the number of proofs are either 0 or countably infinite, and both cases are possible.

The first case is of course possible because there ought to be false statements that consequently should not be provable. But also there may exist undecidable statements (by Gödels Theorem), that is statements $p$ where there exists no proof for neither $p$ nor $\neg p$. Note that according to Gödel a system complete enough will have undecidable statements or contradictions (that means that statements known to be false will be provable).

For the case where proof exists they are countably infinite because for each formal proof you can always put in junk into the proof to generate a new proof.

The way you can prove this is that if you repeat your proof (verbatim) it's still a valid proof, and you can do that any number of times. So they are at least countably infinite.

That there are no more than countably infinite correct proofs follows of the facts that there are no more than countably infinite sequences of statements that could make up a proof (or be invalid as proof). A proof consists of a sequence of symbols from a finite alphabet and these sequences can be enumerated: for each length (being a natural number) we have finite number of sequences to add to the enumeration, so you can sequence them by starting with the empty sequence followed by the finite number of sequences of length one, and then the sequences of length two and so on (then every sequence will be included in the enumeration).

As for deciding which case that applies to a statement I'm not sure, but even for that question Gödels Theorem might apply (that would mean that there are statements for which you cannot decide whether there exists a proof for or against). In that case the only thing you could know is that if you proven it to be unprovable then you know or if you proven it to be provable then you know.

Note: some of this only applies to normal systems, one could for example construct a system where the method of constructing new proofs would result in a disallowed proof. Fx a proof is normally a sequence of statements according to some rules, but the above construction forms new by repeating the same statements over and over - in a system that disallow repeating a statement in a proof this method would only produce invalid proofs.

0
On

I know of one book that contains 256 proofs of the Pythagoran theorem.

Wikipedia claims that several hundred proofs of the law of quadratic reciprocity have been found.

I am sure that there are limits. Especially within a strictly formal logical/mathematical system. But I don't think that the answer is simple.