Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

Thanks all!

share|improve this question
1  
If you want to prove a general case, then you have to prove every point. This basically just means that you have to show it's true for any given $a$ and $b$, not just whichever ones you might choose (where $a$ and $b$ are defined) –  mardat Mar 21 '13 at 7:22
5  
Small numbers of data points can be deceptive. Here's a good read on the subject: math.sjsu.edu/~hsu/courses/126/Law-of-Small-Numbers.pdf –  Plutor Mar 21 '13 at 13:55
5  
I'd like to prove that all the prime numbers are odd. 5 is odd, 41 is odd, 2203 is odd, 3347 is odd... hey, it looks like they're all odd. –  Eric Lippert Mar 21 '13 at 15:34
5  
Sounds like TDD to me. Use a bunch of tests to show that most reasonable use cases seem to work. What TDD doesn't do is provide any formal proof or guarantee that things won't break. –  zzzzBov Mar 21 '13 at 18:03
1  
TDD is a nice analogy. Thanks –  SwimBikeRun Mar 21 '13 at 19:06

13 Answers 13

up vote 17 down vote accepted

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

share|improve this answer
    
Hey this is what I was looking for. I knew it was popular enough to have a name. Although I must say some of these other posts are quite interesting even such as the small numbers pdf link –  SwimBikeRun Mar 21 '13 at 16:20
    
The current version of your link says the Schwartz_Zippel lemma "bounds the probability" of something. It's useful, though not a complete proof. –  MarkDBlackwell Mar 23 '13 at 18:28
    
There is a trivial version of the Schwartz-Zippel argument that gives absolute certainty by testing the polynomial at all integer points in a large box. The proof is immediate and the method takes exponential time, so it is much less interesting than randomized methods where the test can be efficient. @MarkDBlackwell –  zyx Mar 23 '13 at 23:38

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

share|improve this answer
5  
+1 for the awesome reference. Always looking for large counterexamples to show my students, precisely because of this. –  Fixed Point Mar 21 '13 at 8:07
7  
@FixedPoint: Then you may be interested in these two questions here: math.stackexchange.com/questions/111440/… and math.stackexchange.com/questions/514/… –  ShreevatsaR Mar 21 '13 at 10:35
    
Great reference! –  Feanor Mar 21 '13 at 14:58
    
Awesome thank you very much. For some fields, I can see how "seems to be" and proof are two different things as your awesome link so clearly points out. The Schwartz Zippel lemma was exactly what I was looking for. –  SwimBikeRun Mar 21 '13 at 19:42
    
The statement "seems to be" and a proof are different things in every field, but in some cases, you might only want to be "pretty sure," and in those cases, you can use probability and a sufficient amount of random testing to be as sure as you want. Be careful though: not everything can be changed into a polynomial equation. Also, in the polynomial case, it's not a matter of being pretty sure or choosing "good" points, it's still a matter of testing enough points: polynomials just have nice properties, as they are restricted by their degrees. Glad to help! –  Stahl Mar 21 '13 at 20:51

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.

share|improve this answer
7  
Theorem. There exists an odd prime number. Proof. $17$ is an odd prime number. –  GEdgar Mar 21 '13 at 13:51
1  
@GEdgar Theorem. All prime numbers are even. Proof. 2 is even and a prime number. –  Tobias Kienzler Mar 21 '13 at 15:18
6  
This is why Carl specified the form of the statement: "there exists an $X$ such that..." –  GEdgar Mar 21 '13 at 17:12

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.

share|improve this answer
18  
Nice meta-remark... –  Georges Elencwajg Mar 21 '13 at 19:04
8  
Nice meta-meta-remark... –  Robert Israel Mar 21 '13 at 19:07
8  
Obligatory xkcd. –  Marcks Thomas Mar 21 '13 at 22:45

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

share|improve this answer
    
Right. Note however that you will only succeed if $p=0$ identically. So $p$ had rather be some complicated expression that you know is a polynomial of degree at most $n$, but whose coefficients you cannot explicitly determine easily. By the way, is there anything useful along these lines for multivariate polynomials? –  Marc van Leeuwen Mar 21 '13 at 8:55
    
@MarcvanLeeuwen A v-variate polynomial is a 1-variate polynomial over an (v-1) variate polynomial ring. If it is n-ary, then testing n+1 distinct values of the vth variate to see if the resulting (v-1) variate polynomials are identically zero should be sufficient. You can either apply this recursively, or explode the cross product of samples and apply all at once methinks. I'm not sure if this qualifies as useful. –  Yakk Mar 21 '13 at 14:16
    
What is the difference between p = 0 and p = 0 identically? The (A?) utility of this is that determining the coefficients takes exponential time. This is my 2nd favorite answer by the way. Is there anyway to merge it with the answer I selected as I feel this is pretty important note. –  SwimBikeRun Mar 21 '13 at 19:52

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.

share|improve this answer
7  
The four colour problem is not "finite cases" in itself: there are infinitely many planar graphs. Appel and Haken's proof involved checking that each member of an unavoidable set of 1936 configurations was reducible, i.e. if a planar graph containing such a configuration was not 4-colourable, then a smaller graph would also not be 4-colourable. –  Robert Israel Mar 21 '13 at 7:48

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.

share|improve this answer

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

share|improve this answer

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.

share|improve this answer

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.

share|improve this answer

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.

share|improve this answer

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?

share|improve this answer
    
codimension 1 not 2? –  zyx Mar 21 '13 at 19:37

One notion of proof by example that hasn't been mentioned yet involves the classification of finite simple groups. Often times a statement about finite groups will reduce to proving the same about finite simple groups, and then solving the general case via group extensions. Since we can write down all of the finite simple groups, we can just show the statement holds for each of them.

For example, consider the inverse Galois problem which asks if any finite group $G$ is realizable as the Galois group of some extension of $\mathbb{Q}$. This problem is still open, but people have tried to attack it by 'proof by example.' I believe most, if not all, of the sporadic groups have been shown to be Galois groups over $\mathbb{Q}.$ The extension problem, however, seems to be very difficult.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.