Book on proofs?

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

TheWaterBear
Posts: 118
Joined: Tue Jun 24, 2008 2:57 am UTC
Location: Atlanta, GA
Contact:

Book on proofs?

Postby TheWaterBear » Sat Aug 02, 2008 4:13 am UTC

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?

User avatar
Qoppa
Posts: 694
Joined: Sat Nov 24, 2007 9:32 pm UTC
Location: Yes.

Re: Book on proofs?

Postby Qoppa » Sat Aug 02, 2008 4:24 am UTC

I've heard good things about How to Prove It.

Code: Select all

_=0,w=-1,(*t)(int,int);a()??<char*p="[gd\
~/d~/\\b\x7F\177l*~/~djal{x}h!\005h";(++w
<033)?(putchar((*t)(w??(p:>,w?_:0XD)),a()
):0;%>O(x,l)??<_='['/7;{return!(x%(_-11))
?x??'l:x^(1+ ++l);}??>main(){t=&O;w=a();}

User avatar
Yakk
Poster with most posts but no title.
Posts: 11129
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: Book on proofs?

Postby Yakk » Sat Aug 02, 2008 3:20 pm UTC

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? :-)
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

User avatar
Harg
Posts: 130
Joined: Thu Jul 10, 2008 8:24 pm UTC

Re: Book on proofs?

Postby Harg » Sat Aug 02, 2008 6:38 pm UTC

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.

Lycur
Posts: 470
Joined: Thu Jan 03, 2008 11:06 pm UTC
Location: Nutopia

Re: Book on proofs?

Postby Lycur » Sun Aug 03, 2008 3:36 am UTC

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.

User avatar
quintopia
Posts: 2906
Joined: Fri Nov 17, 2006 2:53 am UTC
Location: atlanta, ga

Re: Book on proofs?

Postby quintopia » Sun Aug 03, 2008 9:41 am UTC

Harg: is it
Spoiler:
all x where f=g?

User avatar
Harg
Posts: 130
Joined: Thu Jul 10, 2008 8:24 pm UTC

Re: Book on proofs?

Postby Harg » Sun Aug 03, 2008 11:29 am UTC

Exactly

User avatar
z4lis
Posts: 767
Joined: Mon Mar 03, 2008 10:59 pm UTC

Re: Book on proofs?

Postby z4lis » Sun Aug 03, 2008 3:54 pm UTC

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.
What they (mathematicians) define as interesting depends on their particular field of study; mathematical anaylsts find pain and extreme confusion interesting, whereas geometers are interested in beauty.

User avatar
Harg
Posts: 130
Joined: Thu Jul 10, 2008 8:24 pm UTC

Re: Book on proofs?

Postby Harg » Sun Aug 03, 2008 5:29 pm UTC

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.

User avatar
quintopia
Posts: 2906
Joined: Fri Nov 17, 2006 2:53 am UTC
Location: atlanta, ga

Re: Book on proofs?

Postby quintopia » Mon Aug 04, 2008 5:29 pm UTC

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?

romulox
Posts: 30
Joined: Tue Jun 19, 2007 8:04 pm UTC

Re: Book on proofs?

Postby romulox » Tue Aug 05, 2008 3:51 am UTC

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
n/a

User avatar
ConMan
Shepherd's Pie?
Posts: 1691
Joined: Tue Jan 01, 2008 11:56 am UTC
Location: Beacon Alpha

Re: Book on proofs?

Postby ConMan » Tue Aug 05, 2008 4:27 am UTC

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.
pollywog wrote:
Wikihow wrote:* Smile a lot! Give a gay girl a knowing "Hey, I'm a lesbian too!" smile.
I want to learn this smile, perfect it, and then go around smiling at lesbians and freaking them out.

User avatar
xixheartxyoux
Posts: 31
Joined: Wed Jul 30, 2008 4:58 pm UTC
Location: Michigan
Contact:

Re: Book on proofs?

Postby xixheartxyoux » Wed Aug 06, 2008 4:30 am UTC

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.
Image

“The highest form of pure thought is in mathematics”--Plato


Return to “Mathematics”

Who is online

Users browsing this forum: No registered users and 5 guests