Truth, Proofs, and Theorems
------------------------------------------------------------------------

There are a couple of points that the textbook makes that I want to
clarify, but that I don't want to take class time for.

1.
We defined a (formal) *logical* proof as:
	a sequence of propositions such that each proposition in the
	sequence is either:
		* a tautology (sometimes called an "axiom")
		* a premise (i.e., a proposition *assumed* to be true
				   "for the sake of the argument")
		* or follows from previous propositions in the sequence
		  by a rule of inference (i.e., by a valid argument form)

2.
An (informal) *mathematical* proof can also include previously proved
theorems and definitions.

	Previously proved theorems are called "lemmas";
	they are like subroutines or macros in a computer program

3.
DESPITE WHAT THE TEXTBOOK SAYS, although a theorem *is* a proposition
"that can be shown to be true", that is not its *definition*.

a)  A _theorem_ is(by definition) the conclusion of a proof
    (i.e., of a valid argument) that has no premises.

b)  *Because* a theorem is the last line of a truth-preserving proof,
    it "can be shown to be true".

c)  BUT:  a proposition can be true *without* being provable!

------------------------------------------------------------------------
DIGRESSION:  The most famous example of a true but unprovable
proposition of arithmetic is the following proposition (well, actually
it's a more precise form of the following proposition) from Goedel's
Incompleteness Theorem.  That theorem says that if you take FOL and add
Peano's Axioms, then you can construct an arithmetical proposition that
says this:

	This proposition cannot be proved.

Notice that this is almost like the Barber sentence or the liar paradox.
Almost, but not quite!  Here's why:

Suppose this proposition is false.
Then what it says is false.
But what it says is that it cannot be proved.
If that's false, then it *can* be proved.
But any proposition that can be proved has to be true
	(because it's the last line of a truth-preserving proof).
So it can't be false after all.
But then it's true.
In that case, what it says is true.
But what it says is that it cannot be proved.

So, we have an example of a true proposition that cannot be proved!

The best book on this is:

Hofstatder, Douglas R. (1999), Goedel, Escher, Bach:  An Eternal Golden
Braid, 20th anniversary edition (New York:  Basic Books)
http://www.amazon.com/Godel-Escher-Bach-Eternal-Golden/dp/0465026567
http://en.wikipedia.org/wiki/G%C3%B6del,_Escher,_Bach
END OF DIGRESSION
------------------------------------------------------------------------

4.
AND, DESPITE WHAT THE BOOK SAYS, a proof does *not* "establish the truth
of a theorem".

a)  Rather, a proof shows that the theorem can be *validly derived*
    from axioms.

b)  It *does* "establish" the *relative* truth of the theorem,
    i.e., its truth *relative to* the truth of the axioms

c)  But aren't axioms tautologies?  So don't they have to be true?
   
d)  Not all mathematicians or logicians accept all axioms!

------------------------------------------------------------------------
DIGRESSION:  The most famous example of an axiom that not all
mathematicians or logicians accept is the Axiom of Choice.

This axiom says the following:

Let C be an infinite collection of infinite, non-empty sets.
Then we can choose a set (or "elect a house of representatives")
consisting of one representative from each set.

Some mathematicians don't like this because the axiom doesn't tell you
*how* to make the choice (how to "run the election"), especially since
you have an infinite number of "candidates" and an infinite number of
"polling places", so to speak.

But if you reject this axiom, then you also have to reject almost all of
modern mathematics, including the differential and integral calculus,
and most mathematicians are unwilling to do that.

(Though I suppose some of you who have to take MTH 141-142 might feel
differently :-)

For more information on the Axiom of Choice, see:
http://www.math.vanderbilt.edu/~schectex/ccc/choice.html
http://en.wikipedia.org/wiki/Axiom_of_choice
http://plato.stanford.edu/entries/axiom-choice/
http://mathworld.wolfram.com/AxiomofChoice.html

END OF DIGRESSION
------------------------------------------------------------------------

5.
In general, whether we're talking about theorems in particular or proofs
in general, THE LAST LINE OF A PROOF (WITH OR WITHOUT PREMISES) IS TRUE
ONLY **RELATIVE TO** ITS STARTING POINTS (AXIOMS + PREMISES)