Is there such a thing as proof by example (not counter example)

Question

Is there such a logical thing as proof by example?

I know many times when I am working with algebraic manipulations, I do quick tests to see if I remembered the formula right.

This works and is completely logical for counter examples. One specific counter example disproves the general rule. One example might be whether $(a+b)^2 = a^2+b^2$. This is quickly disproven with most choices of a counter example.

However, say I want to test something that is true like $\log_a(b) = \log_x(b)/\log_x(a)$. I can pick some points a and b and quickly prove it for one example. If I test a sufficient number of points, I can then rest assured that it does work in the general case. Not that it probably works, but that it does work assuming I pick sufficiently good points. (Although in practice, I have a vague idea of what makes a set of sufficiently good points and rely on that intuition/observation that it it should work)

Why is this thinking "it probably works" correct?

I've thought about it, and here's the best I can come up with, but I'd like to hear a better answer:

If the equation is false (the two sides aren't equal), then there is going to be constraints on what a and b can be. In this example it is one equation and two unknowns. If I can test one point, see it fits the equation, then test another point, see it fits the equation, and test one more that doesn't "lie on the path formed by the other two tested points", then I have proven it.

I remember being told in school that this is not the same as proving the general case as I've only proved it for specific examples, but thinking about it some more now, I am almost sure it is a rigorous method to prove the general case provided you pick the right points and satisfy some sort of "not on the same path" requirement for the chosen points.

edit: Thank you for the great comments and answers. I was a little hesitant on posting this because of "how stupid a question it is" and getting a bunch of advice on why this won't work instead of a good discussion. I found the polynomial answer the most helpful to my original question of whether or not this method could be rigorous, but I found the link to the small numbers intuition quiz pretty awesome as well.

edit2: Oh I also originally tagged this as linear-algebra because the degrees of freedom nature when the hypothesis is not true. But I neglected to talk about that, so I can see why that was taken out. When a hypothesis is not true (ie polynomial LHS does not equal polynomial RHS), the variables can't be anything, and there exists a counter example to show this. By choosing points that slice these possibilities in the right way, it's proof that the hypothesis is true, at least for polynomials. The points have to be chosen so that there is no possible way the polynomial can meet all of them. If it still meets these points, the only possibility is that the polynomials are the same, proving the hypothesis by example. I would imagine there is a more general version of this, but it's probably harder than writing proofs the more straightforward way in a lot of cases. Maybe "by example" is asking to be stoned and fired. I think "brute force" was closer to what I was asking, but I didn't realize it initially.

Answer 1

Yes. There are many situations where the truth of a statement is equivalent to some equation holding for all values of a polynomial, or a finite set of polynomials. If you can check the equation at enough points, it is true. Testing it a smaller number of random points is a certificate that it is probably true.

http://en.wikipedia.org/wiki/Schwartz%E2%80%93Zippel_lemma

Answer 2

In mathematics, "it probably works" is never a good reason to think something has been proven. There are certain patterns that hold for a large amount of small numbers - most of the numbers one would test - and then break after some obscenely large $M$ (see here for an example). If some equation or statement doesn't hold in general but holds for certain values, then yes, there will be constraints, but those constraints might be very hard or even impossible to quantify: say an equation holds for all composite numbers, but fails for all primes. Since we don't know a formula for the $n$th prime number, it would be very hard to test your "path" to see where this failed.

However, there is such a thing as a proof by example. We often want to show two structures, say $G$ and $H$, to be the same in some mathematical sense: for example, we might want to show $G$ and $H$ are isomorphic as groups. Then it would suffice to find an isomorphism between them! In general, if you want to show something exists, you can prove it by finding it!

But again, if you want to show something is true for all elements of a given set (say, you want to show $f(x) = g(x)$ for all $x\in\Bbb{R}$), then you have to employ a more general argument: no amount of case testing will prove your claim (unless you can actually test all the elements of the set explicitly: for example when the set is finite, or when you can apply mathematical induction).

Answer 3

It is possible in finite cases only, where by going through every possible case it is proved, an example of this is the four colour problem where it was proved by examining every possible case.

Induction could be thought of as a proof by example, but it is only implicitly, where one shows that a property or condition is satisfied intrinsically by all the elements under consideration.

The only other case is the direct existence proof, where one directly exhibits a case that some object satisfies the requirements by showing it, e.g. existence of even prime number, namely 2.

Answer 4

If you want to prove $p(x) = 0$ for all $x$, where $p$ is a polynomial of degree at most $n$, then it suffices to compute $p(t)$ (obtaining the value $0$) for $n+1$ distinct values $t$.

Answer 5

Your reasoning only applies to linear equations, which $\log_a(b)=\log_x(b)/\log_x(a)$ is not. In general, testing a finite number of points is not enough.

However, what you are doing is a common technique for remembering formulas. Say you want to memorize $\log_a(b)=\log_x(b)/\log_x(a)$, but you keep forgetting if the right-hand-side is $\log_x(b)/\log_x(a)$ or $\log_x(a)/\log_x(b)$, so you just memorize it is precisely one of them. Then, to recall the formula, you choose a set of values, say $x=a=2, b=4$, and test both possibilities. If one of them is false, you know the other case must be true.

This is useful for lots of identities. I use it to remember if the inverse matrix of $\begin{pmatrix}a&b\\c&d\end{pmatrix}$ is $\dfrac1{ad-bc}\begin{pmatrix}d&-b\\-c&a\end{pmatrix}$ or $\dfrac1{ad-bc}\begin{pmatrix}-a&c\\b&-d\end{pmatrix}$ (test with the identity matrix), if $f^{-1}(f(A))$ is $\subseteq A$ or $\supseteq A$ (test with $f(x)=0$), and many others.

Answer 6

Your proof by example may work in some rare cases, but you have to prove additional things.

For your specific example, for $log_a(b) = log_x(b)/log_x(a)$, you have to prove there are no discontinuities, which is obviously not true, since the equation is not correct for $a\leqslant 0$, $b\leqslant 0$, a=1 and $x\leqslant 0$. Assuming you meant to prove that the function is correct in the $a\subseteq [0,1)\cup (1,\infty ]$ and $b\subseteq [0,\infty ]$ regions, with x>0, then you have to prove that the function is linear (no discontinuities) and you can calculate some random value from the regions.

Answer 7

Whether a statement can be proved by example depends on the logical form of the statement.

If the statement is of the form "there exists an $X$ such that ..." then you can prove the statement by providing an example of such an $X$. For example, I can prove that the equation $2x=6$ has a solution over $\mathbb{N}$ by proving that $3$ is a solution. There are other possible proof methods for proving existential theorems, as well, such as proof by contradiction.

The claim than an equation is always correct is not an existential statement, however: it is a universal statement ("for every $z$ in the domain of the equation, the equation holds"). Statements of that form cannot, in general, be proved by presenting examples. In some special cases, though, they can.

For example, if $p(x)$ and $q(x)$ are two polynomial functions of degree $n$ over a field, to prove they are the same function it is sufficient to find $n+1$ points where they are equal. Notice that to use this method we first had to prove a general theorem that two degree $n$ polynomials that agree at $n+1$ points are equal. This is an example of the informal principle of "conservation of difficulty": if a result is made substantially easier to prove through a certain lemma, the proof of the lemma is typically of comparable difficulty to the original result.

Most mathematical theorems are neither existential nor purely universal; they are of the general form "for every $X$ with certain properties, there is a $Y$ with certain properties". For example, the fundamental theorem of algebra says that for every polynomial with complex coefficients there exists a complex number that is a root of the polynomial. Theorems of this form also cannot be proved, in general, by giving examples.

Answer 8

In geometry class, given a set of axioms, finding a model satisfying the axioms proves the consistency of the axioms.

http://en.wikipedia.org/wiki/Axiomatic_system#Models

And yeah, we also have to look for a model to prove independence of axioms. (I think that's how they figured the parallel postulate was independent from the other postulates.)

Answer 9

Proofs "by example" are common in $\mathbb{Z}_n$. For example, to show that 6 divides $n^3-n$ for all integers $n$ it's enough to verify that $n^3-n\equiv 0\pmod{6}$. Since you're working in $\mathbb{Z}_6$, there are only six possibilities for $n\pmod{6}$ so six examples suffice.

Answer 10

As a general rule, as has been pointed out by many in this question, you cannot rigorously prove a statement by "example", unless the claim says "there exists $X$ such that ...", and you give an example of such $X$.

There are many circumstances where it suffices to show the claim in some "generic" situation, which may be what you are thinking of. As has been noted, if you want to prove a polynomial $p(x)$ is identically $0$, then it will be enough to check it for $n$ points. If you are looking at a polynomial $p(x,y)$ in two variables, you can also get away with finitely many points: first, fix $y = y_0$, and check if $p(x,y_0) = 0$ identically (as a polynomial in $x$). If this fails, you have found a counterexample, and $p \neq 0$. Else, $p(x,y)$ is divisible by $y-y_0$, as polynomials. If this holds for more than $\deg_y p(x,y)$, then $p$ is identically $0$. Likewise for higher powers.

If you are trying to prove some identity like the one with logarithms, you can generally write that as $f(x,y,z,\dots) \equiv 0$ for some function $f$. If the function $f$ is decent enough, then the set of zeros of $f$ has codimension $2$ (e.g. if there is just one argument, $\{x \ : \ f(x) = 0 \}$ would consist of isolated points, if there are two arguments, $\{(x,y) \ : \ f(x,y) = 0 \}$ would consist of a curve, etc). I think that if $f$ is, say, complex analytic, then this should work (but I'm making no guarantees here). The point is, if the equation holds for a "generic" point, then it holds. More precisely, if you pick $(x,y,z,\dots)$ at random, the chance that $f(x,y,z,\dots) = 0$, but $f$ is not identically $0$, is equal precisely $0$, i.e. it "never" happens. So, if an eqality holds for a lot of randomly chosen numbers, you can be fairly sure it really holds --- even if noone will be ready to trust you on that.

A warning: If you're out of luck in the choice of the function, than the whole idea fails badly. For instance, imagine you are "proving" $x = |x|$. For $x = 1$ it works. Same for $x = 2,3,100,\pi,\sqrt{2}$... Hmmm, surely it must be true in general ;) Likewise, if you were wondering if $\sin 2 \pi x = 0$, and you had the bad luck to check only $x \in \mathbb{Z}$, you would also not get the right answer.

Even when your function is well behaved, and you use, say, a random number generator for your generic numbers, it is still possible that you get the wrong answer, so this won't be a proof of anything, as we now understand it. After all, your generator could have the bad luck to spit out $10$ multiples of $\pi$ in a row --- why not?

Answer 11

Yes. As pointed out in the comments by CEdgar:

Theorem: There exists an odd prime number. Proof: 17 is an odd prime number.

Incidently, this is also a proof by example that there are proofs by example.

Answer 12

As others have pointed out any proofs of existential claims will qualify as a proof by example.

Also, in algebra you can prove several things about an infinity of structures by example. Consider a trivial algebraic structure under a unary operation U say (0, U). You can prove that such satisfies U(x)=x by example. Since all trivial (one-element) algebraic structures come as isomorphic, the proof by example implies that all trivial algebraic structures satisfy U(x)=x. Consider a trivial algebraic structure under a binary operation B. You can prove commutativity, associativity, idempotence, the existence of an identity, and the existence of an inverse by example. Again, since all trivial algebraic structures are isomorphic, such a proof by example proves that all trivial algebraic structures satisfy those properties. Consider a trivial algebraic structure under two operations U and B, (0, U, B). We can prove by example that

U(x B y)=(U(x) B U(y))=(U(x) B y)=(x B U(y))=(x B y)=x=y. We can proceed to prove things about ternary, and n-ary operations in general if we wish to also.

Answer 13

What is the difference between "proof by examples" and "proof by exhaustion"?

Suppose the theorem can be proved by exhausting one example, then you have "proof by example".