Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

A question about a common pattern in mathematical proofs

  1. Jan 30, 2014 #1

    tom.stoer

    User Avatar
    Science Advisor

    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.
     
  2. jcsd
  3. Jan 30, 2014 #2

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    Then your friend is wrong.

    "P ∧ (∀n∈N:(P → A(n)))" → "∀n∈N : A(n)"
     
  4. Jan 30, 2014 #3

    tom.stoer

    User Avatar
    Science Advisor

    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?
     
  5. Jan 31, 2014 #4

    Stephen Tashi

    User Avatar
    Science Advisor

    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.
     
  6. Jan 31, 2014 #5

    tom.stoer

    User Avatar
    Science Advisor

    good point, thx
     
  7. Jan 31, 2014 #6

    PeroK

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Another approach would be:

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

    Now, suppose [tex]\forall n: \ A(n)[/tex] 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, [tex]\forall n: \ A(n)[/tex] must be true as a result of proving A(n) for an unspecified n.
     
  8. Jan 31, 2014 #7

    FactChecker

    User Avatar
    Science Advisor
    Gold Member

    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?
     
  9. Feb 1, 2014 #8

    tom.stoer

    User Avatar
    Science Advisor

    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
     
  10. Feb 1, 2014 #9

    FactChecker

    User Avatar
    Science Advisor
    Gold Member

    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.
     
    Last edited: Feb 1, 2014
  11. Feb 1, 2014 #10

    PeroK

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Here's an example. Suppose you want to prove: [tex]\forall n \ (n+1)^2 - n^2 \ is \ odd[/tex]. A proof would be: [tex]Let \ n \in N. (n+1)^2 - n^2 = 2n +1 \ (which \ is \ odd)[/tex] 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):[tex]\forall \ n \in N: (n+1)^2 - n^2 = 2n +1 \ (which \ is \ odd)[/tex]

    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.
     
  12. Feb 1, 2014 #11

    tom.stoer

    User Avatar
    Science Advisor

    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 ;-)
     
  13. Feb 1, 2014 #12

    FactChecker

    User Avatar
    Science Advisor
    Gold Member

    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.
     
    Last edited: Feb 1, 2014
  14. Feb 2, 2014 #13

    tom.stoer

    User Avatar
    Science Advisor

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

    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.
     
  15. Feb 2, 2014 #14

    FactChecker

    User Avatar
    Science Advisor
    Gold Member

    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.
     
  16. Feb 2, 2014 #15

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    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.
     
  17. Feb 2, 2014 #16

    tom.stoer

    User Avatar
    Science Advisor

    DH, I agree, that's my impression, too.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: A question about a common pattern in mathematical proofs
Loading...