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.

Solution 1:

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.

Solution 2:

I actually like this one:

There are uncountably many real numbers. However, given that all specifications of specific real numbers (be it by digits, by an algorithm, or even a description of the number in plain English) is ultimately given by a finite string of finitely many symbols, there are only countably many descriptions of real numbers.

A straightforward formalization (but not the only possible, nor the most general one) of that idea is to model the descriptions as natural numbers (think e.g. of storing the description in a file, and then interpreting the file as natural number), and then having a function from the natural numbers (that is, the descriptions) to subsets of the real numbers (namely the set of real numbers which fit the description). A description which uniquely describes a real number would, in this model, be a natural number which maps to a one-element subset of the real numbers; the single element of that subset is. Since there are only countably many natural numbers (by definition), they can only map to at most countably many one-element subsets, whose union therefore only contains countably many real numbers. Since there are uncountably many real numbers, there must be uncountably many numbers not in this set.

Therefore in this formalization, for any given mapping, almost every real number cannot be individually specified by any description. Therefore there exist uncountably many counterexamples to the claim "you can uniquely specify any real number".

Of course I cannot give a counterexample, because to give a counterexample, I'd have to specify an individual real number violating the claim, but if I could specify it, it would not violate the claim and therefore not be a counterexample.

Note that in the first version, I omitted that possible formalization. As I learned from the comments and especially this MathOverflow post linked from them, in the original generality the argument is wrong.

Solution 3:

Yes. For instance,

There exists a non-measurable subset of $\mathbb{R}$ (with respect to Lebesgue measure).

It requires the axiom of choice; so we could claim that it can't really be found. Any non-constructive proof would be another possible answer. See Wikipedia on constructive proofs.

Note the interesting, related question on MO: Are there non-constructive existence proofs without the axiom of choice?

Solution 4:

The question has a bit of ambiguity in it.

What does it mean that a counterexample cannot be found? What does it mean to find something in mathematics?

We might want to talk about purely physical computation (by which I mean using our current technology and reasonably conservative projections thereof; not some hypothetical future in which we have new theorems, algorithms and hardware capable of factoring prime numbers larger than the volume of the observable universe instantly). In this case the word "find" means also verify without any doubt, as well.

In this case we can easily make claims like "Every prime number larger than $2^{2^{100000000000}}$ is of the form $2^n-1$". Of course we can prove that there exists a prime number larger than $2^{2^{100000000000}}$ which is not a Mersenne prime, but computationally speaking verifying that a number which is not a Mersenne prime is prime, is an immensely difficult task.

If the above feels a bit wide, you can also plug in all the other "relatively easily verifiable prime" into the list above. The point in the above example is that there is no efficient way of verifying whether or not a certain number is prime or not; and so to verify whether or not an arbitrary number larger than $2^{2^{100000000000}}$ is a prime number, we are expected to run a very lengthy computation. We can replace "prime number" by "solution to sufficiently complicated problem" just as well.

In contrast, we can easily verify if a given number is even or not. We just need to check one bit of its binary representation (or one digit of a decimal, or hexadecimal representation), or any other "sufficiently simple problem".

If we talk about theoretically computation, it depends on what do you mean prove that a counterexample exists. In particular what do you mean by "prove"? More specifically, prove from what theory?

From $\sf PA$, the axioms of Peano arithmetic, we can develop a nice theory of computation and computability, and we can prove that many natural problems that can be solved, but not in a computable way. For example the ability to decide whether or not a sentence is true or false in the natural numbers.

In this context the term "supercomputer" can be interpreted, perhaps, as an oracle, or more specifically some "additional" function[s] that work in a way we don't necessarily know, and this helps us to solve problems that we couldn't solve before. But even then, we can prove there are always statements that are not computable (now in this stronger sense), but are provably false, so we can't "find" a counterexample.

We can extend this to mathematical questions that we can prove existence of certain objects, without our ability to give an explicit construction (read: definition) of an example. For this we usually move one up a notch and use set theory as our theory for the term "prove". Many objects, in particular infinite (and often uncountable) objects are researched in modern mathematics, and we can prove many things about these sets using an axiom known as the Axiom of Choice. This axiom is non-constructive in its nature, as it asserts the existence of certain objects, but doesn't provide us with a way to define them explicitly.

In this context we have so many examples. For example, the existence of non-measurable sets; a linear order of all the sets of sets of natural numbers; a free ultrafilter on the natural numbers.

To sign off this answer, let me point again, that this depends on what you mean "cannot be found" and what it means "prove to exist". In different contexts the answers will differ. And things which may be considered "definable" or considered "found" in one context might not be considered as such in another.

Solution 5:

This answers your question, maybe in an indirect way. There are a lot of probabilistic proofs in which one proves only the existence of something without the possibility of finding it.

For example, in information theory, the random coding argument is used to show that there is a code which is capacity achieving however we really cannot find any specific code using the argument. Capacity achieving codes were discovered only recently.