A question about a common pattern in mathematical proofs

[tom.stoer]

I am no expert in formal logic, so please forgive me if this question sounds stupid. It's about a common pattern used in many mathematical proofs.

For me it' "obvious" or "trivial" - but I can't prove it.
For a friend of mine it's far from obvious or even wrong - but I don't get his point and I am quite sure that he does not really understand mathematical methods at all ;-)

Let's make a simple example: suppose there's a natural number n and a statement A(n) like "a natural number n is always either even or odd". In many cases there's a proof which does not use a specific property or value of n, so the proof is valid for all n and we conclude that "∀n∈N : A(n)". Now my friend is saying that such a proof is never valid for all numbers n, but only for one single but unspecified number (which I think is nonsense); so he is saying that the "∀n" is wrong (which is think is hogwash).

The common pattern in such proofs is the following: we have a statement A(n) and a proof P which does not use a specific property or value of n. So we could say

"P → ∃n∈N : A(n)" ∧ "P does not use a specific property or value of n" → "∀n∈N : A(n)"

Again: for me it sounds strange; if I have a proof which works for all n then I immediately conclude that "∀n" is right.

Anyway - let me ask the question whether my conclusion is really obvious. Or if one needs a proof for the above mentioned pattern, and how it looks like.

 

[mfb]

Now my friend is saying that such a proof is never valid for all numbers n, but only for one single but unspecified number (which I think is nonsense); so he is saying that the "∀n" is wrong (which is think is hogwash).

Then your friend is wrong.

"P ∧ (∀n∈N:(P → A(n)))" → "∀n∈N : A(n)"

 

[tom.stoer]

mfb, the problem is that we agree on that and we think that this is obvious. How can we convince him or explain to him what we think it's obvious?

 

[Stephen Tashi]

How can we convince him or explain to him what we think it's obvious?

You could try to crush his resistance with the weight of authority. The method of proof by using a symbol as if it is a specific, but "completely general" thing is called (in mathematical logic), the principle of "universal generalization". http://en.wikipedia.org/wiki/Universal_generalization

Many people who create mathematical proofs, don't make a careful study of mathematical logic. They use "universal generalization" without naming it as such, just because they sense it is a correct form of reasoning.

 

[tom.stoer]

good point, thx

 

[PeroK]

Another approach would be:

Suppose you take taken an unspecifed n and proved A(n).

Now, suppose $$\forall n: \ A(n)$$ is not true.

Hopefully, maybe, your friend would accept that there must exist n_0 for which A(n_0) fails?

But, you can take n_0 as your unspecified n and conclude A(n_0)

So, $$\forall n: \ A(n)$$ must be true as a result of proving A(n) for an unspecified n.

 

[FactChecker]

Maybe I am misunderstanding this:
"P → ∃n∈N : A(n)" ∧ "P does not use a specific property or value of n" → "∀n∈N : A(n)"

So I will ask what might be a dumb question.
Is this an example?
"The sunrises in the East implies there is a cat named Whiskers" → "All cats are named Whiskers"

P="The sunrises in the East". N = set of all cats. Clearly P does not use a specific property of cats.
If I do, in fact, have a cat named Whiskers, wouldn't this imply that all cats are named Whiskers?

In fact, if "∃n∈N : A(n)" is any known truth (like "there exists an natural number, n, that is even"), wouldn't the logic statement imply that all natural numbers are even?

 

[tom.stoer]

You misunderstand the meaning of P. P is a proof of A(n), e.g. a proof that n (left unspecified) is either even or of.

n=1 odd
n=2 even
n'=n+1; if n is even, i.e. n=2k, then n'=2k+1, n' is odd
so I can prove for some unspecified n that it is either even or odd

 

[FactChecker]

Ok. I think I see. P proves A(n) using only the properties of N and no unique properties of n. In that case, why does ∃n even get introduced? Why doesn't P talk about ∀n right from the beginning? It seems like the proof you describe would prove existence of at least one element, n, in N and then prove the property A(n) for that constructed n. But wouldn't a construction of n have to refer to the properties of n used in the construction?

I think that P should suppose existence of n in N rather than prove existence of a particular n in N. Say "Let n be an element in N" and prove A(n) using only properties of N. A proof of existence of a particular n in N will almost certainly involve some special properties of n.

 

[PeroK]

Ok. I think I see. P proves A(n) using only the properties of N and no unique properties of n. In that case, why does ∃n even get introduced? Why doesn't P talk about ∀n right from the beginning? It seems like the proof you describe would prove existence of at least one element, n, in N and then prove the property A(n) for that constructed n. But wouldn't a construction of n have to refer to the properties of n used in the construction?

Here's an example. Suppose you want to prove: $$\forall n \ (n+1)^2 - n^2 \ is \ odd$$. A proof would be: $$Let \ n \in N. (n+1)^2 - n^2 = 2n +1 \ (which \ is \ odd)$$ The question now is whether this has proved the case "for all n" or simply for "a single unspecified n". By the "universal generalisation" it has proved the case for all n.

Your idea would be equally valid (certainly outside the realm of formal logic):$$\forall \ n \in N: (n+1)^2 - n^2 = 2n +1 \ (which \ is \ odd)$$

But, formally, you can't actually do a calculation for all n at once, so "under the covers" this is the same as the first proof. You;re doing the calculation for an unspecified n and generalising the result.

 

[tom.stoer]

In that case, why does ∃n even get introduced? Why doesn't P talk about ∀n right from the beginning?

Read my first post.

A friend of mine says "even so the proof does not use any specific property of n, the proof is only valid for one single unspecified n, not for all n".

I agree that this is strange, but I want to convince him that generalization is possible iff the proof is free of any property of n.

I am looking for an argument to explain what is so obvious to me that I am unable to explain it ;-)

 

[FactChecker]

I may not have been clear. The statement "∃n∈N:" is not the same as "Let n∈N".
"∃n∈N:" requires proving the existence of one particular n, which may have very unique properties. This is usually done by constructing a particular n or with a counting argument that makes use of specific properties of n. If your initial proof "P → ∃n∈N : A(n)" did not do something specific to construct or prove the existence of a specific n, then that proof was invalid. If it did construct n or prove the existence of a particular n, then I think you will find that it does not apply to all elements of N.

The phrase "Let n∈N" is what you want to use if you are proving something for all elements of N. If the proof really applies to all n∈N, it should be rewritten correctly.

 

[tom.stoer]

I agree, but this is not the point. Stephen has summarized perfectly what I have to do:

You could try to crush his resistance with the weight of authority. The method of proof by using a symbol as if it is a specific, but "completely general" thing is called (in mathematical logic), the principle of "universal generalization". http://en.wikipedia.org/wiki/Universal_generalization

Many people who create mathematical proofs, don't make a careful study of mathematical logic. They use "universal generalization" without naming it as such, just because they sense it is a correct form of reasoning.

The problem is simply to convince my friend that the principle of universal generalization is valid. He does not "sense it is a correct form of reasoning". That's all.

 

[FactChecker]

If the proof really doesn't use or say anything about n that is not a general property of N, then I agree with you.

But then what purpose is served by the proof of n existing in N? Is it important to construct n to show that N is not empty? But that would only prove the existence of the subset of N that can be constructed that way. The only way that your statement would be true is if all members of N can be constructed that way.

Why not restate P with the stronger and more accurate "n∈N => A(n)."? That would be much better style.

I would think that our friend is wrong in the logic, but right in the mathematical style.

 

[D H]

The problem is simply to convince my friend that the principle of universal generalization is valid. He does not "sense it is a correct form of reasoning". That's all.

It sounds like your friend has intuitionist or constructivist leanings, or perhaps both. Intuitionism rejects the law of the excluded middle. Constructivism demands that all valid proofs be constructive. Universal generalization is invalid in both of these mathematical schools of thought. It obviously is not a constructive technique, and it not quite so obviously depends on the law of the excluded middle.

 

[tom.stoer]

DH, I agree, that's my impression, too.