# Statements with no counterexample

Is there some proven statement that tells us "not all X satisfy Y", but there are currently no examples of X which do not satisfy Y?

Is it necessarily true that there are always explicit counterexamples? Or are there statements that only guarantee the existence of such counterexamples, whose construction is impossible in ZFC.

-

There is a standard way to construct these things in classical logic. Your question is the same as "if we know that at least one $x$ satisfies $Z$, can we find an example of an $x$ that satisfies $Z$" and I'll work with the positive version.

First, choose some well-defined, unambiguous statement whose truth is not known at the moment. For example, P=NP or the Hodge conjecture. Now we can prove there is a natural number $x$ with the following property: "If P=NP then $x=1$ and otherwise $x=0$". But we can't give an explicit example of an $x$ with that property.

We can actually make the property even more elementary by changing it to "If ZFC proves P=NP then $x=1$ and otherwise $x=0$". That has only one quantifier, over ZFC-proofs, which can be regarded as one quantifier over natural numbers if proofs are represented by numbers. As before, "P=NP" can be replaced with any unsolved, unambiguous conjecture, e.g. the Hodge conjecture, and the final sentence is still a sentence just about natural numbers.

The point of this example is that it avoids any difficulties with uncountable sets, the axiom of choice, etc. The existence of examples like this shows that systems like PA and ZFC do not have the witness property [1]. That is, just because you can prove a formula of the form $(\exists x)\phi(x)$ does not mean that there is a specific $t$ such that you can prove $\phi(t)$. One of the benefits of constructive systems is that they do have the witness property (meaning you always can find such a $t$) and this is one reason that it's interesting to ask what sorts of mathematics can be proved in such systems.

-
Question: What if we prove P=NP or the Hodge conjecture or the open problem at hand? Then wouldn't their provability be provable in ZFC (or PA)? And if so wouldn't we be able to find a witness for the statement (either $1$ or $0$)? Or am I missing something? –  Apostolos Mar 10 '11 at 13:02
No, you're not missing anything. The question asked "but there are currently no examples", and I aimed at that here. There is a completely different answer for the question "but there could never be any explicit examples", based on the study of definability. –  Carl Mummert Mar 10 '11 at 13:13
@Carl: I see. Thanks for clarifying this for me. :) –  Apostolos Mar 10 '11 at 13:32
If you prove the existence of a specific natural number $x$, how can you say "If some condition A, then $x = 1$ otherwise $x = 0$"? That is, you say you can't give an explicit example of such an $x$ but you just argued that it's either $0$ or $1$; aren't one of these an explicit example even if we can't prove which it is? –  Michael Burge Mar 16 '11 at 21:31
@Michael Burge, that is not explicit, right? To be explicit, you have to tell me which one, otherwise giving a list of objects and saying one of these is what you are looking for is not explicit. –  Kaveh Mar 17 '11 at 12:15

The statement "not all X satisfy Y" ($\lnot \forall X\,Y(X)$) is equivalent to "there is an X such that Y is not true of X" ($\exists X\,\lnot Y(X)$), which is equivalent to "there is an X such that 'not Y' is true of X" ($\exists X\,(\lnot Y)(X)$).

That is, for any proposition $Y$, asking for an explicit counterexample for $Y$ is the same as asking for an explicit example of the negation of $Y$.

There are many existence results for which no explicit example is known. In particular, for any such result relying strongly on the Axiom of Choice, we cannot explicitly construct an example. And any such existence result can be rephrased as an example of what you are asking for simply by taking the negation of the property in question.

For example, "There exists a nonmeasurable subset of $\mathbb{R}$" can be rephrased as "Not all subsets of $\mathbb{R}$ are measurable."

-
You just beat me to it, Alex! And your first paragraph is almost identical to mine... –  Jesse Madnick Mar 10 '11 at 8:26
Note though that the construction, e.g. of a non-measurable subset of $\mathbb R$, is possible in ZFC. (There is some tension in the original question between the expression "explicit counterexample" and issue of whether a "construction is impossible in ZFC".) –  Matt E Mar 10 '11 at 9:32

Cheat: both the universal and existential quantifiers require a "universal set" of discussion, although this is often omitted.

If you choose your universal set as the empty set, I the seemingly contradictory conditions are both vacuously true.

-

As Carl and Alex have mentioned, it is possible to prove the existence of an object satisfying given properties (e.g., is a counterexample to a given statement) without explicitly constructing the required object. Going along a slightly different route, consider the logical law of Tertium Non Datur, or Law of Excluded Middle, which essentially states that given any sentence either it or its negation is true. (By a sentence I mean any statement that is unambiguous; the statement $x=2$ is not a sentence, since the meaning of $x$ is not fixed, however the statements $(\forall x) (x = 2)$ ("every $x$ is equal to $2$") and $(\exists x) ( x = 2 )$ ("there is an $x$ which is equal to $2$") are sentences.) With Tertium Non Datur one can prove that sentences $( \exists x ) \phi$ ("there is an $x$ for which $\phi$ holds") and $\neg ( (\forall x ) \neg \phi)$ ("it is not the case that every $x$ fails to satisfy $\phi$") are logically equivalent, and so instead of showing that such an object exists, you can show that the non-existence of such an object is contradictory.

Perhaps one of the earliest and most (in)famous examples of such a proof was David Hilbert's proof of a special case of (what is now called) Hilbert's Basis Theorem. At the time this method was quite controversial, and the referee his proof was sent to replied, "This is not mathematics. This is theology." (Well, he actually replied in German.)

-