Examples for proof

1. Jul 13, 2006

0rthodontist

"examples for proof"

Could it be possible to prove some general statement by providing enough examples in a certain context--with the proviso that the examples are in some way more "complicated" than your axiom system? This would be a proof of the form

(Of a general statement, all of a set of instances that are different from each other in a fundamental way are true) and (the axiom system is not complicated enough to support such a large number of statements that differ in that crucial way without the general statement actually being true) implies (the general statement is true)

For an example of the kind of thinking I mean, to show that the null space of a linear transformation T is Rn, it is sufficient to give n independent vectors that T maps to zero. T is in a sense not "complicated" enough to support n independent nonzero vectors being mapped to zero without having, in general, all vectors being mapped to zero.

For another example, let's say that I'm looking at a polynomial sequence and I determine that the first n + 1 terms of it fit a certain polynomial, and I know that the polynomial for the whole sequence has degree n. Then I can conclude that the polynomial that fits those n terms does indeed fit the rest of the terms.

But these are very narrow examples and they both have to do with linear algebra. Are there more general statements of this kind that have to do with general logic systems?

Last edited: Jul 14, 2006
2. Jul 13, 2006

matt grime

with the correct definition of enough, of course, this is trivially true.

that is not sufficient. Nor do I see how it has any relation to the preceding question.

Last edited: Jul 13, 2006
3. Jul 13, 2006

0rthodontist

I mean a finite "enough."

Ah, sorry--I meant a linear transformation whose domain is Rn. The relevance is that you can prove the statement "T has null space Rn" by presenting n vectors that are instances of T having null space Rn (that is, they are in Rn and are mapped to 0) and that differ by the property of being independent.

4. Jul 14, 2006

Alkatran

All numbers are prime. 2 is prime, 3 is prime, 5 is prime... how many examples do you want before you say it's true? Examples don't disprove the existence of counter-examples.

Or maybe I misunderstood?

5. Jul 14, 2006

cliowa

As matt grime pointed out this is not at all a "general statement" which you proof using enough examples. Your linear transformation is one specific example. Of course your argument (taking n linearly independent vectors and showing that they all map to 0) is absolutely correct. But this doesn't mean that you've shown your statement by presenting "enough" examples. What you did (and that's what in this case you could sensibly do) was to take ONE very specific example, i.e. a base for R^n, and then use the theory behind it all. Would you have taken many different sets of n not linearly independent vectors, you wouldn't have gotten anything out of it. So proof by example only works when you need to falsify/invalidate some statement (or when using more theory, like you did).

6. Jul 14, 2006

0rthodontist

To clarify, the statement "the null space of T is Rn" is equivalent to the following statement (of course under the context of T having domain Rn, with 0 appropriately defined):

$$\forall_{v\in R^n} T(v) = 0$$

What finding n independent vectors is doing, is finding n vectors {vi} such that T(vi) = 0, 1<=i<=n, and the vi differ from one another by independence. Each statement T(vi) = 0 is an instance of the universally quantified statement "the null space of T is Rn." And they differ by the fact that the vectors in each statement all are linearly independent.

Of course, the conclusion in this case follows because of the theory of linear algebra. But there are plenty of situations where finding a few examples is enough to prove a general case--it's not an isolated instance. If the theory of linear algebra were a little more complicated--not actually linear--then it might allow situations where those n independent vectors don't together require nul T = Rn. But as it stands linear algebra is too simple to allow that.

Re Alkatran, that's why the examples must differ by some property. If you carefully chose your examples to be similar in that they are all prime, it wouldn't be a good example, just as in the preceding example if you chose your vectors so that they all lay in a line, you couldn't make the conclusion.

I'm talking about cases where you're trying to find some simple function f, and you know--let's say--that f contains at most 20 symbols drawn from a set known to you, e, cos, division, etc. You have a guess that the function is a certain function g where f also contains fewer than 20 of those symbols. Now say can evaluate the original function without knowing its closed form, and from this you have found 200 sufficiently "different"--by some definition of different--points at which f correctly emulates g. Then obviously you would like to conclude that f IS g. If f and g are known to be polynomials with degree less than 200, you clearly can make this conclusion. If f and g are polynomials with degree less than 199, with eCx thrown in for some constant C, then again you can make the conclusion. There is a large number of possibilities for the form of f and g where you can make the conclusion; there should be a theory behind that. Clearly, the more complicated f is allowed to be, the larger the number of specific examples where f(x)=g(x) you need to consider before concluding. And if f can use operators like cos, then your examples must be chosen sufficiently differently so that the cos part of the expression for f does not always evaluate to be the same.

Last edited: Jul 14, 2006
7. Jul 14, 2006

matt grime

So, what you're saying is, if some statement requires only n things to be verified, then checking n of them (and getting a positive answer) is sufficient (anc necessary) is all you need to do.

Again, that is trivially true for those things for which this is sufficient. So, what is your point?

8. Jul 14, 2006

0rthodontist

My point, or rather my question, is, "has this been systematized?" For example, let's say as I supposed earlier that a sequence is known to be solved by an expression of at most 20 basic symbols--sin, cos, e, +, -, /, *, exponentiation, digits 1-9, etc. And let's say that we have found another expression that solves the sequence for the first n values. How large must n be so that it is guaranteed that the expression found is exactly the one sought? Can this be used or is it used to verify combinatorial identities?

Or in the larger view, let's say you have a universally quantified statement consisting of a certain number of symbols. How many instances do you have to verify, and what are the conditions on those instances, before you have proved the universally quantified statement correct? Of course this couldn't work for all universally quantified statements, but what ones does it work for?

9. Jul 14, 2006

matt grime

And I said, it works for those where you can demonstrate that it suffices to find n exhaustive conditions are verified.

Tehre are far too many places where this applies, and far too many where it doesn't, to make this worthwhile to categorize.

10. Jul 15, 2006

matt grime

A famous one where it does apply: the four colour theorem. It also applies to deciding if chess has a winning strategy, or many other situations, but practicality determines that we need a better strategy for solving the problem.

11. Jul 16, 2006

0rthodontist

The four color theorem is definitely an example. But whether chess has a winning strategy looks like a different kind of problem. It would be a huge case analysis, but not specifically an _example_ based analysis--the cases, meaning the specific chess positions or specific strategies, aren't instances of a universal statement, and there isn't much (as far as I know) generalization from a few model positions or strategies to the rest of them.

I've been thinking some more about what I mean by the complexity of the problem. In the linear algebra example, the problem can be divided into four sets of statements:

(1) The context for the problem. This would be a system of logic, the theory of linear algebra, etc., along with the knowledge that T is a linear transformation from Rn to Rm.

(2) The specifics of the problem, in this case specifically what T is, given maybe by a transformation matrix

(3) The universally quantified statement in question (nul T = Rn)

(4) A set of instances of the universally quantified statement that are known to be true from 1 and 2, in this case a set of n linearly independent vectors that T maps to 0, or more precisely the set statements that T maps each of those vectors to 0.

Dividing up the problem this way, (4) actually is not just about a set of linearly independent vectors, it is a set of logically independent statements with respect to (1). No statement in (4) can be derived from any other set of statements in (4) when given only (1). It is also true that given it is independent, (4) is of the maximum possible cardinality. Those two things are sufficient to prove (3). [Edit: the preceding statement is not true]

This is what I think I mean by the examples having to differ "in some way" whether being linearly independent or not all prime, etc: they have to be logically independent with respect to (1).

I think that many example based problems can be broken up in that way. The four-color problem may be an exception because I don't see a good candidate for (2). (2) must be split off from (1) in such a way that the examples actually are logically independent; they can't be re-derivable from (1).

Last edited: Jul 16, 2006
12. Jul 16, 2006

matt grime

In what way is (nul T = R^n) universally quantized? As stated there is not a single quantifier in there.

Of course, it can be universally quantified, if you so wish, but so can chess: for all states S there is a winning strategy for white, can be proved, if it is true, by an exhaustive search. I am surprised you say it is not an example but the four colour theorem is since they are both statements in exhaustive searching over graphs, i.e. combinatorics which just as much of a theory as linear algebra.

Finding a vector v such that Tv=0 is not finding 'an instance' of (nul T = R^n), in my opinion.

Last edited: Jul 16, 2006
13. Jul 16, 2006

0rthodontist

Well, I was speaking loosely--what I meant as I mentioned earlier was interpreting "nul T = Rn" as $$\forall_{v\in R^n} T(v) = 0$$, and finding a vector v such that Tv = 0 is basically the same as being able to state truthfully "Tv = 0" which is an instance.

With chess, it's more of an exhaustive search of the entire space of positions than finding a few examples and generalizing, unless there's something I'm just ignorant of. I have heard of "alpha beta trimming" which might make it a genuine example-based search but I don't know about that besides the name. Also it's pretty hard to find an instance of "for all states S, white has a winning strategy" in the middle of a standard chess game--that's the same as finding a forced mate. (if you have to prove the instance to be a true instance, in addition to just finding it)

Last edited: Jul 16, 2006
14. Jul 16, 2006

0rthodontist

Ah, actually I was wrong when I said that the fact that (4) has the maximum possible cardinality for being independent is sufficient to prove (3). Intuitively (4) must be "large enough" to cover all the instances of (3), but just how large is that?

Basically I want to equate the dimension of Rn to the "logical" dimension of (3), in a similar way to how linear independence corresponds to logical independence. The dimension of nul T is exactly the cardinality of (4), so if the cardinality of (4) matches the "logical dimension" of (3), then (3) has been proved.

One way to do something like that is to consider all possible definitions of (2) that are consistent with (1), whether or not they are consistent with (3). Let (3) be the statement $$\forall_{v\inU} S(v)$$ where S(v) is a statement about v that depends on (2), and U is the universe over which (4) is quantified. For an arbitrary (2), (3) might be false. Let (3a) be the TRUE statement $$\forall_{v\inV} S(v)$$ that is quantified over the largest possible subset V of U for which (3a) is true. Let (3b) be the true statement $$\forall_{v\in V^c} \neg S(v)$$. Let (4a) be a largest-cardinality set of statements that are logically independent with respect to (1) and that are instances of (3a), and let (4b) be a largest-cardinality set of statements that are logically independent with respect to (1) and that are instances of (3b). Then the "logical dimension" of (3) can be defined as the maximum of |(4a)| + |(4b)| over all formulations of (2) that are consistent with (1). This is significant because if |(4)| happens to be equal to the logical dimension of (3), then you know that no statements are consistent with (3b), because if they were they were then the logical dimension of (3) would be at least one greater, so you have proved (3).

Last edited: Jul 16, 2006