2 Replies - 38364 Views - Last Post: 02 September 2013 - 08:08 AM

#1 macosxnerd101   User is offline

  • Games, Graphs, and Auctions
  • member icon

Reputation: 12648
  • View blog
  • Posts: 45,822
  • Joined: 27-December 08

Strategies for Proof Writing

Post icon  Posted 01 September 2013 - 01:31 PM

I've been asked a few times to write tutorials to teach proof-writing. Other than the one tutorial on proof by induction, I don't feel I could really do justice in a tutorial. Instead, I'd love to have a pinned thread in CS where people can contribute their strategies for proof-writing.

Some things I've learned along the way:
-Induction is designed for when previous cases imply a next case. As such, induction proofs are often good to show that something is true, but they are often poor choices to show the "whys" behind theorems. I feel the one exception to this is in Graph Theory, where graphs are often built or transformed inductively.

-Proof by Contradiction is a good "last-ditch effort" strategy. That is, it is difficult to show something directly, but it's easier to show p -> ~q doesn't hold, thus p -> q must instead be valid. It's very similar to working backwards from a Java stack trace.

-Combinatorial proofs are often easier ways to show certain theorems (ie., languages, binomial theorem) than induction.

What other strategies, approaches, and things have you all learned along the way regarding proof writing? What advice would you give someone learning how to formulate proofs?

Is This A Good Question/Topic? 0
  • +

Replies To: Strategies for Proof Writing

#2 raspinudo   User is offline

  • D.I.C Head
  • member icon

Reputation: 61
  • View blog
  • Posts: 232
  • Joined: 19-September 11

Re: Strategies for Proof Writing

Posted 01 September 2013 - 02:05 PM

My first proofs course, mostly concerned with set theory, had a very helpful set of Proof notes written by my instructor. Perhaps others my find them useful as I did.
Was This Post Helpful? 1
  • +
  • -

#3 ishkabible   User is offline

  • spelling expret
  • member icon

Reputation: 1747
  • View blog
  • Posts: 5,898
  • Joined: 03-August 09

Re: Strategies for Proof Writing

Posted 02 September 2013 - 08:08 AM

Practice Practice Practice. Nothing is more important. Writing proofs is A LOT like writing code (in fact, if you limit your self to logic the curry-howard-lambec isomorphism states that proof writing IS writing code). Even relativity simple proofs will not seem apparent unless you practice. Writing proofs is something of an art and while there are general rules you might follow the full picture is more complex than a set of rules.

Also just a note: algebra as you learn it high school is a very simple logic and solving for variables is a kind of proof writing. Interestingly it is not taught this way :/

I should share something I learned in discrete whilst writing a proof for magic squares.
If you are writing math proofs your axioms are often reversible (especially with equations). It is often much easier to assume your conclusion first then derive something you know to be true. This on it's own is not a proof but by simply reversing the above (perhaps with some thought) you do often get a valid proof. By consequence my proof starts out with a seemingly random but true equation and from there derive the conclusion. I wouldn't have been able to find that seemingly random equation had I not done things backwards first.

This post has been edited by ishkabible: 02 September 2013 - 08:34 AM

Was This Post Helpful? 1
  • +
  • -

Page 1 of 1