Page 1 of 1

Book on proofs?

Posted: Sat Aug 02, 2008 4:13 am UTC
by TheWaterBear
I'm going to be taking Calc 3 this fall, so I was hoping that someone might have a good book on proofs...

I basically just need to know the structure that is used, as I've never really done a formal proof before.

Suggestions?

Re: Book on proofs?

Posted: Sat Aug 02, 2008 4:24 am UTC
by Qoppa
I've heard good things about How to Prove It.

Re: Book on proofs?

Posted: Sat Aug 02, 2008 3:20 pm UTC
by Yakk
Try proving stuff. :-)

Ie: Let N be the natural numbers, defined (slightly informally) as:
0 is an element of N
For each element x in N, succ(x) is an element of N.
"=" is an equivalence relation on elements of N (look up what an equivalence relation is)
"+" is an operator that takes two values from N, and returns a value from N. Ie, for a, b from N, a+b is an element of N.
"*" is an operator that takes two values from N, and returns a value from N. Ie, for a, b from N, a*b is an element of N.
1 = succ(0)
For each element a in N, a+0 = a
For each element a, b in N, a+b = b+a
For each element a, b in N, a+succ(b) = succ(a+b), and succ(a)+b = succ(a+b)
For each element a in N, a*1 = a
For each element a, b in N, a*b = b*a
For each element a, b in N, a*succ(b) = a*b + a, and succ(a)*b = a*b+b
For each element a, b, c in N, a*(b+c) = a*b + a*c
For each element a in N, a < succ(a)
For each element a, b in N, a<b is the same as b>a, and a<=b is the same as b>=a
For each element a, b in N, a<=b means a<b or a=b
For each element a, b in N, either a<b or a>=b.
For each element a, b, c in N, if a<b and b<c, then a<c.
For each element a, b in N, if a<b, then a<succ(b).

...

I think that is more than enough to give you the natural numbers, but I left out induction. :-)

So your task:
Prove that the Well Ordering Principle is implies the Principle of Mathematical Induction.

Well Ordering Principle: Let X be some subset of N. Then there is an element a from X such that for all elements b of X, a<=b.

Principle of Mathematical Induction: Let P(x) be some property of elements of N.
If P(0) is true, and ( For all elements a of N, P(a) is true implies P(succ(a)) is true ), then:
For all elements a of N, P(a) is true

Step 2: Define the "Principle of strong induction" to be:
Let P(x) be some property of elements of N.
If P(0) is true, and for each element a from N ((For each element b < a from N, P(b) is true) implies P(a) is true), then
For each element a of N, P(a) is true.

Show that The Principle of Mathematical Induction implies the Principle of Strong induction.

Step 3: show that the Principle of Strong Induction implies the Well Ordering Principle.

Note that this implies that the three principles are equivalent, as assuming any one of them proves the other 2!

I think that was, roughly, the very first proof assignment given to me at university. I think the prof did one of the 3 steps in class, and we did the other 2.

Can you think of how to approach this? :-)

Re: Book on proofs?

Posted: Sat Aug 02, 2008 6:38 pm UTC
by Harg
I like Yakk's example very much and I can't help but give one that I found very enjoyable as well. This was on an exam in my Real Analysis class:
Let [imath]f,g: \mathbb{R} \to \mathbb{R}[/imath] be continuous functions. Define function [imath]h: \mathbb{R} \to \mathbb{R}[/imath] as [math]h(x)=\begin {cases} f(x),&x\in\mathbb{Q}\\g(x),&x\in\mathbb{R}\setminus\mathbb{Q}\\ \end {cases}[/math]Find the set [imath]C=\{x;h\mbox{ is continuous at }x\}[/imath].
I realize this isn't strictly a proof assignment, so I or somebody else can supply the answer for you to prove.

Re: Book on proofs?

Posted: Sun Aug 03, 2008 3:36 am UTC
by Lycur
Well it's probably fun to learn in general, you won't almost certainly won't need to do much in the way of formal proofs in calc 3. Unless 'Calc 3' is introductory Real Analysis for you.

Re: Book on proofs?

Posted: Sun Aug 03, 2008 9:41 am UTC
by quintopia
Harg: is it
Spoiler:
all x where f=g?

Re: Book on proofs?

Posted: Sun Aug 03, 2008 11:29 am UTC
by Harg
Exactly

Re: Book on proofs?

Posted: Sun Aug 03, 2008 3:54 pm UTC
by z4lis
But since this set Q isn't defined, can I not suppose that Q and R are disjoint, and so R\Q = R?

Let x be an element of R => x is an element of R\Q => h(x) = g(x). Since g(x) is continuous over all of R, would it not be continuous at x, regardless of whether or not f and g are equal?

Edit: Silly me, you must have meant R to be the reals and Q to be the rationals. Anyway, wouldn't you need more than just a single point where f=g? I don't know anything about continuity other than what intuition tells me, but it seems we would need an interval (a,b) where a!=b along which f=g in order for h to be continuous.

Re: Book on proofs?

Posted: Sun Aug 03, 2008 5:29 pm UTC
by Harg
Intuition can fail when talking about continuity at a single point, since we always imagine continuous functions to be these nice, connected, wavy lines. Because Q and R\Q are dense in R, you can imagine the graph of h as a superposition of the very (in fact infinitely) finely dotted graphs of f and g. You can probably now see that the only points where h could possibly be continuous is where these dots come very, very close together i.e. where f=g.

Re: Book on proofs?

Posted: Mon Aug 04, 2008 5:29 pm UTC
by quintopia
Here's another one:

Prove that for all natural z, there exist x in {1...9} and y such that x + y = z and x = y (mod 9). Does it work for bases other than 9?

Re: Book on proofs?

Posted: Tue Aug 05, 2008 3:51 am UTC
by romulox
heres a simple one.

note: assume all sets non-empty.

def 1a: Suppose S is a set. S is bounded above if there exists an M such that for every x in S, x <= M.
def 1b: S is bounded below if there exists an L such that for every x in S, x >= L.
def 1c: S is bounded if S is bounded above and bounded below.

def 2: Suppose S is a set. The statement that W is a least upper bound of the set S means that: a) W is an upper bound of the set S, and b) if T is an upper bound of S, then T is less than or equal to W (T <= W).

theorem 1: Suppose S is a set with least upper bound q. If p is a least upper bound of S then p=q.

theorem 2: Suppose S is a set with least upper bound q, and U is the set such that p is in U if and only if p is an upper bound of S, then q is the greatest lower bound of U.

theorem 3: Suppose S is a set with least upper bound M. If p is a number such that p < M, then there exists an x in S such that p < x <= M.


these theorems are fairly basic first semester analysis, and each come from careful application of the definitions. You may assume ZFC or some other basic notion of sets. I can post the answers if there is any trouble.

Also to the op, you will learn how to write good proofs by writing proofs and defending them before professors and students. A book will often be a hinderance and poor substitute for training good proof writing. See the Moore Method of teaching on Wikipedia for proofs and for more general problem analysis and solution approach see Polya's Principles. Also Calculus III at the university I attended was vector and multivariable calculus, which required no proofs whatsoever.

-romulox

Re: Book on proofs?

Posted: Tue Aug 05, 2008 4:27 am UTC
by ConMan
quintopia wrote:Here's another one:

Prove that for all natural z, there exist x in {1...9} and y such that x + y = z and x = y (mod 9). Does it work for bases other than 9?


I'm pretty sure the answer is only odd ones. I can explain the why and then the how if necessary.

Re: Book on proofs?

Posted: Wed Aug 06, 2008 4:30 am UTC
by xixheartxyoux
At my school, we teach proof writing as its own class, which is different than most other universities. One of our professors wrote a book specifically for the course and it was the best money I've ever spent in my life. It goes through basic logic, direct proofs, proofs by contradiction, proofs by induction, and even a bit of set theory. Its called Mathematical Reasonsing by Ted Sundstrom. Its a little pricey, but I think it is definately worth looking into.