Proofs Using Examples: Examples Beyond Linear Algebra

[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 Rⁿ, 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?

 

[matt grime]

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

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

For an example of the kind of thinking I mean, to show that the null space of a transformation T is Rⁿ, it is sufficient to give n independent vectors that T maps to zero.

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

 

[0rthodontist]

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

I mean a finite "enough."

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

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

 

[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?

 

[cliowa]

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

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

 

[0rthodontist]

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

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

What finding n independent vectors is doing, is finding n vectors {v_i} such that T(v_i) = 0, 1<=i<=n, and the v_i differ from one another by independence. Each statement T(v_i) = 0 is an instance of the universally quantified statement "the null space of T is Rⁿ." 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 = Rⁿ. 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 e^Cx 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.

 

[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?

 

[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?

 

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

 

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

 

[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 Rⁿ to R^m.

(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 = Rⁿ)

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

 

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

 

[0rthodontist]

Well, I was speaking loosely--what I meant as I mentioned earlier was interpreting "nul T = Rⁿ" 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)

 

[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 Rⁿ 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).