Mathematical Proof

[simonm]

I know there are various different methods of proof that mathematicians use but I am curious to know if some are considered more valid than others.

For example, you hear much about the inability of induction to justify conclusions but proof by induction is still used, right?

Is proof by contradiction more valid than proof by induction? If so, why?

What other types of proof are there?

[sail3005]

the two main ones we used in geometry were to start with a false statment, and then use a series of true statments to prove it false. Also, list a series of true statments, proven facts, that can prove your conclusion.

[simonm]

That sounds like logical deduction that appears to be another method of justifying conclusions. Perhaps this one is the most valid but not always available to mathematicians.

[kovan]

simonm, shut up

[sail3005]

Originally posted by simonm
That sounds like logical deduction that appears to be another method of justifying conclusions. Perhaps this one is the most valid but not always available to mathematicians.

I don't think that one is more valid than another. If something is proven to be true, then it must be fully proven. If the method that is used works to prove it, then it must be an accepted method, or the problem is not considered proven.

[simonm]

I don't think that one is more valid than another. If something is proven to be true, then it must be fully proven.

You say that but I've heard much critisism of induction as a means of justifying conclusions but it still seems to be a valid tool mathematicians use on occaision.

For example, if you can prove X to be true for N, and then prove it also to be true for N + 1, by induction you assume that X is true for any value of N. I can't remember off the top of my head which proofs this is used in but I'm sure it is still used.

[Nicomachus]

no proof method is more "valid" than any other, the only thing that invalidates a proof is it's end conclusion is incorrect, but if that is the case it is not a proof and is therefore not even mathematics. The criticism you are referring to is that some "forms of proof", that is the logical formation of it, yield results in a more practical manner. You could prove Fermats Last Theorem using various all the different types of logic, the only difference may be the amount of time, or practicality of the proof. example, it may take you 50 steps with logic that premises a the idea being false and contradicts it at then while it may take you 5 steps to prove the same concept using another method .. well those are my thoughts ..
Nico

[star]

All proofs are actually logical deductions, even induction used in math, as there is a fundamental assumption that makes it a valid way of proof. Also you can proove anything with inconsistent premises.

[simonm]

All proofs are actually logical deductions, even induction used in math, as there is a fundamental assumption that makes it a valid way of proof.

Ah, but if induction has been arguably shown to be flawed, should we not then discard (or at least question) any proofs that rest on that principle?

Now, I know all proofs rest on particular assumptions which we hold as true until we find a particular reason to question them. What I'm saying is that there is a particular reason to question the validity of induction and therefore, should we be using it attall.

Then again, perhaps mathematical induction is different from epistemological induction?

[kedaman]

Simon
How come you have to question the validity of a proof, when the method for proof itself is an arbitrary axiom, questioning that would be to question what is arbitrary and what is not, and that depends on the issue. What does epistemological induction mean?

[simonm]

How come you have to question the validity of a proof, when the method for proof itself is an arbitrary axiom...

True, but I know of no good reason to question any of the other axioms. There seems to be a fairly good reason to at least question the use of this particular one.

What does epistemological induction mean?

Well, "Epistemology" is the theory of knowledge itself. The study to what knowledge is, how we gain it and how we justify it.

Induction is a means by which some say we can infer universal statements (generalisations) from a finite collection of singlular statements (observations).

[kedaman]

Simon
Well its obvious that mathematics has nothing to do with observations, it is strictly defined and therefore you have defined the instances ex the aritmetical values to conform to aritmetical rules of operations, so induction would be a part of that agreement.

[simonm]

Well, OK, but I'm using the word "observation" in it's loosest possible sense (and maybe even looser than that).

As I understand it, mathematical proof using induction goes something like this:

1) Prove theorem is true for N.

2) Prive theorem is true for N + 1.

3) By induction, theorem is true for all values of N.

Thus, a universal statement is "prooven" by prooving a finite number of singular statements.

However, my gut feeling is that the nature of mathematics is such that it allows for such inferences. I'm not sure why though...

[kedaman]

well in the "real" world you have no idea what the kernel of these observations are, but in math you start out with the premisses that you know the kernel, because it is defined.

[argentum]

Hi simonm,

I found intriguing your comment about induction being questioned as a valid method of proof. Where have you found that ?

As far as I know, induction is a perfectly valid method of proof, and is widely used by mathematicians.

It is not an axiom you have to accept as valid, it can be proved valid.

Actually, it is called The Principle of Complete Induction, and is described as follows:

Let us call p a proposition or statement we want to prove valid.
Let us call n any positive integer number.

The Principle of Complete Induction states:

If

1) p is true for n = 1,

and

2) p being true for n implies p being true for n + 1,

then

p is true for any value of n.

Note: To make it more clear, 2) could be rewritten as follows:
Each time p is found true for a positive integer k, then it is also found true for next one, k + 1.

The proof of the validity of this method is made by contradiction or reduction to absurd, as follows:

Let us suppose that given the conditions 1) and 2), p is not true for all values of n.
Then, there is at least one positive integer k, for which p is false.
Then, considering 2), p is also false for k -1, because if it were true for k - 1, it should be true for k. (Given that k = [k - 1] + 1 ).
Repeating the same reasoning, p is false for k - 2, k - 3, ... ,
(k - 1) + 1.
Then p is false for k = 1, which contradicts 1).
So p is true for all values of n.

Of course, I might be wrong, as I studied these things quite a time ago.

I will appreciate any comments on this.

[simonm]

argentum,

I found intriguing your comment about induction being questioned as a valid method of proof. Where have you found that ?

Well, I was refering epistemological induction which has been shown to be unreliable if not useless. I merely wondered what the relation with mathematical induction was. Perhaps the same problems were implicit in mathematical induction, I didn't know.

It strikes me that they probably are different and that mathematical induction doesn't suffer the same flaws that epistemological induction does.

Your proof, by contradiction, seems to demonstrate this.

[sql_lall]

Which proofs are best?? Simple:
Any proof that prooves what the person using it set out to proove is a good and valid one. Any proof that has flaws is not a good and valid one. There is no real 'grey' area, just the speed at which the proof was shown, and the ease, or 'beauty' of how the proof was used!

I.e. the proof of saying "I have seen it work for soooo many cases it MUST be true." (proof by observation, so named by my friend) is completely unacceptable.
Whereas saying:
It works for x when x(=k)=n. It works for x when x(=k+1)= (n+1)
=>i.e it works for x(=k)=n+1 => it works for x(=k+1)=n+2
=> it works for x=n+3, etc.

Also, things prooved by induction include sums like 1^2 + 2^2 + ...+ n^2 = (n)(n+1)(2n+1)/6 -apologies if that is incorrect.
and 1*1! + 2*2! + ...+ n*n! = (n+1)! - 1

Finally, although it is not used as often, most MOD questions can be solved using induction.