From owner-cse191-sp08-list@LISTSERV.BUFFALO.EDU  Wed Feb 20 19:52:37 2008
Date:         Wed, 20 Feb 2008 19:52:21 -0500
From: "William J. Rapaport" <rapaport@cse.Buffalo.EDU>
Subject: 191:  MISCELLANEOUS THOUGHTS ABOUT PROOFS
To: CSE191-SP08-LIST@LISTSERV.BUFFALO.EDU

------------------------------------------------------------------------
Subject: 191:  MISCELLANEOUS THOUGHTS ABOUT PROOFS
------------------------------------------------------------------------

Here are some miscellaneous thoughts about proofs that I didn't get a
chance to talk about in lecture:

1.  There are lots of ways to have **invalid** arguments!
    See Rosen, pp. 83-84.

2.  More importantly, it is possible to have an **invalid** argument
    whose conclusion is **true**.  Here's an example:

	All birds fly.               (true)
	Tweety the canary flies.     (true)
	------------------------
	Therefore, Tweety is a bird. (true)

    This is invalid, despite the fact that both premises and the
    conclusion are true:  It is invalid, because the argument 
    form can have true premises and a **false** conclusion:

	Ax[P(x) -> Q(x)]
	R(a) ^ Q(a)
	----------------
	P(a)

    Here's a counterexample, i.e., an argument with this form
    that has true premises but a false conclusion:

	All birds fly.
	Bob the bat flies.
	------------------
	Therefore, Bob is a bird.
    	 
    Just having a true conclusion doesn't make an argument valid.
    And such an argument doesn't prove its conclusion (even though
    the conclusion is true).

3.  Can **any** proposition (or its negation) be proved?

    That is, given a proposition P, we know that either P is true
    or P is false (i.e., that -P is true).  So whichever one is true
    should be provable.  Is it?

    Nope!

    First, there are propositions whose truth value we don't know
    **yet**.

    E.g., once upon a time, no one knew if Fermat's Last Theorem
    could be proved:  As you should recall from today's lecture,
    that's the proposition that the equation	

	x^n + y^n = z^n

    has no solutions for integers x,y,z and integer n > 2.  But
    it has now been proved.

    E.g., no one knows (yet) if Goldbach's Conjecture is true:

	All positive even integers are the sum of 2 primes.
	e.g., 28 = 5 + 23
	In logic:

		Ax[Z(x) ^ (x > 0) ^ Even(x) ->
			EyEz[Prime(y) ^ Prime(z) ^ (x=y+z)]]

    E.g., no one knows (yet) if the Twin Prime Conjecture is true:

	There are an infinite number of "twin" primes,
	i.e., primes m,n such that n = m + 2
	e.g., 2 & 3, 3 & 5, 5 & 7, 9 & 11, 11 & 13, etc.
	In logic:
	
		AmAn[Prime(m) ^ Prime(n) ^ (n = m + 2) ->
			ExEy[Prime(x) ^ Prime(y) ^ (y = x + 2)
			              ^ (y > m) ^ (x > n)]]	

    Second--and much more astounding than our mere inability so far
    to prove or disprove any of these conjectures--there are
    propositions whose truth value is known to be true, but which
    we can prove that we cannot prove!  This is the essence of
    Goedel's Theorem.  Stated informally, it asks us to consider
    this proposition, which is a slight variation on the Liar
    Paradox (to remind you, that is the proposition "This proposition
    is false":  If it's false, then it's true; if it's true then it's
    false):

	This proposition is true but unprovable.	(G)

    We can assume that G is either true or false.  Is it false?  
    If it is false, then it is provable.  But any provable proposition
    has to be true (because proofs are truth-preserving).  So it
    isn't false.  Therefore, it must be true.  But if it's true,
    then it's unprovable.  End of story; no paradox!

    I.e., there are true propositions (moreover, Goedel showed that
    they are propositions that are true in the mathematical system
    consisting of first-order predicate logic plus Peano's axioms;
    i.e., they are propositions of arithmetic!) that cannot be proved.

    For more information on Goedel's proof, see:

Nagel, Ernest; & Newman, James R. (1958), Goedel's Proof (New York:
New York University Press).

Hofstadter, Douglas R. (1979), Goedel, Escher, Bach:  An Eternal Golden
Braid (New York:  Basic Books).