# 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.

-
What do you mean by can't be found? It's incomputable? There's no constructive proof of the existence of a counterexample? –  Loki Clock Apr 15 '14 at 21:05
maybe Riemann Hypothesis is false but no one could find a counter-example until now. In fact, if a problem is undecidable, this would be the case, you could try to find a counter-example until the end of time –  Integral Apr 15 '14 at 21:06
–  leonbloy Apr 15 '14 at 21:10
What evidence is there that the counterexample exists if it cannot be found, and how is that evidence convincing if it does not amount to producing the counterexample? –  Kaz Apr 15 '14 at 22:36
@alfC: The theory has to be first-order, recursively enumerable, and interpret basic truths of arithmetic. Geometry, if I recall, is not first-order; algebraically closed fields can't interpret arithmetic. –  Asaf Karagila Apr 17 '14 at 7:27

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.

-
I disagree that this can be concluded from that statement. What if for every program that never terminates there's a proof of this fact, but no unified way of producing a proof, or no single program which can verify that it terminates? –  Loki Clock Apr 15 '14 at 21:13
@LokiClock I have avoided technical details here, but there always is such a way. Simply enumerate all proofs and check whether they are correct proofs of termination. The standard argument in computability theory is on step $2k$ run the $k$th step of the test program, and on step $2k+1$ check the $k$th proof to see if it is correct (proof checking is known to be computable). –  Alex Becker Apr 15 '14 at 21:18
I'm pretty sure Alex Becker is completely correct here. In general, the undecidability of a certain decision problem guarantees that there exists a specific instance of the problem for which no proof of the correct decision exists in ZFC. This is because there exists a "universal prover" computer program that enumerates all possible consequences of the axioms of ZFC, thereby proving all provable statements. If all instances of a decision problem were provably solvable, then the universal prover would be an algorithm to decide it. –  Jim Belk Apr 16 '14 at 3:52
In particular, since the halting problem is undecidable, it follows that there exists a computer program which never halts, but whose non-halting cannot be proven by the axioms of ZFC. (A computer program that halts can always be proven to do so by the axioms of ZFC -- the proof just consists of the sequence of internal states of the program from when it starts to when it halts.) –  Jim Belk Apr 16 '14 at 3:54
I disagree with this answer for a reason which is (I think) different from previous comments. For the statement to be precise, we must fix a notion of "proof". Say "proof" means "proof in $\mathsf{ZFC}$". But then a counterexample can be found: The program searching for a proof of $\bot$ in $\mathsf{ZFC}$ never halts, but there is no proof (in $\mathsf{ZFC}$) of this fact. Anyone who believes $\mathsf{ZFC}$ to be consistent must believe that this is a counterexample. (Of course, there is no proof in $\mathsf{ZFC}$ that it is a counterexample, but this seems to me to be beside the point.) –  Trevor Wilson Apr 17 '14 at 0:40

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.

-
Actually, there are models of $\mathsf{ZFC}$ in which every real number (and indeed every set) is definable. (It is tempting to say that the statement "every real number is definable" is consistent with $\mathsf{ZFC}$, but this statement cannot be formalized: definability may fail to be definable.) The mistake is the assumption that there is a (partial) function mapping (putative) definitions to the numbers that they define. Although it is tempting to believe that there is an obvious such function (because it seems like we can define it) this is not necessarily the case. –  Trevor Wilson Apr 17 '14 at 0:48
See Joel Hamkins' slides for more information on this subtle point: jdh.hamkins.org/files/2011/09/… for –  Trevor Wilson Apr 17 '14 at 0:50
@TrevorWilson, surely we should be considering models of second-order set theory, i.e. $\mathrm{ZFC2}$ for this question. Otherwise, the model's real line needn't be the true real line relative to the ambient universe. –  goblin Apr 17 '14 at 2:16
Great answer! "There exists a real number whose description cannot ever be uttered." IMHO these numbers should be called Valdemort numbers. –  Michael Apr 17 '14 at 2:19
Ah, here is Joel's MO post: mathoverflow.net/a/44129/1682 (thanks, Asaf.) –  Trevor Wilson Apr 17 '14 at 2:52

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?

-
I don't get this answer: if you assume the axiom of choice then a non-measurable subset of $\mathbb R$ exists and can be found; if you don't then a non-measurable subset doesn't exist –  dani_s Apr 15 '14 at 21:19
The axiom of choice guarantees the existence of this subset, but its not necessarily constructive, so does not follow from this that this subset can be found. –  Integral Apr 15 '14 at 21:32
@Integral Depends on what you mean by "found". –  Alex Becker Apr 15 '14 at 21:51
My objection is that mathematically the axiom of choice isn't more "special" than other set theory axioms. You could have just said something like "There exists an infinite set but it requires axiom of infinity so it can't be found" –  dani_s Apr 15 '14 at 22:06
In any case, the "construction" of the Vitali sets doesn't actually allow you to uniquely specify one single Vitali set in such a way that you could determine, for every real number in the unit interval, whether or not that number is in the set. Thus you aren't really "constructing" anything, and in fact you haven't even uniquely defined a particular subset of the reals. –  Kyle Strand Apr 15 '14 at 23:07

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.

-
-1 Although I agree that the question is ambiguous, the largest known prime is bigger than the proposed upper bound of $2^{10000}$. –  Andrew Kelley Apr 16 '14 at 15:59
@Andrew: Fine. $2^{2^{100000000000}}$ it is, then. As long as you focus on the main idea of the answer, and not a petty detail, it's fine. –  Asaf Karagila Apr 16 '14 at 16:00
Yeah, I agree; sorry about that. Since it was minor, I should have just offered an edit with my comment as an explanation. Your main point is explained well. +1 –  Andrew Kelley Apr 16 '14 at 17:40
Well, no harm done. Thanks for the suggestion. –  Asaf Karagila Apr 16 '14 at 18:18
As long as I'm nit-picking at the other answers in this thread, I'll state an objection to your argument regarding composite numbers. It seems to me that you might as well say that the statement "every number larger than $2^{2^{100000000000}}$ is odd" is false but we cannot find a counterexample. But of course we can find a counterexample: $2^{2^{100000000000}}+2$. The point is that we can express the counterexample in a compact notation. But this may be true for the "composite" version as well... –  Trevor Wilson Apr 17 '14 at 1:07

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.

-
Given the tags, I think the OP wants situations in which a counter-example provably cannot be found. Is that the case here? –  Jack M Apr 16 '14 at 5:34
In OP, it is stated that "we cannot find even if we have super computers" which I interpreted as computational barrier to find it. A random code has infinite length and so the exhaustive search needs infinite computational power. –  Arash Apr 16 '14 at 8:32
Regarding the statement "provably cannot be found", I had the same feeling as Asaf Karagila (another answer in this page). So to be really precise OP should clarify issues stated in his answer. –  Arash Apr 16 '14 at 8:35

There are two opposite answers, both correct on their own terms.

One is that in most situations that have distinct concepts of "finding an example" and "existence of an example", for which finding an example always implies an example exists (but no assumption is made about the reverse implication being valid or not in general), concrete instances can be shown where something "exists" but cannot be "found". For example:

• seeing a dead body in some unusual place and circumstance, it might be easy to demonstrate with at least 99.9% certainty that there exists a murderer of that person, but finding the murderer with 99.9% certainty of the identification is far more difficult both logically and practically.

• a prime factorization of a large number "exists", in the sense that theories of arithmetic have that statement and its generalizations as provable theorems, but one might not be able to "find" the prime factorization if that means writing it down, or computing it efficiently, from the description of the number. Tables of factorizations of special large numbers (such as Mersenne numbers, repunits, Fibonaccis, etc) include entries like C307 to mean a 307-digit factor that is known to be composite number but without a known factorization.

• there "exists" a first-player win in finite two-player games such as $30 \times 30$ Tic Tac Toe or Chomp that are amenable to strategy-stealing arguments, but the resources to "find" and describe the winning strategy are vast compared to the resources needed to find the existence proof, and the strategy is not known.

• there "exists" an optimal strategy for chess, or any finite two-player game with rules that forbid unlimited repetition of positions, but to "find" the strategy requires impossibly large resources compared to what is needed to show "existence".

• the "exists" a shortest length of LISP computer code that will print out the Baghavadad Gita, but if that length is more than $1000$, no proof system that currently exists, such as formalized Zermelo-Fraenkel set theory, could "find" that program. Doing so would require writing down a program code, proving that it works by running it until termination, and a proof that the program is minimal-length, but no such proof exists in the proof system.

The other point of view, which is approximately the "intuitionist" or "constructivist" position, is that:

• the idea of existence proofs without any power to construct examples, is meaningless, and

• any healthy notion of proof will either define existence proof to mean finding an example, or have the property that an abstract existence proof can always be materialized into a proof that a specific example exists (e.g., Numerical Existence Property in intuitionistic proof systems).

In the finite examples, the supposed separation appears when there is an ability to efficiently describe and operate upon elements of a data structure (such as the positions and moves in the game tree of chess), and then extrapolating from that to an imaginary superpower to exhaustively search through the whole structure, and larger structures constructed from it (such as the space of strategies for black and for white). The problem in the infinite case is similar, where it is assumed that one can casually perform an infinite search to decide questions such as whether there "exists" a largest Fermat prime. If you reject the extrapolated abilities as no more than a pleasant fairy tale, it makes sense to reject the distinction between existence and the ability to find witnesses.

-

The busy beaver function has many opportunities for this sort of thing. 'In an axiomatic system of ordinary mathematics, there is a true-but-unprovable sentence of the form "Σ(10↑↑10) = n", and there are infinitely many true-but-unprovable sentences of the form "Σ(10↑↑10) < n".'

So, for the description "a counter-example exists but it cannot be found", the equality with $n$ in the quotation is such a counterexample. And it "cannot be found" in the strong sense that has been discussed in the other answers -- the counterexample exists (it's just some number) but even if you had some finite, "useful" (This word in this context baffles me.) representation of that number, you would not be able to prove the equality. This $n$ would be the greatest counterexample to the inequality with $n$ above.

-
I can prove that $\Sigma(10\uparrow\uparrow10)=\Sigma(10\uparrow\uparrow10)$. –  Mario Carneiro Apr 22 '14 at 19:04
@MarioCarneiro: Logically, yes; arithmetically, I'm not entirely convinced. ($\Sigma$ is not a computable function. en.wikipedia.org/wiki/Busy_beaver#Non-computability_of_.CE.A3 ) Additionally, neither the LHS nor the RHS is a "useful" representation of that number. (I still don't know what that word would mean here.) –  Eric Towers Apr 22 '14 at 20:28
I'm not sure what the distinction between "logical" and "arithmetical" proofs is, but I think that what it means for a sentence to be "of the form $\Sigma(10 \uparrow \uparrow 10) = n$" is that the sentence is "$\Sigma(10 \uparrow \uparrow 10) = \underbrace{1+\ldots + 1}_n$" for some $n \in \mathbb{N}$. That is, the sentence doesn't contain the symbol $n$ at all, but contains $n$ many 1's. So then I suppose Mario's comment wouldn't qualify as "finding a counterexample" because the sentence it proves doesn't have a numeral ($\underbrace{1+\ldots + 1}_n$) on the right hand side. –  Trevor Wilson Apr 22 '14 at 22:24
@TrevorWilson: It's logically true because the same string of symbols occurs on both sides of an equivalence relation. This variety of "true" has nothing to do with the interpretation of the symbols. Example: "tree bark = tree bark" is logically true with the usual logical interpretation of the symbol "=". However, there is no way to validate that a claimed value of $\Sigma$ (with argument $\geq 4$) is actually correct -- the function is uncomputable. So it's not even recursive, so even if you had a valid value, how would you compare that value with anything else? –  Eric Towers Apr 22 '14 at 22:39
I know why $\Sigma(10 \uparrow \uparrow 10) = \Sigma(10 \uparrow \uparrow 10)$ is true; my first point was (or should have been) that I don't see any sense in which it is not true. My second point is that the first point is irrelevant: the result mentioned in your second link is (I hope) using a specific meaning of "of the form", which I think is the one that I mention, and Mario's statement is not of this form. –  Trevor Wilson Apr 22 '14 at 23:05

Here is a very simple wrong hypothesis for which providing a counter-example is impossible:

Every natural number has been said (written, provided, imagined) by someone.

You can't show me a counter-example, but you can prove that there are a bit more numbers than we have ever imagined.

-
This seems more of a semantic-philosophical example, rather than a mathematical example. –  Asaf Karagila Apr 18 '14 at 10:02
You can mathematically calculate upper limit for amount of possible imagined numbers, for example by using Planck time and size or something like that. Whatever you do, it's quite finite. –  Juris Apr 18 '14 at 10:06
And then you can imagine a number just slightly larger. –  Asaf Karagila Apr 18 '14 at 10:10
@Asaf Karagila, Juris mentioned "limit for amount of possible imagined integers", not a number itself. –  VividD Apr 19 '14 at 8:47
How can you prove an upper limit on the number of numbers that have been imagined by people? Do you have a mathematical definition of what it means for a number to be imagined by a person? –  Trevor Wilson Apr 22 '14 at 22:32