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

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

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

Attribution
Source : Link , Question Author : SwimBikeRun , Answer Author : Stahl

Leave a Comment