A. On the nature of theorems
========================================================================
1. We defined a formal logical proof as:
a sequence of propositions such that each is either:
* an axiom (a tautology)
* a premise (sometimes also called an assumption or
a postulate); i.e., a proposition accepted as
true for the sake of the argument
* or follows from previous propositions by a (valid)
rule of inference
where the last proposition is the conclusion
Def: A _theorem_ is, by definition, the conclusion of a valid argument
with no premises (only axioms)
------------------------------------------------------------------------
2. An informal mathematical proof can also include definitions and
previously proved theorems ( = "lemmas");
think of them as like sub-routines
------------------------------------------------------------------------
3. Despite what the text says, although a theorem is a proposition
"that can be shown to be true", that's not how "theorem" is defined.
By definition, a theorem is the conclusion of a valid argument
theorem =df last line of a proof
therefore, a theorem can be shown to be T
(but not all true propositions are provable
--that's Goedel's Theorem!)
And a proof does not "establish the truth of a theorem"
Rather, it shows that the theorem can be validly derived from
axioms
i.e., it establishes the *relative truth* of the theorem
-- its truth *relative to* the truth of the axioms
And not all mathematicians accept all axioms!
(e.g., not all of them accept the axiom of choice,
which says that you can always choose a member from
an infinite set)
In general, the last line of a proof (with or w/o prems) is true
only relative to the starting points (the axioms & premises)
B. Strategies for Proofs
========================================================================
1. A top-level strategy for proving a theorem is to look at its logical
form and then use a lower-level strategy for proving statements of
that form.
Form of theorem Strategy
------------------------------------------------------------------------
a) P(x), where P(x) =df D(x) Show D(x)
(i.e., suppose you have to
prove that something has property
P, where property P is defined in
terms of some other property D)
------------------------------------------------------------------------
b) p -> q Assume (or suppose or make believe)
that p,
& then try to show that q
This is called "direct proof"
You can combine these: If p = P(x), and P(x) =df D(x), then to prove
that p->q, suppose D(x) and then try to show q
------------------------------------------------------------------------
c) Ax[P(x) -> Q(x)] Choose some arbitrary c in the
domain, and try to show
P(c) -> Q(c) (e.g., by direct
proof). Then use Universal
Generalization to get the
universal quantifier back.
------------------------------------------------------------------------
E.g.:
Prove: If n is odd, then n+1 is even.
Hidden assumption: n is an element of Z
Form of proposition: An[Odd(n) -> Even(n+1)]
Strategy:
Let c be an integer
Show Odd(c) -> Even(c+1)
Assume Odd(c) & show Even(c+1)
But Even(x) =df Ej[x=2j]
So, show Ej[c+1=2j]
By assumption, Odd(c)
therefore, Ek[c=2k+1]; this is the definition of Odd(c)
{note another strategy being used here:
replace predicates by their definitions]
therefore, show (2k+1)+1 is even (because c = 2k+1)
Now do some arithmetic/algebra:
(2k+1)+1 = 2k+2 = 2(k+1) -- these are lemmas from algebra
therefore take j = k+1
i.e., Ej[c+1=2j], namely j=k+1
therefore, c+1 is even. QED
2. Form Strategy
------------------------------------------------------------------------
p -> q Try to show -q -> -p (which is logically equiv
to p -> q)
How? by previous strategy, namely:
suppose -q & try to show -p
This is called "proof by contraposition" or "indirect proof".
Especially useful if q is "simpler" than p
------------------------------------------------------------------------
e.g., show: If 7n-5 is odd, then n is even
strategy: show An[Odd(7n-5) -> Even(n)]
Let c be an arbitrary integer, & show Odd(7c-5) -> Even(c).
We *could* suppose that Odd(7c-5) & try to show Even(c).
But *might* be easier to show: -Even(c) -> -Odd(7c-5):
therefore, suppose -Even(c) & show -Odd(7c-5)
i.e., supp. Odd(c) & show Even(7c-5)
Note another strategy: Get rid of negations
i.e., supp. c=2k+1 for some k, &show Ej[7c-5=2j]
i.e., find j such that 7c-5=2j
But we know that c=2k+1
therefore, 7c-5 = 7(2k+1)-5
= 14k+7-5
= 14k+2
= 2(7k+1)
therefore, take j=7k+1 QED
3. When should you use direct proof & when should you use indirect
proof?
In p -> q,if q is simpler than p, then use indirect proof
else try either method; if it goes nowhere, use the other!
------------------------------------------------------------------------
4. More strategies
Form Strategy
------------------------------------------------------------------------
F -> q "vacuous" proof:
where "F" is any contradiction p -> q *must* be T!
p -> T "trivial" proof:
where "T" is any tautology p -> q *must* be T!
5. Proof by Contradiction: (another kind of indirect proof)
(the "look under the street lamp where the light is better
rather than across the street where you lost your keys in
the dark alley" strategy)
Form Strategy
------------------------------------------------------------------------
to show p Suppose -p & try to show Er[r ^ -r]
i.e., find r such that r ^ -r
Why? by truth table: -p -> (r ^ -r)
is equiv to -p -> F
so, tval(-p) = F (because -p -> F is assumed true)
so, tval(p) = T
------------------------------------------------------------------------
famous e.g.:
Show sqrt(2) is irrational (p):
Supp. sqrt(2) *is* rational (-p) & show Er[r ^ -r]:
Supposing sqrt(2) is ratioal, we know there must be integers a,b
such that sqrt(2) = a/b, a fraction in lowest terms
i.e., a, b have no common factors (this will turn out to be "-r")
because sqrt(2) = a/b, we have
2 = (a^2)/(b^2)
so, 2b^2 = a^2
so, a^2 is even
so, a is even (this is a lemma; see exercise 16 in text)
so, Ec[a=2c]; call this constant c1
so, 2b^2 = (2*c1)^2 = 4*(c1)^2
so, b^2 = 2*(c1)^2
so, b is even
so, a and b *do* have a common factor, namely, 2; this is "r"
QED
6. Form Strategy
------------------------------------------------------------------------
to prove p -> q Supp. p
supp. -q
show Er[r ^ -r]
This is another form of proof by contradiction
It works, because the previous strategy for p->q is: supp p & show q
but a previous strategy to show q was to supp -q and show a
contradiction. This just combines them.
------------------------------------------------------------------------
7. to prove p <-> q show p -> q
& show q -> p
(this is an instance of the definitional strategy from earlier)
------------------------------------------------------------------------
8. To prove p1 <-> p2 <-> ... <-> p-n: show p1->p2
& p2->p3
&...&
& p-n -> p1
You could also try to show that all possible pairs of biconditionals are
the case, but this strategy is a lot easier!
Application: Church-Turing thesis:
Turing machines <-> lambda calculus <-> Post production systems
<-> Markov algorithms, etc.
------------------------------------------------------------------------
9. to show -AxP(x) Find a counterexample
i.e. show Ex-P(x)
10. There are lots of ways to have *invalid* arguments (see text, pp.83-84)
More importantly: it's possible that there are *invalid* arguments
with *true* conclusions!
That doesn't make the arguent valid.
And it doesn't prove the conclusion!
E.g.:
All birds fly.
Tweety the canary flies.
So, Tweety is a bird.
This has true premises and a true conclusion,
but is an invalid argument.
Sect 1.7: More Pf Methods & Strategies
========================================================================
1. Proof by Cases
Form of theorem to be proved: Strategies
------------------------------------------------------------------------
(P1 v ... v Pn) -> Q Show P1 -> Q
...
Show Pn -> Q
Justification of this strategy:
(P1 v ... v Pn) -> Q is logically equiv to (P1 -> Q) ^...^ (Pn -> Q)
Note the switch from "v" to "^".
This logical equivalence cannot be proved *by us* *yet*:
we'll need "mathematical induction" (the last Peano Axiom) to do that
But note that:
(P1 v P2) -> Q is logically equivalent to (P1 -> Q) ^ (P2 -> Q)
(you can do a quick truth table to convince yourself of this,
or you can suppose that tval(LHS) = F and tval(RHS) = T
and work backward to derive contradictory tvals for atomic propositions)
------------------------------------------------------------------------
But there is sometimes a trick in applying this, because the antecedent
of a theorem might not look as though it's a disjunction:
e.g.: Theorem: If n is an integer, then n^2 >= n
Note that "n is an integer" is logically equivalent to:
n<0 v n=0 v n>0
So, to show (n is an integer) -> (n^2 >= n),
we only have to show:
(n<0 v n=0 v n>0) -> (n^2 >= n)
and this has the form of a proof by cases.
So, showing that complicated proposition reduces to showing 3 simpler
ones:
(a) (n<0) -> (n^2 >= n) and
(b) (n=0) -> (n^2 >= n) and
(c) (n>0) -> (n^2 >= n)
Case (a): Supp n<0 & show n^2 >= n:
Because n<0, we have n^2 > 0
(the product of 2 negatives is positive)
But n<0 implies 0>n, so 0 >=n (by Addition!)
so n^2 > 0 and 0 >= n
so n^2 >= n
Case (b): Supp n=0 & show n^2 >= n:
Because n=0, we have n^2=0, so n^2=n (because they're both = 0)
so n^2 >= n (by Addition)
Case (c): Supp n>0 & show n^2 >= n:
Because n>0, we have n^2 > 0,
but that doesn't seem to get us anywhere :-(
So, try this: Because n>0, n >= 1
So, n*n >= 1*n (multiplying both sides by n)
So, n^2 >= n
(Case (c) is a nice example of a tricky proof where it's more important
for you to understand the proof than it is to worry about how you would
have come up with the trick at the end.)
QED
2. Existence Pfs
Form Strategy
------------------------------------------------------------------------
ExP(x) (a) Constructive: Find c such that P(c)
Then use existential generalization
(b) Non-Constructive:
e.g.: Use proof by contradiction:
Supp -ExP(x) & try to derive a contra.
or: Show Er[(r v -r) -> ExP(x)]
e.g.:
Theorem: ExEy[Irrational(x) ^ Irrational(y) ^ Rational(x sup y)]
(where "x sup y" = x raised to the y power)
i.e., there are 2 irrational numbers such that when one is raised to the
power of the other, the result is rational (!!)
Let's restate this in a slightly more helpful way,
where Q(x) = x is rational
ExEy[-Q(x) ^ -Q(y) ^ Q(x sup y)]
proof:
Strategy: Find x,y not in Q such that x sup y is in Q
Try x = y = sqrt(2).
Note that sqrt(2) is not in Q, i.e., -Q(sqrt(2)) (by earlier proof)
Consider sqrt(2) sup sqrt(2): For convenience in these notes, call it N
Either Q(N) or -Q(N).
Supp Q(N). Then we're done! We've found our x and y!
Namely, x = y = sqrt(2).
Supp -Q(N). Then consider N sup sqrt(2),
i.e., [sqrt(2) sup sqrt(2)] sup sqrt(2)
Note that -Q(N) (by hypothesis) and -Q(sqrt(2)) by earlier proof.
Could it be possible that N sup sqrt(2) is rational?
N sup sqrt(2) = sqrt(2) sup [sqrt(2) * sqrt(2)], by laws of exponents
= sqrt(2) sup 2, by arithmetic
= 2
and indeed Q(2), so we're done!
Namely, x = N and y = sqrt(2).
But which is it?
WE DON'T KNOW!!
But one of them works, and that's all that we were asked to prove!
QED
This is an example of a non-constructive proof, because we didn't
really find ("construct") the answer; we merely showed that there
was an answer.
Not all mathematicians or computer scientists accept non-constructive
proofs
3. There are lots of other strategies and variations;
we'll introduce them as we need them.
------------------------------------------------------------------------
4. Can *any* old proposition (or its negation) be proved?
NO!
a) There are propositions whose truth value we don't know *yet*
* Up till a few years ago, Fermat's Last Theorem
had not been proved:
"x sup n + y sup n = z sup n has no solutions for integers x,y,z
and integer n>2"
but fairly recently it was proved
* Goldbach's conjecture:
All positive even integers are the sum of 2 primes
i.e.,:
Ax[(Z(x) ^ (x>0) ^ Even(x)) -> EyEz[Prime(y) ^ Prime(z) ^ x=y+z]]
e.g., 28 = 5 + 23
This has not (yet) been proved or disproved!
* Twin Prime Conjecture:
There are an infinite number of twin primes,
i.e., primes m,n such that n=m+2
i.e., AmAn[(Prime(m) ^ Prime(n) ^ n=m+2) ->
ExEy[Prime(x) ^ Prime(y) ^ y=x+2 ^ y>m ^ x>n]]
This has not (yet) been proved or disproved!
b) There are propositions whose truth value we *know* but cannot prove!
Goedel's Incompleteness Theorem:
Here's a highly simplified version of it:
"This proposition is unprovable" is a true proposition
that is unprovable (!)
And here's a highly simplified version of its proof:
Suppose the quoted proposition is false.
Then it is false that it is unprovable.
Therefore, it is provable.
But all provable propositions are true
Therefore, it is true that it is unprovable.
Therefore, it is both true and unprovable.
Cf. Shakespeare: There are more things [that are true]
in heaven and earth than are dreamt of in your philosophy
[i.e., that can be proved by your logic] :-)