Is it possible that “A counter-example exists but it cannot be found”

Then otherwise the sentence “It is not possible for someone to find a counter-example” would be a proof.

I mean, are there some hypotheses that are false but the counter-example is somewhere we cannot find even if we have super computers.

Sorry, if this is a silly question.

Thanks a lot.

Answer

A standard example of this is the halting problem, which states essentially:

There is no program which can always determine whether another program will eventually terminate.

Thus there must be some program which does not terminate, but no proof that it does not terminate exists. Otherwise for any program, we could run the program and at the same time search for a proof that it does not terminate, and either the program would eventually terminate or we would find such a proof.

To match the phrasing of your question, this means that the statement:

If a program does not terminate, there is some proof of this fact.

is false, but no counterexample can be found.

Attribution
Source : Link , Question Author : ThePortakal , Answer Author : Alex Becker

Leave a Comment